Software engineers reach for rand() without a second thought. In hardware, generating pseudo-random sequences efficiently is a solved problem — with a beautifully simple circuit called the Linear Feedback Shift Register (LFSR). It's a shift register where certain bit positions are XORed together and fed back into the input.

Take a 4-bit LFSR with taps at positions 4 and 3 (counting from 1). The circuit is just four flip-flops in a chain, with the outputs of bits 4 and 3 XORed to produce the next input bit. Starting from 0001, the register cycles through 15 unique states before repeating — every possible nonzero 4-bit value. This is called a maximal-length LFSR.

The sequence: 0001 → 1000 → 0100 → 0010 → 1001 → 1100 → 0110 → 1011 → 0101 → 1010 → 1101 → 1110 → 1111 → 0111 → 0011 → back to 0001. That's 2ⁿ−1 states for an n-bit register. The all-zeros state is the one value it never hits — and never escapes from if it lands there, since XOR of all zeros is zero.

Rule of thumb: An n-bit maximal-length LFSR produces a sequence of length 2ⁿ−1. For a 16-bit LFSR, that's 65,535 values before repeating. A 32-bit LFSR gives you over 4 billion. The tap positions that produce maximal-length sequences come from tables of primitive polynomials over GF(2) — you look these up, not derive them.

Why hardware loves LFSRs: The entire circuit is a shift register plus one or two XOR gates. No adders, no multipliers, no carry chains. It runs at the full clock speed of the flip-flops with negligible area. Compare that to a software PRNG that burns ALU cycles on multiplies and adds.

Real-world uses are everywhere:

• CRC computation — Ethernet, USB, and SATA all use LFSRs to compute cyclic redundancy checks on data streams. The polynomial defining the CRC maps directly to LFSR tap positions.
• Built-in self-test (BIST) — Chips test their own logic by feeding LFSR-generated patterns into combinational blocks and compressing outputs with another LFSR (called a signature analyzer).
• Scrambling — PCIe and HDMI XOR data with an LFSR sequence to spread the frequency spectrum and reduce electromagnetic interference.
• DRAM refresh — Some controllers use LFSRs instead of binary counters for refresh addresses, distributing power draw more evenly across time.

The trap: LFSRs are not cryptographically secure. Given 2n consecutive output bits from an n-bit LFSR, you can reconstruct the entire state and predict every future value. Never use one where unpredictability matters — use them where cheap, fast, and "random enough" is the goal.