umontreal.iro.lecuyer.hups
Class CycleBasedLFSR
java.lang.Object
umontreal.iro.lecuyer.hups.PointSet
umontreal.iro.lecuyer.hups.CycleBasedPointSet
umontreal.iro.lecuyer.hups.CycleBasedPointSetBase2
umontreal.iro.lecuyer.hups.CycleBasedLFSR
public class CycleBasedLFSR
- extends CycleBasedPointSetBase2
LFSR generators produce numbers by generating
a sequence of bits from a linear recurrence modulo 2,
and forming fractional numbers by taking blocks of successive bits.
More precisely, let
F2 denote
the finite field with two elements
(say, 0 and 1). Let
P(z) = zk - a1zk-1 - ... - ak
be a polynomial with coefficients in
F2, and consider the recurrence
xn =
a1xn-1 +
... +
akxn-k,
whose characteristic polynomial is P(z).
It should be understood that in
all computations are performed in
F2
(this can be identified with working in integer arithmetic modulo 2).
Suppose that
s0 = (x0,..., xk-1)∈{0, 1}k is fixed and define
where s and L are positive integers.
If P is primitive,
s0
0, and
ρ = 2k - 1 is coprime to s,
then the sequences and are both
purely periodic with period ρ.
Computing un from un-1 involves performing s steps
of the recurrence.
Suppose now that we have J LFSR recurrences,
the j-th one having a primitive
characteristic polynomial Pj(z) of degree kj,
and step size sj.
Let
{xj, n, n >= 0} be the j-th LFSR sequence, and define
xn = (x1, n + ... + xJ, n)mod 2 and un as in.
Equivalently, if
{uj, n, n >= 0} is the output sequence
from the j-th LFSR, then
un = u1, n⊕ ... ⊕uJ, n
where ⊕ denotes the bitwise exclusive-or in the binary expansion.
The sequence {xn} is called the combined LFSR sequence
and a generator that produces this {un} is called a
combined LFSR generator.
Constructor Summary |
CycleBasedLFSR(int step1,
int nbcoeff1,
int[] nocoeff1)
Constructs a point set based on a polynomial in base 2 with 2k1 points. |
CycleBasedLFSR(int step1,
int step2,
int nbcoeff1,
int nbcoeff2,
int[] nocoeff1,
int[] nocoeff2)
Constructs a point set based on a combination of two polynomials in
base 2 with
2k1+k2 points. |
CycleBasedLFSR(String filename,
int no)
Constructs a point set after reading its parameters from
file filename; the parameters associated with number no
of filename corresponds to the no-th polynomial. |
Method Summary |
String |
toString()
Formats a string that contains information about the point set. |
Methods inherited from class umontreal.iro.lecuyer.hups.PointSet |
addRandomShift, addRandomShift, addRandomShift, formatPoints, formatPoints, formatPoints, formatPointsBase, formatPointsBase, formatPointsBase, formatPointsBase, formatPointsNumbered, formatPointsNumbered, getNumPoints, getStream, randomize, randomize, randomize, randomize, randomize, setStream, unrandomize |
CycleBasedLFSR
public CycleBasedLFSR(int step1,
int nbcoeff1,
int[] nocoeff1)
- Constructs a point set based on a polynomial in base 2 with 2k1 points.
step1 is the number of times the recursion is executed in order to
generate the next state.
nbcoeff1 is the number of non-zero coefficients of the polynomial, while
nocoeff1 is the list of the degree of the non-zero coefficients.
Example:
P(z) = z9 - z4 - 1, k1 = 9,
nbcoeff1 = 3, nocoeff1 = {9, 4, 0}.
CycleBasedLFSR
public CycleBasedLFSR(int step1,
int step2,
int nbcoeff1,
int nbcoeff2,
int[] nocoeff1,
int[] nocoeff2)
- Constructs a point set based on a combination of two polynomials in
base 2 with
2k1+k2 points. The meaning of the parameters is the
same as in the case of one polynomial.
CycleBasedLFSR
public CycleBasedLFSR(String filename,
int no)
- Constructs a point set after reading its parameters from
file filename; the parameters associated with number no
of filename corresponds to the no-th polynomial.
The existing files and the number of polynomials they contain are
in the table below. The name of the files describe the number of polynomials J in the
combined LFSR and the number of points 2k generated. For example,
the parameters in file j1_k11.dat are based on J = 1 polynomial
and generates
2k = 211 points, while
those in file j2_k17.dat are based on a combination
of J = 2 polynomials and generates
2k = 217 points.
Thus to use the
3-th combined LFSR of file j2_k17.dat, one must use
CycleBasedLFSR("j2_k17", 3).
Filename |
Num. of polynomials |
j1_k11.dat |
1 |
j2_k17.dat |
6 |
j2_k19.dat |
4 |
toString
public String toString()
- Description copied from class:
PointSet
- Formats a string that contains information about the point set.
- Overrides:
toString
in class CycleBasedPointSet
- Returns:
- string representation of the point set information
To submit a bug or ask questions, send an e-mail to
Pierre L'Ecuyer.