Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 37 ยท Applications: Codes and Cryptography

Linear Codes and Hamming Codes

See how vector spaces over the field Z_2 give error-correcting codes: build the Hamming (7,4) code, compute its distance and correct errors in Python.

When data travels over a noisy channel or sits on a scratched disc, some bits flip. An error-correcting code adds structured redundancy so the receiver can detect and fix such errors. The cleanest codes come from algebra: a linear code is a subspace of a vector space over a finite field, and the field you met earlier, โ„คโ‚‚ = GF(2), is the one used for bits.

Codes and distance

Work in ๐”ฝโ‚‚โฟ, the vectors of n bits, where addition is XOR. A code is a set of allowed vectors called codewords. A linear code C is a subspace: the sum of two codewords is a codeword. If its dimension is k, then C has 2แต codewords. We call it an [n, k] code: k message bits are encoded into n bits.

The Hamming distance d(u, v) is the number of positions where u and v differ, and the weight of v is the number of 1s. For a linear code the minimum distance d equals the smallest weight of a nonzero codeword, since d(u, v) = weight(u + v).

What d buys you:

  • The code detects up to d - 1 errors.
  • It corrects up to t = โŒŠ(d - 1)/2โŒ‹ errors: balls of radius t around codewords do not overlap.

Generator and parity-check matrices

A linear code is described by a generator matrix G (a k ร— n matrix whose rows span the code) with codeword = message ยท G. Equivalently it is the null space of a parity-check matrix H (an (n - k) ร— n matrix): c is a codeword exactly when H cแต€ = 0.

For a received word r, the syndrome s = H rแต€ is zero when r is a codeword. If r = c + e with an error vector e, then s = H eแต€: the syndrome depends only on the error, not the message.

The Hamming (7,4) code

Take a 4 ร— 7 generator matrix G = [Iโ‚„ | P] and a 3 ร— 7 parity-check matrix H = [Pแต€ | Iโ‚ƒ], with

Text
P = [[1, 1, 0],
     [1, 0, 1],
     [0, 1, 1],
     [1, 1, 1]]

This is a [7, 4] code with 16 codewords and minimum distance d = 3, so it corrects any single bit error. The columns of H are the seven distinct nonzero vectors of ๐”ฝโ‚‚ยณ. If one bit j flips, the syndrome equals column j of H, which tells you which bit to fix.

The program builds the code, computes its minimum distance and corrects every possible single-bit error.

Python Hamming (7,4): encode, corrupt, correct

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why distance 3 and not more?

Two errors can fool the code. If bits i and j flip, the syndrome equals H_i + H_j, which is the column H_k of a third position k. The decoder then "fixes" the wrong bit and ends with three wrong bits instead of two. Hamming (7,4) corrects 1 error but cannot always detect 2 when it is used to correct.

Adding an overall parity bit gives the extended Hamming (8,4) code with d = 4: it corrects 1 error and detects 2.

Compare with the simplest alternative, the repetition code (send each bit three times, take a majority vote). It has rate 1/3, while Hamming (7,4) has rate 4/7, so it sends more information per transmitted bit for the same single-error protection. Let's measure what a noisy channel does to each.

Python Simulation: raw bits vs repetition vs Hamming(7,4)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both codes lower the error rate. Repetition does it more strongly here but sends 12 bits per 4 message bits, while Hamming sends only 7. Real codes aim for the best trade-off between protection and overhead. The exact numbers vary with the random seed.

Real systems use stronger relatives: BCH and Reed-Solomon codes (used on QR codes, CDs and in space communication) are linear codes over larger finite fields like GF(2โธ), built with exactly the irreducible-polynomial construction from the previous chapter.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the minimum distance of a linear code?

    Because the sum of two codewords is a codeword, d(u, v) = weight(u + v), so the smallest distance equals the smallest nonzero weight.
  2. 2. How many errors can a code with minimum distance 5 correct?

    t = floor((d - 1)/2) = floor(4/2) = 2.
  3. 3. How many codewords does the Hamming (7,4) code contain?

    An [n, k] binary code has 2^k codewords; here 2^4 = 16.
  4. 4. If a single bit flips, the syndrome of the Hamming code equals...

    s = H (c + e)^T = H e^T, and e has a single 1, so the product selects one column of H.

Summary

  • A binary linear code is a subspace of ๐”ฝโ‚‚โฟ; an [n, k] code has 2แต codewords.
  • The minimum distance d is the smallest nonzero weight; the code corrects โŒŠ(d - 1)/2โŒ‹ errors.
  • G generates the code, H is its parity-check matrix, and the syndrome H rแต€ reveals the error.
  • The Hamming (7,4) code has d = 3 and corrects any single bit error with rate 4/7.
  • More powerful codes, such as Reed-Solomon, use larger finite fields.

Next: RSA from Scratch