GNU Radio v3.6.2-149-ga6d285d9 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_ANALOG_LFSR_H
00024 #define INCLUDED_ANALOG_LFSR_H
00025 
00026 #include <analog/api.h>
00027 #include <stdexcept>
00028 #include <stdint.h>
00029 
00030 namespace gr {
00031   namespace analog {
00032 
00033     /*!
00034      * \brief Fibonacci Linear Feedback Shift Register using specified
00035      * polynomial mask
00036      * \ingroup misc
00037      *
00038      * Generates a maximal length pseudo-random sequence of length
00039      * 2^degree-1
00040      *
00041      * Constructor: analog::lfsr(int mask, int seed, int reg_len);
00042      *
00043      * \param mask - polynomial coefficients representing the
00044      *             locations of feedback taps from a shift register
00045      *             which are xor'ed together to form the new high
00046      *             order bit.
00047      *
00048      *             Some common masks might be:
00049      *              x^4 + x^3 + x^0 = 0x19
00050      *              x^5 + x^3 + x^0 = 0x29
00051      *              x^6 + x^5 + x^0 = 0x61
00052      *
00053      * \param seed - the initialization vector placed into the
00054      *             register durring initialization. Low order bit
00055      *             corresponds to x^0 coefficient -- the first to be
00056      *             shifted as output.
00057      *
00058      * \param reg_len - specifies the length of the feedback shift
00059      *             register to be used. Durring each iteration, the
00060      *             register is rightshifted one and the new bit is
00061      *             placed in bit reg_len. reg_len should generally be
00062      *             at least order(mask) + 1
00063      *
00064      *
00065      * see http://en.wikipedia.org/wiki/Linear_feedback_shift_register
00066      * for more explanation.
00067      *
00068      *  next_bit() - Standard LFSR operation
00069      *
00070      *      Perform one cycle of the LFSR.  The output bit is taken from
00071      *      the shift register LSB.  The shift register MSB is assigned from
00072      *      the modulo 2 sum of the masked shift register.
00073      *
00074      *  next_bit_scramble(unsigned char input) - Scramble an input stream
00075      *
00076      *      Perform one cycle of the LFSR.  The output bit is taken from
00077      *      the shift register LSB.  The shift register MSB is assigned from
00078      *      the modulo 2 sum of the masked shift register and the input LSB.
00079      *
00080      *  next_bit_descramble(unsigned char input) - Descramble an input stream
00081      *
00082      *      Perform one cycle of the LFSR.  The output bit is taken from
00083      *      the modulo 2 sum of the masked shift register and the input LSB.
00084      *      The shift register MSB is assigned from the LSB of the input.
00085      *
00086      * See http://en.wikipedia.org/wiki/Scrambler for operation of these
00087      * last two functions (see multiplicative scrambler.)
00088      */
00089     class lfsr
00090     {
00091     private:
00092       uint32_t d_shift_register;
00093       uint32_t d_mask;
00094       uint32_t d_seed;
00095       uint32_t d_shift_register_length; // less than 32
00096 
00097       static uint32_t
00098         popCount(uint32_t x)
00099       {
00100         uint32_t r = x - ((x >> 1) & 033333333333)
00101           - ((x >> 2) & 011111111111);
00102         return ((r + (r >> 3)) & 030707070707) % 63;
00103       }
00104 
00105     public:
00106       lfsr(uint32_t mask, uint32_t seed, uint32_t reg_len)
00107         : d_shift_register(seed),
00108         d_mask(mask),
00109         d_seed(seed),
00110         d_shift_register_length(reg_len)
00111         {
00112           if(reg_len > 31)
00113             throw std::invalid_argument("reg_len must be <= 31");
00114         }
00115 
00116       unsigned char next_bit()
00117       {
00118         unsigned char output = d_shift_register & 1;
00119         unsigned char newbit = popCount( d_shift_register & d_mask )%2;
00120         d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
00121         return output;
00122       }
00123 
00124       unsigned char next_bit_scramble(unsigned char input)
00125       {
00126         unsigned char output = d_shift_register & 1;
00127         unsigned char newbit = (popCount( d_shift_register & d_mask )%2)^(input & 1);
00128         d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
00129         return output;
00130       }
00131 
00132       unsigned char next_bit_descramble(unsigned char input)
00133       {
00134         unsigned char output = (popCount( d_shift_register & d_mask )%2)^(input & 1);
00135         unsigned char newbit = input & 1;
00136         d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
00137         return output;
00138       }
00139 
00140       /*!
00141        * Reset shift register to initial seed value
00142        */
00143       void reset() { d_shift_register = d_seed; }
00144 
00145       /*!
00146        * Rotate the register through x number of bits
00147        * where we are just throwing away the results to get queued up correctly
00148        */
00149       void pre_shift(int num)
00150       {
00151         for(int i=0; i<num; i++) {
00152           next_bit();
00153         }
00154       }
00155 
00156       int mask() const { return d_mask; }
00157     };
00158 
00159   } /* namespace analog */
00160 } /* namespace gr */
00161 
00162 #endif /* INCLUDED_ANALOG_LFSR_H */