Linear Feedback Shift Registers

LFSRs are an interesting topic since they see so much use in hardware testing, scrambling, and orthogonal coding. Typically they are used as MLS-Maximum Length Sequences. These sequences and the generating polynomials were (I think?) shown to be related groups by Galois. Look for Golomb and Rice coding if you're interested in this math.

https://en.wikipedia.org/wiki/Maximum_length_sequence

It's a bit odd that they only show the Galois generation method in this blog and not the more commonly used Fibonacci feedback method which takes the current state and generate the next bit each clock (rather than modifying multiple bits each shift).

Note that Gold and Kasami codes are related to MLS... and if you recognize those names from NASA, it's because they developed those high auto-correlation codes for GPS and interplanetary communication.

LFSR's are cool. Jason Sachs also has a great article series on LFSR's on Embedded Related, if you're interested in an even more in-depth coverage.

https://www.embeddedrelated.com/showarticle/1065.php

Just don't use them (or any linear function, for that matter) for cryptography:

https://en.wikipedia.org/wiki/Content_Scramble_System#The_ci...

Those are fun. The little flickering LEDs used as replacements for candles have a linear feedback shift register as the random number generator.

It was common to use them as counters in early FPGAs such as XC2000 and XC3000. LFSRs where faster and smaller than binary counters since the early FPGAs did not have fast carry logic.

I used them for column, row and address generation in FPGA-based video capture and display cards.

This 256 byte C64 music project--not mine, unfortunately--used LFSRs to generate the melody.

https://linusakesson.net/scene/a-mind-is-born

LFSR's are cool, I learned a decent amount about them while I was implementing SHA-3 in python.

The Wolfenstein 3D tidbit is lovely. That game's a gem for so many different reasons.