If you associate the linear coefficients with polynomial coefficient (with a sign change, as noted in the previous post) then the LFSR sequence is a De Bruijn sequence if and only if the polynomial is a primitive polynomial of degree n.Ī few months ago I wrote about LFSRs in the context of random number generation. For some choices of linear coefficients the output is a De Bruijn sequence, but not for others. So technically a LFSR is an “nearly always linear feedback shift register.” It’s linear for 2 n – 2 inputs and nonlinear for 2 special inputs.Ī LFSR is more general than a binary De Bruijn sequence. 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. Otherwise return c 1 x 1 + c 2 x 2 + … c n x n mod k.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.

Linear feedback shift register binary