Paper
Part IILinear Block Codes

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 rr check bits miss about one error in 2r2^r. 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 cc crosses a channel that flips each bit with probability pp, and the receiver gets r=c⊕er = c \oplus e, where ee is the error pattern, with a 1 in each flipped position. A syndrome unit computes s=HrTs = H r^{\mathsf T} 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 rr to the user as correct.

With the columns of HH in counting order, column jj is the number jj in three bits, and the rows read

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}.

The syndrome of a pattern is the bitwise XOR of the columns at its ones. The single error 00100000010000 hits position 3 and gives s=011s = 011, which raises the flag. The double error 01001000100100 gives 010⊕101=111010 \oplus 101 = 111, and the triple error 00001110000111 gives 101⊕110⊕111=100101 \oplus 110 \oplus 111 = 100, so both are caught. The triple error 11100001110000 is different. Its columns are 001001, 010010 and 011011, and their XOR is 000000. The flag stays down. So it does for 10011001001100, whose columns 001⊕100⊕101001 \oplus 100 \oplus 101 also cancel, for 00011110001111 and for 11111111111111. Figure 2 lays the seven patterns beside the matrix.

The parity-check matrix H of the (7,4) Hamming code beside seven error patterns and their syndromes. Column j of H is the number j written in three bits, so the rows of H read 0001111, 0110011 and 1010101. The syndrome of an error pattern is the sum, bit by bit without carries, of the columns at its 1s. The patterns 0010000, 0100100 and 0000111 have syndromes 011, 111 and 100 and are caught. The patterns 1110000, 1001100, 0001111 and 1111111 all have syndrome 000 and are missed, because each is a codeword. parity-check matrix H 1234567 0001111 0110011 1010101 column j is j in binary, read from top to bottom syndrome 000 means every check is satisfied error pattern columns added syndrome verdict 0010000011011 0100100010 + 101111 0000111101 + 110 + 111100 1110000001 + 010 + 011000 1001100001 + 100 + 101000 0001111100 + 101 + 110 + 111000 1111111all seven columns000 caught caught caught missed missed missed missed
Figure 2. Seven error patterns and their syndromes under the (7,4) Hamming code. The four with syndrome 000 are codewords, and the detector misses them.

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 GF(2)\mathrm{GF}(2) distributes over XOR, so HrT=HcT⊕HeTH r^{\mathsf T} = H c^{\mathsf T} \oplus H e^{\mathsf T}. Every codeword satisfies HcT=0H c^{\mathsf T} = 0, which leaves HeTH e^{\mathsf T}. The code is the null space of HH, so HeT=0H e^{\mathsf T} = 0 holds exactly when e∈Ce \in C. The condition mentions ee alone, so it is the same for every transmitted codeword. ■\blacksquare

The theorem turns a question about a channel into a question about a list. Of the 27−1=1272^7 - 1 = 127 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 H3H_3 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.

Stacked bar chart of the 127 nonzero error patterns of 7 bits, grouped by weight, each bar split into the patterns the (7,4) Hamming code catches and those it misses. The counts are 7 of weight 1 with 0 missed, 21 of weight 2 with 0 missed, 35 of weight 3 with 7 missed, 35 of weight 4 with 7 missed, 21 of weight 5 with 0 missed, 7 of weight 6 with 0 missed, 1 of weight 7 with 1 missed. Every pattern of weight 1 or 2 is caught, and the 15 missed patterns are exactly the nonzero codewords, 7 of weight 3, 7 of weight 4 and 1 of weight 7. weight of the error pattern, the number of flipped bits number of error patterns 0 10 20 30 40 1 2 3 4 5 6 7 7 21 35 7 missed 35 7 missed 21 7 1 missed caught, syndrome not 000 missed, the pattern is a codeword
Figure 3. The 127 nonzero error patterns of length 7 by weight, split into those the (7,4) code catches and the 15 it misses, which are its nonzero codewords. Data: computed by ch23_charts.py in the companion repository.

02.Counting Codewords by Weight

The numbers of missed patterns in Figure 3, read by weight, are 1,0,0,7,7,0,0,11, 0, 0, 7, 7, 0, 0, 1 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 xx raised to its number of zeros and yy to its number of ones. For the (7,4) Hamming code

W(x,y)=x7+7x4y3+7x3y4+y7.W(x, y) = x^7 + 7 x^4 y^3 + 7 x^3 y^4 + y^7 .

Setting x=y=1x = y = 1 counts the code, W(1,1)=16=24W(1, 1) = 16 = 2^4. The minimum distance is the first nonzero weight with Ai>0A_i > 0, 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 A3=7A_3 = 7 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 jj is the number jj in binary. So the weight-3 codewords are the sets of three positions {a,b,c}\{a, b, c\} with a⊕b=ca \oplus b = c, such as {1,2,3}\{1, 2, 3\} and {1,4,5}\{1, 4, 5\}, which are the patterns 11100001110000 and 10011001001100 met earlier. Choose any two distinct positions aa and bb, in one of (72)=21\binom{7}{2} = 21 ways. Their XOR cc is nonzero because a≠ba \ne b, at most 7 because both fit in three bits, and different from aa and from bb because neither is zero. Each set of three is reached from three of its pairs, so there are 21/3=721 / 3 = 7 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 A4=A3=7A_4 = A_3 = 7, A5=A2=0A_5 = A_2 = 0, A6=A1=0A_6 = A_1 = 0 and A7=A0=1A_7 = A_0 = 1.

Table 1 lists the codes the chapter uses. The repetition code of length 3 is {000,111}\{000, 111\}. The even-weight code of length nn 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

CodennkkA0,A1,…,AnA_0, A_1, \dots, A_n
Repetition311, 0, 0, 1
Even weight321, 0, 3, 0
Even weight431, 0, 6, 0, 1
Repetition411, 0, 0, 0, 1
(7,4) Hamming741, 0, 0, 7, 7, 0, 0, 1
(7,3) simplex731, 0, 0, 0, 7, 0, 0, 0
Extended (8,4) Hamming841, 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 c=0110011c = 0110011 in the (7,4) code and measure the distance to each of the 16 codewords. The counts by distance come out 1,0,0,7,7,0,0,11, 0, 0, 7, 7, 0, 0, 1, the same as the weights. The first codeword at distance 3 is 00101100010110, and the XOR of the two words, 01001010100101, is itself a codeword of weight 3.

Proof. Define the map τ(c′)=c⊕c′\tau(c') = c \oplus c' on CC. It sends codewords to codewords, since the code is closed under XOR, and applying it twice returns c′c', so it is a one-to-one correspondence of CC with itself. The distance d(c,c′)d(c, c') is the number of positions where the words differ, which is w(c⊕c′)=w(τ(c′))w(c \oplus c') = w(\tau(c')). So τ\tau matches the codewords at distance ii from cc one for one with the codewords of weight ii. ■\blacksquare

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 c↦c⊕1c \mapsto c \oplus \mathbf{1} is again a one-to-one correspondence of CC with itself, and it complements every bit, so a codeword of weight ii goes to one of weight n−in - i. ■\blacksquare

The Hamming code, the extended code, the repetition codes and the even-weight code of length 4 all contain 1\mathbf{1} and their lists read the same in both directions. The even-weight code of length 3 does not, since 111111 has odd weight, and its list 1,0,3,01, 0, 3, 0 is lopsided.

03.The Probability of an Undetected Error

On BSC(p)\text{BSC}(p) each bit flips independently with probability pp, so a particular pattern ee of weight ii occurs with probability pi(1−p)n−ip^i (1 - p)^{n - i}, the product of ii flips and n−in - i 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 ee is a nonzero codeword, and there are AiA_i of these of weight ii, each with probability pi(1−p)n−ip^i (1 - p)^{n - i}. Summing over i≥1i \ge 1 gives the first form. Setting x=1−px = 1 - p and y=py = p in Equation 1 gives the same sum plus the i=0i = 0 term (1−p)n(1 - p)^n, which is the second form. By the translation theorem the answer is the same for every transmitted codeword. ■\blacksquare

For the (7,4) code at p=0.01p = 0.01 the three terms are

7p3(1−p)4=6.72417×10−6,7p4(1−p)3=6.79209×10−8,p7=10−14,7 p^3 (1 - p)^4 = 6.72417 \times 10^{-6}, \qquad 7 p^4 (1 - p)^3 = 6.79209 \times 10^{-8}, \qquad p^7 = 10^{-14},

and their sum is Pud(0.01)=6.79209×10−6P_{ud}(0.01) = 6.79209 \times 10^{-6}. The weight-3 term carries nearly all of it. Some error occurs with probability 1−0.997=0.06793471 - 0.99^7 = 0.0679347, so only a share 9.998×10−59.998 \times 10^{-5} of the damaged words gets through. At p=0.1p = 0.1 the terms are 0.00459270.0045927, 0.00051030.0005103 and 10−710^{-7}, and the total is 0.00510310.0051031. The weight-4 term now matters, because a larger pp makes heavy patterns less rare.

The formula has a second reading that explains much of what follows. Group the error patterns by weight. On BSC(p)\text{BSC}(p) the chance that the error has weight exactly ii is (ni)pi(1−p)n−i\binom{n}{i} p^i (1 - p)^{n - i}, and of the (ni)\binom{n}{i} patterns of that weight, AiA_i are missed. Writing

Pud(p)=∑i=1nAi(ni)⋅(ni)pi(1−p)n−iP_{ud}(p) = \sum_{i=1}^{n} \frac{A_i}{\binom{n}{i}} \cdot \binom{n}{i} p^i (1 - p)^{n - i}
(3)

splits each term into two factors. The first is the share of weight-ii patterns that the check misses, and the second is how likely an error of weight ii 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 pp puts nearly all of its probability on errors of weight 1 and 2, where the share is zero, and that is why PudP_{ud} is so small there. As pp grows, the likely weights move up toward npnp, and the sum leans on whatever shares sit at those weights.

Both forms rest on the channel model. BSC(p)\text{BSC}(p) makes every pattern of a given weight equally likely, and Equation 3 needs only that much, since it multiplies the chance of weight ii by the share of weight-ii 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, 11100001110000 and 00101100010110, a share of 2/13=0.1542/13 = 0.154 against 7/35=0.27/35 = 0.2 for all patterns of weight 3. The 4 of weight 4 are the runs of four neighboring flips, and two of them, 01111000111100 and 00011110001111, are codewords, a share of 1/21/2 against 7/357/35 for all patterns of weight 4. In all, 4 of the 39 short bursts are missed, a share of 0.1030.103, below the 15/127=0.11815/127 = 0.118 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 p=1/2p = 1/2, where the channel output carries no information about the input at all.

Proof. At p=1/2p = 1/2 every pattern has probability (1/2)i(1/2)n−i=2−n(1/2)^i (1/2)^{n-i} = 2^{-n}, whatever its weight. The sum in Equation 2 counts the 2k−12^k - 1 nonzero codewords, so it is (2k−1)/2n(2^k - 1) / 2^n, and 2k/2n=2−r2^k / 2^n = 2^{-r}. ■\blacksquare

There is a second way to read the result. At p=1/2p = 1/2 the received word rr is equally likely to be any of the 2n2^n words, so the check is fooled when rr lands on one of the 2k−12^k - 1 codewords other than the one sent. For the (7,4) code that is 15/128=0.117187515/128 = 0.1171875, just under 2−3=0.1252^{-3} = 0.125. Of the damaged words, 15/127=0.1181115/127 = 0.11811 are missed, because at p=1/2p = 1/2 every nonzero pattern is equally likely and 15 of the 127 are codewords. This is where the rule of thumb "rr check bits miss one error in 2r2^r" 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

Coderrp=0.01p = 0.01p=0.1p = 0.1p=1/2p = 1/22−r2^{-r}
Repetition, n=3n = 321×10−61 \times 10^{-6}0.0010.0011/81/80.250.25
Even weight, n=4n = 415.8807×10−45.8807 \times 10^{-4}0.04870.04877/16=0.43757/16 = 0.43750.50.5
(7,4) Hamming36.79209×10−66.79209 \times 10^{-6}0.00510310.005103115/128=0.117187515/128 = 0.11718750.1250.125
Extended (8,4)41.34483×10−71.34483 \times 10^{-7}9.1855×10−49.1855 \times 10^{-4}15/256=0.0585937515/256 = 0.058593750.06250.0625

Source: reproduced by ch23_weight_distributions_and_undetected_errors.py.

Probability of an undetected error against the bit error probability p, both on log scales, for the (7,4) Hamming code and the extended (8,4) Hamming code. Both curves rise steadily from p = 0.001 to p = 0.5. At p = 0.01 they are 6.79 times 10 to the minus 6 and 1.34 times 10 to the minus 7, at p = 0.1 they are 0.0051031 and 0.00091855, and at p = 1/2 they reach 15/128 and 15/256, just under the dashed levels 2 to the minus 3 and 2 to the minus 4. bit error probability p, log scale probability of an undetected error 10−12 10−9 10−6 10−3 1 0.001 0.01 0.1 0.5 6.79 × 10−6 1.34 × 10−7 2−3 = 0.125 2−4 = 0.0625 (7,4) Hamming code extended (8,4) code rule of thumb 2−r
Figure 4. The probability of an undetected error for the (7,4) and extended (8,4) Hamming codes. Each extra check bit roughly halves the value at p = 1/2, and the extended code's minimum distance of 4 lowers it far more at small p. Data: computed by ch23_charts.py in the companion repository.

At small pp the lowest weight dominates. The extended code has no codewords of weight 3, so its leading term is 14p414 p^4 rather than 7p37 p^3, and at p=0.01p = 0.01 its value is 1.34483×10−71.34483 \times 10^{-7} against 6.79209×10−66.79209 \times 10^{-6}, for the price of one more bit.

04.The MacWilliams Identity

A code with kk data bits has 2k2^k codewords. For a word of 64 data bits that is 2642^{64} codewords, far too many to list. Its dual code is generated by the rr rows of the parity-check matrix and has only 2r2^r words, 28=2562^8 = 256 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 C⊥C^{\perp} as the set of words uu with u⋅c=0u \cdot c = 0 for every c∈Cc \in C, where u⋅c=u1c1⊕⋯⊕uncnu \cdot c = u_1 c_1 \oplus \dots \oplus u_n c_n, and showed in "Theorem: The checks generate the dual" that the rows of HH span it. Vector Spaces over Finite Fields showed, in "Theorem: A code and its dual fill the length", that its dimension is n−kn - k. Write B0,…,BnB_0, \dots, B_n for its weight distribution.

The proof turns on one sum. For a word uu, add up (−1)u⋅c(-1)^{u \cdot c} over every codeword cc. Each term is +1+1 when u⋅c=0u \cdot c = 0 and −1-1 when u⋅c=1u \cdot c = 1. Figure 5 does this for the repetition code {000,111}\{000, 111\} and all eight words uu. The rows sum to 2,0,0,2,0,2,2,02, 0, 0, 2, 0, 2, 2, 0. Every row sums either to 2, the size of the code, or to 0, and the rows that reach 2 are 000000, 011011, 101101 and 110110, which is the dual code.

The sign grid behind the MacWilliams identity for the repetition code of length 3, whose codewords are 000 and 111. Each of the 8 rows is a word u of 3 bits, and each entry is minus 1 raised to the power u dot c for the codeword c at the head of its column. The column for c = 000 is all plus 1, and the column for c = 111 is plus 1 when u has even weight and minus 1 when it has odd weight. The row sums are 2, 0, 0, 2, 0, 2, 2 and 0, for u = 000 to 111. The four rows that sum to 2, which are 000, 011, 101 and 110, are highlighted: they are the even-weight words, the dual code of the repetition code. word u c = 000 c = 111 row sum 000001010011 100101110111 +1+1+1+1 +1+1+1+1 +1−1−1+1 −1+1+1−1 2 0 0 2 0 2 2 0 each entry is (−1) raised to the power u · c, the dot product taken mod 2 A row sums to 2, the size of the code, when u · c is 0 for every codeword c. A row sums to 0 when u · c is 1 for exactly half the codewords. The highlighted rows, 000 011 101 110 are the even-weight words, the dual of the code {000, 111}.
Figure 5. The sign grid behind the MacWilliams identity for the repetition code of length 3. A row sums to the size of the code when u is in the dual, and to zero otherwise.

Proof. Let GG be a k×nk \times n generator matrix, so each codeword is c=mGc = m G for exactly one message mm of kk bits. Then u⋅c=mGuT=m⋅au \cdot c = m G u^{\mathsf T} = m \cdot a, where a=GuTa = G u^{\mathsf T} is the column of kk dot products of uu with the rows of GG. The word uu lies in C⊥C^{\perp} exactly when it is orthogonal to every row, which is a=0a = 0. In that case every term is (−1)0=1(-1)^0 = 1 and the sum is 2k=∣C∣2^k = |C|. Otherwise a≠0a \ne 0, and the map m↦m⋅am \mapsto m \cdot a is given by the 1×k1 \times k matrix aTa^{\mathsf T} of rank 1. The rank theorem of Matrices and Elimination over Finite Fields says its null space has dimension k−1k - 1, so 2k−12^{k-1} messages give m⋅a=0m \cdot a = 0 and the other 2k−2k−1=2k−12^k - 2^{k-1} = 2^{k-1} give 1. The terms cancel in pairs and the sum is 0. ■\blacksquare

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

S=∑u∈GF(2)n  ∑c∈C(−1)u⋅c x n−w(u) y w(u).S = \sum_{u \in \mathrm{GF}(2)^n} \; \sum_{c \in C} (-1)^{u \cdot c} \, x^{\,n - w(u)} \, y^{\,w(u)} .

First sum over cc with uu fixed. By Equation 5 the inner sum is ∣C∣|C| for u∈C⊥u \in C^{\perp} and 0 otherwise, so only the dual words survive and

S=∣C∣∑u∈C⊥x n−w(u) y w(u)=∣C∣ WC⊥(x,y).S = |C| \sum_{u \in C^{\perp}} x^{\,n - w(u)} \, y^{\,w(u)} = |C| \, W_{C^{\perp}}(x, y) .

Now sum over uu with cc fixed. Both factors of each term split across the coordinates. The sign is (−1)u1c1⊕⋯⊕uncn=∏i(−1)uici(-1)^{u_1 c_1 \oplus \dots \oplus u_n c_n} = \prod_i (-1)^{u_i c_i}, and the monomial is ∏if(ui)\prod_i f(u_i) with f(0)=xf(0) = x and f(1)=yf(1) = y, since each zero of uu contributes an xx and each one a yy. The sum over all 2n2^n words uu 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, (a0+a1)(b0+b1)=a0b0+a0b1+a1b0+a1b1(a_0 + a_1)(b_0 + b_1) = a_0 b_0 + a_0 b_1 + a_1 b_0 + a_1 b_1, with one term for each word u1u2u_1 u_2. Here the factor at coordinate ii sums to x+(−1)ciyx + (-1)^{c_i} y, so

∑u(−1)u⋅c x n−w(u) y w(u)=∏i=1n(x+(−1)ciy)=(x+y) n−w(c) (x−y) w(c).\sum_{u} (-1)^{u \cdot c} \, x^{\,n - w(u)} \, y^{\,w(u)} = \prod_{i=1}^{n} \bigl( x + (-1)^{c_i} y \bigr) = (x + y)^{\,n - w(c)} \, (x - y)^{\,w(c)} .

The n−w(c)n - w(c) coordinates where ci=0c_i = 0 each give x+yx + y, and the w(c)w(c) coordinates where ci=1c_i = 1 each give x−yx - y. Summing over cc gives S=WC(x+y,x−y)S = W_C(x + y, x - y) by the second form of Equation 1. The two values of SS agree, and dividing by ∣C∣|C| gives the identity. ■\blacksquare

The identity deserves a moment. Its right side needs only the weight distribution of CC, which is n+1n + 1 numbers, and it returns all n+1n + 1 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 CC and C⊥C^{\perp} 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 BjB_j separately. The coefficient of xn−jyjx^{n-j} y^j in (x+y)n−i(x−y)i(x + y)^{n-i} (x - y)^i is the Krawtchouk number Kj(i)K_j(i), and

Bj=1∣C∣∑i=0nAi Kj(i),Kj(i)=∑s(−1)s(is)(n−ij−s).B_j = \frac{1}{|C|} \sum_{i=0}^{n} A_i \, K_j(i), \qquad K_j(i) = \sum_{s} (-1)^s \binom{i}{s} \binom{n - i}{j - s} .
(7)

The sum over ss chooses ss of the yy terms from the ii factors x−yx - y, each bringing a minus sign, and the remaining j−sj - s from the n−in - i factors x+yx + y. 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 W=x3+y3W = x^3 + y^3 and ∣C∣=2|C| = 2. Then

W(x+y,x−y)=(x+y)3+(x−y)3=2x3+6xy2,W(x + y, x - y) = (x + y)^3 + (x - y)^3 = 2x^3 + 6 x y^2 ,

because the odd powers of yy cancel and the even ones double. Dividing by 2 gives x3+3xy2x^3 + 3 x y^2, the distribution 1,0,3,01, 0, 3, 0 of the even-weight code of length 3, which is indeed the dual. Going back, the even-weight code has W=x3+3xy2W = x^3 + 3 x y^2 and ∣C∣=4|C| = 4, and

(x+y)3+3(x+y)(x−y)2=4x3+4y3,(x + y)^3 + 3 (x + y)(x - y)^2 = 4x^3 + 4y^3 ,

which divided by 4 returns 1,0,0,11, 0, 0, 1. 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

W(x+y,x−y)=[(x+y)7+(x−y)7]+7[(x+y)4(x−y)3+(x+y)3(x−y)4].W(x + y, x - y) = \bigl[(x + y)^7 + (x - y)^7\bigr] + 7 \bigl[(x + y)^4 (x - y)^3 + (x + y)^3 (x - y)^4\bigr] .

The first bracket keeps the even powers of yy twice, which gives the coefficients 2,0,42,0,70,0,14,02, 0, 42, 0, 70, 0, 14, 0 for y0y^0 up to y7y^7. The second bracket has the common factor (x+y)3(x−y)3=(x2−y2)3(x + y)^3 (x - y)^3 = (x^2 - y^2)^3 times (x+y)+(x−y)=2x(x + y) + (x - y) = 2x, so it equals 14x(x2−y2)314 x (x^2 - y^2)^3, with coefficients 14,0,−42,0,42,0,−14,014, 0, -42, 0, 42, 0, -14, 0. The sum is 16,0,0,0,112,0,0,016, 0, 0, 0, 112, 0, 0, 0, and dividing by 16 leaves

WC⊥(x,y)=x7+7x3y4.W_{C^{\perp}}(x, y) = x^7 + 7 x^3 y^4 .

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 1,0,0,7,7,0,0,11, 0, 0, 7, 7, 0, 0, 1.

Two more cases complete Table 1. The extended (8,4) code transforms, after division by 16, back to its own distribution 1,0,0,0,14,0,0,0,11, 0, 0, 0, 14, 0, 0, 0, 1, and in fact it is its own dual. The even-weight code of length 4 gives

(x+y)4+6(x+y)2(x−y)2+(x−y)4=8x4+8y4,(x + y)^4 + 6 (x + y)^2 (x - y)^2 + (x - y)^4 = 8x^4 + 8y^4 ,

which divided by 8 is the repetition code of length 4, 1,0,0,0,11, 0, 0, 0, 1.

06.Undetected Errors from the Dual Code

The identity runs in both directions. Applied to C⊥C^{\perp}, whose dual is CC, it reads WC(x,y)=WC⊥(x+y,x−y)/2n−kW_C(x, y) = W_{C^{\perp}}(x + y, x - y) / 2^{n-k}. Substituting into the second form of Equation 2 gives PudP_{ud} from the small code.

Proof. Put x=1−px = 1 - p and y=py = p. Then x+y=1x + y = 1 and x−y=1−2px - y = 1 - 2p, so WC(1−p,p)=2−(n−k)∑jBj 1n−j(1−2p)jW_C(1 - p, p) = 2^{-(n-k)} \sum_j B_j \, 1^{n-j} (1 - 2p)^j. Subtracting (1−p)n(1 - p)^n, as Equation 2 does, gives the result. ■\blacksquare

For the (7,4) code the dual has B0=1B_0 = 1 and B4=7B_4 = 7, so

Pud(p)=18(1+7(1−2p)4)−(1−p)7.P_{ud}(p) = \tfrac{1}{8} \bigl( 1 + 7 (1 - 2p)^4 \bigr) - (1 - p)^7 .

At p=0.01p = 0.01, (0.98)4=0.92236816(0.98)^4 = 0.92236816, the bracket gives 0.932072140.93207214, and (0.99)7=0.93206535(0.99)^7 = 0.93206535. The difference is 6.79209×10−66.79209 \times 10^{-6}, the same value the direct sum gave. At p=0.1p = 0.1 the two terms are 0.48340.4834 and 0.47829690.4782969, and the difference is 0.00510310.0051031. 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 BjB_j needs nothing beyond the parity-check matrix. The rows of HH generate C⊥C^{\perp}, so its 2r2^r words are the XORs of every subset of those rr rows. Listing the subsets, counting the ones in each XOR and tallying the counts gives B0,…,BnB_0, \dots, B_n in 2r2^r steps, however long the code is. For the (7,4) code the three rows of H3H_3 and their four XOR combinations are the seven simplex words, each of weight 4. A code with 32 checks has 2322^{32} 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 2−r2^{-r} at p=1/2p = 1/2, as Equation 4 guarantees. The question is what happens between p=0p = 0 and p=1/2p = 1/2. 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 1/21/2 for a reason. A channel that flips each bit with probability p>1/2p > 1/2 is the same as a channel with flip probability 1−p<1/21 - p < 1/2 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 2−r2^{-r} 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 PudP_{ud} never decreases on [0,1/2][0, 1/2], its largest value there is Pud(1/2)=2−r−2−nP_{ud}(1/2) = 2^{-r} - 2^{-n} by Equation 4, which is below 2−r2^{-r}. ■\blacksquare

Proof. Differentiate the dual form Pud(p)=18(1+7(1−2p)4)−(1−p)7P_{ud}(p) = \tfrac{1}{8}(1 + 7(1 - 2p)^4) - (1 - p)^7. The first term gives 78⋅4(1−2p)3⋅(−2)=−7(1−2p)3\tfrac{7}{8} \cdot 4 (1 - 2p)^3 \cdot (-2) = -7 (1 - 2p)^3 and the second gives +7(1−p)6+7 (1 - p)^6, so

Pud′(p)=7[(1−p)6−(1−2p)3].P_{ud}'(p) = 7 \bigl[ (1 - p)^6 - (1 - 2p)^3 \bigr] .

Since (1−p)2=1−2p+p2≥1−2p≥0(1 - p)^2 = 1 - 2p + p^2 \ge 1 - 2p \ge 0 on the interval, cubing gives (1−p)6≥(1−2p)3(1 - p)^6 \ge (1 - 2p)^3, and the derivative is never negative. ■\blacksquare

Evaluated at every multiple of 0.0010.001 from 0 to 1/21/2, which is the grid the script uses throughout, both the (7,4) and the extended (8,4) code reach their largest value at p=0.500p = 0.500. The inequality in the proof generalizes to a simple sufficient condition on the dual.

Proof. For 0≤p≤1/20 \le p \le 1/2, 0≤1−2p≤(1−p)20 \le 1 - 2p \le (1 - p)^2, so (1−2p)j≤(1−p)2j(1 - 2p)^j \le (1 - p)^{2j}. With 2j≥n2j \ge n and 0≤1−p≤10 \le 1 - p \le 1, (1−p)2j≤(1−p)n(1 - p)^{2j} \le (1 - p)^n. The dual has 2r−12^r - 1 nonzero words, so Equation 8 gives Pud(p)≤2−r(1+(2r−1)(1−p)n)−(1−p)n=2−r(1−(1−p)n)P_{ud}(p) \le 2^{-r}\bigl(1 + (2^r - 1)(1 - p)^n\bigr) - (1 - p)^n = 2^{-r}\bigl(1 - (1 - p)^n\bigr). ■\blacksquare

The lemma is sufficient, not necessary. The smallest nonzero dual weight is 4 for the (7,4) code, at least 3.53.5, 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 0000001100000011, 0000010100000101 and 1111100111111001, 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 00, 22 or 44 gives a codeword of the same weight, in 11, 1010 and 55 ways. A data word of odd weight 11, 33 or 55 adds three ones, giving weights 44, 66 and 88 in 55, 1010 and 11 ways. The distribution is 1,0,10,0,10,0,10,0,11, 0, 10, 0, 10, 0, 10, 0, 1. The dual, from the span of the three rows, is 1,0,3,0,0,0,3,0,11, 0, 3, 0, 0, 0, 3, 0, 1, and the MacWilliams identity gives the same list. Its smallest nonzero weight is 2, far short of n/2=4n/2 = 4.

The code also has three check bits, so its level is 1/81/8. At p=0.3p = 0.3, though, Pud=0.12897P_{ud} = 0.12897, which exceeds 1/81/8. The largest value on the grid is 0.128990.12899 at p=0.304p = 0.304, after which the curve falls back to 31/256=0.1210937531/256 = 0.12109375 at p=1/2p = 1/2, 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 0.3570.357, 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 0.3570.357 against the level 0.1250.125, and at p=0.3p = 0.3 an error of weight 2 is among the likeliest outcomes, since the expected number of flips is np=2.4np = 2.4. The (7,4) code also has shares above 1/81/8, 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.

Probability of an undetected error against the bit error probability p from 0 to 1/2 for two codes with three parity checks. The (7,4) Hamming code rises steadily to 15/128 at p = 1/2 and stays under the dashed level 1/8. The (8,5) code that sends five data bits and their parity three times rises above 1/8, peaks at 0.12899 near p = 0.304, and falls back to 31/256 at p = 1/2. bit error probability p probability of an undetected error 0 0.02 0.04 0.06 0.08 0.10 0.12 0.14 0 0.1 0.2 0.3 0.4 0.5 0.12899 at p = 0.304 1/8 = 0.125 31/256 15/128 triplicated parity (8,5) (7,4) Hamming code the level 1/8
Figure 6. Two codes with three check bits. The (7,4) Hamming code stays under the level 1/8, while the (8,5) triplicated-parity code rises above it and peaks near p = 0.304. Data: computed by ch23_charts.py in the companion repository.

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 1/81/8 anywhere on the grid. Length 8 gives 24 distributions, and two of them do. One is the triplicated-parity code. The other is 1,0,10,1,5,10,0,5,01, 0, 10, 1, 5, 10, 0, 5, 0, whose largest value is 0.129250.12925 at p=0.302p = 0.302. 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 H4H_4. Keep the three checks of H3H_3 and only its first nn columns, for n=4n = 4 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

nnA0,…,AnA_0, \dots, A_nPud(0.01)P_{ud}(0.01)Pud(1/2)P_{ud}(1/2)
41, 0, 0, 1, 09.9×10−79.9 \times 10^{-7}1/16=0.06251/16 = 0.0625
51, 0, 0, 2, 1, 01.9701×10−61.9701 \times 10^{-6}3/32=0.093753/32 = 0.09375
61, 0, 0, 4, 3, 0, 03.9106×10−63.9106 \times 10^{-6}7/64=0.1093757/64 = 0.109375
71, 0, 0, 7, 7, 0, 0, 16.79209×10−66.79209 \times 10^{-6}15/128=0.117187515/128 = 0.1171875

Source: reproduced by ch23_weight_distributions_and_undetected_errors.py.

The code at n=5n = 5 has the codewords 0111101111, 1001110011 and 1110011100 besides zero. The code C5C_5 of Distance, Detection and Correction has different words, 0110101101, 1011010110 and 1101111011, 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 Pud(0.01)=1.9701×10−6P_{ud}(0.01) = 1.9701 \times 10^{-6} found there. Every curve rises along the grid, as Figure 7 shows, and each stays under 1/81/8.

Probability of an undetected error against the bit error probability p from 0 to 1/2 for the (7,4) Hamming code and for the codes made by keeping only its first 4, 5 or 6 positions, all with the same three parity checks. Every curve rises steadily and ends at p = 1/2 below the dashed level 1/8, at 1/16 for n = 4, 3/32 for n = 5, 7/64 for n = 6, 15/128 for n = 7. bit error probability p probability of an undetected error 0 0.02 0.04 0.06 0.08 0.10 0.12 0.14 0 0.1 0.2 0.3 0.4 0.5 1/8 n = 4, 1/16 n = 5, 3/32 n = 6, 7/64 n = 7, 15/128
Figure 7. The undetected-error probability of the four codes in the shortened Hamming family. Each is proper, so each stays below 1/8. Data: computed by ch23_charts.py in the companion repository.

Proof. The case n=7n = 7 is the earlier theorem. At n=4n = 4 the only nonzero codeword is 11101110, so Pud=p3(1−p)P_{ud} = p^3 (1 - p) and Pud′=p2(3−4p)≥0P_{ud}' = p^2 (3 - 4p) \ge 0 for p≤3/4p \le 3/4. At n=5n = 5, Pud=2p3(1−p)2+p4(1−p)P_{ud} = 2p^3 (1 - p)^2 + p^4 (1 - p), and the terms in p3(1−p)p^3(1-p) cancel in the derivative, leaving Pud′=p2(6(1−p)2−p2)P_{ud}' = p^2 \bigl(6 (1 - p)^2 - p^2\bigr). This vanishes only where 6(1−p)=p\sqrt{6}(1 - p) = p, at p=6/(1+6)≈0.71p = \sqrt{6}/(1 + \sqrt{6}) \approx 0.71, so it is positive on (0,1/2](0, 1/2]. At n=6n = 6 the dual distribution is again 1,0,0,4,3,0,01, 0, 0, 4, 3, 0, 0, so Pud=18(1+4(1−2p)3+3(1−2p)4)−(1−p)6P_{ud} = \tfrac{1}{8}\bigl(1 + 4 (1 - 2p)^3 + 3 (1 - 2p)^4\bigr) - (1 - p)^6, and

Pud′(p)=−3(1−2p)2(2−2p)+6(1−p)5=6(1−p)[(1−p)4−(1−2p)2],P_{ud}'(p) = -3 (1 - 2p)^2 \bigl(2 - 2p\bigr) + 6 (1 - p)^5 = 6 (1 - p) \bigl[ (1 - p)^4 - (1 - 2p)^2 \bigr] ,

which is nonnegative because (1−p)2≥1−2p≥0(1 - p)^2 \ge 1 - 2p \ge 0. ■\blacksquare

The code at n=4n = 4 hides a defect that the weight distribution exposes only through the dual. Its last column is 100100, the only column with a 1 in the top row, so the top check forces c4=0c_4 = 0 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 1,1,3,3,01, 1, 3, 3, 0 flags it with B1=1B_1 = 1.

Proof. The dot product ei⋅ce_i \cdot c is the single bit cic_i. It is 0 for every codeword exactly when eie_i is orthogonal to all of CC, which is the definition of ei∈C⊥e_i \in C^{\perp}. The only words of weight 1 are the unit words, so B1B_1 counts such positions. ■\blacksquare

Single parity shows a second effect of length, one that depends on whether nn is even or odd. The dual of the even-weight code is the repetition code {0,1}\{0, \mathbf{1}\}, so Equation 8 gives Pud(p)=12(1+(1−2p)n)−(1−p)nP_{ud}(p) = \tfrac{1}{2}\bigl(1 + (1 - 2p)^n\bigr) - (1 - p)^n. At p=0.01p = 0.01 the double errors carry nearly all of it. At n=8n = 8 there are (82)=28\binom{8}{2} = 28 pairs, Pud=0.0026368P_{ud} = 0.0026368, and the weight-2 term alone is 0.00263610.0026361, a share of 0.999740.99974. At n=9n = 9 there are 36 pairs, Pud=0.0033566P_{ud} = 0.0033566, and the weight-2 share is 0.999640.99964. The ratio of the two values is 1.2731.273, which matches the ratio of pairs times one more factor 1−p1 - p, since 3628×0.99=1.273\tfrac{36}{28} \times 0.99 = 1.273. 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 nn. 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 pp.

Goodness itself can change with one bit of length. Take five checks and let the columns of HH be the numbers 11 to nn written in five bits. At n=16n = 16 the column 1000010000 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 n=17n = 17 and ends at the (31,26) Hamming code. Table 4 gives the two lowest weights at each length and where the largest value of PudP_{ud} on [0,1/2][0, 1/2] 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

nnA3A_3A4A_4Largest PudP_{ud} atGood
1736112p=0.290p = 0.290no
1838126p=0.309p = 0.309no
1941148p=1/2p = 1/2yes
2045176p=1/2p = 1/2yes
2150213p=1/2p = 1/2yes
2256259p=1/2p = 1/2yes
2363315p=1/2p = 1/2yes
2471371p=1/2p = 1/2yes
2580438p=1/2p = 1/2yes
2690516p=1/2p = 1/2yes
27101606p=1/2p = 1/2yes
28113706p=1/2p = 1/2yes
29126819p=1/2p = 1/2yes
30140945p=1/2p = 1/2yes
311551085p=1/2p = 1/2yes

Source: reproduced by ch23_weight_distributions_and_undetected_errors.py.

At n=17n = 17 the largest value is 0.0342540.034254, which is 1.09611.0961 times the level 2−5=0.031252^{-5} = 0.03125, and at n=18n = 18 it is 1.01881.0188 times the level. From n=19n = 19 on, the largest value is 2−5−2−n2^{-5} - 2^{-n}, reached at p=1/2p = 1/2. At n=31n = 31, A3=155=n(n−1)/6A_3 = 155 = n(n - 1)/6, the Hamming count. Figure 8 plots 32 times the largest value, so that the level 2−52^{-5} becomes 1.

Dot plot of 32 times the largest probability of an undetected error on the grid p = 0 to 1/2, for the codes of length 17 to 31 whose parity-check columns are the numbers 1 to n written in five bits. Two lengths rise above the dashed level 1, n = 17 to 1.0961 with its peak at p = 0.290, and n = 18 to 1.0188 with its peak at p = 0.309. From n = 19 to 31 the largest value sits at p = 1/2 and equals 1 minus 2 raised to the power 5 minus n, which is below 1 by less than 0.0001. The full (31,26) Hamming code is the last dot. length n of the code, all with five parity checks largest value on the grid, times 32 0.96 1.00 1.04 1.08 1.12 17 19 21 23 25 27 29 31 1, the level 2−5 n = 17: 1.0961, peak at p = 0.290 n = 18: 1.0188, peak at p = 0.309 (31,26) rises above the level, not good largest value at p = 1/2, good
Figure 8. Thirty-two times the largest undetected-error probability of the five-check codes of length 17 to 31. Only the two shortest lengths exceed the level 2 to the power minus 5. Data: computed by ch23_charts.py in the companion repository.

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 pp 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 nn columns, so the dual at each length comes from five rows and has 25=322^5 = 32 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 2−r2^{-r} 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. [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. [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. [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. [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. [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.

FeedbackBook modePaper
error-correction-codinglinear-block-codes