next up previous

6 Lagged Fibonacci Generators     continued...

If we set m equal to a higher power of two, say , i.e., , then the single-bit values of the X's in Figure 8 will instead be represented by M bits each. Figure 10 is a diagram of the mod-16 linear shift register associated with the equation

In looking at this more general Fibonacci generator, , two things are worth noting:

  1. If we look for a moment at only the least significant bits of the elements in this register, that is, only those bits in the bottom row, then we see that the behavior of this row is unaffected by bits in the higher rows. The contents of the bottom row will therefore be indistinguishable from those of the binary shift register in Figure 8.

    Figure 10: Register Motion for LFG(10,7,4).

    This is no surprise --- when we add two numbers, the answer in the one's place does not depend in any way on the digits in the ten's place (here, the two's place).

  2. If the bottom row of bits is all zeros, then no amount of register motion can produce any ones there. This is to say that if the first values of X are all chosen to be even, then there can be no subsequent X values that are odd when the register is advanced. In such a case the pseudo-random number generator will not be of full period. The period can be no larger --- and may be smaller --- than , since all odd numbers will be excluded.