I - .- -- .I-J {BASB-CB- 174175) . THE UPDEBECXED ERBOR 885-1 35351 

I PBOBBELLLIIY PO% SHOBTZEED BAEBLBG COD35 

! 

i 

dZllinois Inst, of Tech.) 16 g 

HC 802/dF 201 CSCL 12A Unclas I 

L--- -- G3/65 24591 / 

+ 

THE UNDETECTED ERROR PROBABILITY FOR 

SHORTENED HAMMING CODES F -- -- ---- -- ' N85 -13535 

Technical Report 

NASA 

Goddard Space Fl ight Center 

Greenbel t, Mary1 and 

Grant Number NAG 5-234 

Principal Investigators 

Daniel J. Costello, Jr. Shu Lin 

Department of El ectri cal Engi neeri ng Department of Electrical Engineering 

I1 1 inoi s Institute of Techno1 ogy University of Hawaii at Manoa 

Chicago, 1llinoi.s 60616 2540 Dole Street 

Honol ul u , Hawai i 96822 

December 12, 1984 ? -. 

I REPRODUCED BY: U.S. Depanrnent olCommercem 1 National TechnlW Infonnat~on sew^ 

Springfield. Virginia 22161 I 

1. Introduction 

Hamming or shortened Hamming codes are widely used for error detection in 

data comunications. For example, the CCITT (International Telegraph and 

Telephone Consul tative Commi ttee) recommendation X.25 for packet-swi tched 

data networks adopts a distance-4 cyclic Hamming code with 16 parity-check 

bits. for error detection [I]. The code is generated either by the polynomial, 

or by the polynomial 

15 14 13 12 4 3 2 15 14 where X +X +X +X +X +X +X +X+1 and X +X +1 are primitive polynomials of 

degree 15. The natural length of this code is n = 215-1 = 32,767. In practice 

the length of a data packet is no more than a few thousand bits which is much 

shorter than the natural length of the code. Consequently, a shortened version 

of the code is used. Often the length of a data packet varies, say from a few 

hundred bits to a few thousand bits, hence the code must be shortened by various 

degrees. Shortening affects the performance of the code. This is the subject 

of investigation in this paper. 

For a random-error channel with bit error rate (or transition probabil i ty) 

e, it was proved by Korzhik [2] that there exist (n,k) 1 inear codes with probability Pe of an undetected error satisfying the following upper bound: 

for all n, k and E with 0<~<1/2. - - Korzhik's proof is an existence proof, and 

no general method has been found for constructing codes satisfying the bound 

given by (3). Only a few classes of known codes [3-61 have been proved to 

satisfy a weaker bound, 

- (n-k) 

p, 5 2 

A code is said to be good for error detection if it satisfies the above bound, 

because the probability of an undetected error for the code is no greater than 

2-(n-kk) even for the worst channel condition with E = 1/2. In fact for small 

E, the error probability Pe is much smaller than 2 -(n-k). Strict-sense Hamming 

codes, distance-4 Hamming codes, doubl e-error-correcting and some trip1 e-errorcorrecting primitive BCH codes of natural length are known to satisfy the bound 

given by (4) and their error probability Pe decreases monotonically as E decreases 

[3-61. Hence these codes are good error-detecting codes. Using a good errordetecting code with a moderate number of parity-check bits (say n-k = 16-32) in 

an au tomatic-repeat-request (ARQ) system, the probabi 1 i ty of an undetected error 

can be made very small and virtually error-free data transmission can be achieved. 

Even though a Hamming code of natural length satisfies the error probability 

bound, P, - < 2- (n-k), given by (4), a shortened Hamming code does not necessarily 

obey the bound [3]. Whether a shortened Harming code satisfies the bound 2- (n-k) 

depends on the degree of shortening. Because Hamming codes are normally used in 

shortened forms, it is important to know whether a specific shortened Hamming 

code satisfies the bound 2 -(n-k). In this paper we investigate the probabil ity 

of an undetected error for shortened Hamming codes, particularly the shortened 

Hamming codes generated by the polynomials given by (1) or (2). A method for 

computing the probability of an undetected error is presented. We show that the 

codes generated by the polynomial' given by (1) yield better performance than the 

corresponding codes generated by the polynomial given by (2). 

2. Evaluation of Undetected Error Probabil ity of Shortened Cyclic Harnm.ing Codes 

Consider a binary (n,k) 1 inear code C. Let P(C,E) denote the probability 

of an undetected error when code C is used for error detection on a binary 

symmetric channel with transition probabil ity E. Let Ai and Bi be the number 
of codewords of weight i in C and its dual C' respectively. Then P(C,E) can 

be expressed in the following two forms, one is in terms of Ai and the other 

is in terms of Bi [7,8,9]: 

From (5) and (6), we see that, to compute the exact error probability of a 

1 inear code, one needs to know either the weight distribution {Ai :O<i<nl - - of 

the code or the weight distribution {Bi:O<i<n) --of its dual. Theoretically, 

we can compute the weight distribution of an (n,k) linear code by examining its 

k 2 codewords or by examing the 2n-k codewords of its dual. However, for large 

n, k and n-k, the computation becomes practically impossible. Except for some 

short linear codes and a few classes of linear codes [8-111, the weight distributions for most linear codes are still unknown. Consequently, it is very difficult, if not impossible, to compute the probability of . an . undetected error 

for a great many codes. 

For Hamning codes, a simple formula for enumerating Ai or Bi is known 18-11], 

but no general formula is known for shortened Hamming codes. In general, for 

shortened Hamming codes, n-k<k. - Hence it requires less effort in computing 

0: O<i<n} - - than in computing {Ai: O<i<n}. - - The weight distribution of the dual 

of a shortened Hamming code can be computed by generating all linear combinations 

of a parity-check matrix for moderate values of n-k. We call this the direct 

method. In the following, more effective methods for computing the weight distributions of the dual codes of shortened Hamning codes are presented. The 

computation is feasible for moderate values of n-k. 
For any positive integer m>3, - there exists a cyclic Hamming code of length 

2m-l and minimum distance 3. The generator polynomial of the code is a primitive polynomial p(X) of degree m. Let 

. - 

where po=pm=l. Thus the code is a (Zm-1, 2m-m-l) code with m parity-check 

symbols. Let C2m-l denote this Hamming code. The dual code of C2m-l. denoted 

L 

C2m- 1 , is a maximum-length-sequence code 18-11] which consists of the all -zero 

m codeword and 2 -1 maximum-length-sequences. Each maximum-length-sequence has 

weight zm-' and cycl icl y shifting any maximum-1 ength-sequence generates a1 1 

the other maximum-length-sequences. 

A distance-4 Hamming code of length 2m-1 is simply the even weight subcode 

of Czm-l. It is generated by the polynomial g(X) = (X+l)p(~) [9,11]. We denote 

this code by C2m-l,e The dual code of C2m-l,e is the first-order cyclic 

Reed-Muller code of length Zm-1 which also has minimum weight [9,11]. 

For any positive integer n with m<n<zm, let Cn be a shortened (n,n-m) code 

of C2m-l. Cn is obtained from C2m-1 by deleting the first zm-1-n information 

symbols from each codeword in CZm [9-111. Let A and BnSi be the number n,i 

1 of codewords of weight i in Cn and its dual Cn respectively. Let B be an element 

in the Galois field GF(Z~). The trace of 8, denoted Tr(@), is defined as 

follows: 

which is either 0 or 1. Let a be a root of F(X) and let 

- 

2 for 0<i<2~-1. Since F(a )=O for . O<h<m, - it follows from the linearity of trace 

Tr(-) that, for 0<i<2~-1, - 
where the suffixes are to be taken modulo 2"-1. It is known [8] that for a 

- 

nonnegative integer u less than 2"' v = (au,au+l,.. . ,a ) is a maximumu+zm- 2 

length-sequence in C . Since the weight of .i = (au . . ,au+2m-2 ) is 2'"- 1 

2"'l, it is easy to see that 

For 1<i<2~, - let Ni denote the weight of (au,au+ly.. . ,a u+i -1 ) which is a 

prefix of 7. Let No=O. Then Bn is equal to the number of occurrences of 

integer i in the sets 

{Nj+n - Nj: o - < j - < 2"-1-n) , 112) 

and 

For instance, we chan choose u such that au+i=O for O<i<m-1 - and auhn-l=l. 

Now we estimate the order of computation time for finding N Let p be j ' 

the number of nonzero coefficients of the generator polynomial. We consider 

the following two methods. 

For small p, we can generate au+i with 0<i<2~ by using recurrence formula, 

- 

and obtain Ni from N by increasing Ni by one only if i-1 is one. Then the 

computing time is upper bounded by cOp2", where co is a constant. Hereafter, 

ci denotes a constant. 
Met hod- I I 

If m andp are large, then we can use the following procedure for computing 

Nj. We assume that (i) the word length of computer is 2h or greater where 

0<h<m<2~-~, and (i ) word operations, "bi t-wise Logical -AND1' and "bi t-wise 

Exclusive-OR" are available. For - let 

Then it follows from (10) that 

- - 

We first generate (0 ,O,. . . ,O, 1 ,au+m,au+m+l ,aU+(mml l2 h 1, i.e., ao,aly.-~,~m-l by 

using m- 1 

- 

au+i+m j=O 1Pjau+i+j . 

h The computing time is upper bounded by clpm2 . Next we compute im,im+l

. . , - 

a by using (15), the computing time of which is upper bounded by 2m-h- 1 

From zi with 0<i<2~'~, - N1,N2,. . . ,Nj,. . . ,N can be found sequentially as follows. 

h h 2'"- 1 

Let j be 12 +r, where O<r<2 - . Then Nj,l can be obtained from P4. by extracting J 

the (r+l)-th bit of ii. N. is increased by one if and only if the result of J 

the extraction is nonzero. The computing time is c3Zm. Thus the total computing B 

h time is at most clpm2 +~~p(2~-~-m)+c~2~. For most cases, the first term is 

much smaller than the other terms. 

If c2P2'h+c3<~OP, then the secpnd method is more effective than the first 

one. For both methods, IBnyi: 0<i<2~1 - can be found from (11) to (13) by c4Zm 

computing time. Hence, the total computing time for finding {Bn,i: 0<i<2~1 - for 

q different code-lengths is upper bounded as follows: 

(I) For the first method, 
(2) For the second method, 

clpm2h + (c2P2-h+c3+clq 12"' . (17) 

Now we compare the above methods wtth a "direct method" for computing 

i~ 0<i<2~} which generates all linear combinations of the rows of a parity n,iW - 

check matrix of Cn. The computing time for generating a parity check matrix 

is upper bounded by c5pmn. To generate all 1 inear combinations of the rows 

efficiently, we can use the Gray code in such a way that a new combination is 

obtained from preceding one by adding a row to it [12,13]. If we use word operations, bit-wise logical-AND and bit-wise Exclusive-OR, then the computing time 

is proportional to n2mfE, where 2 is the word length of computer. We assume 

that the set of code lengths n. with l<j<q for which {BnjSi: 0<i<2'1 is to be J - - - 

found is given beforehand. Note that we don't need this assumption for the 

methods described above. If we use word operation "find the weight of a word", 

then the-order of the total computing time for finding the distributions 

{B n.. , j • 0<i<2~1 - for l<j<q - - can be estimated as 

J 

where 

Since c2"cgY c4ic7 and nmax/kis much greater than p, for most cases the first 

or second method is more efficient than the direct method, at least if q<nmax/L. 

Let C denote the even weight subcode of Cn. In fact, C is a shortened 

n,e n, e 

code of the distance-4 Hamming code C generated by g(X) = (l+X)p(X). The 

zm-l ,e I 

number of codewords of weight i in the dual code C- of CnSe, denoted Bne is 

n , e 

For 15<n<215, let c::! and c(~) be the even weight shortened codes of 

n,e 

length n generated by il(X) of (1) and i2(x) of (2) respectively. For 
15 14 13 12 4 3 2 15 14 F1(x) = X +X +X +X +X +X +X +X+l and F2(x) = X +X +1. Ni Is with l~ic2 15 

are computed by the first method. From these Ni 's, the weight distributions 

B O<i<n) of the dual codes of c(') and c(') for 16<n<215 are obtained. n,i,e' -- n , e n,e rq! 

From these weight distributions and (6), the error probabilities, PC) and 

(1 P(C,,,,E), are computed and plotted in Figures 1 and 2 respectively as functions 

2 15 of channel bit-error-rate E for code length n=2 with 5<2<14 - - and n=2 -1. 

From Figures 1 and 2, we see that if the two distance-4 Hamming codes 

recommended by CCITT X.25 are shortened too much, the shortened codes do not 

obey the bound 2 -(n-kk) given by (4), i .e., their error-detection performance 

becomes poor as E becomes large. Therefore, in order to maintain the data 

reliability, the'length of a data packet should not be too short. In Tables 1 

and 2, we tabulate some code lengths for which the error probabilities, 

(1 (1 P(Cnye, ) and P(Cnye, ) do not obey the bound 2 -(n-k) given by (4). We also 

tabulate the peak values of error probabil ities and the values of channel biterror-rate E where the peak values occur. Note that in most cases, peak values 

occur for 4/n<~<5/n. For the longer values n.2' with 8<1.<14 - - for c,!,:! and with 

10<e<14 - -. for cnSe, '*) no peak is detected within accuracy in c&nputation. The peak 

values of the probability of undetected error for c::: and c(~) are plottedin n,e 

Figure 3 as functions of code length n. From Tables 1 and 2 and Figures 1-3, 

we see that the codes generated by the polynomial il(X) of (1) give better 

performance than the corresponding codes generated by the polynomial i2(X) 

of (2). 

3. Conclusion 

In this paper, we have investigated the error-detection performance of 

shortened Harming codes, particularly the shortened codes obtained from the 

two distance-4 Hamming codes adopted by CCITT recommendation X.25. First two 

methods for computing the weight distributions of the dual codes of shortened 
Hamning codes have been presented. We have shown that these methods are in 

general more effective than the direct method. Using the weight distributions 

of the dual codes, we have evaluated the probability of undetected error for 

the codes obtained from shortening the two X.25 distance-4 Hamming codes. We 

have shown that shortening does affect the error-detection performance of the 

two X.25 codes. If the codes are shortened too much, the shortened codes do 

not obey the bound 2-16. We have also shown that the codes generated by 

16 12 5 G1(x) = X +X +X +1 give better performance than the corresponding codes 

16 14 generated by j2(X) = X +X +X+1. 
REFERENCES 

1. CCITT: Recommendation X.25, "Interface Between Data Terminal Equipment 

(DTE) and Data Circuit-terminating Equipment (DCE) for Terminals Operating 

in Packet Mode on Public Data Networks," with Plenary Assembly, DOC: No. 

7, Geneva, 1980. 

2. V.'I. Korzhik, "Bound on Undetected Error Probability and Optimum Group 

Codes in achannelwith Feedback," Radiotecknika, 20, Vol. 1, pp. 27-33, 

1965. (English trans1 ation: Telecommunication and Radio Engineering, 2, 

pp. 87-92, January, 1965.) 

3. S.K. Leung-Yan-Cheong and M. E. He1 lman, "Concerninq a Bound on Undetected 

Error ~robabil i ty, ", ~EEE Transaction on ~nformation Theory, Vol . IT-22, 

No. 2, pp. 235-237, March, 1976. 

4. S.K. Leung-Yan-Cheong, E.R. Barnes, and D.U. Friedman, "Some Properties 

of Undetected Error Probability of Linear Codes," IEEE Transaction on 

Information Theory, Vol. IT-25, No. 1, pp. 110-112, January, 1979. 

5. T.. Kasami, T. Kldve, and S. Lin, "Error Detection with Linear Block Codes," 

IEEE Transaction on Information Theory, Vol . IT-29, No. 1, January, 1983. 

6. J.K. Wolf, A.M. Michelson, and A.H. Levesque, "On the Probability of 

Undetected Error for Linear Block Codes," IEEE Transaction on Communication, Vol. COM-30, No. 2, pp. 317-324, February, 1982. 

7. F.J. MacWilliams, "A Theorem on the Distribution of Weights in Systematic 

Code," Bell System Technical Journal, Vol. 42, pp. 79-94, 1963. 

8. F.J. MacWill iams and N.J .A. Sloane, Theory of Error-Correcting Codes, 

North Holland, Amsterdam, 1977. 

9. S. Lin and D.J. Costello, Jr., Error Control Coding: Fundamentals and 

Applications, Prentice-Hall , New Jersey, 1983. 

10. E.R. Berl ekamp, A1 gebrai c Coding Theory, McGraw-Hill , New York, 1968. 

11. W.N. Peterson and E.J. Weldon, Jr., Error-Correcting Codes, 2nd Edition, 

MIT Press, Cambridge, MA, 1972. 

12. T. Kasami, T. Fujiwara, and S. Lin, "An Approximation of the Weight Distribution of Binary Linear Codes," Proceedings of the 6th Conference on 

Information Theory and Its Applications, Matsuyama, Japan, November, 1983. 

13. T. Fujiwara, A. Sitai, S. Yamamura, T. Kasami and S. Lin, "On the "obabbility of Undetected Error for Shortened Cyclic Hamming cod~s," Proceedings 

of the 5th Conference on Information Theory and Its Applications, 

Hachimantai, Japan, Oct~ber, 1982. 
Table 1 

The maximum values of P(Cn,e, E) for 0<~0/2 - 
Table 2 

The maximum values of P(C,,~,E) for 0<~cl/2 - 
BIT-ERROR-RATE E 

Figure 1 Actual values of probabil ity of undetected error for 

the shortened cyclic Hamming code of length n generated 

by G1(x) = 1+~5+~12+~16 as a function of channel bit 

error rate E. 
&m c A. 3 ooa 

3 -hm ct 

PROBABILITY OF UNDETECTED ERROR P(C~?!,E) 
Figure 3 The peak values of the probability of undetected error 

(1 12) for C,,, and C,,,. 

I 1 I 1 11 111 I 1 1 ! 1 I 1.1 z+ 1 0-5 

. . 

10 . 100 1000 

CODE LENGTH n 

I 1i Ill