Hamming code — single-error-correcting block codes

Basic structure and operation

A Hamming code encodes a block of message bits together with r parity bits into a codeword of length n = 2^r - 1, leaving k = n - r message bits. Each parity bit covers a selected subset of positions in the codeword; common construction places parity bits at positions that are powers of two (1, 2, 4, 8, ...). When a codeword is received, the receiver recomputes the parity checks and collects their results into a binary vector called the syndrome. For a single-bit error the syndrome equals the binary index of the erroneous position, so the receiver can flip that bit to correct the error.

Typical example

The well-known (7,4) Hamming code uses r = 3 parity bits and encodes k = 4 data bits into 7-bit codewords. Parity bits occupy positions 1, 2 and 4; the remaining positions hold data bits. If a single bit is corrupted in transmission, the three parity checks produce a 3-bit syndrome that points to the corrupted bit's index (1–7). This allows automatic single-bit correction without retransmission. The shortest nontrivial Hamming code is (3,1); more generally codes exist for any r >= 2 with length 2^r - 1.

Construction rules and decoding

Construction rules commonly taught are: place parity bits at power-of-two indices; each parity bit examines positions whose binary index has a 1 in the parity bit's place; set each parity bit so that the parity (even or odd) of its covered bits meets the chosen convention. Decoding recomputes these parities and interprets the syndrome. Variants include adding an overall parity bit to create SECDED (single-error-correcting, double-error-detecting) codes, which detect but do not correct two-bit errors.

History and context

Hamming codes were developed by Richard Hamming in the early 1950s while working with electromechanical computers that used relays and punched cards. He sought an automated way to correct the frequent single-bit errors that arose in those systems instead of relying on human operators to spot and repair errors. The resulting algebraic construction became a foundational idea in coding theory and inspired many later codes.

Applications, variants and notable facts

Hamming codes are used in memory error-correcting systems (ECC RAM), low-latency communications, and forms of digital signal processing and telecommunications where modest overhead and single-bit correction suffice. They work by introducing controlled redundancy so a receiver can detect and correct errors without retransmission. Though modern systems sometimes use more powerful codes (e.g., Reed–Solomon or LDPC) for higher error rates, Hamming codes remain a compact, efficient solution when only single-bit errors are expected.

Key properties

• Perfect single-error-correcting: Hamming codes meet the theoretical bound for correcting one error per block.
• Systematic form: message bits can appear unchanged in the codeword, simplifying implementation.
• Extendable: adding an overall parity bit yields double-error detection at small extra cost.