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.
![linear feedback shift register example linear feedback shift register example](https://i.stack.imgur.com/ocbGF.png)
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.
![linear feedback shift register example linear feedback shift register example](https://i.gyazo.com/6b8e0f7b97c93860463a9791d2a638f0.png)
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.