LFSR / PRBS – Mathematical Background

LFSRs and PRBS generators are based on polynomial arithmetic over the Galois Field GF(2). Although their hardware implementation uses shift registers and XOR gates, the underlying theory is algebraic and closely related to CRCs. This page summarizes the essential mathematical concepts behind maximal‑length sequences, primitive polynomials, and the equivalence between Fibonacci and Galois forms.

1. Polynomials over GF(2)

An LFSR state is interpreted as a polynomial whose coefficients belong to GF(2). For example, the bit string:

1011001

represents the polynomial:

x^6+x^4+x^3+1

Arithmetic rules in GF(2):

• addition = XOR
• subtraction = XOR
• multiplication = AND + XOR
• no carries or borrows

This makes LFSRs extremely efficient in hardware.

2. Feedback Polynomial

The behavior of an LFSR is defined by its feedback polynomial:

P(x)=x^N+a_kx^k+\dots +a_1x+1

where each coefficient a_i is either 0 or 1.

The polynomial determines:

• the taps in the LFSR
• the sequence length
• whether the sequence is maximal
• the statistical properties of the output

3. Primitive Polynomials and Maximal-Length Sequences

A polynomial is primitive over GF(2) if it generates a maximal-length sequence:

2^N-1

This sequence cycles through all non‑zero states of the register. The all‑zero state is excluded because it would lock the LFSR permanently.

Common primitive polynomials:

• PRBS7: x^7+x^6+1
• PRBS15: x^{15}+x^{14}+1
• PRBS23: x^{23}+x^{18}+1
• PRBS31: x^{31}+x^{28}+1

4. Fibonacci and Galois Equivalence

Fibonacci and Galois LFSRs implement the same polynomial but distribute the XOR operations differently.

• Fibonacci form applies feedback only at the input.
• Galois form distributes feedback across multiple taps.

Mathematically, both forms implement the same linear recurrence:

The difference is purely architectural, not mathematical.

5. Autocorrelation and Spectral Properties

Maximal-length sequences (m‑sequences) have excellent statistical properties:

• uniform distribution of 0s and 1s
• two-level autocorrelation
• flat power spectrum except for a DC notch

These properties make PRBS sequences ideal for:

• stressing communication links
• spread-spectrum systems
• radar and correlators
• BIST and pseudo-random testing

6. Relationship to CRCs

LFSRs and CRCs share the same mathematical foundation:

• both use polynomials over GF(2)
• both rely on feedback defined by the polynomial
• both can be unrolled to parallel form
• both avoid the all-zero state

The main difference is purpose:

• CRCs compute remainders
• LFSRs generate sequences

7. Related Pages

• LFSR & PRBS — Overview, Families & Architecture
  Provides a unified view of Linear Feedback Shift Registers and Pseudo‑Random Binary Sequences, covering architectural principles, polynomial families, implementation trade‑offs, and their role in line coding, scrambling, and verification flows.
• LFSR / PRBS – Reference Table
  Primitive polynomials, taps, and sequence lengths for common LFSR and PRBS variants, suitable for implementation and verification
• LFSR / PRBS – RTL Implementation Notes
  Implementation details for serial and parallel LFSR/PRBS generators, including initialization rules, pipelining, and verification strategies
• CRC — Overview, Families & Architecture
  CRC computation shares the same GF(2) polynomial arithmetic used in LFSR and PRBS structures, making CRC a direct architectural extension of these mathematical foundations.
• Data Path — Architecture & Fundamentals
  Integration of LFSR/PRBS generators and checkers into streaming datapaths, including placement, throughput considerations, and interaction with downstream blocks.
• Flow Control — Architecture & Fundamentals
  Mechanisms that regulate data movement and ensure correct alignment, seeding, and checking of LFSR/PRBS sequences within streaming pipelines.
• Pipelining — Architecture & Fundamentals
  Architectural techniques used to balance LFSR/PRBS computation latency, improve timing closure, and maintain full‑rate throughput.