Linear Feedback Shift Registers For FPGAs

28 Comments

If you want to start an argument at a Hackaday meeting, you have only to ask something like “How much does this weigh?” or “What time is it?” But if you really want to start a street brawl, you can always say, “Are these numbers random?” Making random numbers that are actually random is actually a tough nut to crack. Most of what we do is, technically, pseudo-random (but we’ll say random number and assume you know what we mean). One way to generate seemingly random sequences is to use a linear feedback shift register or LFSR. You can use LFSRs in software, but they are also very useful in hardware design and [Adam Taylor] takes us through his use of them on FPGAs in a recent post.

As [Adam] points out, they not only generate random-like patterns but they are often used as high-performance counters and in error detection and correction schemes. As the name implies, the mechanism is a simple shift register with one or more of its outputs fed back around to the input. How can that be random? Well, it can’t be, but it is often good enough for places where you need a sequence of numbers. Depending on how you organize the outputs — or taps — and how you feed them back means you can control the pseudo-random sequence.

A Fibonacci LFSR

There are two common methods for creating LFSRs. A Fibonacci-style design uses XOR (or inverted XOR) gates in the feedback loop. For example, consider an eight-stage counter. The post shows the output of flip flop 4, feeding an XOR gate that drives the counter’s input. The other input of the XOR gate is the output of another XOR gate that receives input from flip flop 5 and the output of yet another XOR gate. That XOR gate receives its inputs from flip flop 6 and the output of the shift register.

The Galois scheme is similar, but uses the XOR gates in the shift path. In other words, the output of the shift register directly feeds the input, but it also feeds several XOR gates that go between the flip flops. Why choose one over the other? Read the post. The summary is that it depends on how your FPGA resets and what kind of support it has for shift registers so, as usual, it pays to understand what’s going on in the FPGA fabric.

As for where to put the taps, it depends on how you want the pattern to repeat. If you want the repeating kept to a minimum, you can look them up in a table based on research from [Wayne Stahnke] and popularized by Xilinx in an app note. [Solomon Golumb] also published tables of taps for maximum sequence generation. As you might expect, there’s a program that will help you if you don’t want to use the tables.

The math may be hairy, but implementing this in hardware is simple if you ever need a random-looking sequence. Maybe you want a random flicker in your fake candle. You can do it with relays, even.

28 thoughts on “Linear Feedback Shift Registers For FPGAs”

      1. Quantum mechanics is entirely deterministic and even linear. That is the evolution of the wave function is determiniatic and linear.

        It’s just the so called collapse of the wave function that random, but that’s not part of quantum mechanics, only part of some interpretations of it, like the old Copenhagen interpretation. Many-worlds doesn’t have wave function collapse, neither random nor otherwise.

        (Of course, you still have the Born rule.)

        Report comment
        Reply

  2. Since the ’80s I’ve had in my mind the possibility of a processor with a pseudo-random program counter! The idea being that a linear feedback shift register uses fewer gates than a full adder/incrementer, but with suitable tap points would generate a maximal length sequence for the PC size. But these days gates are plentiful so probably yet another never-do-it project!

    Report comment
    Reply

    2. LFSR counters got used for address-type counters a lot in days of yore: it’s not just that it’s fewer gates, it’s fewer gates in the critical path.

      You still do get some savings in FPGAs because of the limited feedback logic – in most FPGAs ripple-carry adders require 1 LUT/bit and need to pack tightly no matter what because they have to use the carry chain, whereas an LFSR can mostly use registers only and frees up the routing.

      Report comment
      Reply

  3. Coded an LFSR into a PIC 12F675 years ago.

    Added a power transistor and used it to run a short string of LED Christmas lights.

    Drove my mother crazy trying to work out the pattern.

    Job done.

    Report comment
    Reply

  5. Rather than “random” I’ll settle for “chaotic”.
    The longer you need to observe the output, in order to determine the sequence (or your place in a known sequence) the more chaotic the system is.

    Report comment
    Reply

  6. The Xilinx app note makes a few weird choices for some LFSRs. There are also a class of LFSRs that can be implemented in the built in shift registers, making them absurdly tiny.

    Because they’re deterministic sequences you can use them for large delays instead of counters: it’s cheaper to detect a run of n equal values (log2(n)) plus an LFSR if the LFSR only costs you a LUT+FF or two.

    https://github.com/barawn/verilog-library-barawn/wiki/Timer-clock-enable-divider-tricks#lfsr-timer

    Report comment
    Reply

  9. Hi, thank you for posting it. Let me clear the idea of randomness. There are 2 classes of randomness, true random and pseudo random. They both exhibit random patterns, the only difference is the probability dependency. True random is truly unpredictable, and only achievable in hardware. Pseudo random has equal chance for all number, can be done on software and hardware. Says if the first sequence is 1 (or seed), then we know that the next sequence will have higher chance, much like card counting. The LFSR random patterns will repeat for every complete shift cycle.

    For those says that LFSR is useless, FYI, I implemented AI CNN hardware accelerator on FPGA with LFSR as the clock source, literally. There are more exotic computing paradigms than you could imagine. Read more literature before leaving comment. Anyway, it is a good start to explore randomness in FPGA, keep the good work.

    Report comment
    Reply

    1. I happen to love cryptographically weak prng. The NES/Famicom made good use of LFSR in games. An encoded drum pattern can be put through an LFSR to give you a whole sequence of pattern permutations. And all of this at very minimal system resources, or can be done without a CPU even with logic circuits.

      Report comment
      Reply

    2. “For those says that LFSR is useless”

      I would say that there’s very few people reading this for which the statement wasn’t encoded and decoded through an LFSR, considering they’re the basis for whitening in PCIe/USB3/GigE/SATA/HDMI/etc.

      Report comment
      Reply

  10. That’s how the Atari vcs graphics chip was built

    Using a bunch of lfsr organized in polynomial counting logic

    Explain why the 2600 has the most unique audio tones, since its frequency is tapped (divided) from different stages of an oscillator/lfsr circuit but I guess Jay miner didn’t have the most musical ear

    Guess he learned by the time the pokey came into being or just had someone else do it.

    Report comment
    Reply

      1. Cycle length isn’t a meaningful metric to compare algorithms. Anything can have a cycle length that long (a several-hundred bit LFSR would, for instance), and nothing algorithmic can have a cycle length longer than 2^(total number of bits). LFSRs are actually very efficient in terms of cycle length per generated bits given that they only give up one state.

        Report comment
        Reply

Leave a Reply

Please be kind and respectful to help make the comments section excellent. (Comment Policy)

This site uses Akismet to reduce spam. Learn how your comment data is processed.