gri_lfsr.h

Go to the documentation of this file.

/* -*- c++ -*- */
/*
 * Copyright 2008,2010 Free Software Foundation, Inc.
 *
 * This file is part of GNU Radio
 *
 * GNU Radio is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3, or (at your option)
 * any later version.
 *
 * GNU Radio is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with GNU Radio; see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street,
 * Boston, MA 02110-1301, USA.
 */

#ifndef INCLUDED_GRI_LFSR_H
#define INCLUDED_GRI_LFSR_H

#include <gr_core_api.h>
#include <stdexcept>
#include <stdint.h>

/*!
 * \brief Fibonacci Linear Feedback Shift Register using specified polynomial mask
 * \ingroup misc
 *
 * Generates a maximal length pseudo-random sequence of length 2^degree-1
 *
 * Constructor: gri_lfsr(int mask, int seed, int reg_len);
 *
 *      mask - polynomial coefficients representing the locations
 *             of feedback taps from a shift register which are xor'ed
 *             together to form the new high order bit.
 *
 *             Some common masks might be:
 *              x^4 + x^3 + x^0 = 0x19
 *              x^5 + x^3 + x^0 = 0x29
 *              x^6 + x^5 + x^0 = 0x61
 *
 *      seed - the initialization vector placed into the register
 *             durring initialization.   Low order bit corresponds
 *             to x^0 coefficient -- the first to be shifted as output.
 *
 *   reg_len - specifies the length of the feedback shift register
 *             to be used.   Durring each iteration, the register
 *             is rightshifted one and the new bit is placed in bit reg_len.
 *             reg_len should generally be at least order(mask) + 1
 *
 *
 * see http://en.wikipedia.org/wiki/Linear_feedback_shift_register
 * for more explanation.
 *
 *
 *
 *  next_bit() - Standard LFSR operation
 *
 *      Perform one cycle of the LFSR.  The output bit is taken from
 *      the shift register LSB.  The shift register MSB is assigned from
 *      the modulo 2 sum of the masked shift register.
 *
 *  next_bit_scramble(unsigned char input) - Scramble an input stream
 *
 *      Perform one cycle of the LFSR.  The output bit is taken from
 *      the shift register LSB.  The shift register MSB is assigned from
 *      the modulo 2 sum of the masked shift register and the input LSB.
 *
 *  next_bit_descramble(unsigned char input) - Descramble an input stream
 *
 *      Perform one cycle of the LFSR.  The output bit is taken from
 *      the modulo 2 sum of the masked shift register and the input LSB.
 *      The shift register MSB is assigned from the LSB of the input.
 *
 * See http://en.wikipedia.org/wiki/Scrambler for operation of these
 * last two functions (see multiplicative scrambler.)
 *
 */

class GR_CORE_API gri_lfsr
{
 private:
  uint32_t d_shift_register;
  uint32_t d_mask;
  uint32_t d_seed;
  uint32_t d_shift_register_length;     // less than 32

  static uint32_t
  popCount(uint32_t x)
  {
    uint32_t r = x - ((x >> 1) & 033333333333)
                   - ((x >> 2) & 011111111111);
    return ((r + (r >> 3)) & 030707070707) % 63;
  }

 public:

  gri_lfsr(uint32_t mask, uint32_t seed, uint32_t reg_len)
    : d_shift_register(seed),
      d_mask(mask),
      d_seed(seed),
      d_shift_register_length(reg_len)
  {
    if (reg_len > 31)
      throw std::invalid_argument("reg_len must be <= 31");
  }

  unsigned char next_bit() {
    unsigned char output = d_shift_register & 1;
    unsigned char newbit = popCount( d_shift_register & d_mask )%2;
    d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
    return output;
  }

  unsigned char next_bit_scramble(unsigned char input) {
    unsigned char output = d_shift_register & 1;
    unsigned char newbit = (popCount( d_shift_register & d_mask )%2)^(input & 1);
    d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
    return output;
  }

  unsigned char next_bit_descramble(unsigned char input) {
    unsigned char output = (popCount( d_shift_register & d_mask )%2)^(input & 1);
    unsigned char newbit = input & 1;
    d_shift_register = ((d_shift_register>>1) | (newbit<<d_shift_register_length));
    return output;
  }

  /*!
   * Reset shift register to initial seed value
   */
  void reset() { d_shift_register = d_seed; }

  /*!
   * Rotate the register through x number of bits
   * where we are just throwing away the results to get queued up correctly
   */
  void pre_shift(int num){
    for(int i=0; i<num; i++){
      next_bit();
    }
  }

  int mask() const { return d_mask; }
};

#endif /* INCLUDED_GRI_LFSR_H */