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