Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 46 ยท Information and Channel Coding

Hamming Codes and Block Codes

Learn linear block codes: code rate, Hamming distance, error detection and correction, parity checks, the Hamming (7,4) code and syndrome decoding with runnable code.

The simplest way to protect a message is to add a parity bit: one extra bit chosen so that the total number of 1s is even. If a single bit flips, the count becomes odd and the receiver knows something went wrong. It cannot tell which bit, though, so it can only ask for a repeat.

Richard Hamming, frustrated at Bell Labs in the late 1940s when a weekend batch job crashed on one bad bit, asked a better question: can the machine find and fix the bad bit by itself? The answer is the code that bears his name. It is also the cleanest example of ideas that all block codes share.

Three overlapping circles with data bits d1 to d4 and parity bits p1 to p3, and a table showing which pattern of failing checks points to which bit.
Each circle must contain an even number of 1s. A single error breaks the circles that contain it, and the pattern of broken circles names the culprit.

What you will learn

  • Define an (n, k) linear block code and its rate.
  • Use Hamming distance and dmin to find how many errors a code detects and corrects.
  • Encode and decode with the Hamming (7,4) code, using the syndrome.
  • Explain what happens when two errors occur.
  • Say what a CRC does and how it differs from an error-correcting code.

Key terms

  • (n, k) block code: maps each k-bit message to an n-bit codeword.
  • Hamming weight / distance: the number of 1s in a word / the number of positions in which two words differ.
  • dmin: the smallest distance between two different codewords.
  • Syndrome: the result of the parity checks on a received word; zero means "no detected error".
  • Systematic code: the message bits appear unchanged inside the codeword.

Distance decides everything

A code is a subset of all 2โฟ possible n-bit words; the codewords are chosen to be far apart. If the minimum Hamming distance is dmin, then:

  • the code detects up to dmin โˆ’ 1 errors (no way to turn one codeword into another with fewer flips);
  • it corrects up to t = โŒŠ(dmin โˆ’ 1) / 2โŒ‹ errors (the received word is still closer to the right codeword than to any other).

A single parity bit has dmin = 2: it detects one error and corrects none. A 3x repetition code (two codewords, 000 and 111) has dmin = 3, so it corrects one error, but its rate is only 1/3. The Hamming code does better: it corrects one error with rate 4/7.

The Hamming (7,4) code

Send four data bits d1 d2 d3 d4 followed by three parity bits chosen so that each circle in the figure holds an even number of 1s:

p1 = d1 โŠ• d2 โŠ• d4, p2 = d1 โŠ• d3 โŠ• d4, p3 = d2 โŠ• d3 โŠ• d4.

The data 1011 therefore becomes the codeword 1011010. In matrix form (arithmetic modulo 2) the codeword is c = d ยท G with a generator matrix G = [Iโ‚„ | P], and the receiver computes the syndrome s = H ยท rแต€ with the parity-check matrix

H = [ 1 1 0 1 | 1 0 0 ; 1 0 1 1 | 0 1 0 ; 0 1 1 1 | 0 0 1 ].

The seven columns of H are the seven different non-zero 3-bit patterns. So if exactly one bit is flipped, the syndrome equals the column of that bit. Reading the syndrome therefore tells you which bit to flip back. For example, if d3 is flipped, checks 2 and 3 fail and the syndrome is (0, 1, 1), the column of d3.

Minimum distance: the smallest non-zero codeword weight is 3, so dmin = 3 and t = 1.

The parameters generalize: for any r โ‰ฅ 2 there is a Hamming code with n = 2^r โˆ’ 1 and k = n โˆ’ r, such as (15,11) and (31,26). Rates get better as blocks grow, but the code still corrects only one error per block. Adding an overall parity bit gives the extended Hamming code with dmin = 4, which corrects one error and detects two; computer memory (ECC RAM) uses this arrangement.

Two errors, and the cost of correction

If two bits are flipped, the syndrome is the sum of two columns, which is some other non-zero column, so the decoder "corrects" the wrong bit and produces a wrong message with high confidence. Hamming (7,4) is a perfect code: every one of the 2โท = 128 words is within distance 1 of exactly one codeword (16 codewords ร— 8 words each), so there is no room to flag a double error. This is why an error-correcting decoder must be paired with a channel good enough that double errors are rare.

CRC: detection only

A cyclic redundancy check (CRC) appends a checksum computed by polynomial division over binary arithmetic. It has no correcting power to speak of, but it detects all single-bit errors, all bursts up to its length, and almost all other corruptions. Ethernet, Wi-Fi, USB and storage formats use CRCs to decide whether to accept a frame or ask for a retransmission (ARQ).

Common misconceptions

  • "A code that corrects errors also detects the same number." Correcting t errors uses up distance; with dmin = 3 you can either correct 1 or detect 2, not both at once.
  • "Parity bits are an extra copy of the data." They are combinations of data bits, which gives far more protection per extra bit than copying.
  • "More redundancy is always better." Redundancy costs rate; the useful comparison is correction power for a given rate.
  • "A zero syndrome means no errors." It means no detected error; an error pattern that equals a nonzero codeword goes unnoticed.

Try it

First, implement the encoder and decoder, prove by brute force that every single error is corrected, and see what double errors do.

Python 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.

Second, put the code on a real link. BPSK with hard decisions gives a bit flip probability p = Q(โˆš(2ยทEb/N0)). With a rate-4/7 code, the energy per coded bit is only 4/7 of the energy per information bit, so p rises, but the decoder corrects single errors. Does it pay off? The simulation compares information-bit error rates.

Python Coded versus uncoded BPSK

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.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A code has minimum distance dmin = 5. How many errors can it correct?

    t = โŒŠ(5 โˆ’ 1)/2โŒ‹ = 2 errors can be corrected (and up to 4 detected).
  2. 2. What is the code rate of the Hamming (15,11) code?

    R = k/n = 11/15 โ‰ˆ 0.73.
  3. 3. In Hamming (7,4), the received word has syndrome (1, 1, 1). Which bit is flipped?

    (1,1,1) is the column of d4, which is in all three parity circles.
  4. 4. What happens in Hamming (7,4) when two bits are in error?

    The code is perfect: every word is within distance 1 of some codeword, so a double error looks like a single error elsewhere.
  5. 5. What is a CRC mainly used for?

    A CRC detects errors with a short checksum; ARQ then requests a retransmission.

Summary

  • A block code maps k bits to n bits; its distance dmin sets its power: detect dmin โˆ’ 1, correct โŒŠ(dmin โˆ’ 1)/2โŒ‹.
  • Hamming (7,4) has rate 4/7, dmin = 3 and corrects one error using the syndrome as a pointer.
  • Double errors are miscorrected; perfect codes leave no room to flag them.
  • A CRC only detects, and is paired with retransmission.

Next: Convolutional codes and Viterbi decoding