Cyclic Codes: CRC, BCH & Reed–Solomon

A cyclic code is a linear block code whose legal words remain legal after a cyclic shift. That symmetry turns an $n$-symbol vector into a polynomial modulo $x^n-1$, so encoding, checking, and much of decoding become polynomial arithmetic over a finite field. CRCs, BCH codes, and Reed–Solomon (RS) codes share this machinery, but they solve different problems: a CRC is normally a high-quality detector, while BCH and RS spend more redundancy and decoder work to correct errors.

The family name is not an on-wire specification. Field construction, generator polynomial, coefficient order, initialization, reflection, shortening, symbol order, and final XOR all affect the transmitted bits. Interoperability starts with those conventions, not with the label “CRC-32” or “RS(255,223).”

Vectors become polynomials #

Represent a word $(c_0,c_1,\ldots,c_{n-1})$ by

$$c(x)=c_0+c_1x+\cdots+c_{n-1}x^{n-1}.$$

Multiplication by $x$ shifts every coefficient. Reducing modulo $x^n-1$ wraps the coefficient of $x^n$ back to the constant position, exactly implementing a cyclic shift. A cyclic code over $GF(q)$ is generated by a monic polynomial $g(x)$ that divides $x^n-1$:

$$\mathcal C=\{m(x)g(x)\bmod(x^n-1)\}.$$

If $\deg g=n-k$, the code has $k$ information symbols and $n-k$ check symbols. The complementary polynomial

$$h(x)=\frac{x^n-1}{g(x)}$$

plays the parity-check role. This is the same $G/H$ relationship described for linear block codes, written in a basis where shifting has algebraic structure.

flowchart TD
  M["message polynomial"] --> E["systematic encode<br/>append places → divide by g(x) → add remainder"]
  E --> C["codeword divisible by g(x)"]
  C --> CH["noisy channel"]
  CH --> S["compute remainder or root syndromes"]
  S --> Z{"all zero?"}
  Z -->|yes| OK["accept as codeword"]
  Z -->|no| ACT["detect, or locate and correct"]

The diagram deliberately ends in two actions. A nonzero syndrome proves that the received word is outside the code, but a detector may stop there; a corrector needs enough independent syndrome information to identify an error pattern uniquely.

Systematic encoding is polynomial division #

To keep the message visible, shift it by $n-k$ positions and divide by $g(x)$:

$$x^{n-k}m(x)=q(x)g(x)+r(x),\qquad \deg r<n-k.$$

Over $GF(2)$ subtraction and addition are both XOR, so the systematic codeword is

$$c(x)=x^{n-k}m(x)+r(x).$$

It is divisible by $g(x)$. At the receiver, polynomial division of $r_{cv}(x)$ by $g(x)$ produces a zero remainder for every legal codeword and a nonzero remainder for most corrupted words. “Most” matters: an error polynomial that is itself divisible by $g(x)$ is undetected.

Worked CRC division #

Use message 1101, interpreted highest power first as

$$m(x)=x^3+x^2+1,$$

and generator 1011,

$$g(x)=x^3+x+1.$$

The generator has degree three, so append three zeros: 1101000. XOR long division gives remainder 001; append that remainder to obtain 1101001. Dividing the complete seven-bit word by 1011 gives zero.

The same calculation can be implemented as a three-stage linear-feedback shift register. The register is only a streaming form of polynomial division; its tap drawing must still match the chosen coefficient and shift convention.

A degree-$r$ CRC with nonzero constant coefficient detects every single burst of length at most $r$. A burst shorter than or equal to $r$ has an error polynomial $x^ib(x)$ with $\deg b<r$ and nonzero end coefficients; a degree-$r$ generator with no factor $x$ cannot divide it. Other guarantees depend on the polynomial and protected length. If $(x+1)$ divides $g(x)$, every odd-weight error is detected; that benefit is bought by constraining the generator and is not implied by its degree alone.

A CRC is a parameter tuple #

RFC 1662 provides a concrete interoperability lesson. Its 16-bit FCS is built from the polynomial $x^{16}+x^{12}+x^5+1$, but the specification also fixes the initial value, complementing, least-significant-bit-first transmission, and a receiver residue check. An implementation that copies only 0x1021 can produce the wrong octets while believing it uses the same polynomial.

Record at least:

• width and full mathematical polynomial;
• initial register value;
• input and output reflection conventions;
• final XOR/complement;
• byte order on the wire;
• protected byte range, including or excluding headers and the check field;
• a normative check value and the expected residue after processing a complete valid frame.

The CRC should be checked after the transforms the protocol declares part of its protected word. Descrambling, de-stuffing, byte unescaping, and FEC decoding can sit on either side of the check in different protocols; guessing the order produces consistent false failures.

BCH codes design roots, not just a remainder #

Let $\alpha$ be an element of an extension field and let the code length be compatible with its multiplicative order. A narrow-sense BCH code with designed distance $\delta$ chooses a generator whose roots include

$$\alpha,\alpha^2,\ldots,\alpha^{\delta-1}.$$

Because coefficients may live in the base field while those roots live in an extension, $g(x)$ is the least common multiple of the roots' minimal polynomials. The BCH bound guarantees

$$d_{min}\ge\delta.$$

For a binary code designed to correct $t$ errors, a common choice is $\delta=2t+1$. The actual distance may be larger, but the designed distance is the guaranteed construction parameter.

For received polynomial $r(x)=c(x)+e(x)$, evaluate root syndromes

$$S_j=r(\alpha^j)=e(\alpha^j),$$

because every legal $c(x)$ vanishes at the specified roots. A practical algebraic decoder then follows a causal chain:

1. compute the syndromes; all zero means no error is visible to the code;
2. solve the key equation for an error-locator polynomial, commonly with Berlekamp–Massey or the extended Euclidean algorithm;
3. perform a Chien search over field locations to find the locator roots;
4. compute error magnitudes, commonly with Forney's formula; in a binary BCH code each nonzero magnitude is simply one;
5. correct, then recompute every syndrome before releasing the word.

If the locator degree, number of roots, or post-correction syndrome is inconsistent, declare decoding failure. Silently applying a partial correction turns a detectable codeword failure into plausible corrupted payload.

Reed–Solomon moves from bits to symbols #

An RS message is a polynomial $p(x)$ of degree below $k$ over $GF(q)$. Evaluate it at $n$ distinct field points:

$$c=(p(\beta_0),p(\beta_1),\ldots,p(\beta_{n-1})).$$

Two different degree-$(k-1)$ polynomials can agree at no more than $k-1$ points, so their codewords differ in at least

$$d_{min}=n-k+1$$

positions. RS meets the Singleton bound and is therefore maximum-distance separable (MDS). With $n-k$ parity symbols it can recover any mixture satisfying

$$2t+e\le n-k,$$

where $t$ is the number of unknown erroneous symbols and $e$ the number of erasures at known locations.

This distance is measured in field symbols, not bits. In an RS code over $GF(2^8)$, one wrong bit and eight wrong bits inside the same byte both consume one erroneous-symbol position. A physical burst that crosses byte boundaries can consume several positions, while interleaving can spread a long channel burst across different codewords.

Shortening, puncturing, and erasures are different #

Shortening

Fix selected information positions to known values, omit them on the wire, and restore them before decoding. Both $n$ and $k$ shrink by the same amount, so the parity count and designed distance are retained.

Puncturing

Omit selected transmitted parity symbols and restore them as erasures. The effective rate rises and correction margin falls.

Erasure decoding

Transmit the symbol, but let the receiver mark its location unreliable. The decoder spends one distance unit rather than two because it no longer needs to discover the position.

Conflating these operations causes off-by-one and alignment bugs. A shortened RS decoder may expose a full-length API, but the caller must insert the implicit symbols in the exact declared locations. A punctured symbol must enter as zero information, not as a confident numeric zero.

Choose the decoder for the failure model #

A CRC after FEC is not redundant. The algebraic decoder corrects patterns within its guaranteed radius and may miscorrect patterns outside it; an independent CRC sharply reduces the chance that an out-of-radius output is accepted. Conversely, a CRC alone is often the right answer when a fast retransmission path exists and permanent FEC overhead would cost more than rare retries.

Bit-exact verification #

Before running a random BER campaign, build small deterministic evidence:

1. state the field size and primitive polynomial, then enumerate multiplication and inverses against a reference;
2. state polynomial coefficient order and map the first and last wire bits to powers of $x$;
3. encode all-zero, one-hot, all-one, and a published check vector;
4. verify the systematic payload positions and complete-codeword residue;
5. inject every single error position, then boundary mixtures with $2t+e=n-k$ and one step beyond;
6. confirm that a declared failure leaves no partially corrected payload marked valid;
7. test shortening, interleaving, and puncturing boundaries independently before composing them;
8. record decoder syndromes, locator degree, root count, corrected positions, and post-check residue for every failed frame.

The durable mental model is one algebra with three contracts: divisibility defines legal cyclic words, roots and syndromes make error patterns observable, and the protocol parameter tuple maps that algebra to actual bits and bytes. Most theory bugs are distance mistakes; most deployed bugs are convention mistakes.