gri_lfsr.h

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

Generated on Wed Jul 29 06:23:29 2009 for GNU Radio 3.2.2 C++ API by  doxygen 1.5.9