GNU Radio Manual and C++ API Reference  3.7.9.2
The Free & Open Software Radio Ecosystem
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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_DIGITAL_LFSR_H
24 #define INCLUDED_DIGITAL_LFSR_H
25 
26 #include <gnuradio/digital/api.h>
27 #include <stdexcept>
28 #include <stdint.h>
29 
30 namespace gr {
31  namespace digital {
32 
33  /*!
34  * \brief Fibonacci Linear Feedback Shift Register using specified
35  * polynomial mask
36  * \ingroup misc
37  *
38  * \details
39  * Generates a maximal length pseudo-random sequence of length
40  * 2^degree-1
41  *
42  * Constructor: digital::lfsr(int mask, int seed, int reg_len);
43  *
44  * \param mask - polynomial coefficients representing the
45  * locations of feedback taps from a shift register
46  * which are xor'ed together to form the new high
47  * order bit.
48  *
49  * Some common masks might be:
50  * x^4 + x^3 + x^0 = 0x19
51  * x^5 + x^3 + x^0 = 0x29
52  * x^6 + x^5 + x^0 = 0x61
53  *
54  * \param seed - the initialization vector placed into the
55  * register durring initialization. Low order bit
56  * corresponds to x^0 coefficient -- the first to be
57  * shifted as output.
58  *
59  * \param reg_len - specifies the length of the feedback shift
60  * register to be used. Durring each iteration, the
61  * register is rightshifted one and the new bit is
62  * placed in bit reg_len. reg_len should generally be
63  * at least order(mask) + 1
64  *
65  *
66  * see http://en.wikipedia.org/wiki/Linear_feedback_shift_register
67  * for more explanation.
68  *
69  * next_bit() - Standard LFSR operation
70  *
71  * Perform one cycle of the LFSR. The output bit is taken from
72  * the shift register LSB. The shift register MSB is assigned from
73  * the modulo 2 sum of the masked shift register.
74  *
75  * next_bit_scramble(unsigned char input) - Scramble an input stream
76  *
77  * Perform one cycle of the LFSR. The output bit is taken from
78  * the shift register LSB. The shift register MSB is assigned from
79  * the modulo 2 sum of the masked shift register and the input LSB.
80  *
81  * next_bit_descramble(unsigned char input) - Descramble an input stream
82  *
83  * Perform one cycle of the LFSR. The output bit is taken from
84  * the modulo 2 sum of the masked shift register and the input LSB.
85  * The shift register MSB is assigned from the LSB of the input.
86  *
87  * See http://en.wikipedia.org/wiki/Scrambler for operation of these
88  * last two functions (see multiplicative scrambler.)
89  */
90  class lfsr
91  {
92  private:
93  uint32_t d_shift_register;
94  uint32_t d_mask;
95  uint32_t d_seed;
96  uint32_t d_shift_register_length; // less than 32
97 
98  static uint32_t
99  popCount(uint32_t x)
100  {
101  uint32_t r = x - ((x >> 1) & 033333333333)
102  - ((x >> 2) & 011111111111);
103  return ((r + (r >> 3)) & 030707070707) % 63;
104  }
105 
106  public:
107  lfsr(uint32_t mask, uint32_t seed, uint32_t reg_len)
108  : d_shift_register(seed),
109  d_mask(mask),
110  d_seed(seed),
111  d_shift_register_length(reg_len)
112  {
113  if(reg_len > 31)
114  throw std::invalid_argument("reg_len must be <= 31");
115  }
116 
117  unsigned char next_bit()
118  {
119  unsigned char output = d_shift_register & 1;
120  unsigned char newbit = popCount( d_shift_register & d_mask )%2;
121  d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
122  return output;
123  }
124 
125  unsigned char next_bit_scramble(unsigned char input)
126  {
127  unsigned char output = d_shift_register & 1;
128  unsigned char newbit = (popCount( d_shift_register & d_mask )%2)^(input & 1);
129  d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
130  return output;
131  }
132 
133  unsigned char next_bit_descramble(unsigned char input)
134  {
135  unsigned char output = (popCount( d_shift_register & d_mask )%2)^(input & 1);
136  unsigned char newbit = input & 1;
137  d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
138  return output;
139  }
140 
141  /*!
142  * Reset shift register to initial seed value
143  */
144  void reset() { d_shift_register = d_seed; }
145 
146  /*!
147  * Rotate the register through x number of bits
148  * where we are just throwing away the results to get queued up correctly
149  */
150  void pre_shift(int num)
151  {
152  for(int i=0; i<num; i++) {
153  next_bit();
154  }
155  }
156 
157  int mask() const { return d_mask; }
158  };
159 
160  } /* namespace digital */
161 } /* namespace gr */
162 
163 #endif /* INCLUDED_DIGITAL_LFSR_H */
unsigned char next_bit_descramble(unsigned char input)
Definition: lfsr.h:133
unsigned char next_bit_scramble(unsigned char input)
Definition: lfsr.h:125
unsigned char next_bit()
Definition: lfsr.h:117
Include this header to use the message passing features.
Definition: logger.h:131
void pre_shift(int num)
Definition: lfsr.h:150
lfsr(uint32_t mask, uint32_t seed, uint32_t reg_len)
Definition: lfsr.h:107
void reset()
Definition: lfsr.h:144
Fibonacci Linear Feedback Shift Register using specified polynomial mask.
Definition: lfsr.h:90
int mask() const
Definition: lfsr.h:157