Hacker News new | comments | show | ask | jobs | submit login
Linear Feedback Shift Registers (datagenetics.com)
62 points by signa11 57 days ago | hide | past | web | favorite | 10 comments

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.


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.

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


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

Most 2D Nintendo games too.

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.


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.

You might find Linear Hybrid Cellular Automata (LHCA) interesting as well. They're similar to LFSRs, but with potentially better performance.


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


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.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact