Concerning a bound on undetected error probability

In the past, it has generally been assumed that the probability of undetected error for an (n,k) block code, used solely for error detection on a binary symmetric channel, is upper bounded by 2-(n-k). In this correspondence, it is shown that Hamming codes do indeed obey this bound, but that the bound is violated by some more general codes. Examples of linear, cyclic, and Bose-Chaudhuri-Hocquenghem (BCH) codes which do not obey the bound are given.

Illustrations explain the paper; they do not show study data.

AI-generated illustration

↗ Enlarge

The 2-p Bound ConceptClose ×

AI-generated conceptual illustration (digital data blocks represented as grids of binary cubes). It explains the idea and does not show study data.

Open full-size image ↗

Introduction

An (n, k) block code with minimum distance dmin can be used in an error correcting capacity to correct all error patterns of weight [(dmin -1)/2] or less [2] , where [x] denotes the greatest integer less than or equal to X. Alternatively, it can be used in an error detecting capacity to detect all error patterns of weight dmin -1 or less [2] . In the latter case, the guaranteed performance (i.e., assuming all patterns of weight dmin or greater cause undetected errors) is frequently much inferior to the actual performance. For example, a Hamming (127,120) code with dmin = 3 has a guaranteed undetected error rate P (e) I 0.135 when used on a binary symmetric channel (BSC) with crossover probability E = 0.01. This guaranteed performance is greatly inferior to the actual performance, and it will be shown that the bound can easily be strengthened to P (e) < 2 -7 = 0.0078 and that the actual value is P(e) = 0.0011. The reason for the large discrepancy between the guaranteed and the actual performance is that, although the code cannot detect all error patterns of weight 3, it can detect most errors of this, and even higher, weight. The simple but fairly tight bound, P(e) < 2 -7 , is a special case of what has often been assumed to be a general rule for block codes, namely, P(e) < 2 -p , where p = n -k is the number of parity bits [1] . In this correspondence we show that, while a Hamming code used on a BSC with   ½ has P (e) M 2 -p , block codes in general need not obey this bound. We further show that even linear, cyclic, and Bose-Chaudhuri-Hocquenghem (BCH) codes can violate the bound, as can shortened Hamming codes. The "justification" for the 2 -p bound went as follows. Assume that the (n, k) code is used over a totally noisy BSC (i.e.,  = ½). Then, all 2 n possible received sequences are equally likely, and of these only 2 k -1 are codewords other than the one actually transmitted. Therefore, P (e) = (2 k -1)/2 n < 2 k /2 n = 2 -p . since for this worst of all possible channels, P (e) would still be bounded by 2 -p . Unfortunately, as shown below, the above argument is true only for those codes in which the codewords have a very symmetrical distribution in n-space. The question, therefore, arises as to which block codes satisfy the 2 -p bound. We attempt to provide some answers in the following.

Applicability of the 2 -p Bound

Proposition I: Linear block codes do not necessarily obey the 2 -p bound. Proof: Consider a (1023,1013) code in which the ten parity check bits are identically zero. On a totally noisy channel this code has P(e) < 2 -l0 = 9.77 x 10 -4 ; however, on a BSC with E = 0.01, we find P(e) = 0.904. This is because the probability of some error occurring in the 1013 information bits is essentially one, while the probability of at least one error in the 10 parity bits is only 0.096. However, only when at least one of the parity bits is received in error does the decoder detect an error. Proof: The generator polynomial for the (63, 24) BCH code is g (x) = 1 + x 5 + x 8 + x 11 + x 17 + x 22 + x 23 + x 25 + x 27 + x 28 + x 31 + x 33 + x 34 + x 36 + x 37 + x 38 + x 39 . From this, the weight distribution of the code can be computed. Here P = 63 -24 = 39 and 2 -p = 1.82  10 -12 . On a BSC with crossover probability  = 0.28 it can be shown that P (e) = 2.13  10 -12 which exceeds 2 -p .

). This, is turn, is equivalent to (x + 1) g (x) divides (x n + 1). However, we know g (x) divides (x n + 1) (see [2, p. 62, theorem 4.2]), and, since g (x) and (x + 1) are relatively prime, (x + 1) g (x) divides (x n + 1).

Proof:

We have already shown that the probability of undetected error of a block code on a BSC with  = ½ is bounded above by 2 -p . Therefore, it is sufficient to show that P(e) is monotonically increasing for 0   ½. This is proved in the following lemma. Lemma: For Hamming codes, P (e) is monotonically increasing in .

Proof: From [3] , the weight distribution for binary Hamming (n, k) codes is given by

Where Ai denotes the number of codewords of weight

Since the probability of undetected error is independent of the transmitted codeword, we can assume the all zeros codeword is sent and find

Differentiating P (e) with respect to , we obtain.

Where l is some odd positive integer since n = 2 m -1. Note that .

So, by mathematical induction, [(1-) 2l -(1 -2) l ] > 0, for 0 <  < ½. This concludes the proof that P(e) is monotonically increasing in .

Note:

It is easy to extend proposition 4 to the repetition and Golay codes and thereby to all binary perfect codes. Proposition 5: Shortened Hamming codes do not necessarily obey the 2 -p bound. Proof: Consider a Hamming (1023, 1013) code which has its parity check bits at positions 2 i , i = 0, I, …, 9 [4] . his implementation is useful for error correction because the syndrome gives the position of the error. If we shorten this code to a (12, 2) code by eliminating the leading 1011 information bits, it is easily seen that the codewords for this shortened code are

So in this case P (e) =  3 (1 -) 9 +  10 (1 -) 2  11 (1 -). For example, for  = 0.25 P (e) = 1.174  10 -3 > 2 -10 = 9.766  10 -4 . We might also consider shortening a Hamming code in cyclic form. Recall that an (n, k) Hamming code is a cyclic code whose generator polynomial g (x) is a primitive polynomial of degree m, where n = 2 m -1 and k = 2 m -m -1. From [3] we find that x 10 + x 3 + 1 is a primitive polynomials so that the generator matrix for a cyclic Hamming (1023, 1013) code might be

If we shorten the code [3, p. 241] to an (11, 1) code, the generator matrix will be just [10010000001]. This gives P (e) =  3 (1 -) 8 which has its maximum at  = 3/11. At  = 3/11, P (e) = 1.59  10 -3 > 2 -10 = 9.77  10 -4 .

It should be noted that we chose a primitive polynomial which had the minimum number of nonzero coefficients. This reduces the cose for hardware implementation.

Conclusion

It has been demonstrated that Hamming codes always obey the 2 -p bound on P (e) for   ½. However, this is not necessarily true for more general cyclic codes. Therefore, caution is needed when using the bound, especially in the design of systems in which the probability of undetected error, is critical. Fortunately, the bound is not badly violated by the cyclic codes we have used as counterexamples, providing hope that a slight overdesign should suffice. More careful analysis or simulation should be used to check out such designs. Even for Hamming codes, P (e) can be larger than 2 -p for   ½. This leads one to wonder if there are any codes which are uniformly good for all 0    1. We have been able to show that an (n, k) Hamming code altered to an (n, k -1)  (n', k') code by deleting all codewords of weight greater than n/2 has P (e) < 2 -(n -k) = 2 -(n'-k')+1 , for all 0    1. The proof is straight forward and relies on evaluation of P (e) through use of the weight enumerator polynomial. We have further found, through numerical evaluation, that, when the (7, 4) code is thus shortened to a (7, 3) code, P (e) < 2 -4 as opposed to the 2 -3 value predicted by the above argument, for all 0    1. And it is easily shown that the code obtained by affixing an overall parity-check bit to a maximal length shift register code has its maximum undetected error rate at  =½, and thus has P(e)  (2 k -1)/2 n , for all 0   1. Thus, for these codes,  = ½ is the "worst of all possible channels" for error detection. However, we doubt that this is true for codes with more reasonable rates.

1. Hellman ME. Error detection made simple: in Conference Record Int. Conf. on Communications, Minneapolis, Minn. 1974; 17(19):9A-4.
2. Lin S. An Introduction to Error-Correcting Codes. Englewood Cliffs N.J.: Prentice-Hall, 1970.
3. Peterson WW, Weldon EJ. Error Correcting Codes, 2nd ed. Cambridge, Mass. M.I.T. Press, 1972.
4. Bennett W, Davey J. Data Transmission. New York: McGraw-Hill, 1965.