Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 79 ยท Data Link Layer

Error Correction and Hamming Codes

Learn forward error correction, how Hamming(7,4) finds and fixes a flipped bit with a syndrome, and how interleaving defeats burst errors, with live Python.

Error detection tells a receiver that a frame is damaged. What happens next is a design choice. The receiver can ask for the frame again, which is retransmission, or it can repair the frame itself using extra bits the sender included, which is forward error correction (FEC). The word "forward" means the fix flows in the same direction as the data, with no return trip.

Which one is better depends on the link. On a fiber inside a data center, errors are rare and a retransmission takes microseconds, so detection plus retransmission is cheap. On a satellite link with a 500 ms round trip, or in a live video stream where a late packet is useless, waiting for a resend is too slow, and spending a few percent of bandwidth on correction wins. In this lesson you build the classic Hamming(7,4) code, see exactly why it works, and then learn how interleaving lets such a small code survive bursts.

Detection versus correction

Recall Hamming distance: the number of positions where two bit strings differ. If every pair of valid codewords is at least distance d apart, the code detects d - 1 errors and corrects โŒŠ(d - 1) / 2โŒ‹ of them. To correct one error you need d = 3. A damaged word that is one flip away from the right codeword is then still at least two flips from any other, so the nearest codeword is unambiguous.

Minimum distance Detects Corrects
2 1 error 0
3 2 errors 1 error
4 3 errors 1 error (and detects 2)
5 4 errors 2 errors

Redundancy costs bandwidth. The code rate is data bits divided by total bits. Hamming(7,4) sends 4 data bits in 7, a rate of 4/7, about 57%. That is a heavy price, but it is the smallest code that fixes any single-bit error in a block of four.

How Hamming(7,4) works

Richard Hamming designed this code in the late 1940s to make a computer fix its own punched-card read errors. The trick is to number the seven bit positions 1 to 7 and place the parity bits at the power-of-two positions (1, 2 and 4). The data bits fill positions 3, 5, 6 and 7.

Each parity bit covers the positions whose binary number contains its own bit:

Parity bit Position in binary Covers positions
p1 001 1, 3, 5, 7
p2 010 2, 3, 6, 7
p4 100 4, 5, 6, 7

Each parity bit is set so that its group has an even number of ones. For data bits d1 d2 d3 d4 at positions 3, 5, 6, 7:

  • p1 = d1 โŠ• d2 โŠ• d4
  • p2 = d1 โŠ• d3 โŠ• d4
  • p4 = d2 โŠ• d3 โŠ• d4

At the receiver, recompute the three checks. Each check gives 0 if its group still has even parity and 1 if not. Read the three results as a binary number (p4 p2 p1). That number is the syndrome, and it is the position of the flipped bit. A syndrome of 0 means no error. If position 5 was flipped, groups p1 (which includes 5) and p4 (which includes 5) fail while p2 passes, giving binary 101 = 5. The receiver flips bit 5 back.

flowchart LR
    A["4 data bits"] --> B["Add 3 parity bits<br/>(positions 1, 2, 4)"]
    B --> C["7-bit codeword<br/>sent over a noisy link"]
    C --> D["Recompute 3 checks"]
    D --> E["Syndrome = position<br/>of the bad bit"]
    E --> F["Flip it back,<br/>read the data"]

The syndrome is not just an alarm. Its value points straight at the damaged bit.

Python A Hamming(7,4) encoder and decoder

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.

The output shows all seven single-bit errors being repaired, and the syndrome always equals the position that was flipped. With two flips the code is fooled: it computes a syndrome that points to a third, innocent bit and "repairs" the wrong place, so the data comes out wrong without any warning. The last line confirms the minimum distance of 3, which is exactly why one error is correctable and two are not.

Adding one more overall parity bit gives Hamming(8,4), also called SECDED (single error correction, double error detection). It has distance 4, so it fixes one error and at least notices two. Server memory (ECC RAM) uses the same idea on 64-bit words with 8 extra bits.

The general Hamming bound

For m parity bits, a Hamming code has block length 2m - 1 and carries 2m - 1 - m data bits. With m = 3 you get (7,4); m = 4 gives (15,11); m = 5 gives (31,26). Longer blocks waste less: the rate climbs from 57% to 73% to 84%. The catch is that a longer block has a higher chance of containing two errors, and one parity scheme still corrects only one error per block. That is the central trade-off of FEC: more efficiency against less protection per block.

Burst errors and interleaving

Real channels rarely flip isolated bits. A lightning strike, a scratch on a disc, or a deep fade on a radio link wipes out several adjacent bits at once. A single-error code is useless against that: two bad bits in one codeword defeat it.

Interleaving reorders the bits before sending so that adjacent bits on the wire come from different codewords. Picture the codewords as rows of a table. Instead of sending row by row, the sender sends column by column. The receiver rebuilds the rows. A burst on the wire then lands in one column and damages only one bit per row, which Hamming can repair easily. With n rows, a burst of up to n consecutive bits is survivable.

The price is delay: the sender must collect all n rows before sending a single column, and the receiver must wait for all columns before decoding. Interleaving suits one-way streams like music discs and broadcast, and less so interactive traffic.

flowchart TB
    subgraph T["4 codewords as rows"]
        R1["row 1: c1 c1 c1 c1 c1 c1 c1"]
        R2["row 2: c2 c2 c2 c2 c2 c2 c2"]
        R3["row 3: c3 c3 c3 c3 c3 c3 c3"]
        R4["row 4: c4 c4 c4 c4 c4 c4 c4"]
    end
    T --> W["Send column by column:<br/>c1 c2 c3 c4 c1 c2 c3 c4 ..."]
    W --> X["A burst of 4 hits each<br/>codeword once"]

Reading the table by columns spreads a burst across all codewords.

Python Interleaving defeats a burst

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.

Without interleaving, a burst of even two bits inside one codeword breaks the message. With seven codewords interleaved, bursts up to seven bits long are corrected, and the eighth bit finally puts two errors into one row. The depth of the interleaver sets the burst length it can absorb.

Stronger codes in practice

Hamming codes are the teaching case. Real systems use stronger relatives:

  • Reed-Solomon codes work on whole symbols (bytes) rather than bits, so a burst of bad bits damages only a few symbols. They protect CDs, DVDs, QR codes, DSL and some satellite links.
  • Convolutional codes and Viterbi decoding protected early cellular and Wi-Fi radio links.
  • LDPC and turbo codes get close to the Shannon limit from Signals, Bandwidth and Transmission Media and are used by Wi-Fi 6, 5G, DVB-S2 and 10GBASE-T.
  • Erasure codes spread a file over many packets so that any large-enough subset rebuilds it; they appear in streaming and distributed storage.

The Internet mostly picks the other path. Ethernet uses CRC detection and drops bad frames, and TCP retransmits. FEC lives where the physical channel is noisy: wireless, optical and storage. Even then the usual design combines both: FEC to fix most errors cheaply and ARQ, covered in Flow Control and ARQ, to catch what is left.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What minimum Hamming distance does a code need to correct any single-bit error?

    With distance 3, a word with one flipped bit is one step from the true codeword and at least two steps from every other, so the nearest codeword is unique.
  2. 2. In Hamming(7,4), the receiver computes a syndrome of 6 (binary 110). What does it do?

    The syndrome equals the position of the bad bit. Position 6 is one of the data bits, and flipping it restores the codeword.
  3. 3. Why does interleaving help against burst errors?

    Sending column by column puts consecutive wire bits into different rows. A burst then damages only one bit per codeword, which a single-error-correcting code can fix.
  4. 4. What is the main cost of interleaving?

    Interleaving does not add bits; it reorders them. The sender and receiver must buffer a full block, which adds latency.

Summary

  • FEC lets the receiver repair errors without asking for a resend; it suits long-delay, noisy or one-way links.
  • Distance d detects d - 1 errors and corrects โŒŠ(d - 1) / 2โŒ‹; Hamming(7,4) has distance 3 and a code rate of 4/7.
  • Parity bits sit at positions 1, 2 and 4; the syndrome is the position of the single flipped bit.
  • Two errors in one Hamming block are miscorrected; an extra overall parity bit (SECDED) at least detects them.
  • Interleaving turns a burst into scattered single errors at the cost of delay; Reed-Solomon, LDPC and turbo codes are the real-world workhorses.

Next: Flow Control and ARQ