Error-correcting codes: Hamming, CRC and modern codes
Hamming distance and correcting capability with proof, the Hamming (7,4) code with an example, syndrome, CRC, convolutional codes, Reed-Solomon, turbo, LDPC, polar codes, interleaving.
Shannon proved that data can be sent almost error-free up to the channel capacity, but only by coding it: adding redundancy bits computed so that the receiver can discover and correct errors. Error-correcting codes are in every digital communication and every memory: CDs, QR codes, SSDs, Wi-Fi, 5G, space probes. In this lesson we cover minimum distance, the Hamming code with a complete example, CRC detection codes and modern codes.
Hamming distance
An 
block code turns 
information bits into an 
-bit codeword; the ratio 
is the code rate. The Hamming distance between two words is the number of bits in which they differ; the code’s minimum distance 
is the smallest over all pairs of codewords.
Theorem. A code with minimum distance detects up to 
errors and corrects up to
![\[ t = \left\lfloor\frac{d_{min} - 1}{2}\right\rfloor \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-0d93e67de7a0a9e688773b6812f4b12d_l3.png "Rendered by QuickLaTeX.com")
Proof. If at most errors occur, the received word cannot coincide with another codeword (which is at least away), so the error shows. For correction, the nearest codeword is chosen. If there are at most 
errors, with 
, the transmitted word is at most away from the received one, while every other codeword is at least 
away (triangle inequality). The nearest is therefore the right one. ∎
Geometrically: around each codeword there is a “sphere” of radius , and the spheres do not touch.
The Hamming (7,4) code
Four information bits 
and three parity bits 
, each equal to the exclusive OR of three information bits. The clearest way to see it is three circles:
Each circle must contain an even number of 1s. A single-bit error is located from which circles turn out odd: each bit sits in a different combination of circles.
Example. Data 
. The parities: 
, 
, 
. Seven bits are sent. If the channel flips 
, the receiver recomputes the parities: the green circle (
) and the red one (
) turn out odd, the blue one even. The only bit in green and red but not in blue is : it is flipped back and the data is correct.
In algebraic form, the three checks form the syndrome, a 3-bit number that is zero if there are no errors and otherwise points to which of the 7 bits is wrong. The code has 
: it corrects one error per word, at a rate of 4/7. Adding an overall parity bit (extended code, 
) corrects single errors and detects double ones: it is the SECDED code of server ECC memory.
Detection: the CRC
Often it is enough to notice the error and ask for retransmission. The cyclic redundancy check (CRC) treats the message as a polynomial with binary coefficients, divides it by a fixed generator polynomial and appends the remainder. The receiver repeats the division: a non-zero remainder means an error. A 32-bit CRC (the one in Ethernet, ZIP, PNG) detects all burst errors up to 32 bits and lets a random error through with probability about 
. It is computed with a shift register and a few XOR gates, or with a table in software.
Modern codes
- Convolutional codes with Viterbi decoding: they encode the continuous stream with a small shift register; used for decades in mobile telephony and satellites.
- Reed-Solomon: they work on multi-bit symbols and are very strong against burst errors. They are in CDs and DVDs (where they correct millimetre-sized scratches), in QR codes (which stay readable even when partly covered) and in transmissions from space probes.
- Turbo codes and LDPC: with iterative decoding, exchanging probabilities instead of hard decisions, they come within a few tenths of a decibel of the Shannon limit. LDPC codes are in Wi-Fi, 5G, satellite television and SSDs; polar codes, the first provably capacity-achieving codes, in 5G control channels.
Interleaving. Codes correct scattered errors well and concentrated ones poorly, and fading channels produce exactly bursts of errors. Before transmission the order of the bits is shuffled (interleaving), and the receiver restores it: a burst on the channel becomes a series of isolated errors, which the code corrects.
How much is gained. With a good rate-1/2 code, an error probability of 10⁻⁵ is reached with about 1 to 2 dB of 
instead of the 9.6 dB of uncoded BPSK: a coding gain of 7 to 8 dB, worth as much as multiplying the transmitted power by five, at the cost of bandwidth and of the computation for decoding.
