Hamming Code Calculator

A Hamming code adds parity bits in positions chosen so that the failing checks, read as a binary number, spell the position of the bit that went wrong. That is the whole idea, and everything below is the mechanism that makes it true.

A single parity bit can tell you that a byte is damaged; it cannot tell you which bit. A Hamming code spends a few more bits and buys the position. It is the opposite move to Huffman coding, which removes redundancy — a real system compresses first and then adds error correction back, in that order.

Parity bits sit at the powers of two — positions 1, 2, 4, 8, 16 — and the data fills every other position in ascending order. The reason is that position 2ʲ is the only position covered by parity bit j and by no other parity bit, so each parity bit can be solved for on its own without simultaneous equations.

Parity bit j covers every position whose binary expansion has bit jset. Position 1 covers 1, 3, 5, 7…; position 2 covers 2, 3, 6, 7…; position 4 covers 4, 5, 6, 7…. Write each position number in binary and read down its column and you have the coverage grid.

For the data word 1011, the data lands at positions 3, 5, 6 and 7 as d₁=1, d₂=0, d₃=1, d₄=1. Then p1 = d(3) ⊕ d(5) ⊕ d(7) = 1 ⊕ 0 ⊕ 1 = 0; p2 = d(3) ⊕ d(6) ⊕ d(7) = 1 ⊕ 1 ⊕ 1 = 1; p4 = d(5) ⊕ d(6) ⊕ d(7) = 0 ⊕ 1 ⊕ 1 = 0. The codeword is 0110011.

When encoding, a parity bit is computed from the other positions in its coverage set and excludes itself, because its value is what is being solved for. When checking, the same XOR includes the parity bit, so a clean word gives 0. Mixing the two conventions is the commonest way to get a syndrome that is right but inverted.

Recompute every check over the received word, including each parity bit’s own position. Each check gives a bit; assemble them with p1’s check as the least significant. The syndrome, read as a binary number, is the position of the flipped bit.

Flip position 5 of 0110011 and you receive 0110111. The p1 check fails, the p2 check passes, the p4 check fails, so the syndrome is 101₂ = 5 — the position that changed. Flipping bit 5 back recovers the codeword and the data. A syndrome of 0 means no single-bit error was detected. Click any cell of the codeword above to try it.

The Hamming distance d(x,y) between two words of equal length is the number of positions where they differ, which is the weight — the number of ones — of x ⊕ y. For a linear code, whose codewords are closed under XOR, the minimum distance d_min is simply the smallest weight of any non-zero codeword, which makes it computable without comparing every pair.

Everything a block code can promise follows from d_min: it detects up to d_min − 1 errors, and it corrects up to ⌊(d_min − 1)/2⌋.

Four data bits give 16 codewords out of the 128 possible seven-bit words. Their weight enumerator is one word of weight 0, seven of weight 3, seven of weight 4 and one of weight 7, so d_min = 3 and the code corrects one error.

(7,4) is a perfect code: 16 × (1 + 7) = 128 = 2⁷. Every seven-bit word is either a codeword or exactly one bit away from exactly one codeword — the radius-1 balls around the 16 codewords tile the whole space with nothing left over. That is why every non-zero syndrome names a real position and none is spare.

Because the code is linear, flipping positions a and bproduces the syndrome a ⊕ b — which is non-zero, and is itself a valid position. The decoder therefore “corrects” a third, innocent bit and hands back a word that is now three bits from the truth. All 21 two-bit error patterns on 0110011 behave this way; none of them recovers the data.

A (7,4) code cannot tell a double error from a single error — it will “correct” the wrong bit. That is what the extended (8,4) SECDED code fixes.

Adding one more parity bit over the whole codeword raises d_min from 3 to 4 and separates the two cases, because a single error changes the overall parity and a double error does not. The result has four distinct outcomes, and they stay four.

The same code has a matrix form over GF(2), where addition is XOR. The parity-check matrix H has one column per position and its column for position i is simply i written in binary — which is another way of saying that the syndrome is the position. The generator matrix G turns a message into a codeword: c = m·G, and the check is s = H·rᵀ.

Two conventions are in use and both appear above. In the positionalform the columns stay in position order 1…n, which is what makes the syndrome readable as a position. In the systematic form the columns are permuted so that G is [I | P] and H is [Pᵀ | I], which is what linear-algebra courses show. They generate the same code, and in both conventions G · Hᵀ = 0.

The number of parity bits r for k data bits is the smallest rwith 2ʳ ≥ k + r + 1: the syndrome has to be able to name every position plus the “no error” case. When the bound is met with equality the code is perfect — (7,4), (15,11), (31,26) — and 2ᵏ × (1 + n) = 2ⁿ holds exactly. When it is not, the code is shortened: it still works, some syndromes simply never occur.

The rate k/n is the fraction of the transmitted bits that carry your data: 4/7 ≈ 57% for (7,4), 11/15 ≈ 73%, 26/31 ≈ 84%, and 64/72 ≈ 89% for the SECDED code that ECC memory uses. Bigger codes are cheaper per bit because the parity count grows logarithmically while the data count grows linearly.

They are also worse at bursts: one code word can still only survive one error, however long it is, so a burst that hits two adjacent bits defeats a big code just as easily as a small one. Burst detection is a CRC’s job. The information-theoretic framing — redundancy as the price of reliability — is Shannon’s, and the entropy calculator measures it in the same unit.

Hamming was running weekend batch jobs on a relay machine that halted on a single detected error, so a two-day run could be lost to one bad relay and nobody was there to restart it. His 1950 paper introduced the distance metric between codewords and the positional construction on this page, which together turn “something is wrong” into “bit five is wrong”.

• Positions are numbered from 1, left to right, so position 1 is the leftmost character of the codeword string.
• Parity bits sit at every power of two and data bits fill the rest in ascending position order.
• Parity is even throughout.
• A check s_j includes the parity bit’s own position, and the syndrome is S = Σ s_j·2ʲ.
• SECDED prepends an overall parity bit numbered 0, so the SECDED word is indexed from 0 while the inner code stays indexed from 1; both indices are printed above the strip.
• ⊕ is XOR, and matrices are over GF(2), where addition is XOR.

• R. W. Hamming, “Error Detecting and Error Correcting Codes” (opens in a new tab), Bell System Technical Journal 29(2):147–160, April 1950 — the distance metric, the positional construction and the (7,4) code.
• C. E. Shannon, “A Mathematical Theory of Communication” (opens in a new tab), Bell System Technical Journal 27:379–423 and 623–656, 1948 — the rate-and-redundancy framing used in the section above.