next up previous

6 Lagged Fibonacci Generators     continued...

This problem is addressed by Mascagni, et al.\ [41], where they describe a canonical form for initializing Fibonacci generators. This canonical form is determined by and k, but is independent of M. To understand the use of this canonical form, consider a second view of the register shown in Figure 11. The L-shaped region along the left column and the bottom row is fixed with all zeros, except for a one in the least significant bit of word 7 (the word associated with ). The remaining bits, those in the -bit rectangular region filled with z's, are free to be chosen in any combination. Each combination of bits in the area will generate a distinct cycle of pseudo-random numbers. In other words, every possible bit pattern that can be put in the canonical form will occur in one and only one full period cycle.

Figure 11: Canonical Form for LFG(10,7,4).