9. Shift Registers

A shift register is a chain of flip-flops where each one's output feeds the next one's input, all sharing the same clock. On every edge, the data shifts one position.

   Input ──→ FF₀ ──→ FF₁ ──→ FF₂ ──→ FF₃ ──→ Output
            CLK       CLK       CLK       CLK

Variants by how data enters and leaves:

9.1 SISO (serial-in, serial-out)

Data enters one bit at a time, ripples through, exits one bit at a time. Used as delay lines (the chain delays the data by N clocks), and historically in digital audio echo effects (a tape delay built from shift registers).

9.2 SIPO (serial-in, parallel-out)

Data enters serially; all flip-flop outputs are exposed in parallel after $N$ clocks. Used in:

• UART receivers: the serial line clocks bits into the SIPO; after the start, data, and stop bits, the parallel outputs hold the received byte.
• LED matrix drivers: a serial bitstream from the MCU is shifted into a long SIPO whose parallel outputs drive each LED. The 74HC595 (8-bit SIPO with output latch) is the canonical chip and shows up in countless Arduino projects, from cube displays to stadium scoreboards.
• Network deserializers: every Ethernet PHY ends with a SIPO that reconstructs parallel data from serial line code.

9.3 PISO (parallel-in, serial-out)

The inverse: load the chain in parallel from $N$ data lines, then clock out serially one bit at a time. Used in:

• UART transmitters: the data byte is loaded into the chain, then shifted out at the baud rate over the TX line.
• JTAG TDI/TDO: scan chains on chips are giant PISO/SIPO combinations. We will see this in Chapter 24.
• Test pattern generators: LFSR-based test patterns scan into chip flip-flops to trigger specific failure modes during manufacturing test.
• Network serializers: every Ethernet PHY starts with a PISO that turns parallel data into a high-rate serial line.

9.4 PIPO (parallel-in, parallel-out)

Load all flip-flops in parallel, read them out in parallel. This is just an ordinary $N$-bit register. The "shift" capability may exist as a bonus feature but is not the main use.

9.5 Bidirectional shift registers

Can shift left or shift right, depending on a direction input. Useful for arithmetic shifts (multiply or divide by 2) and barrel rotations.

9.6 Universal shift register

Combines all four modes: serial-in/parallel-in, serial-out/parallel-out, shift left/shift right, hold. Selected by mode inputs. The 74LS194 was a classic 4-bit universal shift register.

In Verilog:

module universal_shift_register #(parameter N=8) (
    input            clk, rst,
    input [1:0]      mode,        // 00=hold, 01=shift right, 10=shift left, 11=load
    input            sr_in, sl_in,
    input  [N-1:0]   parallel_in,
    output reg [N-1:0] q
);
    always @(posedge clk or posedge rst) begin
        if (rst)            q <= 0;
        else case (mode)
            2'b00: q <= q;                       // hold
            2'b01: q <= {sr_in, q[N-1:1]};       // shift right
            2'b10: q <= {q[N-2:0], sl_in};       // shift left
            2'b11: q <= parallel_in;             // load
        endcase
    end
endmodule

9.7 LFSR: the workhorse of pseudorandom sequences

A linear feedback shift register (LFSR) is a shift register with XOR feedback from selected stages back to the input. With well-chosen "tap" positions, an $n$-bit LFSR produces a maximum-length pseudorandom sequence: $2^n - 1$ distinct nonzero values before repeating.

   ┌──────[XOR]←──[XOR]←─────┐
   │         ↑       ↑       │
   ↓         │       │       │
  [FF₀]──→[FF₁]──→[FF₂]──→[FF₃]──→ ...

The taps are chosen using the theory of primitive polynomials over GF(2). Tables exist (Xilinx Application Note 052 has a famous one) listing taps for every $n$ up to 168.

LFSRs are everywhere:

• Stream ciphers. A5/1 (old GSM cellular), E0 (Bluetooth), Trivium, Grain. Pseudo-random key streams XORed with plaintext. Some early stream ciphers (RC4 is not LFSR-based but the principle is similar) have been broken, often because the LFSR state leaks too quickly.
• Built-in self-test (BIST). Chips include LFSRs that generate test patterns and signature analyzers that compress responses. Manufacturing test would otherwise need terabytes of test vectors.
• GPS pseudo-random codes. Each GPS satellite transmits a unique 1023-bit Gold code, which is itself derived from XORing two LFSRs. The receiver correlates against the locally-generated code (Chapter 3 cross-correlation) to acquire and track the satellite.
• CRC checksums. A CRC generator is essentially an LFSR that ingests data and produces a final residue. Ethernet uses CRC-32; Bluetooth and many wireless protocols use shorter CRCs.
• Hardware-security PUFs and challenges. LFSR-derived challenges to physically unclonable functions explore a wide range of inputs without storing them all.
• Whitening for flash memory and SSDs. Data is XORed with an LFSR sequence before storage to break up patterns that could otherwise stress particular cells.

Hardware-security note: do not use LFSRs as cryptographic random number generators. The output of an $n$-bit LFSR with publicly-known taps can be fully recovered from $n$ consecutive output bits, by setting up the linear system and solving over GF(2). For cryptographic purposes you need a non-linear post-processor (Trivium uses a non-linear filter; SP 800-90 DRBGs use AES or hash post-processing). Any "secure RNG" you write that is just an LFSR is broken.