Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 37 ยท Error-correcting Codes

Repetition Codes and Hamming Codes

Correct bit errors, not just detect them: build repetition and Hamming(7,4) codes in Python, decode with syndromes, and simulate them on a binary symmetric channel.

Detecting damage is useful, but often there is nobody to ask for a retransmission: a deep-space probe, a flash memory chip, a QR code. These systems need forward error correction (FEC): enough redundancy for the receiver to repair the damage on its own.

We start with the obvious idea, repeating bits, and then meet Richard Hamming's much cleverer code, which corrects any single error in a 7-bit block using only 3 check bits. Along the way you simulate both over a binary symmetric channel and see how coding trades rate for reliability, exactly as Shannon's theorem describes.

Repetition codes

Send every bit three times (0 -> 000, 1 -> 111) and decode by majority vote. This corrects one flipped bit per group of three. The rate is k/n = 1/3: you spend three channel bits for each information bit. If the channel flips each bit with probability p, the decoded bit is wrong when two or three of the copies flip: 3pยฒ(1-p) + pยณ.

For p = 0.05 that is about 0.00725, a big improvement over 0.05, but at the price of a third of the speed. To push the error probability toward zero with repetition you must let the rate go to zero. Shannon says that is not necessary, and Hamming codes are the first sign.

Hamming(7,4)

Take four data bits d1 d2 d3 d4 and add three parity bits, each covering a different subset of the data:

TEXT
p1 = d1 + d2 + d4   (mod 2)
p2 = d1 + d3 + d4
p3 = d2 + d3 + d4

The 7-bit codeword is d1 d2 d3 d4 p1 p2 p3. The rate is 4/7. Written as matrices, the generator matrix G is [I | P] and the parity-check matrix H is [P^T | I]; a word c is a codeword exactly when H c = 0 over GF(2).

If one bit flips, the product H r (the syndrome) is not zero and equals the column of H that belongs to the flipped position. All seven columns of H are different and non-zero, so the syndrome pinpoints the error.

Python Encode, corrupt and repair

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.

Every one of the seven single flips is repaired. Notice that the syndrome of each flip is different; that is the design principle.

Two errors defeat it

Hamming(7,4) has minimum distance 3: it can correct 1 error or detect 2, but not both. With two flips, the decoder sees a non-zero syndrome, "repairs" a third bit and delivers wrong data. The next lesson shows how to add one more parity bit to detect double errors too.

Simulation on a noisy channel

Let us compare three schemes over a BSC with p = 0.05: no coding, the repetition code with 3 copies and Hamming(7,4). We measure the bit error rate (BER) after decoding, but we should also compare rate.

Python BER: none, repetition, Hamming

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.

At small p both codes are far better than nothing, but compare rates: repetition spends 3 bits per data bit (rate 0.33), Hamming spends 1.75 (rate 0.57). At p = 0.1, though, Hamming helps much less (0.067 against 0.100 uncoded): with 7 bits per block, two errors in one block are common. A short single-error-correcting code cannot cope with a very noisy channel.

The block error probability

Hamming(7,4) fails when two or more of the seven bits flip. Block error probability is 1 - (1-p)^7 - 7p(1-p)^6. You can check it against the simulation: for p = 0.05 it is about 0.0444 per block of 4 data bits, an improvement over the uncoded block error 1 - 0.95^4 โ‰ˆ 0.185.

Python Compute the exact block error rates

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.

Perfect codes

Hamming(7,4) is a perfect code: the 16 codewords each own a "ball" of radius 1 containing 8 words (the codeword and its 7 neighbours), and 16 ร— 8 = 128 = 2^7, so the balls tile the whole space with no gaps. Every received word is within one flip of exactly one codeword, so a single-error corrector never has to give up. The same construction works with r check bits for lengths n = 2^r - 1: Hamming(15,11), Hamming(31,26) and so on, with ever better rates but still a single-error limit.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the rate of the 3-fold repetition code?

    One information bit is sent as three channel bits, so k/n = 1/3.
  2. 2. What does the syndrome of a received Hamming(7,4) word equal if one bit flipped?

    H applied to codeword + error equals H applied to the error, which is the column of H at the error position.
  3. 3. How many errors can Hamming(7,4) correct in one block?

    Its minimum distance is 3, so it corrects one error. Two errors lead to a wrong correction.
  4. 4. Why is Hamming(7,4) called a perfect code?

    16 codewords times 8 words per ball equals 2^7, so every 7-bit word is within distance 1 of exactly one codeword.

Summary

  • Forward error correction repairs errors without retransmission, at the cost of rate.
  • Repetition codes are simple but have poor rate.
  • Hamming(7,4) adds 3 parity bits to 4 data bits and corrects any single-bit error via the syndrome.
  • Two errors in a block defeat it; its minimum distance is 3.
  • Its balls of radius 1 tile the space exactly, making it a perfect code.

Next: Linear Block Codes and Syndrome Decoding