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 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 check bits can protect at most positions. Taking every nonzero column of bits as the parity-check matrix reaches this limit exactly, and the result is the Hamming code of length , 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 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 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 plus an error pattern , and its syndrome depends only on the error. A single error in position is the pattern with one 1, and its syndrome is , the column of .
Proof. Such a decoder must also return a codeword unchanged when no error occurs. Suppose some column is zero, . Then , so is a codeword. The received word is then both the codeword hit in position , which must decode to , and the codeword received cleanly, which must stay . Suppose next that with . Over every element is its own negative, so and is a codeword. The received word is then both hit in position and hit in position , two single errors that demand different outputs. So the columns are nonzero and distinct. A column has bits, which allows patterns, one of them zero, so , which is .
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 | Check bits | Length | Test |
|---|---|---|---|
| 1 | 2 | 3 | |
| 4 | 3 | 7 | |
| 8 | 4 | 12 | |
| 11 | 4 | 15 | |
| 16 | 5 | 21 | |
| 26 | 5 | 31 | |
| 32 | 6 | 38 | |
| 57 | 6 | 63 | |
| 64 | 7 | 71 | |
| 120 | 7 | 127 |
Source: reproduced by ch19_hamming_codes_and_perfect_codes.py.
In the rows that meet the test with equality every nonzero column of 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
Read any column from top to bottom and it spells its own position. Column 6 reads , which is . 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 , and , 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 say , and , and solving them gives the encoding rule
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 . It sets , , and . Then , and , and the codeword is . The message bits appear in it unchanged, so the code is systematic, with the check bits interleaved among the data.
For every the check positions are the powers of two , the numbers with a single 1 in binary. Check bit is the XOR of the data bits whose position number has a 1 in the place, and the data fill the remaining positions in increasing order.
Proof. The length is the number of nonzero columns of bits, which is . The columns in positions are the unit columns, which are linearly independent, so has rank , the most its 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 .
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 the product is the sum of the columns in the positions where has a 1. A codeword of weight 1 would need a zero column, and one of weight 2 would need , that is , 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 in binary has no carries, so . The word with 1s in positions 1, 2 and 3 is therefore a codeword of weight 3, and .
For that codeword is . The same reasoning counts every codeword of weight 3. Adding columns and with gives the binary form of the bitwise XOR , which is nonzero and differs from both, so each pair of positions lies in exactly one weight-3 codeword, the one with 1s at , and . Each such codeword contains three pairs, so there are of them. For that is , 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 , and in counting order a column is its own position number.
Proof. Matrix multiplication distributes over addition, so . The first term is because is a codeword. The second is the sum of the columns where has a 1, which is the single column . By the definition of counting order, is in binary.
The decoder follows directly. Compute the syndrome . If , accept the word as it stands. Otherwise read as a binary number and flip the bit in that position. Take the codeword from the previous section and flip position 6, which gives the received word . The three checks are
The syndrome is the number 6, so the decoder flips back to 1 and recovers . Reading positions 3, 5, 6 and 7 returns the message . 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 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 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.
Take the eleven-bit message . Placed in the data positions in increasing order, it sets , , , , , , , , , and . The four check bits come from the four rows of .
The check bits are , and the full codeword is , which has weight 9. Now suppose the channel flips position 11, so that the received word is . Each syndrome bit is the XOR of the received bits in the eight positions its row covers, check position included.
The syndrome is . Figure 2 shows why. Position 11 is 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 back to 1, reads the eleven data positions and returns the message .
An exhaustive check confirms the hand calculation. All 2,048 codewords of the (15,11) code have zero syndrome, and every one of the single-error words decodes back to the codeword it came from.
05.The Hamming Family
Each value of gives one member of the family, and Table 2 lists the first six. The smallest, , has length 3 and dimension 1, and its two codewords are and . 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 | Code | Length | Dimension | Rate |
|---|---|---|---|---|
| 2 | (3,1) | 3 | 1 | 0.333 |
| 3 | (7,4) | 7 | 4 | 0.571 |
| 4 | (15,11) | 15 | 11 | 0.733 |
| 5 | (31,26) | 31 | 26 | 0.839 |
| 6 | (63,57) | 63 | 57 | 0.905 |
| 7 | (127,120) | 127 | 120 | 0.945 |
Source: reproduced by ch19_hamming_codes_and_perfect_codes.py.
The rate 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 , 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 keeps the remaining columns nonzero and distinct, so the distance stays at least 3, and keeping the unit columns keeps the rank at . 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 of words within distance of , showed that a binary ball holds words, and noted the bound . 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, words. The code has 16 codewords, and , 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.
Proof. Count first the words at distance exactly from . Such a word differs from in exactly positions. The set of those positions can be chosen in ways. In each chosen position the word holds one of the symbols other than the symbol of there, which gives choices, and elsewhere it agrees with . Each word at distance arises from exactly one such choice, so there are words at distance exactly . A word has only one distance from , so the counts for do not overlap, and adding them gives . For the factor is 1, and the formula becomes the binary one of Distance, Detection and Correction.
Proof. Take two different codewords and and suppose some word lies in both balls of radius . In every position where and differ, cannot agree with both of them, so it disagrees with at least one. Each position where and differ is therefore counted in or in , which gives . That is less than , the least distance between two codewords, which is impossible. So the balls are pairwise disjoint. By the lemma each holds words, so together they hold different words, and all of them are among the words of length .
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 . A linear code has , and the bound becomes , the condition of Equation 1 once more. The bound itself, , holds for every code. At the lengths it allows at most 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 and dividing by gives a rate of at most . The Hamming codes sit on that curve. Between them the best linear code with distance 3 has 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 .
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 never share a coset, because their difference would be a nonzero codeword of weight at most . A perfect linear code has exactly such words and cosets, so the coset leaders are exactly the words of weight at most . That arrangement of a group code into cosets goes back to Slepian [2].
Proof. The code has , so . It has codewords, and a ball of radius 1 holds words. The product is .
Proof. The two codewords differ in all positions, so , and the claim is . The full sum counts all subsets of positions, so it is . Choosing positions is the same as choosing the left out, so , and because this matches the terms with one for one with the terms with . Each half is therefore .
For the ball holds words, and . The repetition codes are perfect but uninteresting, since their rate falls to zero. For three errors in 23 bits the ball holds
so a code with codewords would fill the 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 , and its codewords fill the 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
| Code | Alphabet | Errors | Codewords | Ball | |
|---|---|---|---|---|---|
| Hamming (7,4) | 2 | 1 | 8 | ||
| Hamming (15,11) | 2 | 1 | 16 | ||
| Repetition (5,1) | 2 | 2 | 16 | ||
| Golay (23,12) | 2 | 3 | 2048 | ||
| Ternary Golay (11,6) | 3 | 2 | 243 | ||
| Candidate (90,78) | 2 | 2 | 4096 |
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 words, so 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 , and has an parity-check matrix whose columns must be nonzero and distinct, as the theorem on check bits showed, so they are all nonzero words in some order, and the code is equivalent to .
08.Hamming Codes over Larger Fields
Over the construction needs one change. A column and its double differ, but , 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 the nonzero columns are , and they fall into the four groups , , and . Keeping , , and gives
over , with all arithmetic modulo 3. Its null space has codewords, , , , , , , , and , and every nonzero one has weight 3. This (4,2) ternary code is sometimes called the tetracode.
The length is a count. The nonzero words split into groups of nonzero multiples, and each group holds exactly one word whose first nonzero entry is 1, so there are columns. For this is , 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 unit columns are in the matrix. They are independent, so the rank is , and the rank theorem gives . A codeword of weight 1 would be with , and its syndrome is nonzero because a nonzero field element times a nonzero column is nonzero. A codeword of weight 2 would be with and , and it needs , that is . Then and are multiples of each other with first nonzero entries in the same row, both equal to 1, so the multiplier is 1 and , which is false. So . The unit columns and , with their 1 in the first and second rows, and the column all have first nonzero entry 1, and gives a codeword with entries , and in those three positions, of weight 3. So and . Finally and , so .
For the tetracode, a ball of radius 1 holds words, and the 9 balls hold all 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 | Check symbols | Length | Dimension | Ball |
|---|---|---|---|---|
| 3 | 2 | 4 | 2 | 9 |
| 4 | 2 | 5 | 3 | 16 |
| 5 | 2 | 6 | 4 | 25 |
| 7 | 2 | 8 | 6 | 49 |
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 , the syndrome is . The column has first nonzero entry 1, so the first nonzero entry of is the error value , and dividing by gives the column and with it the position. Take the received word . Its syndrome has entries and , so . Its first nonzero entry is 1, so the error value is 1 and the column is , which sits in position 3. Subtracting 1 in position 3 turns into , 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 has even weight, so it becomes , and a codeword of odd weight gets a 1 in front.
The bit is a linear function of the rest, so the code is linear, with length and the same dimension . The first members are (4,1), (8,4), (16,11), (32,26) and (64,57).
Proof. The weight of an extended codeword is , where is the weight of . The bit is 1 exactly when is odd, so the total weight is when is even and when it is odd. Either way it is even. A nonzero extended codeword has , because forces , so 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 of has odd weight, so it gets and becomes an extended codeword of weight exactly 4. Hence .
The (8,4) code has 14 codewords of weight 4. The other two are and , since every row of has four 1s, which makes a codeword of odd weight. The decoder now computes two things, the syndrome of the last bits as before and the overall parity of all the bits.
Proof. A codeword has even weight, so its overall parity is 0, and each flipped bit toggles the parity. So after one flip and after none or two. The syndrome sees only positions 1 to . No flip, or a flip of alone, gives . One flip at gives , which names by the lemma on single errors. Two flips at , both at least 1, give because the columns are distinct, and a flip of with one at gives . So the four cases give the four different pairs listed.
Figure 5 draws the four cases as a grid, with an example from the codeword in each. Flipping positions 2 and 5 gives , with and , 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.
The (15,11) codeword of the hand calculation has weight 9, so its extended form gets and reads . Flipping positions 3 and 12, the pair from the warning, now gives and , 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 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 values to one with exactly gates, and no network does it with fewer. A balanced tree takes levels, the depth that sets the delay. Figure 6 draws the (7,4) encoder, three trees of two gates each. With the message they give , and , the check bits of .
Proof. Exactly half of the numbers from 0 to have a 1 in the place, and 0 is not among them, so positions from 1 to have that bit set. One is the check position , and no other check position is among them, since every other power of two has its 1 elsewhere. So check bit is the XOR of data bits, which takes gates. There are check bits, which gives gates. For the inequalities hold, so .
The (15,11) encoder needs gates in three levels, and needs 434. Check bits that share a sub-sum, as and in the (7,4) code share , 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 the XOR of the received bits in the positions its row covers, check bit included, which takes gates in all. The second gives each position a wire that carries 1 exactly when , an AND gate with inputs that takes where has a 1 in the place and the complement 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 inputs reduces values to one, so it takes two-input gates, as the XOR tree did. The gate for position outputs 1 exactly when each equals the bit of in the place, that is, when . With no error , which equals no position, so nothing fires. With one error at , the lemma on single errors gives , so only the gate for fires and its XOR flips back.
Figure 7 draws the (7,4) decoder on the received word , with the AND gates and correction XORs for the four data positions only. The syndrome trees give , and . The gate for position 6 sees , and the complement of , so it fires, and the correction XOR turns into 1.
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 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 gates | 6 | 24 |
| Encoder levels | 2 | 3 |
| Syndrome XOR gates | 9 | 28 |
| Syndrome levels | 2 | 3 |
| NOT gates | 3 | 4 |
| AND gates with inputs | 7 | 15 |
| The same AND gates as two-input gates | 14 | 45 |
| Correction XOR gates | 7 | 15 |
| Decoder gates in all, NOT gates and two-input ANDs included | 33 | 92 |
| Decoder levels, each AND one level | 5 | 6 |
Source: reproduced by ch19_hamming_codes_and_perfect_codes.py.
The syndrome trees grow like gates while the depth grows only like , 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]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]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]Golay, Marcel J. E. (1949). “Notes on Digital Coding.” Proceedings of the IRE, 37(6), pp. 657. doi:10.1109/JRPROC.1949.233620
- [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]van Lint, J. H. (1999). “Introduction to Coding Theory.” 3rd edition. Springer. doi:10.1007/978-3-642-58575-3
- [6]Huffman, W. Cary and Pless, Vera (2003). “Fundamentals of Error-Correcting Codes.” Cambridge University Press. doi:10.1017/CBO9780511807077
- [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.