SSJ
3.2.1
Stochastic Simulation in Java
|
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...
Public Member Functions | |
CycleBasedLFSR (int step1, int nbcoeff1, int [] nocoeff1) | |
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 \(2^{k_1 + k_2}\) points. More... | |
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. More... | |
String | toString () |
This method returns a string containing the polynomials and the stepping parameters. | |
![]() | |
double | getCoordinate (int i, int j) |
PointSetIterator | iterator () |
void | addRandomShift (int d1, int d2, RandomStream stream) |
Adds a random digital shift in base 2 to all the points of the point set, using stream stream to generate the random numbers, for coordinates d1 to d2 - 1 . More... | |
void | clearRandomShift () |
Erases the current digital random shift, if any. | |
String | formatPoints () |
![]() | |
double | getCoordinate (int i, int j) |
void | addRandomShift (int d1, int d2, RandomStream stream) |
Adds a random shift to all the points of the point set, using stream stream to generate the random numbers, for coordinates d1 to d2 - 1 . More... | |
void | clearRandomShift () |
Erases the current random shift, if any. | |
int | getDimension () |
PointSetIterator | iterator () |
String | toString () |
String | formatPoints () |
![]() | |
int | getDimension () |
Returns the dimension (number of available coordinates) of the point set. More... | |
int | getNumPoints () |
Returns the number of points. More... | |
abstract double | getCoordinate (int i, int j) |
Returns \(u_{i,j}\), the coordinate \(j\) of the point \(i\). More... | |
PointSetIterator | iterator () |
Constructs and returns a point set iterator. More... | |
void | setStream (RandomStream stream) |
Sets the random stream used to generate random shifts to stream . More... | |
RandomStream | getStream () |
Returns the random stream used to generate random shifts. More... | |
void | randomize (PointSetRandomization rand) |
Randomizes the point set using the given rand . More... | |
void | addRandomShift (int d1, int d2, RandomStream stream) |
This method does nothing for this generic class. More... | |
void | addRandomShift (RandomStream stream) |
This method does nothing for this generic class. More... | |
void | addRandomShift (int d1, int d2) |
Similar to addRandomShift(d1, d2, stream) , with the current random stream. | |
void | addRandomShift () |
Similar to addRandomShift(0, d2, stream) with the current random stream and d2 the dimension of the current random shift. | |
void | clearRandomShift () |
Erases the current random shift, if any. | |
void | randomize (int fromDim, int toDim, RandomStream stream) |
By default, this method simply calls addRandomShift (fromDim, toDim, stream) , which does nothing. | |
void | randomize (RandomStream stream) |
By default, this method simply calls randomize(0, dim, stream). | |
void | randomize (int d1, int d2) |
By default, this method simply calls addRandomShift(d1, d2) . | |
void | randomize () |
By default, this method simply calls addRandomShift() . | |
void | unrandomize () |
By default, this method simply calls clearRandomShift() . | |
String | toString () |
Formats a string that contains information about the point set. More... | |
String | formatPoints () |
Same as invoking formatPoints(n, d) with \(n\) and \(d\) equal to the number of points and the dimension of this object, respectively. More... | |
String | formatPoints (int n, int d) |
Formats a string that displays the same information as returned by toString, together with the first \(d\) coordinates of the first \(n\) points. More... | |
String | formatPoints (PointSetIterator iter) |
Same as invoking formatPoints(iter, n, d) with \(n\) and \(d\) equal to the number of points and the dimension, respectively. More... | |
String | formatPoints (PointSetIterator iter, int n, int d) |
Same as invoking formatPoints(n, d), but prints the points by calling iter repeatedly. More... | |
String | formatPointsBase (int b) |
Similar to formatPoints(), but the points coordinates are printed in base \(b\). More... | |
String | formatPointsBase (int n, int d, int b) |
Similar to formatPoints(n, d), but the points coordinates are printed in base \(b\). More... | |
String | formatPointsBase (PointSetIterator iter, int b) |
Similar to formatPoints(iter), but the points coordinates are printed in base \(b\). More... | |
String | formatPointsBase (PointSetIterator iter, int n, int d, int b) |
Similar to formatPoints(iter, n, d), but the points coordinates are printed in base \(b\). More... | |
String | formatPointsNumbered () |
Same as invoking formatPointsNumbered(n, d) with \(n\) and \(d\) equal to the number of points and the dimension, respectively. More... | |
String | formatPointsNumbered (int n, int d) |
Same as invoking formatPoints(n,d), except that the points are numbered. More... | |
Additional Inherited Members | |
![]() | |
void | addCycle (AbstractList c) |
Adds the cycle c to the list of all cycles. More... | |
![]() | |
int | numBits |
double | normFactor |
![]() | |
int | numCycles = 0 |
ObjectArrayList | cycles = new ObjectArrayList() |
![]() | |
double | EpsilonHalf = 1.0 / Num.TWOEXP[55] |
int | dim = 0 |
int | numPoints = 0 |
int | dimShift = 0 |
int | capacityShift = 0 |
RandomStream | shiftStream |
![]() | |
static final int | MAXBITS = 31 |
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 \(\mathbb F_2\) denote the finite field with two elements (say, 0 and 1). Let \(P(z) = z^k - a_1 z^{k-1} - \cdots- a_k\) be a polynomial with coefficients in \(\mathbb F_2\), and consider the recurrence
\[ x_n = a_1 x_{n-1} + \cdots+ a_k x_{n-k}, \tag{mrg} \]
whose characteristic polynomial is \(P(z)\). It should be understood that in ( mrg ) all computations are performed in \(\mathbb F_2\) (this can be identified with working in integer arithmetic modulo 2). Suppose that \(\mathbf{s}_0 = (x_0,…,x_{k-1})\in\{0,1\}^k\) is fixed and define
\[ u_n = \sum_{i=1}^L x_{ns+i-1} 2^{-i}, \tag{taus} \]
where \(s\) and \(L\) are positive integers. If \(P\) is primitive, \(\mathbf{s}_0\not0\), and \(\rho= 2^k-1\) is coprime to \(s\), then the sequences ( mrg ) and ( taus ) are both purely periodic with period \(\rho\). Computing \(u_n\) from \(u_{n-1}\) involves performing \(s\) steps of the recurrence ( mrg ).
Suppose now that we have \(J\) LFSR recurrences, the \(j\)-th one having a primitive characteristic polynomial \(P_j(z)\) of degree \(k_j\), and step size \(s_j\). Let \(\{x_{j,n}, n\ge0\}\) be the \(j\)-th LFSR sequence, and define \(x_n = (x_{1,n} + \cdots+ x_{J,n}) \mod2\) and \(u_n\) as in ( taus ). Equivalently, if \(\{u_{j,n}, n\ge0\}\) is the output sequence from the \(j\)-th LFSR, then \(u_n = u_{1,n}\oplus\cdots\oplus u_{J,n}\) where \(\oplus\) denotes the bitwise exclusive-or in the binary expansion. The sequence \(\{x_n\}\) is called the combined LFSR sequence and a generator that produces this \(\{u_n\}\) is called a combined LFSR generator.
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 \(2^{k_1 + k_2}\) points.
The meaning of the parameters is the same as in the case of one polynomial.
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 \(2^k\) generated. For example, the parameters in file j1_k11.dat
are based on \(J = 1\) polynomial and generates \(2^k = 2^{11}\) points, while those in file j2_k17.dat
are based on a combination of \(J=2\) polynomials and generates \(2^k = 2^{17}\) 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 |