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