GNU Radio 3.7.1 C++ API
lfsr.h
Go to the documentation of this file.
00001 /* -*- c++ -*- */
00002 /*
00003  * Copyright 2008,2010,2012 Free Software Foundation, Inc.
00004  *
00005  * This file is part of GNU Radio
00006  *
00007  * GNU Radio is free software; you can redistribute it and/or modify
00008  * it under the terms of the GNU General Public License as published by
00009  * the Free Software Foundation; either version 3, or (at your option)
00010  * any later version.
00011  *
00012  * GNU Radio is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with GNU Radio; see the file COPYING.  If not, write to
00019  * the Free Software Foundation, Inc., 51 Franklin Street,
00020  * Boston, MA 02110-1301, USA.
00021  */
00022 
00023 #ifndef INCLUDED_DIGITAL_LFSR_H
00024 #define INCLUDED_DIGITAL_LFSR_H
00025 
00026 #include <gnuradio/digital/api.h>
00027 #include <stdexcept>
00028 #include <stdint.h>
00029 
00030 namespace gr {
00031   namespace digital {
00032 
00033     /*!
00034      * \brief Fibonacci Linear Feedback Shift Register using specified
00035      * polynomial mask
00036      * \ingroup misc
00037      *
00038      * \details
00039      * Generates a maximal length pseudo-random sequence of length
00040      * 2^degree-1
00041      *
00042      * Constructor: digital::lfsr(int mask, int seed, int reg_len);
00043      *
00044      * \param mask - polynomial coefficients representing the
00045      *             locations of feedback taps from a shift register
00046      *             which are xor'ed together to form the new high
00047      *             order bit.
00048      *
00049      *             Some common masks might be:
00050      *              x^4 + x^3 + x^0 = 0x19
00051      *              x^5 + x^3 + x^0 = 0x29
00052      *              x^6 + x^5 + x^0 = 0x61
00053      *
00054      * \param seed - the initialization vector placed into the
00055      *             register durring initialization. Low order bit
00056      *             corresponds to x^0 coefficient -- the first to be
00057      *             shifted as output.
00058      *
00059      * \param reg_len - specifies the length of the feedback shift
00060      *             register to be used. Durring each iteration, the
00061      *             register is rightshifted one and the new bit is
00062      *             placed in bit reg_len. reg_len should generally be
00063      *             at least order(mask) + 1
00064      *
00065      *
00066      * see http://en.wikipedia.org/wiki/Linear_feedback_shift_register
00067      * for more explanation.
00068      *
00069      *  next_bit() - Standard LFSR operation
00070      *
00071      *      Perform one cycle of the LFSR.  The output bit is taken from
00072      *      the shift register LSB.  The shift register MSB is assigned from
00073      *      the modulo 2 sum of the masked shift register.
00074      *
00075      *  next_bit_scramble(unsigned char input) - Scramble an input stream
00076      *
00077      *      Perform one cycle of the LFSR.  The output bit is taken from
00078      *      the shift register LSB.  The shift register MSB is assigned from
00079      *      the modulo 2 sum of the masked shift register and the input LSB.
00080      *
00081      *  next_bit_descramble(unsigned char input) - Descramble an input stream
00082      *
00083      *      Perform one cycle of the LFSR.  The output bit is taken from
00084      *      the modulo 2 sum of the masked shift register and the input LSB.
00085      *      The shift register MSB is assigned from the LSB of the input.
00086      *
00087      * See http://en.wikipedia.org/wiki/Scrambler for operation of these
00088      * last two functions (see multiplicative scrambler.)
00089      */
00090     class lfsr
00091     {
00092     private:
00093       uint32_t d_shift_register;
00094       uint32_t d_mask;
00095       uint32_t d_seed;
00096       uint32_t d_shift_register_length; // less than 32
00097 
00098       static uint32_t
00099         popCount(uint32_t x)
00100       {
00101         uint32_t r = x - ((x >> 1) & 033333333333)
00102           - ((x >> 2) & 011111111111);
00103         return ((r + (r >> 3)) & 030707070707) % 63;
00104       }
00105 
00106     public:
00107       lfsr(uint32_t mask, uint32_t seed, uint32_t reg_len)
00108         : d_shift_register(seed),
00109         d_mask(mask),
00110         d_seed(seed),
00111         d_shift_register_length(reg_len)
00112         {
00113           if(reg_len > 31)
00114             throw std::invalid_argument("reg_len must be <= 31");
00115         }
00116 
00117       unsigned char next_bit()
00118       {
00119         unsigned char output = d_shift_register & 1;
00120         unsigned char newbit = popCount( d_shift_register & d_mask )%2;
00121         d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
00122         return output;
00123       }
00124 
00125       unsigned char next_bit_scramble(unsigned char input)
00126       {
00127         unsigned char output = d_shift_register & 1;
00128         unsigned char newbit = (popCount( d_shift_register & d_mask )%2)^(input & 1);
00129         d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
00130         return output;
00131       }
00132 
00133       unsigned char next_bit_descramble(unsigned char input)
00134       {
00135         unsigned char output = (popCount( d_shift_register & d_mask )%2)^(input & 1);
00136         unsigned char newbit = input & 1;
00137         d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
00138         return output;
00139       }
00140 
00141       /*!
00142        * Reset shift register to initial seed value
00143        */
00144       void reset() { d_shift_register = d_seed; }
00145 
00146       /*!
00147        * Rotate the register through x number of bits
00148        * where we are just throwing away the results to get queued up correctly
00149        */
00150       void pre_shift(int num)
00151       {
00152         for(int i=0; i<num; i++) {
00153           next_bit();
00154         }
00155       }
00156 
00157       int mask() const { return d_mask; }
00158     };
00159 
00160   } /* namespace digital */
00161 } /* namespace gr */
00162 
00163 #endif /* INCLUDED_DIGITAL_LFSR_H */