Paper
Part IILinear Block Codes

Hamming Codes and Perfect Codes

November 15, 202653 min readbeginner

Hamming codes correct one error with the fewest check bits any code can use. The chapter builds them from every nonzero column, proves distance three, reads the error's position off the syndrome and proves them perfect.

Syndrome Decoding and the Standard Array decoded any linear code by looking up its syndrome in a table of coset leaders, and Linear Codes met the (7,4) Hamming code through its Venn diagram. Neither chapter asked the design question behind that code. A memory word holds kk data bits and must survive any single flipped bit. How few check bits can do the job, and which parity-check matrix uses them best?

The answer comes in two steps, a count and a construction. Every single error has to leave its own nonzero syndrome, so mm check bits can protect at most 2m−12^m - 1 positions. Taking every nonzero column of mm bits as the parity-check matrix reaches this limit exactly, and the result is the Hamming code of length 2m−12^m - 1, published by Richard Hamming in 1950 [1]. With its columns in counting order, the syndrome of a single error is the error's position written in binary. The same count made over balls of words gives the sphere-packing bound, which the Hamming codes meet with equality. Codes that do so are called perfect, and they are very rare.

Every number in the chapter is recomputed by ch19_hamming_codes_and_perfect_codes.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch19_charts.py in the same folder. The GNU Octave twin ch19_hamming_codes_and_perfect_codes.m prints the same lines, as The Octave Route explains.

01.How Many Check Bits Does One Error Need

Start with four data bits and three check bits, seven bits in all. A syndrome decoder sees only the three check results, which form 23=82^3 = 8 patterns, and it must tell apart eight situations, no error and a single error in each of the seven positions. The fit is exact. With eight data bits and the same three checks, the word has 11 positions and the decoder faces 11+1=1211 + 1 = 12 situations with only 8 patterns, so two situations must share a pattern. Eight data bits need at least four check bits.

The general statement is about the columns of the parity-check matrix. A received word is a codeword cc plus an error pattern ee, and its syndrome H(c+e)T=HeTH (c + e)^{\mathsf T} = H e^{\mathsf T} depends only on the error. A single error in position ii is the pattern eie_i with one 1, and its syndrome is HeiT=hiH e_i^{\mathsf T} = h_i, the column ii of HH.

Proof. Such a decoder must also return a codeword unchanged when no error occurs. Suppose some column is zero, hi=0h_i = 0. Then HeiT=0H e_i^{\mathsf T} = 0, so eie_i is a codeword. The received word eie_i is then both the codeword 00 hit in position ii, which must decode to 00, and the codeword eie_i received cleanly, which must stay eie_i. Suppose next that hi=hjh_i = h_j with i≠ji \ne j. Over GF(2)\mathrm{GF}(2) every element is its own negative, so H(ei+ej)T=hi+hj=0H (e_i + e_j)^{\mathsf T} = h_i + h_j = 0 and ei+eje_i + e_j is a codeword. The received word eie_i is then both 00 hit in position ii and ei+eje_i + e_j hit in position jj, two single errors that demand different outputs. So the columns are nonzero and distinct. A column has mm bits, which allows 2m2^m patterns, one of them zero, so n≤2m−1n \le 2^m - 1, which is k+m+1≤2mk + m + 1 \le 2^m. ■\blacksquare

Table 1 applies the theorem to ten message sizes. The overhead falls quickly, because each extra check bit doubles the number of syndromes while adding one to the length, so four data bits need three check bits and 120 need only seven.

Table 1. The least number of check bits m that lets a binary linear code correct one error in k data bits, and the resulting length n

Data bits kkCheck bits mmLength n=k+mn = k + mTest k+m+1≤2mk + m + 1 \le 2^m
1234≤44 \le 4
4378≤88 \le 8
841213≤1613 \le 16
1141516≤1616 \le 16
1652122≤3222 \le 32
2653132≤3232 \le 32
3263839≤6439 \le 64
5766364≤6464 \le 64
6477172≤12872 \le 128
1207127128≤128128 \le 128

Source: reproduced by ch19_hamming_codes_and_perfect_codes.py.

In the rows that meet the test with equality every nonzero column of mm bits must be used, and only their order is free. The other rows, such as 64 data bits in 71 positions, come from deleting columns of the next larger case, as the first worked example does for one byte.

02.The Binary Hamming Code

For three check bits the seven nonzero columns are the binary numbers 1 to 7. Writing them side by side in counting order, with the most significant bit in the top row, gives

H3=[000111101100111010101].H_3 = \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix}.
(2)

Read any column from top to bottom and it spells its own position. Column 6 reads 110110, which is 4+2=64 + 2 = 6. The top row has its 1s in positions 4 to 7, the numbers with a 1 in the 4s place, so it checks the 4s bit of the position, and the rows below check the 2s and 1s bits.

Any other order of the same columns gives an equivalent code in the sense of Linear Codes, such as the systematic form that chapter used for the (7,4) code. Counting order is the one that makes the decoder simple.

The columns at positions 1, 2 and 4 are 001001, 010010 and 100100, each with a single 1, so each row's parity equation contains exactly one of these positions and can be solved for that bit. The three rows of H3H_3 say c4⊕c5⊕c6⊕c7=0c_4 \oplus c_5 \oplus c_6 \oplus c_7 = 0, c2⊕c3⊕c6⊕c7=0c_2 \oplus c_3 \oplus c_6 \oplus c_7 = 0 and c1⊕c3⊕c5⊕c7=0c_1 \oplus c_3 \oplus c_5 \oplus c_7 = 0, and solving them gives the encoding rule

c1=c3⊕c5⊕c7,c2=c3⊕c6⊕c7,c4=c5⊕c6⊕c7.c_1 = c_3 \oplus c_5 \oplus c_7, \qquad c_2 = c_3 \oplus c_6 \oplus c_7, \qquad c_4 = c_5 \oplus c_6 \oplus c_7.
(3)

The positions 1, 2 and 4 hold check bits, and the message goes into the other four positions, 3, 5, 6 and 7, in that order. Take the message 10111011. It sets c3=1c_3 = 1, c5=0c_5 = 0, c6=1c_6 = 1 and c7=1c_7 = 1. Then c1=1⊕0⊕1=0c_1 = 1 \oplus 0 \oplus 1 = 0, c2=1⊕1⊕1=1c_2 = 1 \oplus 1 \oplus 1 = 1 and c4=0⊕1⊕1=0c_4 = 0 \oplus 1 \oplus 1 = 0, and the codeword c1c2⋯c7c_1 c_2 \cdots c_7 is 01100110110011. The message bits appear in it unchanged, so the code is systematic, with the check bits interleaved among the data.

For every mm the check positions are the powers of two 1,2,4,…,2m−11, 2, 4, \dots, 2^{m-1}, the numbers with a single 1 in binary. Check bit c2ic_{2^i} is the XOR of the data bits whose position number has a 1 in the 2i2^i place, and the data fill the remaining positions in increasing order.

Proof. The length is the number of nonzero columns of mm bits, which is 2m−12^m - 1. The columns in positions 1,2,4,…,2m−11, 2, 4, \dots, 2^{m-1} are the mm unit columns, which are linearly independent, so HmH_m has rank mm, the most its mm rows allow. The rank theorem of Matrices and Elimination over Finite Fields says that the rank and the dimension of the null space add up to the number of columns, so the code has dimension n−m=2m−1−mn - m = 2^m - 1 - m.

For the distance, Linear Codes proved that the minimum distance of a linear code equals the least weight of a nonzero codeword. For any word cc the product HmcTH_m c^{\mathsf T} is the sum of the columns in the positions where cc has a 1. A codeword of weight 1 would need a zero column, and one of weight 2 would need hi+hj=0h_i + h_j = 0, that is hi=hjh_i = h_j, and neither happens. So every nonzero codeword has weight at least 3. The columns in positions 1, 2 and 3 are the binary numbers 1, 2 and 3, and 1+2=31 + 2 = 3 in binary has no carries, so h1+h2+h3=0h_1 + h_2 + h_3 = 0. The word with 1s in positions 1, 2 and 3 is therefore a codeword of weight 3, and d=3d = 3. ■\blacksquare

For m=3m = 3 that codeword is 11100001110000. The same reasoning counts every codeword of weight 3. Adding columns hih_i and hjh_j with i≠ji \ne j gives the binary form of the bitwise XOR i⊕ji \oplus j, which is nonzero and differs from both, so each pair of positions lies in exactly one weight-3 codeword, the one with 1s at ii, jj and i⊕ji \oplus j. Each such codeword contains three pairs, so there are (n2)/3\binom{n}{2} / 3 of them. For n=7n = 7 that is 21/3=721 / 3 = 7, and a search of the 16 codewords finds the same seven.

03.Decoding by Reading the Syndrome

The decoder of a Hamming code needs no table. The syndrome of a single error is a column of HmH_m, and in counting order a column is its own position number.

Proof. Matrix multiplication distributes over addition, so Hm(c+ej)T=HmcT+HmejTH_m (c + e_j)^{\mathsf T} = H_m c^{\mathsf T} + H_m e_j^{\mathsf T}. The first term is 00 because cc is a codeword. The second is the sum of the columns where eje_j has a 1, which is the single column hjh_j. By the definition of counting order, hjh_j is jj in binary. ■\blacksquare

The decoder follows directly. Compute the syndrome s=HmrTs = H_m r^{\mathsf T}. If s=0s = 0, accept the word as it stands. Otherwise read ss as a binary number and flip the bit in that position. Take the codeword 01100110110011 from the previous section and flip position 6, which gives the received word 01100010110001. The three checks are

s4=r4⊕r5⊕r6⊕r7=0⊕0⊕0⊕1=1,s2=r2⊕r3⊕r6⊕r7=1⊕1⊕0⊕1=1,s1=r1⊕r3⊕r5⊕r7=0⊕1⊕0⊕1=0.\begin{aligned} s_4 &= r_4 \oplus r_5 \oplus r_6 \oplus r_7 = 0 \oplus 0 \oplus 0 \oplus 1 = 1, \\ s_2 &= r_2 \oplus r_3 \oplus r_6 \oplus r_7 = 1 \oplus 1 \oplus 0 \oplus 1 = 1, \\ s_1 &= r_1 \oplus r_3 \oplus r_5 \oplus r_7 = 0 \oplus 1 \oplus 0 \oplus 1 = 0. \end{aligned}
(6)

The syndrome s4s2s1=110s_4 s_2 s_1 = 110 is the number 6, so the decoder flips r6r_6 back to 1 and recovers 01100110110011. Reading positions 3, 5, 6 and 7 returns the message 10111011. The script repeats this for every one of the 16 codewords and each of its 7 single errors, and all 112 cases decode correctly.

In the language of Syndrome Decoding and the Standard Array, the (7,4) code has 27−4=82^{7-4} = 8 cosets, whose leaders are the zero word and the seven words of weight 1. Each of the eight syndromes is claimed by exactly one correctable error, with none left over, which is the exact fit that later sections call perfect.

04.The (15,11) Code by Hand

Four check bits give fifteen nonzero columns, and Figure 1 lays them out. The check positions are 1, 2, 4 and 8, and the eleven data positions are 3, 5, 6, 7, 9, 10, 11, 12, 13, 14 and 15. Each row of H4H_4 has eight 1s, since half of the numbers from 0 to 15 have a 1 in any given binary place. One of the eight is the row's own check position, so each check bit is the XOR of seven data bits.

The parity-check matrix of the (15,11) Hamming code, column j holding j in binary position 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 8s bit 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 4s bit 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 2s bit 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1s bit 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 bit c1 c2 d1 c4 d2 d3 d4 c8 d5 d6 d7 d8 d9 d10 d11 check position: one 1 in its column, a power of two data position: two or more 1s in its column
Figure 1. The parity-check matrix of the (15,11) Hamming code in counting order. Column j is the number j in binary, and the four columns with a single 1, at positions 1, 2, 4 and 8, are the check positions. Data: computed by ch19_charts.py in the companion repository.

Take the eleven-bit message 1011001101010110011010. Placed in the data positions in increasing order, it sets c3=1c_3 = 1, c5=0c_5 = 0, c6=1c_6 = 1, c7=1c_7 = 1, c9=0c_9 = 0, c10=0c_{10} = 0, c11=1c_{11} = 1, c12=1c_{12} = 1, c13=0c_{13} = 0, c14=1c_{14} = 1 and c15=0c_{15} = 0. The four check bits come from the four rows of H4H_4.

c1=c3⊕c5⊕c7⊕c9⊕c11⊕c13⊕c15=1⊕0⊕1⊕0⊕1⊕0⊕0=1,c2=c3⊕c6⊕c7⊕c10⊕c11⊕c14⊕c15=1⊕1⊕1⊕0⊕1⊕1⊕0=1,c4=c5⊕c6⊕c7⊕c12⊕c13⊕c14⊕c15=0⊕1⊕1⊕1⊕0⊕1⊕0=0,c8=c9⊕c10⊕c11⊕c12⊕c13⊕c14⊕c15=0⊕0⊕1⊕1⊕0⊕1⊕0=1.\begin{aligned} c_1 &= c_3 \oplus c_5 \oplus c_7 \oplus c_9 \oplus c_{11} \oplus c_{13} \oplus c_{15} = 1 \oplus 0 \oplus 1 \oplus 0 \oplus 1 \oplus 0 \oplus 0 = 1, \\ c_2 &= c_3 \oplus c_6 \oplus c_7 \oplus c_{10} \oplus c_{11} \oplus c_{14} \oplus c_{15} = 1 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 1 \oplus 0 = 1, \\ c_4 &= c_5 \oplus c_6 \oplus c_7 \oplus c_{12} \oplus c_{13} \oplus c_{14} \oplus c_{15} = 0 \oplus 1 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 0 = 0, \\ c_8 &= c_9 \oplus c_{10} \oplus c_{11} \oplus c_{12} \oplus c_{13} \oplus c_{14} \oplus c_{15} = 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 0 = 1. \end{aligned}
(7)

The check bits c1c2c4c8c_1 c_2 c_4 c_8 are 11011101, and the full codeword c1c2⋯c15c_1 c_2 \cdots c_{15} is 111001110011010111001110011010, which has weight 9. Now suppose the channel flips position 11, so that the received word is 111001110001010111001110001010. Each syndrome bit is the XOR of the received bits in the eight positions its row covers, check position included.

s8=r8⊕r9⊕r10⊕r11⊕r12⊕r13⊕r14⊕r15=1⊕0⊕0⊕0⊕1⊕0⊕1⊕0=1,s4=r4⊕r5⊕r6⊕r7⊕r12⊕r13⊕r14⊕r15=0⊕0⊕1⊕1⊕1⊕0⊕1⊕0=0,s2=r2⊕r3⊕r6⊕r7⊕r10⊕r11⊕r14⊕r15=1⊕1⊕1⊕1⊕0⊕0⊕1⊕0=1,s1=r1⊕r3⊕r5⊕r7⊕r9⊕r11⊕r13⊕r15=1⊕1⊕0⊕1⊕0⊕0⊕0⊕0=1.\begin{aligned} s_8 &= r_8 \oplus r_9 \oplus r_{10} \oplus r_{11} \oplus r_{12} \oplus r_{13} \oplus r_{14} \oplus r_{15} = 1 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 0 \oplus 1 \oplus 0 = 1, \\ s_4 &= r_4 \oplus r_5 \oplus r_6 \oplus r_7 \oplus r_{12} \oplus r_{13} \oplus r_{14} \oplus r_{15} = 0 \oplus 0 \oplus 1 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 0 = 0, \\ s_2 &= r_2 \oplus r_3 \oplus r_6 \oplus r_7 \oplus r_{10} \oplus r_{11} \oplus r_{14} \oplus r_{15} = 1 \oplus 1 \oplus 1 \oplus 1 \oplus 0 \oplus 0 \oplus 1 \oplus 0 = 1, \\ s_1 &= r_1 \oplus r_3 \oplus r_5 \oplus r_7 \oplus r_9 \oplus r_{11} \oplus r_{13} \oplus r_{15} = 1 \oplus 1 \oplus 0 \oplus 1 \oplus 0 \oplus 0 \oplus 0 \oplus 0 = 1. \end{aligned}
(8)

The syndrome s8s4s2s1=1011s_8 s_4 s_2 s_1 = 1011 is 8+2+1=118 + 2 + 1 = 11. Figure 2 shows why. Position 11 is 10111011 in binary, so it belongs to the checks on the 8s, 2s and 1s bits and to no other, and flipping it upsets exactly those three. The decoder flips r11r_{11} back to 1, reads the eleven data positions and returns the message 1011001101010110011010.

The four parity checks on the received word, whose failures spell position 11 in binary position 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 received r 1 1 1 0 0 1 1 1 0 0 0 1 0 1 0 parity check on the 8s bit 1 0 0 0 1 0 1 0 1 check on the 4s bit 0 0 1 1 1 0 1 0 0 check on the 2s bit 1 1 1 1 0 0 1 0 1 check on the 1s bit 1 1 0 1 0 0 0 0 1 Read down the parity column: s = 1011, and binary 1011 is 8 + 2 + 1 = 11. The checks that fail are exactly the checks that include position 11.
Figure 2. The four checks of the (15,11) code on a received word with position 11 flipped. Only the checks whose sets contain position 11 fail, and their pattern 1011 is 11 in binary. Data: computed by ch19_charts.py in the companion repository.

An exhaustive check confirms the hand calculation. All 2,048 codewords of the (15,11) code have zero syndrome, and every one of the 2,048×15=30,7202{,}048 \times 15 = 30{,}720 single-error words decodes back to the codeword it came from.

05.The Hamming Family

Each value of mm gives one member of the family, and Table 2 lists the first six. The smallest, m=2m = 2, has length 3 and dimension 1, and its two codewords are 000000 and 111111. It is the threefold repetition code of Why Codes Exist, so the family begins with the simplest correcting code there is.

Table 2. The binary Hamming codes for m = 2 to 7, with their length, dimension and rate

Check bits mmCodeLength n=2m−1n = 2^m - 1Dimension k=n−mk = n - mRate k/nk/n
2(3,1)310.333
3(7,4)740.571
4(15,11)15110.733
5(31,26)31260.839
6(63,57)63570.905
7(127,120)1271200.945

Source: reproduced by ch19_hamming_codes_and_perfect_codes.py.

The rate 1−m/(2m−1)1 - m / (2^m - 1) climbs toward 1, because the check bits grow only like the logarithm of the length. The distance stays at 3, though, so every member corrects one error per block, and a longer block gives a second error more places to land. For a small error probability the chance of two or more errors grows roughly like (n2)\binom{n}{2}, which is why memory systems protect words of 32 or 64 data bits rather than whole pages.

A message size between two members of the family is served by deleting columns. Removing data columns from HmH_m keeps the remaining columns nonzero and distinct, so the distance stays at least 3, and keeping the unit columns keeps the rank at mm. The rows of Table 1 that do not meet the test with equality are built this way, and Modifying and Combining Codes gives the construction its name and studies it in general.

06.The Sphere-Packing Bound

The theorem on check bits counted syndromes, so it speaks only about linear codes. A count over words applies to every code. Distance, Detection and Correction defined the ball B(c,t)B(c, t) of words within distance tt of cc, showed that a binary ball holds V(n,t)=∑i=0t(ni)V(n, t) = \sum_{i=0}^{t} \binom{n}{i} words, and noted the bound M V(n,t)≤2nM \, V(n, t) \le 2^n. This section proves the bound for any alphabet size, which the Hamming codes over larger fields need.

Start with the (7,4) code. A ball of radius 1 around a codeword holds the codeword and its seven neighbors, 1+7=81 + 7 = 8 words. The code has 16 codewords, and 16×8=128=2716 \times 8 = 128 = 2^7, the number of all words of length 7. Figure 3 lists the sixteen balls, and every word of length 7 appears in exactly one of them.

The 16 balls of radius one around the (7,4) Hamming codewords, covering all 128 words of length 7 0000000 1000000 0100000 0010000 0001000 0000100 0000010 0000001 1101001 0101001 1001001 1111001 1100001 1101101 1101011 1101000 0101010 1101010 0001010 0111010 0100010 0101110 0101000 0101011 1000011 0000011 1100011 1010011 1001011 1000111 1000001 1000010 1001100 0001100 1101100 1011100 1000100 1001000 1001110 1001101 0100101 1100101 0000101 0110101 0101101 0100001 0100111 0100100 1100110 0100110 1000110 1110110 1101110 1100010 1100100 1100111 0001111 1001111 0101111 0011111 0000111 0001011 0001101 0001110 1110000 0110000 1010000 1100000 1111000 1110100 1110010 1110001 0011001 1011001 0111001 0001001 0010001 0011101 0011011 0011000 1011010 0011010 1111010 1001010 1010010 1011110 1011000 1011011 0110011 1110011 0010011 0100011 0111011 0110111 0110001 0110010 0111100 1111100 0011100 0101100 0110100 0111000 0111110 0111101 1010101 0010101 1110101 1000101 1011101 1010001 1010111 1010100 0010110 1010110 0110110 0000110 0011110 0010010 0010100 0010111 1111111 0111111 1011111 1101111 1110111 1111011 1111101 1111110 codeword, the center of its ball its seven neighbors, the changed bit in orange
Figure 3. The 16 balls of radius 1 around the codewords of the (7,4) Hamming code. Each holds 8 words, no word appears twice, and together they hold all 128 words of length 7. Data: computed by ch19_charts.py in the companion repository.

Proof. Count first the words at distance exactly ii from cc. Such a word differs from cc in exactly ii positions. The set of those positions can be chosen in (ni)\binom{n}{i} ways. In each chosen position the word holds one of the q−1q - 1 symbols other than the symbol of cc there, which gives (q−1)i(q - 1)^i choices, and elsewhere it agrees with cc. Each word at distance ii arises from exactly one such choice, so there are (ni)(q−1)i\binom{n}{i} (q - 1)^i words at distance exactly ii. A word has only one distance from cc, so the counts for i=0,1,…,ti = 0, 1, \dots, t do not overlap, and adding them gives Vq(n,t)V_q(n, t). For q=2q = 2 the factor (q−1)i(q - 1)^i is 1, and the formula becomes the binary one of Distance, Detection and Correction. ■\blacksquare

Proof. Take two different codewords cc and c′c' and suppose some word xx lies in both balls of radius tt. In every position where cc and c′c' differ, xx cannot agree with both of them, so it disagrees with at least one. Each position where cc and c′c' differ is therefore counted in d(c,x)d(c, x) or in d(x,c′)d(x, c'), which gives d(c,c′)≤d(c,x)+d(x,c′)≤t+t=2td(c, c') \le d(c, x) + d(x, c') \le t + t = 2t. That is less than dd, the least distance between two codewords, which is impossible. So the MM balls are pairwise disjoint. By the lemma each holds Vq(n,t)V_q(n, t) words, so together they hold M⋅Vq(n,t)M \cdot V_q(n, t) different words, and all of them are among the qnq^n words of length nn. ■\blacksquare

The step in the middle is the triangle inequality, argued position by position so that it holds for any alphabet. Hamming derived the bound in the paper that introduced his codes [1], which is why it is also called the Hamming bound.

For one binary error the bound reads M(n+1)≤2nM (n + 1) \le 2^n. A linear code has M=2kM = 2^k, and the bound becomes n+1≤2mn + 1 \le 2^m, the condition of Equation 1 once more. The bound itself, M≤2n/(n+1)M \le 2^n / (n + 1), holds for every code. At the lengths n=2m−1n = 2^m - 1 it allows at most 2n−m2^{n-m} codewords, exactly as many as the Hamming code has, so no single-error-correcting code of those lengths, linear or not, beats it.

Figure 4 turns the bound into a rate. Taking the base-2 logarithm of M≤2n/(n+1)M \le 2^n / (n + 1) and dividing by nn gives a rate of at most 1−log⁡2(n+1)/n1 - \log_2(n + 1) / n. The Hamming codes sit on that curve. Between them the best linear code with distance 3 has m=⌈log⁡2(n+1)⌉m = \lceil \log_2(n + 1) \rceil check bits, by the theorem on check bits and the deletion of columns, so its rate falls below the curve in steps and touches it again at the next length of the form 2m−12^m - 1.

The rate of single-error-correcting codes against the sphere-packing bound, lengths 3 to 255 code length n, plotted at log2(n + 1) rate k/n 3 7 15 31 63 127 255 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 (3,1) (7,4) (15,11) (31,26) (63,57) (127,120) (255,247) sphere-packing bound, 1 - log2(n + 1)/n best linear code with distance 3 Hamming codes, on the bound
Figure 4. The rate of single-error-correcting binary codes against the sphere-packing bound. The Hamming codes lie on the bound, and the best linear codes between them step below it. Data: computed by ch19_charts.py in the companion repository.

07.Perfect Codes

The tiling of Figure 3 is the extreme case of the bound, in which the balls leave no word uncovered. Such codes have a name.

A perfect code wastes nothing, since every received word lies within the correcting radius of a codeword. For a linear code the same fact appears in the standard array. Two words of weight at most tt never share a coset, because their difference would be a nonzero codeword of weight at most 2t<d2t \lt d. A perfect linear code has exactly V(n,t)=2n−kV(n, t) = 2^{n-k} such words and 2n−k2^{n-k} cosets, so the coset leaders are exactly the words of weight at most tt. That arrangement of a group code into cosets goes back to Slepian [2].

Proof. The code has d=3=2⋅1+1d = 3 = 2 \cdot 1 + 1, so t=1t = 1. It has M=2n−mM = 2^{n-m} codewords, and a ball of radius 1 holds V(n,1)=1+n=1+(2m−1)=2mV(n, 1) = 1 + n = 1 + (2^m - 1) = 2^m words. The product is 2n−m⋅2m=2n2^{n-m} \cdot 2^m = 2^n. ■\blacksquare

Proof. The two codewords differ in all nn positions, so d=n=2t+1d = n = 2t + 1, and the claim is ∑i=0t(ni)=2n−1\sum_{i=0}^{t} \binom{n}{i} = 2^{n-1}. The full sum ∑i=0n(ni)\sum_{i=0}^{n} \binom{n}{i} counts all subsets of nn positions, so it is 2n2^n. Choosing ii positions is the same as choosing the n−in - i left out, so (ni)=(nn−i)\binom{n}{i} = \binom{n}{n-i}, and because n−t=t+1n - t = t + 1 this matches the terms with i≤ti \le t one for one with the terms with i≥t+1i \ge t + 1. Each half is therefore 2n−12^{n-1}. ■\blacksquare

For n=5n = 5 the ball holds V(5,2)=1+5+10=16V(5, 2) = 1 + 5 + 10 = 16 words, and 2×16=252 \times 16 = 2^5. The repetition codes are perfect but uninteresting, since their rate 1/n1/n falls to zero. For three errors in 23 bits the ball holds

V(23,3)=1+23+253+1771=2048=211,V(23, 3) = 1 + 23 + 253 + 1771 = 2048 = 2^{11},
(12)

so a code with 2122^{12} codewords would fill the 2232^{23} words exactly. Golay found such a code in 1949, along with a ternary code of length 11 that corrects two errors [3]. For the ternary code V3(11,2)=1+11⋅2+55⋅4=243=35V_3(11, 2) = 1 + 11 \cdot 2 + 55 \cdot 4 = 243 = 3^5, and its 363^6 codewords fill the 3113^{11} words. Golay Codes builds both. Table 3 collects the counts.

Table 3. The sphere-packing count for six sets of parameters. All but the last row are perfect codes, and the last meets the equality although no code with those parameters exists

CodeAlphabet qqErrors ttCodewords MMBall Vq(n,t)V_q(n, t)M⋅Vq(n,t)M \cdot V_q(n, t)
Hamming (7,4)21242^48272^7
Hamming (15,11)212112^{11}162152^{15}
Repetition (5,1)222216252^5
Golay (23,12)232122^{12}20482232^{23}
Ternary Golay (11,6)32363^62433113^{11}
Candidate (90,78)222782^{78}40962902^{90}

Source: reproduced by ch19_hamming_codes_and_perfect_codes.py.

The last row shows that the count alone proves nothing. Two errors in 90 bits give a ball of 1+90+4005=2121 + 90 + 4005 = 2^{12} words, so 2782^{78} codewords would fill the space exactly, yet no such code exists. The full answer took until the early 1970s.

Tietäväinen completed the proof in 1973 [4], and van Lint's text gives the whole argument [5]. It rests on algebra this book has not built, so it is cited rather than proved. The (90,78) candidate matches none of the three. The theorem speaks of parameters on purpose, since nonlinear binary codes exist with the parameters of a Hamming code [6]. Among linear codes the Hamming code is the only one. A linear code with n=2m−1n = 2^m - 1, k=n−mk = n - m and d=3d = 3 has an m×nm \times n parity-check matrix whose columns must be nonzero and distinct, as the theorem on check bits showed, so they are all 2m−12^m - 1 nonzero words in some order, and the code is equivalent to Ham(m)\mathrm{Ham}(m).

08.Hamming Codes over Larger Fields

Over GF(3)\mathrm{GF}(3) the construction needs one change. A column hh and its double 2h2h differ, but h+2h=3h=0h + 2h = 3h = 0, so a matrix holding both has a codeword of weight 2. The fix is to keep one column from each group of multiples, the one whose first nonzero entry from the top is 1. For two rows over GF(3)\mathrm{GF}(3) the nonzero columns are 01,02,10,20,11,22,12,2101, 02, 10, 20, 11, 22, 12, 21, and they fall into the four groups {01,02}\{01, 02\}, {10,20}\{10, 20\}, {11,22}\{11, 22\} and {12,21}\{12, 21\}. Keeping 0101, 1010, 1111 and 1212 gives

H=[01111012]H = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 2 \end{bmatrix}
(13)

over GF(3)\mathrm{GF}(3), with all arithmetic modulo 3. Its null space has 34−2=93^{4-2} = 9 codewords, 00000000, 01110111, 02220222, 10121012, 11201120, 12011201, 20212021, 21022102 and 22102210, and every nonzero one has weight 3. This (4,2) ternary code is sometimes called the tetracode.

The length is a count. The qm−1q^m - 1 nonzero words split into groups of q−1q - 1 nonzero multiples, and each group holds exactly one word whose first nonzero entry is 1, so there are (qm−1)/(q−1)(q^m - 1)/(q - 1) columns. For q=2q = 2 this is 2m−12^m - 1, and the definition becomes the binary one. Golay's note of 1949 already gave this generalization for a prime number of symbols [3].

Proof. Each unit column, with a single 1 and zeros elsewhere, has 1 as its first nonzero entry, so all mm unit columns are in the matrix. They are independent, so the rank is mm, and the rank theorem gives k=n−mk = n - m. A codeword of weight 1 would be aeia e_i with a≠0a \ne 0, and its syndrome ahia h_i is nonzero because a nonzero field element times a nonzero column is nonzero. A codeword of weight 2 would be aei+beja e_i + b e_j with a,b≠0a, b \ne 0 and i≠ji \ne j, and it needs ahi+bhj=0a h_i + b h_j = 0, that is hi=−(b/a)hjh_i = -(b/a) h_j. Then hih_i and hjh_j are multiples of each other with first nonzero entries in the same row, both equal to 1, so the multiplier is 1 and hi=hjh_i = h_j, which is false. So d≥3d \ge 3. The unit columns u1u_1 and u2u_2, with their 1 in the first and second rows, and the column u1+u2u_1 + u_2 all have first nonzero entry 1, and u1+u2−(u1+u2)=0u_1 + u_2 - (u_1 + u_2) = 0 gives a codeword with entries 11, 11 and −1-1 in those three positions, of weight 3. So d=3d = 3 and t=1t = 1. Finally M=qn−mM = q^{n-m} and Vq(n,1)=1+n(q−1)=1+(qm−1)=qmV_q(n, 1) = 1 + n(q - 1) = 1 + (q^m - 1) = q^m, so M⋅Vq(n,1)=qn−m⋅qm=qnM \cdot V_q(n, 1) = q^{n-m} \cdot q^m = q^n. ■\blacksquare

For the tetracode, a ball of radius 1 holds 1+4⋅2=91 + 4 \cdot 2 = 9 words, and the 9 balls hold all 9×9=81=349 \times 9 = 81 = 3^4 ternary words of length 4. Table 4 lists a few more members. The field with four elements is not the integers modulo 4, as Vector Spaces over Finite Fields showed, but the table needs only its size.

Table 4. Some Hamming codes over fields with more than two elements, with m = 2 check symbols

Field size qqCheck symbols mmLength nnDimension kkBall 1+n(q−1)=qm1 + n(q - 1) = q^m
32429
425316
526425
728649

Source: reproduced by ch19_hamming_codes_and_perfect_codes.py.

Decoding needs one more step than in the binary case, because an error now has a size as well as a position. If the received word is r=c+aejr = c + a e_j, the syndrome is s=ahjs = a h_j. The column hjh_j has first nonzero entry 1, so the first nonzero entry of ss is the error value aa, and dividing ss by aa gives the column hjh_j and with it the position. Take the received word 12111211. Its syndrome has entries 0⋅1+1⋅2+1⋅1+1⋅1=4≡10 \cdot 1 + 1 \cdot 2 + 1 \cdot 1 + 1 \cdot 1 = 4 \equiv 1 and 1⋅1+0⋅2+1⋅1+2⋅1=4≡11 \cdot 1 + 0 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 = 4 \equiv 1, so s=11s = 11. Its first nonzero entry is 1, so the error value is 1 and the column is 1111, which sits in position 3. Subtracting 1 in position 3 turns 12111211 into 12011201, a codeword from the list. All 72 single errors on the 9 codewords decode the same way.

09.The Extended Hamming Code

A Hamming decoder turns two errors into three without noticing, and one more bit cures the silence. Put in front of each codeword the bit that makes its total number of 1s even. The codeword 01100110110011 has even weight, so it becomes 0011001100110011, and a codeword of odd weight gets a 1 in front.

The bit c0c_0 is a linear function of the rest, so the code is linear, with length 2m2^m and the same dimension 2m−1−m2^m - 1 - m. The first members are (4,1), (8,4), (16,11), (32,26) and (64,57).

Proof. The weight of an extended codeword is w(c)+c0w(c) + c_0, where w(c)w(c) is the weight of c=c1⋯cnc = c_1 \cdots c_n. The bit c0c_0 is 1 exactly when w(c)w(c) is odd, so the total weight is w(c)w(c) when w(c)w(c) is even and w(c)+1w(c) + 1 when it is odd. Either way it is even. A nonzero extended codeword has c≠0c \ne 0, because c=0c = 0 forces c0=0c_0 = 0, so w(c)≥3w(c) \ge 3 by the theorem on dimension and distance. Its weight is therefore an even number that is at least 3, so it is at least 4. The weight-3 codeword 1110⋯01110 \cdots 0 of Ham(m)\mathrm{Ham}(m) has odd weight, so it gets c0=1c_0 = 1 and becomes an extended codeword of weight exactly 4. Hence d=4d = 4. ■\blacksquare

The (8,4) code has 14 codewords of weight 4. The other two are 0000000000000000 and 1111111111111111, since every row of H3H_3 has four 1s, which makes 11111111111111 a codeword of odd weight. The decoder now computes two things, the syndrome s=Hm(c1⋯cn)Ts = H_m (c_1 \cdots c_n)^{\mathsf T} of the last nn bits as before and the overall parity p=c0⊕c1⊕⋯⊕cnp = c_0 \oplus c_1 \oplus \cdots \oplus c_n of all the bits.

Proof. A codeword has even weight, so its overall parity is 0, and each flipped bit toggles the parity. So p=1p = 1 after one flip and p=0p = 0 after none or two. The syndrome sees only positions 1 to nn. No flip, or a flip of c0c_0 alone, gives s=0s = 0. One flip at j≥1j \ge 1 gives s=hj≠0s = h_j \ne 0, which names jj by the lemma on single errors. Two flips at i≠ji \ne j, both at least 1, give hi+hj≠0h_i + h_j \ne 0 because the columns are distinct, and a flip of c0c_0 with one at jj gives hj≠0h_j \ne 0. So the four cases give the four different pairs listed. ■\blacksquare

Figure 5 draws the four cases as a grid, with an example from the codeword 0011001100110011 in each. Flipping positions 2 and 5 gives 0001011100010111, with s=111s = 111 and p=0p = 0, and the decoder reports a double error instead of changing anything. An exhaustive check over the (8,4) and (16,11) codes confirms that every single error is named, the parity bit included, and that all 28 and all 120 double-error patterns are detected on every codeword.

How the extended (8,4) Hamming decoder reads its two checks. The syndrome s of positions 1 to 7 is either zero or not, and the overall parity p of all eight bits is either 0 or 1. Zero syndrome and even parity means no error. Zero syndrome and odd parity means only the parity bit c0 was hit. A nonzero syndrome with odd parity means one error, at position s. A nonzero syndrome with even parity means two errors, which are detected but not corrected. The examples are the codeword 00110011 and words made from it by flipping c0, position 5, and positions 2 and 5. overall parity p = 0 overall parity p = 1 syndrome s = 000 syndrome nonzero no error flip the parity bit c0 double error detected flip position s accept the word as received c1 to c7 are clean, only c0 was hit two errors, report them, change nothing one error among c1 to c7 example example example example 00110011 10110011 00010111, s = 111 00110111, s = 101 bit order c0 c1 c2 c3 c4 c5 c6 c7, codeword 00110011 for the message 1011
Figure 5. How the extended (8,4) decoder reads its two checks. The overall parity says whether an odd or even number of bits flipped, and the syndrome says where a single error sits.

The (15,11) codeword of the hand calculation has weight 9, so its extended form gets c0=1c_0 = 1 and reads 11110011100110101111001110011010. Flipping positions 3 and 12, the pair from the warning, now gives s=1111s = 1111 and p=0p = 0, and the decoder reports a double error where the plain decoder handed back a wrong codeword. A code that corrects one error and detects two is called a SEC-DED code, and memory systems use it on 64-bit words in the form of a (72,64) code, one parity bit added to the (71,64) code of Table 1.

10.The Encoder and Decoder as Gates

Each check bit is the XOR of ww data bits. A two-input XOR gate turns two values into one, so a tree of them, in which each value feeds one gate, reduces ww values to one with exactly w−1w - 1 gates, and no network does it with fewer. A balanced tree takes ⌈log⁡2w⌉\lceil \log_2 w \rceil levels, the depth that sets the delay. Figure 6 draws the (7,4) encoder, three trees of two gates each. With the message 10111011 they give c1=0c_1 = 0, c2=1c_2 = 1 and c4=0c_4 = 0, the check bits of 01100110110011.

The encoder of the (7,4) Hamming code as three trees of two-input XOR gates. Check bit c1 is the XOR of c3, c5 and c7, check bit c2 the XOR of c3, c6 and c7, and check bit c4 the XOR of c5, c6 and c7. Each tree is two gates deep, six gates in all. With the message 1011 placed at c3, c5, c6 and c7 the trees give c1 = 0, c2 = 1 and c4 = 0, so the codeword is 0110011. message 1011 placed at c3 c5 c6 c7 = 1 0 1 1 c3c5c7 c3c6c7 c5c6c7 1011 1101 0111 c1 = 0 c2 = 1 c4 = 0 XOR of positions 3, 5, 7 XOR of positions 3, 6, 7 XOR of positions 5, 6, 7 level 1 level 2 6 gates in 2 levels, codeword 0110011
Figure 6. The encoder of the (7,4) Hamming code as three XOR trees. Each check bit is the XOR of three data bits, so each tree has two gates in two levels.

Proof. Exactly half of the numbers from 0 to 2m−12^m - 1 have a 1 in the 2i2^i place, and 0 is not among them, so 2m−12^{m-1} positions from 1 to nn have that bit set. One is the check position 2i2^i, and no other check position is among them, since every other power of two has its 1 elsewhere. So check bit c2ic_{2^i} is the XOR of w=2m−1−1w = 2^{m-1} - 1 data bits, which takes w−1=2m−1−2w - 1 = 2^{m-1} - 2 gates. There are mm check bits, which gives m(2m−1−2)m(2^{m-1} - 2) gates. For m≥3m \ge 3 the inequalities 2m−2<2m−1−1<2m−12^{m-2} \lt 2^{m-1} - 1 \lt 2^{m-1} hold, so ⌈log⁡2w⌉=m−1\lceil \log_2 w \rceil = m - 1. ■\blacksquare

The (15,11) encoder needs 4×6=244 \times 6 = 24 gates in three levels, and m=7m = 7 needs 434. Check bits that share a sub-sum, as c1c_1 and c2c_2 in the (7,4) code share c3⊕c7c_3 \oplus c_7, can compute it once, and SECDED and Hsiao Codes takes up that saving.

The decoder has three stages. The first computes the syndrome, each bit s2is_{2^i} the XOR of the received bits in the 2m−12^{m-1} positions its row covers, check bit included, which takes m(2m−1−1)m(2^{m-1} - 1) gates in all. The second gives each position jj a wire that carries 1 exactly when s=js = j, an AND gate with mm inputs that takes s2is_{2^i} where jj has a 1 in the 2i2^i place and the complement s2i‾\overline{s_{2^i}} where it has a 0, with one shared NOT gate per syndrome bit. The third XORs each received bit with its AND output.

Proof. An AND of mm inputs reduces mm values to one, so it takes m−1m - 1 two-input gates, as the XOR tree did. The gate for position jj outputs 1 exactly when each s2is_{2^i} equals the bit of jj in the 2i2^i place, that is, when s=js = j. With no error s=0s = 0, which equals no position, so nothing fires. With one error at jj, the lemma on single errors gives s=js = j, so only the gate for jj fires and its XOR flips rjr_j back. ■\blacksquare

Figure 7 draws the (7,4) decoder on the received word 01100010110001, with the AND gates and correction XORs for the four data positions only. The syndrome trees give s4=1s_4 = 1, s2=1s_2 = 1 and s1=0s_1 = 0. The gate for position 6 sees 11, 11 and the complement of 00, so it fires, and the correction XOR turns r6=0r_6 = 0 into 1.

The syndrome decoder of the (7,4) Hamming code. Three XOR trees turn the received word r1 to r7 into the syndrome bits s4, s2 and s1. Each data position j has an AND gate whose inputs are the three syndrome bits, with an inverting circle on every input where the binary form of j has a 0, so the gate gives 1 only when the syndrome equals j. A final XOR flips the received bit when its gate fires. For the received word 0110001 the syndrome is 110, only the gate for position 6 fires, and r6 is flipped from 0 to 1, giving the data 1011. received r = 0110001, an error in position 6 r10 r21 r31 r40 r50 r60 r71 syndrometrees 9 XOR gates2 levels s4 = 1s2 = 1s1 = 0 fires on 0110r3 = 1c3 = 1fires on 1010r5 = 0c5 = 0fires on 1101r6 = 0c6 = 1flipped from 0fires on 1110r7 = 1c7 = 1 A small circle inverts its input, so each AND gate gives 1 for exactly one syndrome.Data out c3 c5 c6 c7 = 1011
Figure 7. The syndrome decoder of the (7,4) Hamming code on the received word 0110001. The syndrome 110 makes only the AND gate for position 6 fire, and its XOR restores the data 1011. Each small circle on an AND input stands for the shared NOT gate on that syndrome bit.

Table 5 collects the counts. Counting each AND gate as one level, the delay is the depth of the syndrome trees plus one level each for the NOT, the AND and the correction XOR, 5 levels for the (7,4) code and 6 for the (15,11) code. A decoder that needs only the data, as in the figure, keeps the AND gates and correction XORs for the kk data positions alone.

Table 5. Gate counts for the encoder and the full decoder of the (7,4) and (15,11) Hamming codes, with every XOR a two-input gate and the AND gates counted both ways

Part(7,4)(15,11)
Encoder XOR gates624
Encoder levels23
Syndrome XOR gates928
Syndrome levels23
NOT gates34
AND gates with mm inputs715
The same AND gates as two-input gates1445
Correction XOR gates715
Decoder gates in all, NOT gates and two-input ANDs included3392
Decoder levels, each AND one level56

Source: reproduced by ch19_hamming_codes_and_perfect_codes.py.

The syndrome trees grow like nlog⁡2nn \log_2 n gates while the depth grows only like log⁡2n\log_2 n, so the decoder stays fast for long words. The script checks the gate-level decoder against every correctable word of both codes.

11.Looking Ahead

The extended Hamming code detects every double error, but its decoder says nothing reliable about three. A triple error has odd parity, so the decoder takes it for a single error and miscorrects. SECDED and Hsiao Codes takes up the extended decoder as a circuit, the triple errors it miscorrects, and Hsiao's choice of odd-weight columns, which cuts the gate count and makes the double-error test a check on the syndrome alone [7]. That chapter builds the (72,64) and (39,32) codes that protect memory words in practice.

Several threads from this chapter run further ahead. Deleting columns, which served message sizes between the Hamming lengths, becomes shortening in Modifying and Combining Codes, alongside puncturing and other ways of building one code from another. The count of weight-3 codewords is one entry of a code's weight distribution, which Weight Distributions and Undetected Errors computes in full. Golay Codes constructs the two Golay codes whose counts appeared in Table 3. And Bounds on Codes sets the sphere-packing bound beside the Singleton and Plotkin bounds, which limit codes that are far from perfect, and the Gilbert–Varshamov bound, which guarantees that good codes exist.

12.Worked Examples

13.Exercises

References

  1. [1]Hamming, Richard W. (1950). “Error Detecting and Error Correcting Codes.” Bell System Technical Journal, 29(2), pp. 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x
  2. [2]Slepian, David (1956). “A Class of Binary Signaling Alphabets.” Bell System Technical Journal, 35(1), pp. 203–234. doi:10.1002/j.1538-7305.1956.tb02379.x
  3. [3]Golay, Marcel J. E. (1949). “Notes on Digital Coding.” Proceedings of the IRE, 37(6), pp. 657. doi:10.1109/JRPROC.1949.233620
  4. [4]Tietäväinen, Aimo (1973). “On the Nonexistence of Perfect Codes over Finite Fields.” SIAM Journal on Applied Mathematics, 24(1), pp. 88–96. doi:10.1137/0124010
  5. [5]van Lint, J. H. (1999). “Introduction to Coding Theory.” 3rd edition. Springer. doi:10.1007/978-3-642-58575-3
  6. [6]Huffman, W. Cary and Pless, Vera (2003). “Fundamentals of Error-Correcting Codes.” Cambridge University Press. doi:10.1017/CBO9780511807077
  7. [7]Hsiao, M. Y. (1970). “A Class of Optimal Minimum Odd-weight-column SEC-DED Codes.” IBM Journal of Research and Development, 14(4), pp. 395–401. doi:10.1147/rd.144.0395

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes