git.gag.com Git - debian/gnuradio/blob - gnuradio-core/src/lib/general/gri_lfsr.h

   1 /* -*- c++ -*- */
   2 /*
   3  * Copyright 2007 Free Software Foundation, Inc.
   4  *
   5  * This file is part of GNU Radio
   6  *
   7  * GNU Radio is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 3, or (at your option)
  10  * any later version.
  11  *
  12  * GNU Radio is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with GNU Radio; see the file COPYING.  If not, write to
  19  * the Free Software Foundation, Inc., 51 Franklin Street,
  20  * Boston, MA 02110-1301, USA.
  21  */
  22
  23 #ifndef INCLUDED_GRI_LFSR_H
  24 #define INCLUDED_GRI_LFSR_H
  25
  26 #include <stdexcept>
  27 #include <stdint.h>
  28
  29 /*!
  30  * \brief Fibonacci Linear Feedback Shift Register using specified polynomial mask
  31  * \ingroup math
  32  *
  33  * Generates a maximal length pseudo-random sequence of length 2^degree-1
  34  *
  35  * Constructor: gri_lfsr(int mask, int seed, int reg_len);
  36  *
  37  *      mask - polynomial coefficients representing the locations
  38  *             of feedback taps from a shift register which are xor'ed
  39  *             together to form the new high order bit.
  40  *
  41  *             Some common masks might be:
  42  *              x^4 + x^3 + x^0 = 0x19
  43  *              x^5 + x^3 + x^0 = 0x29
  44  *              x^6 + x^5 + x^0 = 0x61
  45  *
  46  *      seed - the initialization vector placed into the register
  47  *             durring initialization.   Low order bit corresponds
  48  *             to x^0 coefficient -- the first to be shifted as output.
  49  *
  50  *   reg_len - specifies the length of the feedback shift register
  51  *             to be used.   Durring each iteration, the register
  52  *             is rightshifted one and the new bit is placed in bit reg_len.
  53  *             reg_len should generally be at least order(mask) + 1
  54  *
  55  *
  56  * see http://en.wikipedia.org/wiki/Linear_feedback_shift_register
  57  * for more explanation.
  58  *
  59  *
  60  *
  61  *  next_bit() - performs once cycle of the lfsr,
  62  *               generating the new high order bit from the mask
  63  *               and returning the low order bit which has been
  64  *               shifted out of the register.
  65  *
  66  *
  67  */
  68
  69
  70 class gri_lfsr
  71 {
  72  private:
  73   uint32_t d_shift_register;
  74   uint32_t d_mask;
  75   uint32_t d_shift_register_length;     // less than 32
  76
  77   static uint32_t
  78   popCount(uint32_t x)
  79   {
  80     uint32_t r = x - ((x >> 1) & 033333333333)
  81                    - ((x >> 2) & 011111111111);
  82     return ((r + (r >> 3)) & 030707070707) % 63;
  83   }
  84
  85  public:
  86
  87   gri_lfsr(uint32_t mask, uint32_t seed, uint32_t reg_len)
  88     : d_shift_register(seed), d_mask(mask), d_shift_register_length(reg_len)
  89   {
  90     if (reg_len > 31)
  91       throw std::invalid_argument("reg_len must be <= 31");
  92   }
  93
  94   unsigned char next_bit() {
  95     unsigned char bit = d_shift_register & 1;
  96     unsigned char newbit = popCount( d_shift_register & d_mask )%2;
  97     d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
  98     return bit;
  99   }
 100
 101   int mask() const { return d_mask; }
 102 };
 103
 104 #endif /* INCLUDED_GRI_LFSR_H */