bb.science
Class Lfsr

java.lang.Object
  extended by bb.science.Lfsr

public class Lfsr
extends Object

Implements a linear feedback shift register (LFSR). The register's size (an int named n) may be any value from 2 thru 32. Any starting state of the register (called the seed) may also be specifed.

This class is not multithread safe.

Author:
Brent Boyer
See Also:
this forum posting

Nested Class Summary
static class Lfsr.UnitTest
          See the Overview page of the project's javadocs for a general description of this unit test class.
 
Field Summary
private static int count
           
private  int mask
           
private  int n
           
private static Random random
           
private  int register
           
private  int taps
           
 
Constructor Summary
Lfsr(int n)
          Convenience constructor that simply calls Lfsr(n, 1).
Lfsr(int n, int seed)
          Fundamental constructor.
 
Method Summary
 int advance()
          Convenience method that simply returns advance(1).
 int advance(long numberTransitions)
          Advances the internal state of this instance by numberTransitions.
 int getMask()
          Accessor for mask.
 int getRegister()
          Accessor for register.
 int getTaps()
          Accessor for taps.
private static int makeMask(int n)
          Returns an int with all the n low order bits set to 1 and all the high order bits set to 0.
static int makeSeedNext(int n)
          Returns the next seed suitable for an LFSR of size n.
static int makeSeedRandom(int n)
          Returns a pseudo-random seed suitable for an LFSR of size n.
private static int makeTaps(int n)
          Returns an int which can function as the taps of n order maximal LFSR.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

random

private static final Random random

count

private static int count

n

private final int n

mask

private final int mask

taps

private final int taps

register

private int register
Constructor Detail

Lfsr

public Lfsr(int n)
     throws IllegalArgumentException
Convenience constructor that simply calls Lfsr(n, 1).

Throws:
IllegalArgumentException - if n < 2 or n > 32

Lfsr

public Lfsr(int n,
            int seed)
     throws IllegalArgumentException
Fundamental constructor.

Throws:
IllegalArgumentException - if n < 2 or n > 32; if seed == 0 or has high bits (i.e. beyond the nth bit) set
Method Detail

makeSeedNext

public static int makeSeedNext(int n)
                        throws IllegalArgumentException
Returns the next seed suitable for an LFSR of size n. The result (before masking) comes from an internal sequence which starts at 1 and is incremented at least once each time this method is called. This method is normally used when calling the seed specifying constructor.

Throws:
IllegalArgumentException - if n < 0 or n > 32

makeSeedRandom

public static int makeSeedRandom(int n)
                          throws IllegalArgumentException
Returns a pseudo-random seed suitable for an LFSR of size n. This method is normally used when calling the seed specifying constructor.

This method is an

Throws:
IllegalArgumentException - if n < 0 or n > 32

makeMask

private static int makeMask(int n)
                     throws IllegalArgumentException
Returns an int with all the n low order bits set to 1 and all the high order bits set to 0. When used as a bitwise AND mask, this will preserve the n low order bits and drop the high order bits.

Throws:
IllegalArgumentException - if n < 0 or n > 32

makeTaps

private static int makeTaps(int n)
                     throws IllegalArgumentException
Returns an int which can function as the taps of n order maximal LFSR.

Throws:
IllegalArgumentException - if n < 2 or n > 32

getMask

public int getMask()
Accessor for mask.


getTaps

public int getTaps()
Accessor for taps.


getRegister

public int getRegister()
Accessor for register.


advance

public int advance()
Convenience method that simply returns advance(1).


advance

public int advance(long numberTransitions)
            throws IllegalArgumentException
Advances the internal state of this instance by numberTransitions.

Ignoring an initial argument check and a final return statement, this method is essentially 2 lines of code: a loop head and its body. The loop body involves 6 bitwise and/or unary int operators, so it is very simple and fast. In spite of the simplicity of the computation, the LFSR internal state (stored in the register field) is pseudo-random. It should be impossible for a smart compiler to cut many corners and avoid doing the computations.

Returns:
the final value of the internal state after all the transitions have been carried out
Throws:
IllegalArgumentException - if numberTransitions < 0