LFSR

From The Lancashireman's wiki
Jump to: navigation, search

Linear feedback shift registers

A LFSR can be used to generate a pseudo-random bit stream. The length of the pseudo-random bit stream before it repeats is given by the number of bits in the shift register and the feedback function. It's possible to devise feedback functions so that a LFSR with n bits generates a bit stream that starts repeating after 2n-1 bits. This is called a maximum-length LFSR.

LFSRs are often used to generate noise (especially "white noise") for audio applications.

There's a wealth of information on the 'net about LFSRs so I won't bang on about them here.

Combination of two LFSRs

This section is related to a discussion at https://electricdruid.net/white-noise-source/

If we combine the output of two LFSRs by interleaving the bits, we get a new sequence whose length is twice the lowest common multiple of the two individual lengths. In the trivial case of 2- and 3-bit LFSRs, the lengths are coprime and the new sequence has 42 bits:

 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0   = LFSR-2 (length 3) repeated 7 times
  1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0  = LFSR-3 (length 7) repeated 3 times
 111101101001101101111000111001111100101100

Note that output sequence is biased towards 1. In this case, there are 26 1s but only 16 0s.

For the rest of this discussion it is assumed that we combine two max-length LFSRs, J and K, with register lengths j and k respectively and with j < k. The sequence lengths are denoted by Lj = 2j-1 and Lk = 2k-1. Lj and Lk are coprime.

Such a combination has some interesting features:

  • The resulting sequence has length Lj * Lk.
  • There are Lk repetitions of J in the output and Lj repetitions of K.
  • It doesn't matter where we start the combination, because each bit of J occurs before each bit of K somewhere in the combined output.
  • The longest run of 1s is 2j+1. This happens whenever a longest run of 1s from J starts and ends in a longest run of 1s from K.
  • The longest run of 0s is 2j-1. This happens whenever a longest run of 0s from J starts and ends in a longest run of 0s from K.
  • Each repetition of each LFSR contributes one "missing" 0-bit, so the number of 1s in the output is Lj+Lk greater than the number of 0s.
  • If the combination of two LFSRs is used to generate audio noise, the bias towards 1 causes a DC offset, which in audio applications is probably irrelevant. Whether the bias causes any other artifacts in the noise is beyond my capability to analyse.