GNU Radio 3.6.3 C++ API
lfsr.h
Go to the documentation of this file.
1 /* -*- c++ -*- */
2 /*
3  * Copyright 2008,2010,2012 Free Software Foundation, Inc.
4  *
5  * This file is part of GNU Radio
6  *
7  * GNU Radio is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 3, or (at your option)
10  * any later version.
11  *
12  * GNU Radio is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with GNU Radio; see the file COPYING. If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street,
20  * Boston, MA 02110-1301, USA.
21  */
22 
23 #ifndef INCLUDED_ANALOG_LFSR_H
24 #define INCLUDED_ANALOG_LFSR_H
25 
26 #include <analog/api.h>
27 #include <stdexcept>
28 #include <stdint.h>
29 
30 namespace gr {
31  namespace analog {
32 
33  /*!
34  * \brief Fibonacci Linear Feedback Shift Register using specified
35  * polynomial mask
36  * \ingroup misc
37  *
38  * Generates a maximal length pseudo-random sequence of length
39  * 2^degree-1
40  *
41  * Constructor: analog::lfsr(int mask, int seed, int reg_len);
42  *
43  * \param mask - polynomial coefficients representing the
44  * locations of feedback taps from a shift register
45  * which are xor'ed together to form the new high
46  * order bit.
47  *
48  * Some common masks might be:
49  * x^4 + x^3 + x^0 = 0x19
50  * x^5 + x^3 + x^0 = 0x29
51  * x^6 + x^5 + x^0 = 0x61
52  *
53  * \param seed - the initialization vector placed into the
54  * register durring initialization. Low order bit
55  * corresponds to x^0 coefficient -- the first to be
56  * shifted as output.
57  *
58  * \param reg_len - specifies the length of the feedback shift
59  * register to be used. Durring each iteration, the
60  * register is rightshifted one and the new bit is
61  * placed in bit reg_len. reg_len should generally be
62  * at least order(mask) + 1
63  *
64  *
65  * see http://en.wikipedia.org/wiki/Linear_feedback_shift_register
66  * for more explanation.
67  *
68  * next_bit() - Standard LFSR operation
69  *
70  * Perform one cycle of the LFSR. The output bit is taken from
71  * the shift register LSB. The shift register MSB is assigned from
72  * the modulo 2 sum of the masked shift register.
73  *
74  * next_bit_scramble(unsigned char input) - Scramble an input stream
75  *
76  * Perform one cycle of the LFSR. The output bit is taken from
77  * the shift register LSB. The shift register MSB is assigned from
78  * the modulo 2 sum of the masked shift register and the input LSB.
79  *
80  * next_bit_descramble(unsigned char input) - Descramble an input stream
81  *
82  * Perform one cycle of the LFSR. The output bit is taken from
83  * the modulo 2 sum of the masked shift register and the input LSB.
84  * The shift register MSB is assigned from the LSB of the input.
85  *
86  * See http://en.wikipedia.org/wiki/Scrambler for operation of these
87  * last two functions (see multiplicative scrambler.)
88  */
89  class lfsr
90  {
91  private:
92  uint32_t d_shift_register;
93  uint32_t d_mask;
94  uint32_t d_seed;
95  uint32_t d_shift_register_length; // less than 32
96 
97  static uint32_t
98  popCount(uint32_t x)
99  {
100  uint32_t r = x - ((x >> 1) & 033333333333)
101  - ((x >> 2) & 011111111111);
102  return ((r + (r >> 3)) & 030707070707) % 63;
103  }
104 
105  public:
107  : d_shift_register(seed),
108  d_mask(mask),
109  d_seed(seed),
110  d_shift_register_length(reg_len)
111  {
112  if(reg_len > 31)
113  throw std::invalid_argument("reg_len must be <= 31");
114  }
115 
116  unsigned char next_bit()
117  {
118  unsigned char output = d_shift_register & 1;
119  unsigned char newbit = popCount( d_shift_register & d_mask )%2;
120  d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
121  return output;
122  }
123 
124  unsigned char next_bit_scramble(unsigned char input)
125  {
126  unsigned char output = d_shift_register & 1;
127  unsigned char newbit = (popCount( d_shift_register & d_mask )%2)^(input & 1);
128  d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
129  return output;
130  }
131 
132  unsigned char next_bit_descramble(unsigned char input)
133  {
134  unsigned char output = (popCount( d_shift_register & d_mask )%2)^(input & 1);
135  unsigned char newbit = input & 1;
136  d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
137  return output;
138  }
139 
140  /*!
141  * Reset shift register to initial seed value
142  */
143  void reset() { d_shift_register = d_seed; }
144 
145  /*!
146  * Rotate the register through x number of bits
147  * where we are just throwing away the results to get queued up correctly
148  */
149  void pre_shift(int num)
150  {
151  for(int i=0; i<num; i++) {
152  next_bit();
153  }
154  }
155 
156  int mask() const { return d_mask; }
157  };
158 
159  } /* namespace analog */
160 } /* namespace gr */
161 
162 #endif /* INCLUDED_ANALOG_LFSR_H */