Error-Correcting Codes

Hamming codes, decoding spheres, and Reed-Solomon. Recovery from corruption.

Error-Correcting Codes

Error-correcting codes add a little redundancy so a receiver can repair symbols that flip in transit. They protect CDs, QR codes, and the pictures Voyager sends home.

Hamming(7,4) and the Three Parity Circles

Toggle the four data bits to re-encode, then click any bit on the diagram to flip it. The failing parity circles name the flipped bit; flip two bits and the decoder is fooled.
data bits (d3 d5 d6 d7):
codeword sent
0 1 1 0 0 1 1
received
0 1 1 0 0 1 1
distance
0 bits
decoded data
1 0 1 1

Toggle any data bit to re-encode; the parity bits update so every circle contains an even number of ones. Click any bit on the diagram to flip it (simulating channel noise). Failing parity circles turn red — the binary number formed by which circles fail is the syndrome, and it names the bit position to flip back. Try flipping two bits to see how the decoder is fooled into "correcting" the wrong one.

Go deeper:The math objects

Shannon's noisy channel coding theorem promises that reliable communication is possible up to channel capacity — but it does not tell you how. Error-correcting codes are the constructive answer. They take k information symbols, append redundancy, and transmit n > k symbols. A clever receiver can then recover the original message even when some of those symbols flip mid-flight.

  • Syndrome: the result of the parity-check equations applied to the received word. A zero syndrome means no detected error; for Hamming(7,4) the syndrome read in binary is exactly the bit position of a single error.

Decoding Spheres

Switch between codes and watch the decoding spheres around each codeword. Minimum distance 3 leaves room to correct one error; distance 1 or 2 does not.
received word:
d_min
3
corrects
1
decodes to
000
distance
1

d_min = 3, so this code corrects 1 error. Each sphere has radius 1 — every received word lies in exactly one sphere. The cube shows every binary word of length 3. Codewords are large filled dots; non-codewords are color-coded by which codeword they decode to. The dashed circles are the decoding spheres of radius t = ⌊(d_min − 1)/2⌋. Click any vertex to choose a received word — the decoder maps it to the nearest codeword by Hamming distance.

Go deeper:Hamming space

The geometry behind every code is the same. Each codeword sits at the center of a decoding sphere in Hamming space — the set of all received words it is closer to than any other codeword. A code with minimum distance d has spheres of radius ⌊(d−1)/2⌋, so it can detect d−1 errors and correct ⌊(d−1)/2⌋. Hamming(7,4) has d = 3 and corrects one bit error per block; Reed-Solomon codes work over larger alphabets and correct symbol errors, which is why they protect CDs, QR codes, and the data packets sent home by the Voyager probes.

  • Block code (n, k, d): a set of M = q^k codewords of length n over an alphabet of size q, with minimum pairwise Hamming distance d. The rate is k/n; the redundancy is n − k.
  • Hamming distance: the number of positions in which two equal-length words differ. The minimum distance d determines what the code can do: detect any pattern of up to d − 1 errors, or correct up to ⌊(d − 1)/2⌋.
  • Decoding spheres: the ball of radius t = ⌊(d−1)/2⌋ around each codeword. Spheres around distinct codewords are disjoint, so a received word inside any sphere decodes uniquely to its center.

Reed-Solomon over GF(11)

Set n, k, and the number of symbol errors. Up to ⌊(n−k)/2⌋ errors the polynomial comes back; push past that and the decoder picks the wrong one.
data symbols
2 10 6
codeword (mod 11)
2 7 2 9 6 4 3
received
2 7 2 0 6 4 3
decoded data
2 10 6
true polynomial
2 + 10x + 6x^2
recovered polynomial
2 + 10x + 6x^2

Encode k = 3 symbols by treating them as the coefficients of a polynomial and evaluating at n = 7 points in GF(11). The Singleton bound says d ≤ n − k + 1 = 5, so this code corrects up to 2 symbol errors. Push the error slider beyond 2 and watch the recovered polynomial diverge from the true one — decoding is no longer guaranteed.

Go deeper:Reed-Solomon and the Singleton bound
  • Singleton bound: for any (n, k, d) code, k + d ≤ n + 1. Codes that meet this bound are called MDS (maximum distance separable). Reed-Solomon codes are MDS.
  • Reed-Solomon: evaluations of a degree-<k polynomial at n distinct points in a finite field. Any k uncorrupted evaluations recover the polynomial via Lagrange interpolation, corrupting more than ⌊(n−k)/2⌋ defeats it.

Key takeaways

  • Codewords sit far apart in Hamming space, and decoding picks the nearest one.
  • A code with minimum distance d detects d − 1 errors and corrects ⌊(d − 1)/2⌋.
  • Hamming(7,4) corrects any single-bit error; the syndrome names the bit to flip.
  • Reed-Solomon codes meet the Singleton bound k + d ≤ n + 1.

Spot a mistake or have an idea?

Search