Hamming Code Error Correction Explained (with Math)

Encode Hamming(7,4), compute a syndrome, correct every single-bit position, extend it to SECDED, and verify the decoder without overstating its limits.

Denny

May 7, 20267 min read

Chalkboard feature illustration for “Hamming Code Error Correction Explained (with Math)”

TL;DR: Hamming(7,4) maps four data bits into seven positions. Three parity checks give each position a unique nonzero three-bit column, so a single flipped bit produces a syndrome equal to that position’s binary index. The decoder can then invert it. Plain Hamming(7,4) cannot distinguish a double-bit error from some single-bit error; an overall parity bit extends it to SECDED under the assumed error limit.

A parity bit can report that an odd number of positions changed, but one check cannot identify which position. Hamming’s construction uses several overlapping parity checks. The pattern of failed checks—the syndrome—acts as an address.

That idea is powerful because the encoder, checker, and corrector can all be built from XOR networks and decoding logic. It also has a strict boundary: the familiar correction rule assumes at most one error in the protected block unless an extended code adds another check.

Positioning the Bits

Number codeword positions from 1. Powers of two hold parity:

Position	1	2	3	4	5	6	7
Role	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
Binary index	001	010	011	100	101	110	111

Each parity check corresponds to one bit of the binary position:

$P_1$ covers positions whose index has bit 0 set: 1, 3, 5, 7.
$P_2$ covers positions whose index has bit 1 set: 2, 3, 6, 7.
$P_4$ covers positions whose index has bit 2 set: 4, 5, 6, 7.

Every position has a unique nonzero membership pattern. Position 5, for example, belongs to checks 1 and 4 because $5=101_2$ .

This one-based convention is convenient, not mystical: the parity-check matrix columns are simply the binary labels 1 through 7.

Encoding with Even Parity

Choose each parity bit so the XOR of its complete coverage set is zero:

P_1=D_1\oplus D_2\oplus D_4

P_2=D_1\oplus D_3\oplus D_4

P_4=D_2\oplus D_3\oplus D_4

These equations make the code systematic: the original data appears unchanged in positions 3, 5, 6, and 7, while parity occupies the remaining positions.

Odd parity could be used with consistent changes to the expected check values. Even parity keeps the linear-algebra form especially direct because every valid codeword has a zero syndrome.

Worked Encoding: Data 1011

Assign:

D_1=1,\quad D_2=0,\quad D_3=1,\quad D_4=1

Then:

P_1=1\oplus0\oplus1=0

P_2=1\oplus1\oplus1=1

P_4=0\oplus1\oplus1=0

Place those values into the seven positions:

Position	1	2	3	4	5	6	7
Role	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
Bit	0	1	1	0	0	1	1

Reading position 1 through position 7, the codeword is:

Some texts print codewords in the opposite visual direction. The arithmetic remains correct if the position convention is explicit and used consistently.

Computing the Syndrome

Let the received positions be $R_1$ through $R_7$ . Recompute the complete parity checks:

S_1=R_1\oplus R_3\oplus R_5\oplus R_7

S_2=R_2\oplus R_3\oplus R_6\oplus R_7

S_4=R_4\oplus R_5\oplus R_6\oplus R_7

Interpret the syndrome as:

S=(S_4S_2S_1)_2

For an unchanged valid codeword, $S=000$ . If exactly one position $i$ flips, each check that covers $i$ toggles. The resulting syndrome is the binary column assigned to position $i$ .

Correcting a flip at position 5

Flip position 5 in the encoded example:

sent:     0 1 1 0 0 1 1
received: 0 1 1 0 1 1 1
position: 1 2 3 4 5 6 7

Now:

S_1=0\oplus1\oplus1\oplus1=1

S_2=1\oplus1\oplus1\oplus1=0

S_4=0\oplus1\oplus1\oplus1=1

Therefore:

S_4S_2S_1=101_2=5

Under the one-error assumption, invert received position 5. The corrected word returns to 0110011, and positions 3, 5, 6, and 7 yield data 1011.

A flip in a parity position works the same way. If position 2 changes, the syndrome is 010, and the corrector inverts position 2.

Matrix View

Using codeword vector

\mathbf r=[R_1\ R_2\ R_3\ R_4\ R_5\ R_6\ R_7]^T

one parity-check matrix is:

H= \begin{bmatrix} 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}

The syndrome is:

\mathbf s=H\mathbf r\pmod 2

Column $i$ of H is the binary representation of $i$ , ordered as $(S_1,S_2,S_4)^T$ . A single-bit error vector with its 1 in position $i$ therefore returns exactly column $i$ .

This formulation scales more cleanly than memorizing overlapping circles. It also makes linearity explicit: XORing two valid codewords produces another valid codeword.

Why Plain Hamming Cannot Safely Correct Two Errors

Hamming(7,4) has minimum Hamming distance:

d_{\min}=3

A code with minimum distance $d_{\min}$ can:

detect up to $d_{\min}-1$ arbitrary errors if it is only deciding valid versus invalid; or
correct up to $\left\lfloor(d_{\min}-1)/2\right\rfloor$ errors by choosing the nearest codeword.

Thus Hamming(7,4) can correct one error. It can also detect a two-bit corruption as “not a codeword” if no correction is attempted. But its nonzero three-bit syndrome cannot say whether it came from one error or a particular pair of errors.

If a standard single-error decoder sees a double-bit error, the XOR of the two error-position columns equals a third nonzero column. The decoder will invert that third position and create a three-bit difference from the transmitted codeword. This is a miscorrection, not double-error correction.

Always state the decoder’s assumed error model. “Syndrome nonzero, so flip that position” is valid only when the system has established that at most one protected position is wrong.

Extended Hamming and SECDED

Add one overall parity bit $P_0$ across the seven-bit Hamming word. The eight-bit extended code has $d_{\min}=4$ and supports single-error correction, double-error detection (SECDED), assuming no more than two errors in a codeword.

Compute:

the original three-bit syndrome S from positions 1–7;
an overall parity check P across all eight received positions.

For even overall parity:

Syndrome S	Overall check P	Interpretation under 0–2 errors	Action
000	0	no error	accept
nonzero	1	one error in positions 1–7	correct position S
000	1	overall parity position error	correct or report parity-bit error
nonzero	0	two errors	report uncorrectable; do not single-correct

The qualification matters. Three or more errors can imitate another table row. SECDED is not an unlimited error detector.

Real memory and communication systems may use shortened Hamming codes, interleaving, symbol-oriented codes, BCH or Reed–Solomon codes, low-density parity-check codes, product codes, or proprietary schemes. Do not infer a system’s ECC capability solely from its visible data and check-bit widths.

General Hamming-Code Sizing

For $m$ data bits and $r$ Hamming parity bits, there must be enough syndrome patterns for every codeword position plus the no-error case:

2^r\ge m+r+1

The full-length binary Hamming family uses:

n=2^r-1

k=n-r=2^r-r-1

Parity bits r	Code length n	Data bits k	Full code
3	7	4	Hamming(7,4)
4	15	11	Hamming(15,11)
5	31	26	Hamming(31,26)
6	63	57	Hamming(63,57)

Shortened variants omit selected data positions while preserving the check structure. Extended variants add the overall parity bit and increase distance from 3 to 4.

Overhead should name its denominator. Hamming(7,4) adds 3 check bits per 4 data bits—75% overhead relative to payload, or 3/7 of the transmitted word. Hamming(63,57) adds 6/57, about 10.5% relative to payload, and check bits occupy 6/63, about 9.5% of the codeword.

Hardware Architecture

A straightforward systematic implementation has four stages:

data ─▶ parity generator ─▶ codeword
                              │
received word ─▶ check matrix ─▶ syndrome
                                      │
                       syndrome decoder ─▶ one-hot flip mask
received word ─────────────────────────── XOR ─▶ corrected word ─▶ extract data

For Hamming(7,4):

the encoder calculates three parity equations;
the checker calculates three syndrome equations;
a 3-to-8 decoder can form a one-hot position mask, with output 0 meaning no correction;
seven XOR gates apply that mask;
wiring extracts positions 3, 5, 6, and 7.

Exact gate count and timing depend on XOR-tree factoring, shared terms, cell libraries, or FPGA mapping. A wide decoder may pipeline syndrome calculation and correction. If a flags or status register reports “corrected” and “uncorrectable,” align those signals with the corresponding data pipeline stage.

Verification Plan

For the seven-bit code:

Encode all 16 possible data inputs.
Confirm every encoded word has syndrome zero.
For each codeword, flip each of the seven positions individually.
Confirm the syndrome equals the flipped position.
Apply correction and confirm all 16×7 cases recover the original data.
Inject representative two-bit errors and demonstrate why a plain single-error decoder miscorrects.

For the extended eight-bit version:

Repeat every single-position test, including the overall parity position.
Test all $\binom82=28$ two-position patterns for each data word.
Confirm every pair is reported uncorrectable and none is single-corrected.
Add assertions that correction is enabled only for S != 0 and overall parity mismatch.

Functional simulation proves the implemented truth table for tested or exhaustively enumerated bit patterns. It does not provide a physical soft-error rate, establish independence of faults, or replace system-level reliability analysis.

Common Design Mistakes

Numbering positions from zero while still interpreting the syndrome as a one-based address.
Printing the word in reverse order without documenting the convention.
Mixing even-parity encoding with odd-parity checking.
Correcting every nonzero syndrome without bounding the error count.
Treating SECDED as detection of every error with weight three or greater.
Forgetting that check bits and the overall parity bit can fail.
Comparing “overhead percentages” that use different denominators.
Assuming all products labeled ECC implement the same code.

Hamming(7,4) is valuable because the full mechanism is visible: unique parity-check columns turn a one-bit fault into an address. Once that is clear, plain parity looks like a one-row check matrix, while stronger block codes become larger versions of the same central idea—structured redundancy matched to an explicit fault model.

Reference

R. W. Hamming, “Error Detecting and Error Correcting Codes,” Bell System Technical Journal, 1950