4 ms·
Linear Feedback Shift Registers
- kurthr 9y agoLFSRs 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 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.
- Animats 9y agoThose are fun. The little flickering LEDs used as replacements for candles have a linear feedback shift register as the random number generator.
- monocasa 9y agoMost 2D Nintendo games too.
- deleted 9y ago[deleted]
- lpmay 9y agoLFSR'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 https://www.embeddedrelated.com/showarticle/1065.php
- jhallenworld 9y agoIt 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.
- SAI_Peregrinus 9y agoYou 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.pdf http://webhome.cs.uvic.ca/~mserra/AttachedFiles/CA_Tutorial....
- bascule 9y agoJust don't use them (or any linear function, for that matter) for cryptography: https://en.wikipedia.org/wiki/Content_Scramble_System#The_cipher https://en.wikipedia.org/wiki/Content_Scramble_System#The_ci...
- jonnycomputer 9y agoThis 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
- jabujabu 9y agoLFSR's are cool, I learned a decent amount about them while I was implementing SHA-3 in python.
- lou1306 9y agoThe Wolfenstein 3D tidbit is lovely. That game's a gem for so many different reasons.