schemd
← all environments 12 · Advanced · Sequential digital · v0.2.1

Maximal-Length LFSR

Sequential digital

A 4-bit Fibonacci linear-feedback shift register with taps at stages 3 and 4 — the primitive polynomial x4+x3+1x^4+x^3+1. Each clock edge shifts the register and feeds back the XOR of the tapped bits. The result cycles through all 15 non-zero states before repeating: a deterministic sequence wearing the disguise of randomness.

7 components · 11 connections · clocked shift register over GF(2)

the aha

A handful of flip-flops and a single XOR generate a stream that passes for random — yet is perfectly deterministic and repeats after exactly 2n−12^n - 1 steps.

why it works
Each clock edge, the register shifts one place and a new bit enters from the left: the XOR of a chosen set of taps. Over the field GF(2)\text{GF}(2) this is just repeated multiplication, and if the tap positions correspond to a primitive polynomial — here x4+x3+1x^4 + x^3 + 1 — the register visits every non-zero 4-bit state before returning home. That is 24−1=152^4 - 1 = 15 states in a fixed but scrambled order: a maximal-length sequence. It looks statistically random (equal 0s and 1s, flat autocorrelation) which is why LFSRs sit inside CRCs, spread-spectrum radios, and cheap noise sources — yet knowing the taps and one state predicts all of it forever. The all-zero state is the one trap: it maps to itself, a dead register.
governing model
x4+x3+1  ⋅  period=2n−1=15x^4 + x^3 + 1 \;\cdot\; \text{period} = 2^n - 1 = 15
structural inventory
  • shared clock
  • 4×4\times D flip-flop chain
  • XOR feedback taps 3,43,4
  • serial m-sequence output
boundaries
  • period 24−1=152^4-1=15
  • all-zero state forbidden
  • primitive polynomial taps
fault relay feedback tap moved (short cycle)

  1. Single-step the clock and read the state.

    Each edge produces a new 4-bit pattern. Write them down — you will pass through all 15 non-zero values with no repeats until the cycle closes.

  2. Confirm the period is exactly 15.

    The sequence returns to its start after 24−12^4 - 1 clocks. Fewer flip-flops would give 2n−12^n - 1; the maximal length is the payoff of primitive taps.

  3. Move a feedback tap.

    A non-primitive tap set shatters the one long cycle into several short ones — the register gets stuck in a stunted loop of length 5 or 3. Same hardware, ruined sequence.
causal signal trace paused

Clock the register One clock edge samples every D input simultaneously.

step 1 / 7 Clock the register

Loading Maximal-Length LFSR model…