LSFR can also be used as a random number generator. The generated signal that can be picked at any digit of the register, is not fully random (pseudorandom), still reasonably chaotic. The number of possible states (hence the randomness of the signal) would likely increase when increasing the number of bits in the register.
The "theoretically correct" LSFR should use XOR gate, however such device may stall the generator in "all zeros" state. Using XNOR (XOR with inverted output) makes the opposite "all ones" state illegal (stall state), however it is often easier to reset the register to the "all zeros" state on startup. While XNOR-based device is not strictly a LSFR, in practice it behaves largely the same way as a XOR based device.
Register bits from where the signal is picked for the generating the next value for the lowest bit are called taps. The pictured diagram has two taps, the bit 3 and the highest bit 4 (the device may also work with different taps).
The LFSR is only a maximum-length if the number of taps is even. Just 2 or 4 taps can suffice even for very long sequences. To produce a maximum length counter, the set of taps — taken all together, not pairwise (i.e. as pairs of elements) — must be relatively prime (there must be no common divisor to all taps). There can several ways of connecting taps to produce a maximum-length LSFR.
Device that only modifies the currently lowest bit (computing it from the tap outputs) is also called a Fibonacci LFSR. If some logic is also inserted to compute values for the intermediate bits (rather than inheriting these values from the lower bit as in usual shift operation), the device is a Galois LFSR.
New articles (RSS)
