Weight Distributions and Undetected Errors
November 15, 202651 min readbeginner
A detecting code misses an error exactly when the error is itself a codeword. The chapter counts codewords by weight, derives the chance of a miss, proves the MacWilliams identity, and shows why the exact length matters.
Hamming Codes and Perfect Codes used the (7,4) code to correct one error. The same code can be put to a different job. A receiver that never tries to repair anything, and only asks for a resend whenever the syndrome is nonzero, turns the three check bits into a detector. Every pattern of one or two flipped bits raises the alarm, since the minimum distance is 3. Most heavier patterns raise it too. A few do not, and those few are the subject of this chapter. When the detector stays silent on a damaged word, the receiver accepts wrong data and nothing downstream knows.
Which patterns slip through, and how often, turns out to depend on a single list of numbers, the count of codewords of each weight. That list gives the probability of an undetected error on a binary symmetric channel in closed form. A theorem of Jessie MacWilliams computes it from the much smaller dual code when the code itself is too large to list, and it settles which codes obey the rule of thumb that check bits miss about one error in . Some codes do not, and the difference can come down to a single bit of length.
Every number in the chapter is recomputed by ch23_weight_distributions_and_undetected_errors.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch23_charts.py in the same folder. The GNU Octave twin ch23_weight_distributions_and_undetected_errors.m prints the same lines, as The Octave Route explains.
01.When a Check Stays Silent
Figure 1 shows the link. Four data bits enter the encoder, the seven-bit codeword crosses a channel that flips each bit with probability , and the receiver gets , where is the error pattern, with a 1 in each flipped position. A syndrome unit computes and an OR gate reduces its three bits to one flag. A flag of 1 asks for the word again, and a flag of 0 hands to the user as correct.
With the columns of in counting order, column is the number in three bits, and the rows read
The syndrome of a pattern is the bitwise XOR of the columns at its ones. The single error hits position 3 and gives , which raises the flag. The double error gives , and the triple error gives , so both are caught. The triple error is different. Its columns are , and , and their XOR is . The flag stays down. So it does for , whose columns also cancel, for and for . Figure 2 lays the seven patterns beside the matrix.
The four missed patterns have something in common. Each is a codeword of the (7,4) code, and that is no accident.
Proof. Matrix multiplication over distributes over XOR, so . Every codeword satisfies , which leaves . The code is the null space of , so holds exactly when . The condition mentions alone, so it is the same for every transmitted codeword.
The theorem turns a question about a channel into a question about a list. Of the nonzero patterns of seven bits, exactly 15 are codewords, so 15 are missed and 112 are caught. Figure 3 sorts them by weight. All 7 single and all 21 double errors are caught. Of the 35 triple errors, 28 are caught and 7 missed, and the same split holds for the 35 patterns of weight 4. Every pattern of weight 5 or 6 is caught, and the single pattern of weight 7, which flips every bit, is missed.
The detector is small in hardware. Each row of has four ones, so each syndrome bit is the XOR of four received bits, a tree of three two-input XOR gates, and one OR gate turns the three syndrome bits into the flag. Nothing locates or flips a bit, so there is no decoder at all, and the check settles in a few gate delays. That economy is why detection with a resend is the usual choice wherever the sender can be asked again, as on a bus with a retry signal or a network link that keeps a copy of each frame until the receiver acknowledges it. The price is the 15 patterns that pass. A detector is judged by its rate of silent failures, and the rest of the chapter is about computing that rate.
02.Counting Codewords by Weight
The numbers of missed patterns in Figure 3, read by weight, are if the zero word is counted at weight 0. That list is the code's weight distribution, the single object the rest of the chapter works with.
In the second form each codeword contributes one term, with raised to its number of zeros and to its number of ones. For the (7,4) Hamming code
Setting counts the code, . The minimum distance is the first nonzero weight with , which is 3 here, because Linear Codes proved, in "Theorem: Minimum distance equals minimum weight", that the two coincide for a linear code.
The count can be found without listing the code. A pattern of weight 3 is a codeword when the three columns at its ones XOR to zero, and with the columns in counting order the column at position is the number in binary. So the weight-3 codewords are the sets of three positions with , such as and , which are the patterns and met earlier. Choose any two distinct positions and , in one of ways. Their XOR is nonzero because , at most 7 because both fit in three bits, and different from and from because neither is zero. Each set of three is reached from three of its pairs, so there are such sets. The seven columns together XOR to zero, so the all-ones word is a codeword, and a symmetry proved later in this section then gives , , and .
Table 1 lists the codes the chapter uses. The repetition code of length 3 is . The even-weight code of length holds every word with an even number of ones, which is the single-parity code of Distance, Detection and Correction. The simplex code is the dual of the (7,4) code, and the extended (8,4) code adds an overall parity bit to the Hamming code.
Table 1. Weight distributions of the small codes used in the chapter, with A_i for i = 0 up to the length n
| Code | |||
|---|---|---|---|
| Repetition | 3 | 1 | 1, 0, 0, 1 |
| Even weight | 3 | 2 | 1, 0, 3, 0 |
| Even weight | 4 | 3 | 1, 0, 6, 0, 1 |
| Repetition | 4 | 1 | 1, 0, 0, 0, 1 |
| (7,4) Hamming | 7 | 4 | 1, 0, 0, 7, 7, 0, 0, 1 |
| (7,3) simplex | 7 | 3 | 1, 0, 0, 0, 7, 0, 0, 0 |
| Extended (8,4) Hamming | 8 | 4 | 1, 0, 0, 0, 14, 0, 0, 0, 1 |
Source: reproduced by ch23_weight_distributions_and_undetected_errors.py.
The weight distribution counts weights from the zero word. A receiver, though, cares about distances from whichever codeword was actually sent, and that codeword is usually not zero. For a linear code the two views agree. Take in the (7,4) code and measure the distance to each of the 16 codewords. The counts by distance come out , the same as the weights. The first codeword at distance 3 is , and the XOR of the two words, , is itself a codeword of weight 3.
Proof. Define the map on . It sends codewords to codewords, since the code is closed under XOR, and applying it twice returns , so it is a one-to-one correspondence of with itself. The distance is the number of positions where the words differ, which is . So matches the codewords at distance from one for one with the codewords of weight .
The theorem is what makes the earlier result hold "whichever codeword was sent". The same translation argument gives a symmetry that several rows of Table 1 share.
Proof. The map is again a one-to-one correspondence of with itself, and it complements every bit, so a codeword of weight goes to one of weight .
The Hamming code, the extended code, the repetition codes and the even-weight code of length 4 all contain and their lists read the same in both directions. The even-weight code of length 3 does not, since has odd weight, and its list is lopsided.
03.The Probability of an Undetected Error
On each bit flips independently with probability , so a particular pattern of weight occurs with probability , the product of flips and non-flips. Combining that with the theorem on undetected patterns gives the formula that Distance, Detection and Correction stated for a code closed under XOR, and that Error-Control Strategies and Performance used for the slip probability.
Proof. Fix the transmitted codeword. Distinct error patterns are distinct outcomes of the channel, so their probabilities add. The error is undetected exactly when is a nonzero codeword, and there are of these of weight , each with probability . Summing over gives the first form. Setting and in Equation 1 gives the same sum plus the term , which is the second form. By the translation theorem the answer is the same for every transmitted codeword.
For the (7,4) code at the three terms are
and their sum is . The weight-3 term carries nearly all of it. Some error occurs with probability , so only a share of the damaged words gets through. At the terms are , and , and the total is . The weight-4 term now matters, because a larger makes heavy patterns less rare.
The formula has a second reading that explains much of what follows. Group the error patterns by weight. On the chance that the error has weight exactly is , and of the patterns of that weight, are missed. Writing
splits each term into two factors. The first is the share of weight- patterns that the check misses, and the second is how likely an error of weight is. For the (7,4) code the shares are 0 at weights 1 and 2, 7 of 35 at weights 3 and 4, 0 at weights 5 and 6, and 1 at weight 7. A small puts nearly all of its probability on errors of weight 1 and 2, where the share is zero, and that is why is so small there. As grows, the likely weights move up toward , and the sum leans on whatever shares sit at those weights.
Both forms rest on the channel model. makes every pattern of a given weight equally likely, and Equation 3 needs only that much, since it multiplies the chance of weight by the share of weight- patterns that are missed. A real bus or serial link often breaks that assumption. A glitch near a clock edge or a short burst of noise flips several neighboring bits together, so patterns whose flips lie close together become more likely than scattered ones. The answer then depends on which codewords happen to be bursts, and for the (7,4) code they can be counted. Call a nonzero pattern a short burst when all its flips fall within four neighboring positions. There are 39 short bursts, and every one of weight 1 or 2 is caught. Of the 13 of weight 3, two are codewords, and , a share of against for all patterns of weight 3. The 4 of weight 4 are the runs of four neighboring flips, and two of them, and , are codewords, a share of against for all patterns of weight 4. In all, 4 of the 39 short bursts are missed, a share of , below the of a pattern drawn evenly from all 127 nonzero ones. So short bursts are missed less often than random patterns of the same weight, with one exception in this code, the runs of four, which are missed more than twice as often. The weight distribution cannot see any of that, because it counts codewords without recording where their ones sit. Codes built around where the ones sit, and the guarantees against bursts that come with them, are the subject of Part IV.
The extreme case is , where the channel output carries no information about the input at all.
Proof. At every pattern has probability , whatever its weight. The sum in Equation 2 counts the nonzero codewords, so it is , and .
There is a second way to read the result. At the received word is equally likely to be any of the words, so the check is fooled when lands on one of the codewords other than the one sent. For the (7,4) code that is , just under . Of the damaged words, are missed, because at every nonzero pattern is equally likely and 15 of the 127 are codewords. This is where the rule of thumb " check bits miss one error in " comes from. Error-Control Strategies and Performance flagged it as a heuristic, not a theorem, and the rest of the chapter asks when it is an honest upper bound.
Table 2 evaluates Equation 2 for four codes, and Figure 4 plots the two Hamming codes on log scales.
Table 2. The probability of an undetected error at three bit error probabilities, beside the level 2 to the power minus r for r check bits
| Code | |||||
|---|---|---|---|---|---|
| Repetition, | 2 | ||||
| Even weight, | 1 | ||||
| (7,4) Hamming | 3 | ||||
| Extended (8,4) | 4 |
Source: reproduced by ch23_weight_distributions_and_undetected_errors.py.
At small the lowest weight dominates. The extended code has no codewords of weight 3, so its leading term is rather than , and at its value is against , for the price of one more bit.
04.The MacWilliams Identity
A code with data bits has codewords. For a word of 64 data bits that is codewords, far too many to list. Its dual code is generated by the rows of the parity-check matrix and has only words, for eight check bits. Florence Jessie MacWilliams proved in 1963 that the weight distribution of a code is determined by that of its dual [1], so the small code is enough. Her identity is the most important single fact about weight distributions, and MacWilliams and Sloane build much of their treatment around it [2].
Linear Codes defined the dual as the set of words with for every , where , and showed in "Theorem: The checks generate the dual" that the rows of span it. Vector Spaces over Finite Fields showed, in "Theorem: A code and its dual fill the length", that its dimension is . Write for its weight distribution.
The proof turns on one sum. For a word , add up over every codeword . Each term is when and when . Figure 5 does this for the repetition code and all eight words . The rows sum to . Every row sums either to 2, the size of the code, or to 0, and the rows that reach 2 are , , and , which is the dual code.
Proof. Let be a generator matrix, so each codeword is for exactly one message of bits. Then , where is the column of dot products of with the rows of . The word lies in exactly when it is orthogonal to every row, which is . In that case every term is and the sum is . Otherwise , and the map is given by the matrix of rank 1. The rank theorem of Matrices and Elimination over Finite Fields says its null space has dimension , so messages give and the other give 1. The terms cancel in pairs and the sum is 0.
The lemma is a sharper form of "Lemma: Half the words have dot product one" from Linear Codes. With it, the identity follows by adding up one double sum in two orders.
Proof. Consider
First sum over with fixed. By Equation 5 the inner sum is for and 0 otherwise, so only the dual words survive and
Now sum over with fixed. Both factors of each term split across the coordinates. The sign is , and the monomial is with and , since each zero of contributes an and each one a . The sum over all words of a product of one factor per coordinate equals the product, over the coordinates, of the sum of that factor over its two values. This is ordinary expansion of brackets. For two coordinates, , with one term for each word . Here the factor at coordinate sums to , so
The coordinates where each give , and the coordinates where each give . Summing over gives by the second form of Equation 1. The two values of agree, and dividing by gives the identity.
The identity deserves a moment. Its right side needs only the weight distribution of , which is numbers, and it returns all numbers of the dual. Neither the generator matrix nor the codewords themselves appear in the answer, only their counts by weight. So two linear codes with the same weight distribution have duals with the same weight distribution, even when the codes are different sets of words. In practice the identity runs in whichever direction saves work, from the smaller of and to the larger, and for a detecting code with few check bits the smaller one is always the dual.
Reading off one coefficient gives a formula for each separately. The coefficient of in is the Krawtchouk number , and
The sum over chooses of the terms from the factors , each bringing a minus sign, and the remaining from the factors . The second worked example uses it to find one coefficient of the simplex code by hand.
05.Checking the Identity on Small Codes
The identity deserves a check on codes small enough to verify directly. The repetition code of length 3 has and . Then
because the odd powers of cancel and the even ones double. Dividing by 2 gives , the distribution of the even-weight code of length 3, which is indeed the dual. Going back, the even-weight code has and , and
which divided by 4 returns . The transform is its own inverse up to the scale factor, as it must be, since the dual of the dual is the original code.
The (7,4) code is the first real test. Its enumerator transforms to
The first bracket keeps the even powers of twice, which gives the coefficients for up to . The second bracket has the common factor times , so it equals , with coefficients . The sum is , and dividing by 16 leaves
Every nonzero word of the dual has weight 4, which is "Theorem: The dual of the Hamming code has constant weight" from Linear Codes, now recovered by algebra alone. Transforming the simplex enumerator and dividing by 8 returns .
Two more cases complete Table 1. The extended (8,4) code transforms, after division by 16, back to its own distribution , and in fact it is its own dual. The even-weight code of length 4 gives
which divided by 8 is the repetition code of length 4, .
06.Undetected Errors from the Dual Code
The identity runs in both directions. Applied to , whose dual is , it reads . Substituting into the second form of Equation 2 gives from the small code.
Proof. Put and . Then and , so . Subtracting , as Equation 2 does, gives the result.
For the (7,4) code the dual has and , so
At , , the bracket gives , and . The difference is , the same value the direct sum gave. At the two terms are and , and the difference is . Wolf, Michelson and Levesque studied the probability of undetected error for linear block codes [3], and the route pays off exactly where the direct sum is hopeless, a long code with few checks.
Finding the needs nothing beyond the parity-check matrix. The rows of generate , so its words are the XORs of every subset of those rows. Listing the subsets, counting the ones in each XOR and tallying the counts gives in steps, however long the code is. For the (7,4) code the three rows of and their four XOR combinations are the seven simplex words, each of weight 4. A code with 32 checks has dual words at any length, a loop a computer can finish, while the code itself may have more codewords than could ever be listed.
07.Proper Codes and Good Codes
Table 2 shows each code below its level at , as Equation 4 guarantees. The question is what happens between and . A designer would like the miss rate never to exceed the rule of thumb, and ideally to fall steadily as the channel improves.
The interval stops at for a reason. A channel that flips each bit with probability is the same as a channel with flip probability followed by an inverter, so a sensible receiver would invert every bit and work on the better channel.
The question of which codes obey the bound was studied by Leung-Yan-Cheong and Hellman [4], and further properties of the undetected-error probability of linear codes by Leung-Yan-Cheong, Barnes and Friedman [5]. Two results are short enough to prove here.
Proof. If never decreases on , its largest value there is by Equation 4, which is below .
Proof. Differentiate the dual form . The first term gives and the second gives , so
Since on the interval, cubing gives , and the derivative is never negative.
Evaluated at every multiple of from 0 to , which is the grid the script uses throughout, both the (7,4) and the extended (8,4) code reach their largest value at . The inequality in the proof generalizes to a simple sufficient condition on the dual.
Proof. For , , so . With and , . The dual has nonzero words, so Equation 8 gives .
The lemma is sufficient, not necessary. The smallest nonzero dual weight is 4 for the (7,4) code, at least , and 4 for the extended code, at least 4, so both are good by the lemma as well. Not every code passes.
Take the (8,5) code whose codewords are five data bits followed by their parity bit written three times. Its parity-check matrix has the rows , and , which say that the last three bits agree and that the eighth bit is the parity of the first five. A data word of even weight , or gives a codeword of the same weight, in , and ways. A data word of odd weight , or adds three ones, giving weights , and in , and ways. The distribution is . The dual, from the span of the three rows, is , and the MacWilliams identity gives the same list. Its smallest nonzero weight is 2, far short of .
The code also has three check bits, so its level is . At , though, , which exceeds . The largest value on the grid is at , after which the curve falls back to at , as Figure 6 shows. The trouble is the 10 codewords of weight 2. They make 10 of the 28 double-error patterns undetectable, a share of , and on a noisy channel double errors are common. The code is neither proper nor good.
Equation 3 says why in one line. The share at weight 2 is against the level , and at an error of weight 2 is among the likeliest outcomes, since the expected number of flips is . The (7,4) code also has shares above , 7 of 35 at weights 3 and 4, but it pairs them with zero shares at weights 1, 2, 5 and 6, and the weighted sum never reaches the level. Goodness is a property of the whole list, not of any one entry in it.
The triplicated-parity code is not an oddity hunted down for the purpose. The script enumerates every parity-check matrix of three independent rows built from nonzero columns of three bits, with repeated columns allowed, and keeps the codes in which no position is zero in every codeword. Lengths 4, 5, 6 and 7 give 1, 3, 7 and 14 distinct weight distributions, and none rises above anywhere on the grid. Length 8 gives 24 distributions, and two of them do. One is the triplicated-parity code. The other is , whose largest value is at . The smallest failure in this family is at length 8, and both failures share ten codewords of weight 2.
08.Why the Length Matters
A designer rarely gets to pick the length freely. The data come in bytes or bus widths, and the code is cut to fit, as Hamming Codes and Perfect Codes did for one byte by deleting columns of . Keep the three checks of and only its first columns, for to 7, and four codes result. Modifying and Combining Codes treats this operation in general. Here the four codes serve only as a family of lengths sharing three checks, and Table 3 lists them.
Table 3. The codes formed by the first n columns of H_3 in counting order, all with three parity checks
| 4 | 1, 0, 0, 1, 0 | ||
| 5 | 1, 0, 0, 2, 1, 0 | ||
| 6 | 1, 0, 0, 4, 3, 0, 0 | ||
| 7 | 1, 0, 0, 7, 7, 0, 0, 1 |
Source: reproduced by ch23_weight_distributions_and_undetected_errors.py.
The code at has the codewords , and besides zero. The code of Distance, Detection and Correction has different words, , and , but reading its positions in the order 3, 1, 4, 2, 5 turns them into exactly these three, so the two codes are equivalent, the same code up to a reordering of positions. A reordering changes no weight, so both have the weights 3, 3 and 4 and the same found there. Every curve rises along the grid, as Figure 7 shows, and each stays under .
Proof. The case is the earlier theorem. At the only nonzero codeword is , so and for . At , , and the terms in cancel in the derivative, leaving . This vanishes only where , at , so it is positive on . At the dual distribution is again , so , and
which is nonnegative because .
The code at hides a defect that the weight distribution exposes only through the dual. Its last column is , the only column with a 1 in the top row, so the top check forces and the fourth bit is 0 in every codeword. That bit carries no data and a flip there is always caught, but it is wasted. The dual distribution flags it with .
Proof. The dot product is the single bit . It is 0 for every codeword exactly when is orthogonal to all of , which is the definition of . The only words of weight 1 are the unit words, so counts such positions.
Single parity shows a second effect of length, one that depends on whether is even or odd. The dual of the even-weight code is the repetition code , so Equation 8 gives . At the double errors carry nearly all of it. At there are pairs, , and the weight-2 term alone is , a share of . At there are 36 pairs, , and the weight-2 share is . The ratio of the two values is , which matches the ratio of pairs times one more factor , since . One more bit of length raises the miss rate by that factor, almost entirely through the eight new pairs it creates.
The parity of the length matters for a different pattern. No odd-weight pattern is ever a codeword of an even-weight code, at any length. The all-ones pattern, which flips every bit, has weight . On a bus of even width it is a codeword and passes the check, and on a bus of odd width it is caught. An inverted bus is a realistic fault, since a driver with the wrong polarity flips every line at once, so a check that passes it at width 8 and catches it at width 9 behaves differently for a reason that has nothing to do with .
Goodness itself can change with one bit of length. Take five checks and let the columns of be the numbers to written in five bits. At the column is the only one with a 1 in the top row, so position 16 is dead, and the first 15 columns have only four independent checks between them. The family proper starts at and ends at the (31,26) Hamming code. Table 4 gives the two lowest weights at each length and where the largest value of on sits.
Table 4. The codes whose parity-check columns are the numbers 1 to n in five bits, with their weight-3 and weight-4 counts and where P_ud is largest
| Largest at | Good | |||
|---|---|---|---|---|
| 17 | 36 | 112 | no | |
| 18 | 38 | 126 | no | |
| 19 | 41 | 148 | yes | |
| 20 | 45 | 176 | yes | |
| 21 | 50 | 213 | yes | |
| 22 | 56 | 259 | yes | |
| 23 | 63 | 315 | yes | |
| 24 | 71 | 371 | yes | |
| 25 | 80 | 438 | yes | |
| 26 | 90 | 516 | yes | |
| 27 | 101 | 606 | yes | |
| 28 | 113 | 706 | yes | |
| 29 | 126 | 819 | yes | |
| 30 | 140 | 945 | yes | |
| 31 | 155 | 1085 | yes |
Source: reproduced by ch23_weight_distributions_and_undetected_errors.py.
At the largest value is , which is times the level , and at it is times the level. From on, the largest value is , reached at . At , , the Hamming count. Figure 8 plots 32 times the largest value, so that the level becomes 1.
The lesson for a designer is plain. Two codes with the same checks and nearly the same length can sit on opposite sides of the bound, and no rule of thumb says which side. The only safe course is to compute the weight distribution, or that of the dual, at the exact length that will be built, and evaluate Equation 2 over the whole range of the link may see.
The calculation is cheap. Every code in this family takes its parity-check matrix from the same five rows, cut to the first columns, so the dual at each length comes from five rows and has words. Tallying their weights and putting the tally into Equation 8 gives the whole curve, and Table 4 took fifteen such tallies, one per length. A designer who skips that step and trusts is trusting a heuristic that this family breaks at two of its fifteen lengths.
09.Looking Ahead
Modifying and Combining Codes takes up the operations this chapter used without defining them in general, deleting columns to shorten a code, adding an overall parity bit to extend one, and others such as puncturing, and it shows how each changes the length, dimension and minimum distance. The weight distributions found here are a quick way to check what each operation does to a small code.
The tools of this chapter return in Part IV, Cyclic Codes, CRCs and Burst Errors. A cyclic redundancy check is a long code with few checks, exactly the case where the dual form of the undetected-error probability is the only practical route, and the CRC chapters there compare polynomials by their weight distributions at each message length, since this chapter found that goodness can change with a single bit of length.
10.Worked Examples
11.Exercises
References
- [1]MacWilliams, Jessie (1963). “A Theorem on the Distribution of Weights in a Systematic Code.” Bell System Technical Journal, 42(1), pp. 79–94. doi:10.1002/j.1538-7305.1963.tb04003.x
- [2]MacWilliams, F. Jessie and Sloane, Neil J. A. (1977). “The Theory of Error-Correcting Codes.” North-Holland. doi:10.1016/S0924-6509(08)X7030-8
- [3]Wolf, J. K. and Michelson, A. M. and Levesque, A. H. (1982). “On the Probability of Undetected Error for Linear Block Codes.” IEEE Transactions on Communications, 30(2), pp. 317–325. doi:10.1109/TCOM.1982.1095473
- [4]Leung-Yan-Cheong, S. K. and Hellman, M. E. (1976). “Concerning a Bound on Undetected Error Probability.” IEEE Transactions on Information Theory, 22(2), pp. 235–237. doi:10.1109/TIT.1976.1055515
- [5]Leung-Yan-Cheong, S. K. and Barnes, E. R. and Friedman, D. U. (1979). “On Some Properties of the Undetected Error Probability of Linear Codes.” IEEE Transactions on Information Theory, 25(1), pp. 110–112. doi:10.1109/TIT.1979.1055991
— Anirban
Hardware–software at the seam where compilers meet microcode.