The algorithm couldn’t be entirely linear because it would get stuck It would produce nothing but zeros forevermore once it encountered an input sequence of all zeros. Note that the LFSR algorithm is a linear operator over the field GF(2), except for the special cases in steps 1 and 2. Hence the name “linear feedback shift register” sequence. We then shift the register content over by one and add the new output on the end. We take the feedback from the previous outputs and compute a linear combination. That is, we operate on the latest n symbols, saving them to registers. Note that the last line says to return a linear combination of the previous symbols. Here’s the algorithm from the previous post: If we set k = 2, the generating algorithm is an example of a linear feedback shift register (LFSR) sequence.

As noted near the end of the post, the case k = 2 is especially important in application, i.e. These are optimal sequences that contain every possible consecutive sequence of n symbols from an alphabet of size k. The previous post looked at an algorithm for generating De Bruijn sequences B( k, n) where k is a prime number.