Linear Feedback Shift Registers(datagenetics.com)
datagenetics.com
Linear Feedback Shift Registers
http://datagenetics.com/blog/november12017/index.html
11 comments
Just don't use them (or any linear function, for that matter) for cryptography:
https://en.wikipedia.org/wiki/Content_Scramble_System#The_ci...
https://en.wikipedia.org/wiki/Content_Scramble_System#The_ci...
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.
I used them for column, row and address generation in FPGA-based video capture and display cards.
You might find Linear Hybrid Cellular Automata (LHCA) interesting as well. They're similar to LFSRs, but with potentially better performance.
http://webhome.cs.uvic.ca/~mserra/AttachedFiles/CA_Tutorial....
http://webhome.cs.uvic.ca/~mserra/AttachedFiles/CA_Tutorial....
[deleted]
This 256 byte C64 music project--not mine, unfortunately--used LFSRs to generate the melody.
https://linusakesson.net/scene/a-mind-is-born
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.
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.
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.
https://www.embeddedrelated.com/showarticle/1065.php