On the Undetected Error Probability of BCH Codes by William Chong B. Eng., Liverpool University, 1988 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA March 1992 © William Chong, 1992. In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of The University of British Columbia Vancouver, Canada Date DE-6 (2/88) Abstract The undetected error probability, P(e), for a variety of Bose-Chaudhuri Hocquenghem (BCH) codes, used solely for error detection on a binary symmetric channel (BSC) with cross-over probability , is studied. The undetected error probability can be evaluated if the weight distribution of the code or its dual is available. Unfortunately, no general expression for the weight disthbution of BCH codes which correct more than 3 errors is known. A few BCH codes for which it is computationally feasible to determine the weight clisiribution are studied. A proper code is one for which P (e) increases monotonically with for 0 0.5. Algorithms for determining the properness of linear block codes based on Fourier’s and Sturm’s Theorems for finding the number of real roots of a polynomial in a given interval are investigated. They are useful in cases where the weight distribution is known. Kasami et a! have studied linear programming methods for obtaining upper and lower bounds on the weight distributions of 4- and 5-error-correcting BCH codes. Here, two methods which can be used to improve these bounds are presented. The first method uses the minimum distance of a dual BCH code. The second method requires, in addition, the number of codewords at the minimum distance. Comparisons between the improved bounds and the Kasami bounds are given for several BCH codes. 11 Table of Contents Abstract ii List of Tables v List of Figures vii Acknowledgments viii 1 Introduction 1 1.1 General Background 1 1.2 Overview of the Thesis 5 2 Weight Distribution and Undetected Error Probability for Some BCH Codes6 2.1 Computing Weight Distribution of the BCH Codes 2.2 Computing Undetected Error Probability of the BCH Codes 6 9 2.3 Any Code with Weight Distribution {Ao = A 1,A m 2 -i_j = 2 rA n_i = — 1} is Proper 10 2.4 Weight Distribution and Undetected Error Probability for Extended BCH Codes 11 3 Determining the Properness of a Code 3.1 Method Based on Fourier’s Theorem 14 14 3.1.1 d-th Derivative for P(e) with Weight {A} 15 3.1.2 d-th Derivative for F(E) with Weight {B } 1 16 3.2 Method Based on Sturm’s Theorem 19 3.3 Testing of the Algorithms on Some BCH Codes 20 JLI1 4 Bounds on the Weight Distributions of BCH Codes 24 4.1 A Review of Some Approximations to the Weight Distributions of BCH Codes 24 4.2 Computation of and 28 4.3 Two Methods for Improving Kasami’s Bounds on the Weight Distribution of BCH Codes 35 4.3.1 Method 1: Using the Minimum Distance of an Extended Dual BCH Code 35 4.3.2 Method 2: Using the Number of Codewords at the Minimum Distance of an Extended Dual BCH Code 36 5 Conclusions 5.1 47 Summary 47 5.2 Suggestions for Future Work 47 Bibliography 49 Appendix A 52 A.1 The Weight Distribution of the BCH Codes for n = 31 52 A.2 The Weight Distribution of the BCH Codes for n = 63 52 A.3 The Weight Distribution of the BCH Codes for n = 127 54 A.4 The Weight Distribution of the BCH Codes for n = 255 55 A.5 The Weight Distribution of the BCH Codes for n = 511 56 A.6 The Weight Distribution of the BCH Codes for n = 1023 56 Appendix B 58 B. 1 Proof of (3.11) 58 iv List of Tables 2.1 The BCH codes whose weight distributions are evaluated 2.2 The BCH codes in Table 2.1 which do not obey the 2 bound 2.3 The weight distribution of the (2m_2 — 8 10 1)-error-correcting BCH codes for 3m1O 2.4 11 The weight distribution of the extended (2m—2 — 1)-error-correcting BCH codesfor3<m1O 12 2.5 The extended BCH codes in Table 2.1 which do not obey the 2 bound. 3.6 The weight distribution of the dual (31,11) BCH code 20 3.7 Summary of results of the properness of BCH codes in Table 2.1 22 4.8 Upper bounds LP Ofl Eex,i for the extended BCH codes for 4 < t . . 7, 6m l0formlog w and2t+2i2t+12 2 4.9 Lower bounds LP on Eex,i for the extended BCH codes for 4 30 t < 7, 2 6ml0 w and2t-form I-2i<2t-l-12 log 4.10 33 Ratio, RDUB and RDLB for the t 3,m = 7,8 and t = 4,m = 6,7,8 extended BCH codes 4.12 34 The din,ext, j, w’ and w for the extended dual (64,39), (64,36), (128,99), (128,92) and (256,223) BCH codes 4.13 Exact 37 1 and RDUB 2 for the extended BCH Relative deviations RDUB, RDUB codes listed in Table 4.12 for 2t + 2 < i 4.15 35 and LPJ’f, LFe LFf for the extended BCH codes listed inTable4.12for2t+2<i<2t--1O 4.14 31 Parameters to compute LP and LP for the extended BCH codes in Tables 4.8 and 4.9 4.11 13 Exact 2t + 10 38 and LPei LF’, LP for the extended BCH codes listed inTable4.l2for2t+2<i 2t+10 V 39 4.16 1 and RDLB 2 for the extended BCH codes Relative deviations RDLB, RDLB listed in Table 4.12 for 2t + 2 < i < 2t + 10 40 4.17 Comparison of Ratio 41 A. 18 The weight distribution of the (31,11) BCH code 52 A.19 The weight distribution of the dual (63,39) BCH code. 52 A.20 The weight distribution of the dual (63,36) BCH code. 52 A.21 The weight distribution of the (63,30) BCH code 53 A.22 The weight distribution of the (6 3,24) BCH code 53 A.23 The weight distribution of the (63,18) BCH code 53 A.24 The weight distribution of the (63,16) BCH code 53 A.25 The weight distribution of the (63,10) BCH code 54 A.26 The weight distribution of the dual (127,99) BCH code. A.27 The weight distribution of the dual (127,92) BCH code A.28 The weight distribution of the (127,29) BCH code.. 54 A.29 The weight distribution of the (127,22) BCH code.. 55 A.30 The weight distribution of the (127,15) BCH code. 55 A.31 The weight distribution of the dual (255,223) BCH code 55 A.32 The weight distribution of the (255,29) BCH code 55 A.33 The weight distribution of the (255,21) BCH code 55 A.34 The weight distribution of the (255,13) BCH code 56 A.35 The weight distribution of the (5 11,31) BCH code 56 A.36 The weight distribution of the (511,28) BCH code 56 A.37 The weight distribution of the (511,19) BCH code 56 A.38 The weight distribution of the (1023,26) BCH code 56 A.39 The weight distribution of the (1023,16) BCH code 57 vi . . 54 . 54 List of Figures 1.1 Binary symmetric channel with bit error rate 4.2a Comparison of 2 . pUB’ exi,u(e’, PL(e), P(e) with Pext,u() for the ‘ extended (64,39) BCH code 4.2b 42 ) 6 Comparison of P(E), P(e), pL( 2 pLB ext,u” ) with Pex,u(E) for the extended (64,39) BCH code 4.3a Comparison of 42 F(E), P(e), P(e) with Pex,u(E) for the extended of (64,36) BCH code 4.3b Comparison of 43 Pf(), P(e) with for the extended of (64,36) BCH code 4.4a 43 Comparison of P(e), Pf(e), P(e), P(e) with Pext,u(E) for the extended (128,99) BCH code .44 4.4b ),pL pL.( ) 6 ( 2 Comparison of 2 P(E),P ( with Pext,u(E) for the e ezi,u’ 1’ ex extended (128,99) BCH code .44 4.5a Comparison of F(E), Ff(E), P(e), P(e) with Pex,u(e) for the extended (128,92) BCH code 4.5b 45 (E),pu ( EpL(E B ) Comparison of pUf 2 ext,u\ I P(6) with Pext,u(E) for the extended (128,92) BCH code • 45 4.6a Comparison of F(E), Pf(e), P(E), P(E) with Pext,u(E) for the extended (256,223) BCH code 4.6b Comparison of 46 Pf(6), P.(E), P(€) with Pez,u(E) for the extended (256,223) BCH code 46 vii Acknowledgments I would like to express my special gratitude to Professor C. Leung, whose patience and guidance were essential to the successful completion of this thesis. His dedication to this field of research has given me much motivation throughout the entire period of his supervision. I would also like to thank Dr. J. Whittaker whom I consulted on certain mathematical issues. I am also grateful to William Cheung for his assistance in programming, Xiaotian Shi, Anthony To and Victor Wong for their help in preparing this thesis using PublisherTM. My appreciation goes to Brenden Wong for many useful discussions and to Barry Buternowsky for his time in proof-reading the various drafts of the thesis. This research was partially supported by NSERC grant OGP000 1731 Finally, I would like to thank my parents and family for their encouragement and support. vu’ Chapter 1. Introduction 1.1 General Background The birth of coding theory was inspired by a classical paper “A Mathematical Theory of Communication” written by Shannon in 1948 [1]. This paper stated that if the signaling rate of a system is less than the channel capacity, reliable communication can be achieved if one chooses proper encoding and decoding techniques. Since then, a great deal of research effort has been devoted to the design of efficient encoding and decoding methods by which digital information can be coded for reliable and fast transmission through a noisy communication channel such as a telephone line, a high frequency radio link, or a satellite communication link. The sources of noise include lightning, thermal noise, imperfections in equipment, etc., and results in the data received being different from the data transmitted. Linear block codes are commonly used to detect, locate and correct errors in data transmission. The basic idea is to encode the message bits, by adding redundancy in the form of parity-check bits, so that the original message may be recovered in spite of channel errors. Coding for error-control is now widely used in applications such as digital communication and data storage systems. An (ri, k) linear block code, where n is the block length and k is the number of information bits, with minimum distance dmin can be used in three ways for controlling transmission errors in a data communications system: purely for error detection; purely for error correction; or, a combination of error correction and detection. If the code is used solely for error detection, any combination of dmin — 1 or fewer errors are guaranteed to be detectable. If the code is used solely for error correction, any combination of L(dm:n — 1)72] or fewer errors are guaranteed to be correctable, where[xj is defined as the greatest integer less than or equal to x. If the code is used for error correction and 1 Chapter 1. Introduction 2 1—c 0 0 Input Output 1 1 1—c Figure 1.1 Binary symmetric channel with bit error rate c detection, it is able to simultaneously correct up to a errors and detect up to /3 errors provided that a + /3 dmin 1 and /3 a. A simple and commonly used channel model is the binary symmetric channel (BSC) which is shown in Figure 1.1. This is a discrete memoryless channel with a binary input and output alphabet of 0 and 1. Successive errors are statistically independent and the probability of bit error is e. When a codeword is sent over a channel, an undetected error occurs if the noise on the channel transforms the transmitted codeword into some other codeword. For a binary linear code used solely for error detection over a BSC, this happens if and only if the error pattern is identical to a nonzero codeword. Therefore, the probability of undetected error, P(e), of an (n, k) linear block code can be written as [2, p.66] A?(1 _&)n_z, (1.1) Chapter 1. Introduction 3 where A is the number of codewords of weight i. The set {Ai, ..., A} is referred to as the weight distribution of the code. For a code with minimum distance dmin, A is zero for 0 < j < dmin. For i 0 0, A = 1. Another formula to compute P(e) is [2, p.77] = B(1 — 2e)i — (1 — (1.2) e), where B, is the number of codewords of weight i in the dual code. We see from (1.1) and (1.2) that knowledge of the weight distribution of a code or its dual allows the evaluation of P (e). MacWilliam’s identity [3, p.lTl] gives the relationship between the weight distribution of a code and its dual. We can use this identity to determine the weight distribution of a code if the weight distribution of its dual is known. In fact, this identity can be used to derive (1.2) from (1.1). Flowever, the exact values of A 2 and B 2 for most codes are unknown. Use of the guaranteed error detecting capabilities of a linear code to estimate P 1 (e) (i.e. assuming all error patterns of weight dmin and higher are undetectable) generally leads to a very pessimistic result. This is because most error patterns of weight dmjn are in fact detectable. Prior to the work of Leung and Heliman [4], it was commonly assumed that F() of a linear block code was upper bounded by 2, where p is the parity-check bits equal to n — k. This assumption arises from the understanding that when P(e) of a code is monotonically increasing with e, the maximum value of the probability of undetected error Fu(max) at £max P(0.5) = 2 = 0.5 from (1.1) is A (1.3) An (n, k) linear block code whose P(E) is monotonically increasing with e(0 e 0.5) is termed a proper code [5]. A code which is not proper is referred to as an improper code. Chapter 1. Introduction 4 A number of papers have shown that certain linear codes do not obey the 2 bound. A summary of various results regarding P(e) of block codes is listed below: 1. Linear block codes are not necessarily proper [4]. 2. Cyclic codes are not necessarily proper [4]. 3. Binary single error correcting Hamming codes are proper [4]. 4. Shortened binary single error correcting Hamming codes are not necessarily proper [4]. 5. Binary codes are proper [5]. 6. Single parity-check codes are proper [5]. 7. The extension of a proper code containing odd-weight codewords is not necessarily proper [5]. 8. Extended Hamming codes are proper 9. Maximal length codes are proper [5]. [5]. 10. The dual of a binary perfect code is proper [5]. 11. The dual of a proper code is not necessarily proper [5]. 12. Double-error-correcting BCH codes are proper [5]. 13. Square single parity-check product codes of size (m m) are proper for 2 <m . 4. For m > 4, these codes are improper [6]. 14. Maximum Distance Separable codes are proper [7]. 15. Cyclic redundancy check codes are not necessarily proper [8] 16. The (15,5) triple—error—correcting BCH code is proper [9]. 17. Triple-error-correcting primitive BCH codes with block length for odd m 5 and are improper for even m i-i = 2 —1 are proper 6 [9]. 18. Extended double-error-correcting primitive BCH codes with block length n proper for odd m 3 and are improper for even in 5 and are improper for even m 2 are = 2 are 4 [9]. 19. Extended triple-error-correcting primitive BCH codes with block length n proper for odd m = 6 [9]. Chapter 1. Introduction 5 A cyclic code is an (n, k) linear block code C which has the property that a cyclic shift of any codeword in C is also a codeword in C [2, p.851. BCH codes form a large class of random error-correcting cyclic codes and can be viewed as a generalization of Hamming codes for multiple-error correction. Detailed descriptions of BCH codes, their algebraic properties and decoding algorithms can be found [10], [11] and [3]. 1.2 Overview of the Thesis In Chapter 2, we evaluate the weight distribution of some BCH codes for cor recting more than 3 errors. It is also shown that any code with weight distribution 0 = A = 1, 1 m-i_ = A 2 A rn-i = 2 1} is proper. Moreover, we numerically show {A — that the (63,39), (63,24), (127,92) and (255,29) BCH codes and their extended codes are improper. In Chapter 3, the application of Fourier’s and Sturm’s Theorems to determine the properness of an (n, k) linear block code is considered. The advantages and disadvantages of the two approaches are discussed. The two methods are used to test the properness of the BCH codes in Table 2.1 and the extended codes. In Chapter 4, a summary of the bounds on the weight distribution of BCH codes is given. The upper and lower bounds derived by Kasami et al [12] on the relative deviation Eext,i of the number of codewords of weight i from the binomial distribution for the extended BCH codes are computed for 6 i m 2 _ (n_k)() 20, 4 < t < 7 and 2t + 2 < 2t + 20. Two methods for improving the tightness of the upper and lower bounds on are investigated. The (64,39), (64,36), (128,99), (128,92) and (256,223) extended BCH codes are used as examples to study the improvements. The results of this research are summarized on Chapter 5 which also contains some suggestions for future work. Chapter 2. Weight Distribution and Undetected Error Probability for Some BCH Codes In this chapter, we will evaluate the weight distribution and the probability of unde tected error of several binary primitive BCH codes and their extensions. We also prove that any code with weight distribution {Ao = A = 1, -_ 2m A 1 = 2m A - = — 1} is proper. An (n, k) binary primitive BCH code with block length 2 — 1 where m 3 has the following properties: the number of parity-check bits, the designed distance, and the minimum distance t (0 t < 2—’) are n — k < 2t + 1 and dmin nit, is the number of the correctable errors. There is no simple method for determining the exact number of parity-check digits n n — 2t + 1, respectively, where — k, except for small t, where k is exactly equal to mt [2, p.1421. For many of the binary primitive BCH codes, the minimum distance is equal to the designed distance [11, p.2’78]. 2.1 Computing Weight Distribution of the BCH Codes The weight distribution of a binary primitive BCH code has the following symmetric property: = (0 A_ Ii Hence, we only consider A 2 for 0 for for for < 0<i<2tand n—2t<i<n 2t + 1 <i < n 2t 1 i=Oandi=n. — m—1 < 2 — — (2.1) 1. There is a lack of general results for the weight distributions of t-error-correcting BCH codes for t> 3. Exact expressions for the weight distribution of the duals of the double-error-correcting and triple-error-correcting BCH codes were derived by Kasami [13]. An exhaustive enumeration of the weight of each of the for reasonably small value of k. 6 k 2 codewords is possible Chapter 2. Weight Distribution and Undetected Error Probability for Some BCH Codes Let the generator polynomial of an (n, k) BCH code be g(X) gfl_Xfl_JC where g_ = = 1. Let u = 7 go + giX + ... + , ul...uk_1) be the message vector to be 0 (u = encoded. The corresponding codeword v is given as v = (2.2) uG where G is the k x n generator matrix of the code and can be written in the following form [2, p. j: 92 go o o gi g2 g gi g • 0 go gi g2 • . . . 0 . 0 0 ga—k ga—k . 0 0 0 0 0 0 . . . G= . o o . . . 0 go gi g2 (2.3) gm—k . Also, consider the dual of an (n, k) BCH code which is an (n, n . — k) code. The generator polynomial h(X) of the dual code is [2, p.93] h(X) = where h(X) = 0+1 h h+ X ... (2.4) g(X) 0 + hkX’ with h = hk = 1 . The corresponding codeword x is given by x where w is a message vector of length n = — wH k, and H is the (2.5) (i-i — k) x n generator matrix of the dual code which can be written in the following form [2, p.93]: Chapter 2. Weight Distribution and Undetected Error Probabilfly for Some BCH Codes hk o o o hk_l hk hk_2 hk_1 hk_2 0 hk hk_1 hk_2 . . . 0 h • • 0 0 h 8 0 0 0 0 0 . . . 0 The generator polynomials of BCH codes for 3 hk_1 h,, m hk_2 (2.6) 10 are given in [2, p.583]. To compute the weight distribution of a code by (2.2) or a dual code by (2.5) is —k vectors. Although computationally intensive, as it requires enumeration of 2’ or n2 this approach is applicable to any linear block code, it is impractical for codes with large values of k and n or (2 — — k. Hence, we consider only the BCH codes with 242 1) x for 3 rn 2 ( — 242 1) x < 10. Table 2.1 lists the BCH codes whose weight distributions will be computed. n k t k t 31 11 5 15 27 6 7 8 31 39 4 223 4 36 5 29 47 30 6 21 55 24 7 13 59 18 10 9 63 16 11 31 109 10 13 28 111 7 15 19 119 99 4 10 127 92 5 26 239 29 21 16 147 22 23 11 255 63 127 255 511 1023 Table 2.1 The BCH codes whose weight distributions are evaluated. Chapter 2. Weight Distribution and Undetected Error Probability for Some BCH Codes We use (2.2) whenever k < n — k, and (2.5) whenever n — 9 k < k . Consider as an example the computation of the weight distribution of the (63,39) quadruple-errorcorrecting BCH code. The weight distribution of the dual code was evaluated. For this dual code there are 224 codewords of length 63 bits. If the weight distribution of the (63,39) BCH code is evaluated directly, we need to generate codewords and the computational time required to calculate the weight distribution would be much longer. MacWilliam’s identity [2, p.lZ7] can then be used to obtain the weight distribution of the original code from that of its dual. The generator polynomial of the (63,39) BCH code is [2, p.583] g(x) = 1+x+x 2+ 4 x 5 6 8 9 1 + 2 6 7 9 0 2 3 4 x Using (2.4), the generator polynomial h(x) of its dual code can be determined as h(x) = 9 l+x 3 5 6 + 8 + x” x +x + 19 14 5 16 17 + 18 x . x 2 + + 3 X 1 3 7 0 2 4 6 8 9 x The MAPLETM library routine “Rem(a,b,x) mod 2” [14, p.193] was used to determine h(x). The weight distributions for the BCH codes in Table 2.1 were evaluated on a SUN SPARC workstation II and the results are given in Appendix A. As an example of the runtime lengths, the weight distribution of the dual of the (127,92) BCH code required approximately 16.7 days of CPU time to compute. The number of operations is roughly +m_I_l(2m 2m given by O(2k+mk) for a BCH code andO(2 — k)) for a dual BCH code. 2.2 Computing Undetected Error Probability of the BCH Codes An infinite precision package of MAPLETM [14] was used to evaluate the probability of undetected error P () for the codes in Table 2.1. The region of o e 0.5 . E of interest is Equation (1.1) or (1.2) was evaluated in increments of 0.001 for € for each code in the Table. The results indicate that the probability of undetected error of the (63,39), (63,24), (127,92) and (255,29) BCH codes violate the 2 bound. Table 2.2 Chapter 2. Weight Distribution and Undetected Error Probability for Some BCH Codes 10 gives the maximum values of the probability of undetected error Fu(Emax) at 6 max as well as the values of 2 to an accuracy of 7 significant figures. The improperness of the (63,24) BCH code has been reported in [4]. At this point, we cannot conclude that the other codes in Table 2.1 are proper since only a finite number of values (500) of e were evaluated. The probability of undetected error may exceed the 2 bound at some unused value of In Chapter 3, we derive . algorithms to test the properness of a code and will show that the rest of the codes in Table 2.1 are indeed proper. (n,k) £rna Pu(rnax) 2 (63,39) 0.26815 5.9625902E-8 5.9604645E-8 (63,24) 0.27899 2.1419779E-12 1.8189894E-12 (127,92) 0.13918 2.9329424E-11 2.9103830E-11 (255,29) 0.37675 2.0855015E-68 9.2730154E-69 Table 2.2 The BCH codes in Table 2.1 which do not obey the 2 bound. 2.3 Any Code with Weight Distribution {Ao = A 1, 1 m-i_ = A 2 A m-i = 2 — i} is Proper In [2, p.143], the values of k and t for BCH codes of length n = 2 — 1 with 3 < m < 10 are given. From this table, for a fixed value of n, the maximum error m—2 correcting capability is 2 — 1 errors and the corresponding value of k is m + 1. Table 2.3 gives the weight distribution of the (2m_2 for 3 < m 1)-error-correcting BCH codes 10. Proposition: 2 A 1 m =2’ — — Any code with weight distribution {Ao l} is proper. = A = 1, -_ 2m A 1 = Chapter 2. Weight Distribution and Undetected Error Probability for Some BCH Codes 11 Proof. From (1.1), the probability of undetected error of a code with weight distri bution {A 0 = A = 1, 1 rn.-i_ = A 2 A rn-i = 2 1} is — = (2 = (2 = The terms {e(1 0 <e 0.5 . (2 1) — [e2 2 1)c rn—i rn—i —1(1 rn—i rn—i —‘(1 1)[e(1 — — - rn-i — — and e 2 Therefore, the + — rn—i — 2 +e 2 e) — rn 1 ( m 2 _2 — 2 +e rn—I (1 rn—i — 2 e) 1] + e rn 2 m —1 (2.7) m in (2.7) are monotonically increasing with for 1)-error-correcting BCH codes are proper. i 0 1 2m_1_l 2—1 2m_1 2”—1 n 1 Table 2.3 The weight distribution of the (2m_2 — 1)-error-correcting BCH codes for 3 m < lot. 2.4 Weight Distribution and Undetected Error Probability for Extended BCH Codes For an extended BCH code, the block length n is equal to 2 for m number of parity-check bits and the designed distance are n — k mt 3. The + 1 and 2t + 2, respectively [12]. Let Aext,j and Bext,j be the number of codewords of weight i of an extended BCH code and the extended dual code, respectively. Aext,i = 1 +A A_ can be written as [11, p.264.1 (2.8) The weight distribution of Table 2.3 corresponds to that of a code consisting of a maximum length code [2, p.201] and the complements of the codewords. Chapter 2. Weight Distribution and Undetected Error Probability for Some BCH Codes for even values of (0 < < 12 2w). The symmetric property of A is also applicable to Aext,i. Hence, we only consider 0 < < m 2 —1. The relationship between B and Bext,j is given as [9] Bext,i = B+B _ 1 (2.9) and [12] Bext,j (2.10) = The last equation shows the symmetric weight distribution of the extended dual code. However, {B 2 } is not symmetrically distributed. Hence, we consider 0 i — 1 for B. From (2.8) and (2.9), we can evaluate the weight distributions of extended BCH codes. Table 2.3 gives the weight distribution of the ( m 2 _2 — 1)-error-correcting codes. Thus, the weight distribution of the extended BCH codes, according to (2.8), is given in Table 2.4. i 0 1 m—1 2 m-f-1 2 — n 1 Table 2.4 (2m_2 2 — The weight distribution of the extended 1)-error-correcting BCH codes for 3 < m < 10. Proposition: Any code with weight distribution 0 {A = = 1, A 2 m = 2’ — 2} is proper. Proof: The proof is similar to the proof in Section 2.3. From (1.1), the probability of undetected error of an extended code with weight distribution Chapter 2. Weight Distribution and Undetected Error Probability for Some BCH Codes 0 {A = A = 2 m +1 — 2m l,A — Pextu(6) = 2} is (2m+1 = (2m+1 The terms [e(1 o < < — E)]2m1 and 13 62m —2) r 2 rn—I L (1 —e) m—11 2 I m—1 2 — 2)[6(1 in (2.11) 0.5 indicate that the extended — are + e)] 2 +eh (2.11) m monotonically increasing with e for ( m 2 _2 — 1) -error-correcting BCH codes are proper. We use (2.8) or (2.9) to evaluate the weight distribution for the extended BCH codes of Table 2.1. We then use (1.1) or (1.2) to compute the probability of undetected errors for these codes. We find that the probability of undetected error for (64,39), (64,24), (128,92) and (256,29) extended BCH codes violates the 2 bound. Table 2.5 gives the values of Fext,u(6max) and 2 for these codes. (n, k) £rnaz Pezt,u(maz) (64,39) 0.27272 2.98 12565E-8 2.9802322E-8 (64,24) 0.28268 1.0701 137E- 12 9.0949466E- 13 (128,92) 0.14260 1.4661603E-11 1.4551915E-11 (256,29) 0.37724 1 .0426388E-68 4.6365077E-69 Table 2.5 The extended BCH codes in Table 2.1 which do not obey the 2 bound. Chapter 3. Determining the Properness of a Code In this chapter, we examine two methods to test the properness of an (n, k) linear block code whose weight distribution is known. The methods are based on Fourier’s and Sturm’s Theorems to determine the number of real roots that a polynomial equation has within a given interval. We will use them to determine the properness of the BCH codes in Table 2.1. 3.1 Method Based on Fourier’s Theorem If the probability of undetected error P(e) monotonically increases with (0 e < 0.5), it has no local minimum or maximum point in this interval. It follows that its first derivative P () should have no roots in this region of e. One of the methods to test whether a polynomial has real roots in a certain interval is based on Fourier’s Theorem [15, p.338]. Letf(x) = 1 0 x cqx+cq_ x _l+...+c +c = 0 be a polynomial equation with real coefficients of degree q> 0. The Fourier sequence of f(x) is defined as fseq(x) = d-th derivative of f(x) for 0 < d {f(x), f’(x), f”(x) q. The functions , f(e), f()(x)} ..., where f(d)(x) is the f()(E) are called Fourier’s functions. If we replace x in fseq(x) by any two real numbers, say, y and y < z and neither y nor roots of the polynomial z is a root of f(x) f(x) located in the = = z. (where 0 [15, pL34.O]), then the number of real interval between y and z is less than the number of sign variations lost in fseq(x) in passing from the substitution x substitution x z = y to the A root of multiplicity m is counted as m roots [18, p.103]. Fourier’s Theorem gives an upper bound on the number of real roots a polynomial equation has in a given interval. In order to use this theorem to determine whether a code is proper for 0 e < 0.5, the number of sign variations of the Fourier sequence of the first derivative of the probability of undetected error of a code at e number of sign variations at = 0.5 must be zero. 14 = 0 minus the Chapter 3. Determining the Properness of a Code 15 3.1.1 d-th Derivative for P(E) with Weight {A} p.56] to rewrite the term (1 If we use the Binomial Theorem [16, (mz) — 2 e)’ in (1.1) as (—1)’e’, then the first derivative of (1.1) is = f(e) > = i) (n A (—1) ( 1 i+ We want to determine if the polynomial equation f(e) = 0.5), by using Fourier’s Theorem. The Fourier sequence of fseq(e) l)ei+1_1. (3.1) 0 has no real roots in (0, f(e) is = {f(e),f’(e),f”(),...,f(W_1)(e)}. We now derive the d-th derivative of (3.1) for 0 d (i + 1 — (3.2) 1). Because A is zero for 0 < j < dmj, (3.1) can be re-written as f(e) (n_i)(i)l(.+l)i+I_l = jdmj,, tO We note that in (3.3) the lowest degree of of e is n — 1. As a result, there are dmin in — f(e) is dmjn 1 roots at e = roots from (3.3) by multiplying both sides of (3.3) by the multiple roots of f(s) at e = — 1 and the highest degree 0. We remove these multiple mj1)• This is to eliminate 0 and also to reduce Fourier’s functions in define the polynomial g(e) of degree g(e) (3.3) = ri — Aj>Z jdmin fseq(E). We dmin as (n i)(l )1 (i + t)i+l_dmin (3.4) 10 The d-th derivative of g(e) is ) 6 g(d)( (n = jdmin 10 i) (—1) ( 1 i + l)Ei+ mind H (i + 1— dmin j=0 — j), (3.5) Chapter 3. Determining the Properness of a Code for 0 < d < ii — dmin. For g(d)(0) = 6 = 0, (3.5) reduces to (dmin + d)d! Zdmin When e the term = 16 i+ldmind 6 ( )dmn+d_Z 1 (_ dmin+ equals to () (3.6) j) dm:n+d 2 — i—l (n g(d)Q) 2 = d mj x — and (3.5) becomes i)(i)l(. +1) z—dm,n 1—0 i+l d—1 (3.7) fJ(i+l_dminj). 3.1.2 d-th Derivative for P(e) with Weight {B} In this section we derive the d-th derivative of the probability of undetected error of (1.2). The first derivative P(E) is -P ) 2 = u(6) = (_ iB(1 — 2€)i_1 We want to determine if the polynomial equation u(e) 0.5) by using Fourier’s Theorem. Theorem to rewrite the term (1 ‘ — + n(1 = — 6)fh. (3.8) 0 has no real roots in (0, Multiplying (3.8) by 2 and using the Binomial as (2_i) (_2&)1 and the term (1 — )fll as (‘)—e’ we have u(e) = (—2) iB In the previous Section, we proved that there are 2t when f(e) = (n + 2n 0. We remove the common factor of 2t 6 dmin — — 1) () 1 roots at e (3.9) = 0 in (3.3) from (3.9) by multiplying both Chapter 3. Determining the Properness of a Code 17 sides by e . This is, again, to eliminate the multiple roots of u(e) at 2 Fourier’s function in Also, note that B is zero for 0 fseq(). < = 0 and reduce where i < is the minimum distance of a dual code. Hence, (3.9) becomes 1) (_2)1e1_2t (i =(—2) >iBj v(e) (3.10) — (n +2’n — l=2t The d-th derivative v(d)(e) )(e) t v =(—2) of (3.10) is (i iB — 1) ( )l1_2_d 2 fl(l — 21— mm (3 11) (n +2n l)(l)11_2t_d(l 1=2t+d for 0 d 21 — j) 21—j) j=0 1. A detailed derivation of (3.11) is given in Appendix B. In — (3.11), we let A (i — 1) = )11_2t_d 2 ( fi (1— 21— j) (3.12) j=O 1=2t+d and B (n — 1) = 2t e 1 1) ’ ( (1— 21 — j). (3.13) l—2t+d We are interested in evaluating (3.11) at e First we consider the case when e A = () = 0 and e = 0.5. 0. We write (3.12) as (_2)200 . = H (d - j) j=0 i—i d—1 (3.14) ‘)(_2)lol_22_dfj(121_i) + 1=2t+d+1 j=0 and (3.13) as B =(;)1)2t+doorj(d_) (3.15) (n l2t—d+1 ‘)(1)dOl-2t-d fl(1-21-i). j=0 Chapter 3. Determining the Properness of a Code Since O term = 0 and x° () 18 I \ j—i 1 for x > 0, only the term 2+d)(_2)6 = d— 1 fl (d — j) and the j=o (_1)20 dñl (d j) remain in (3.14) and (3.15), respectively. Assuming j=o e is very close to 0, (3.11) becomes — v(d)(o) =(-2) iB i=d-’mm (:) d— 1 (_2)2t+d H (d - j) j=O (3.16) d— 1 1)(l)2t+dfl(di) +2n j=O d— 1 The terms fl (d j), j=O (_ ) 2 2t — (_l)2t+d1 2 2 +d and (_ ) 1 d, and (_ ) 1 2+d in (3.16) can be rewritten as respectively. Thus, we have common factors of (—l)’ and ci! in (3.16). After collecting like terms, (3.16) becomes v(d)(o) d+21+1 2 = (l)dd! [(_l) iBi(+) +2Pn(;)] (3.17) _dmn For e -, (3.12) reduces to i—i A= l=2t+d —2i—d d—1 Ii —1” 1 fl(l-2t-j) (3.18) j=O and (3.13) reduces to (n_l)(_i)lQ)’ B= 2—d d—1 fJ(l_2t-j). (3.19) 1=2t-fd By writing (—2)’ (d) (1) = 2 1+2t+d (—1)’2’ and 2t+d[( 2 2) 1) iB mmn (3.11) becomes (-1)’ fl(l- 2t j=O l=2t+d (1)(_1)12_1(l_2t_i)J. l=2+d j=O - j) (3.20) Chapter 3. Determining the Properness of a Code 19 3.2 Method Based on Sturm’s Theorem Fourier’s Theorem enables us to determine the maximum possible number of real roots that a polynomial equation with real coefficients has within a given interval. Sturm improved Fourier’s method and derived an algorithm which yields the exact number of real roots that a polynomial equation with integer coefficients, without multiple zeros, has within a given interval [15, p.34.1]. In this Section, we use Strum’s Theorem to determine the properness of a code. Let sseq(x) be the Sturm sequence of a polynomial equation f(x) + cix + co = = cqx+Cq_ x_l 1 + 0. .sseq(x) is defined as sseq(x) = {f(x), f’(x), ri(x), ..., (3.21) r(x)}. This sequence is obtained by applying the Euclidean algorithm to the polynomial f(x) and f’(x), where f’(x) is the first derivative of f(x), and talcing r (x), i 2 = 1, ...,j as the negative of the remainder polynomial. The sequence is defined by the following relations: f(x) f The functions f(x), f’(x), rl(x), If there are no multiple roots in = f’(x)qi(x) (x) = rl(x)q2(x) r,_2(x) roots exist in f(x) = ..., = - — _i(x)q 3 r ( x) r,(x) f(x) = ri(x) r2(x) — (x) 3 r in the sequence are called Sturm’s functions. 0, then r(x) is a constant. When multiple 0, the last Sturm’s function in the sequence is the greatest common divisor (gcd) of f(x) and f’(x) [17, p.53]. Sturm’s Theorem then states that the number of real roots of f(x) f(x) = 0 from the z, neither y nor z is a root of [18, p.96], is equal to the number of sign variations lost in sseq(x) in passing substitution x = y to the substitution x = z. = 0 located between the interval y and Chapter 3. Determining the Properness of a Code 20 One of the methods to test the existence of multiple roots in gcd of f(x) and f’(x) multiple roots in f(x) Proof: Assume (x f(x) = 0 is to find the [19, p.222]. If gcd(f(x), f’(x)) is not a constant, then there are 0. The proof is given as follows: = — a) is a factor of f(x). Rewriting f(x) as f(x) then the first derivative f’(x) f’(x) = (x — a)ag(x), (3.23) of f(x) becomes = (x — a)_1 [g(x) + (x — a)g’(x)] (3.24) where g’(x) is the first derivative of g(x). Thus the greatest common divisor of f(x) and f’(x) is gcd(f(x), f’(x)) Therefore, there are ci roots at x = a = in f(x) (x = a)’. — (3.25) 0. 3.3 Testing of the Algorithms on Some BCH Codes In Appendix A the weight distribution A, of the (31,11) code is given. In order to illustrate the methods described in Sections 3.1 and 3.2, we use the MacWilliam’s Identity to obtain the weight distribution B 2 of the dual code. The weight distribution is tabulated in Table 3.6. i 2 B i 2 B 0 1 16 301971 6 806 18 195300 8 7905 20 85560 10 41602 22 18910 12 142600 24 2635 14 251100 26 186 Table 3.6 The weight distribution of the dual (3 1,11) BCH code. Chapter 3. Determining the Properness of a Code Let e = represent a positive value and ‘+‘ ‘—‘ 21 represent a negative value in a sequence. For 0, the numerical values in the Fourier sequence fseq(e) = {f(e), f’(e), ..., f(20)(e)} evaluated by expressions (3.6) or (3.17) are fseq(= 0) {+,—,+,—,+,--,+,—,+,—,+,—,+,—,+,—,+,—,+,—,+}. (3.26) = The number of sign variations for this sequence is 20. For E = 0.5, the numerical values in the Fourier sequence evaluated by expressions (3.7) or (3.20) are fseq(e = 0.5) = —, +, —, +, —, +, —, +, —, +, —, +, —, +, —, +, —, +, —, (3.27) The number of sign variations for this sequence is also 20. Hence, the number of sign variations lost is fseq(e For e = 0) — fseqfr = 0.5) = 0. sseq() equals to 0, the numerical values of the Sturm sequence {f(e),f’(e),ri(),...,ris(6)} are sseq(e = 0) = {+, —, +, +, —, —, +, +, —, —, +, +, —, +, +, +, —, —, +, +}. (3.28) The number of sign variations for this sequence is 10. For e equals to 0.5, the numerical values of the Sturm sequence are .s.seq(e = 0.5) = {+, —, +, +, —, +, +, +, —, +, +, —, —, —, +, +, +, —, +, +}. (3.29) The number of sign variations for this sequence is also 10. Hence, the number of sign variations lost is sseq(e = 0) — sseq(e = 0.5) = 0. The results imply that there are no real roots of P(6) = 0 in the region of e (0, 0.5). Therefore, we conclude this code is proper. We also test of the properness of the codes in Table 2.1 (except the ( m 2 _2 correcting BCH codes for 3 < m < 10) using the algorithms as follows: 1. The sign variations of the fseq(e 2. The sign variations of the sseq(e = 0) — f.seq(e = 0) — sseq(e = = 0.5) were computed. 0.5) were computed. — 1)-error- Chapter 3. Deternilning the Properness of a Code 22 The results corresponding to the items listed above are: 1. There are four codes whose sign variations of the fseq(€ = 0) 2. There are four codes whose sign variations of the .sseq(e = 0) — — fseq(6 sseq(e = 0.5) = 2. 0.5) = 2. These four BCH codes are (63,39), (63,24), (127,92) and (255,29). In Table 3.7, we summarize the results regarding the properness of the codes in Table 2.1. n k t 31 11 63 39 36 proper improper proper 30 127 n k t 22 15 proper proper 223 proper proper 29 improper 24 improper 21 proper 18 proper 13 proper 16 proper 31 proper 10 proper 28 proper 99 proper 19 proper 92 improper 26 proper 29 proper 16 proper 255 511 1023 Table 3.7 Summary of results of the properness of BCH codes in Table 2.1. We also applied the algorithm to the extended BCH codes of Table 2.1. The results show that the properness of the extended BCH codes of Table 2.1 are the same as their primal codes. Fourier’s and Sturm’s Theorems were tested on the BCH codes given in Table 2.1. The general expressions of (3.6), (3.7) and (3.16), (3.20) were derived in terms of {A} and { B}, respectively, for Fourier’s functions in fseq(e = 0) and fseq(e = 0.5). However, Fourier’s method yields only an upper bound on the number of roots and ambiguity would arise if fseq(e = 0) — fseq(e = 0.5) > 0 . In contrast, Sturm’s method gives Chapter 3. Determining the Properness of a Code 23 the exact number of roots, but the disadvantage is the somewhat greater complexity in computing Sturm’s function. Using the MAPLETM library routines “diff(a,xl ,x2,...,xn)” and “rem(a,b,x)” to com pute Fourier’s and Sturm’s function for the BCH codes in Table 2.1 showed that the Sturm’s functions took somewhat longer to compute. Simple programs could also be written to compute Fourier’s functions for the BCH codes in Table 2.1 using expressions of (3.6), (3.7), (3.16) and (3.20) which should take only a fraction of the time required by MAPLE. The upper bound on the number of roots obtained by Fourier’s method is the same as the exact results provided by the more complex Sturm’s method for the BCH codes investigated in this thesis. This suggest that it may be beneficial to try Fourier’s method first. Chapter 4. Bounds on the Weight Distributions of BCH Codes Because general expressions for the weight distributions of BCH codes for correcting more than three errors are not known, a number of authors have given bounds on these weight distributions [20], [21], [22], and [12]. In this chapter, we consider two methods to tighten the upper and lower bounds discussed in [121. 4.1 A Review of Some Approximations to the Weight Distributions of BCH Codes Peterson [23] observed that the number of codewords of weight i for most of the binary (n, k) BCH codes for which the weight distributions are known is closely approximated by the binomial distribution, namely 2 A —(n—k) 2 (4.1) (‘) over their nonzero range i. It can be shown [24] that a code with a binomial weight distribution is proper. Sidel’nikov [21] proved the following result on the weight distribution of BCH codes: 2 A for 0 < t < /7fO = —(n—k) 2 () (1 + E), and weight i satisfies the inequalities 2t + v(t) (4.2) i n — 2t — v(t) where v(t)= where lxi E2tln t + 4.5t + 0.lln i-il 0.5lnn—lnt—2.25 (4.3) denotes the smallest integer which is greater than or equal to x. E is given as EI < Cn 01 where C is a constant. In (4.2), E is the relative deviation of the 7 ( 2 m_k)( . From the constraint number of codewords A from the binomial distribution ) 24 Chapter 4. Bounds on the Weight Distributions of BCH Codes of 0 < t < 25 J7iö, we see that Sidel’nikov’s result is mostly applicable to BCH codes with large n. Also for n large and t < 0.2(in n/in in n), v(t) is approximately equal to 1. Kasami et at. [22] improved Sidel’nilcov’s result. They obtained upper and lower bounds on E by solving a linear programming problem using the simplex algorithm. Unlike Sidel’nilcov’s method, their method is applicable to all values of n and t. Kasami et a!. [12] further improved the linear programming approach [22] to approximate the weight distribution of extended BCH codes. Because the extended dual binary primitive BCH code is a subcode of the r-th order Reed-Muller code )?(r, m), where r is any integer between 0 and m. Kasami et al. were able to use the restriction on the nonzero weights of Reed-Muller codes to improve the bounds. The restriction on the nonzero weights of F(r, m) is that all such weights are multiples of 2 Em/ri—i [3, p.44.7] . The relationship between r and t is given as [12] r = [log2(2t + 2)1 — i. (4.4) Consider a binary (n, k) BCH code C. Let Ca-, C€ and C be the dual code, extended code and extended dual code of C, respectively. For C with designed distance 2t + 1 where 2t — 1 < 21m/21 + 1, the weight j 2m1 2— + (t of any nonzero codeword in C- lies 1 in the range [3, p.281], where j — (t — 1)2m/2 <1 — 1)2m/2 (4.5) is even. Kasami et a!. defined the weight distribution width w of Cg as [121 w= Actually, equation (10) in [12] L2(t_1)2m/ i 2 . contains a typographical error. (4.6) Chapter 4. Bounds on the Weight Distributions of BCH Codes Let Bext,j be the number of codewords of weight 26 j of C when j lies in the range of (4.5). Then, Bext,j if j is not a multiple of 2Cm/ri_i or 0 <j = (4.7) 0 < (n — w)/2 and (n + w)/2 <j < n. From MacWilliam’s identity, the relationship between Aext,j and Bext,j is [3, p.1281 Aext,i = -(n--k) Pj(j)Bext,j 2 (4.8) where 1 P ( j) is a Krawtchouk polynomial defined as [3, p.128] P(j) Since = .t,n 2 Be = Aezt,j (4.9) = (_i)1() 1 [12], and, P (0) = P 2 (n) 2 = 2 -(n—k)+i [() = (fl, then (4.8) can be rewritten as (4.10) Pi()Bext]. + n—2,Iw Define Eex,j as [12] Eezt,i = 1(n)_i Fi(j)Bext,j, (4.11) In—2i1 u’ then (4.10) becomes Aext,i = 2 —(n---k)+1 ()(i + Eex,i) (4.12) where Eext,j is the relative deviation of the number of codewords At from the binomial distribution —(n—k)+i 2 (fl) For the weight distribution of the following Pless power-moment identities also hold [12] Im—2i1w ( — j)Bext,j = 21 2n_kM — 2(i), for 0 < I t (4.13) Chapter 4. Bounds on the Weight Distrthutions of BCH Codes 27 where M, = d( ) 1 cosh’x dx() 2 (4.14) . x=O The linear programming approach in [12] finds the maximal or minimal solution of the objective function {)- (4.15) F(i)b} In—2i1w subject to the following constraints I n—2j — ( <w = = 3 b = 21 2n_kM b_,, for n — — for 0 2(-), 2j w 1 t (4.17) , 0, if j is not a multiple of 21m/’1_1 (4.16) (4.18) , and 3 b 0, otherwise, (4.19) where b,’s are the variables of the objective function. The constraints (4.16)-(4.19) are the same as the restrictions (4.13), (2.10) and (4.7) on the weight Let j of C. be the maximal value of (4.15) subject to the constraints of (4.16)-(4.l9), then LP is an upper bound on Eex,i, i.e. Eexi,i LPf. Similarly, let LF be the minimal value of (4.15) with the constraints of (4.16)(4.19). The lower bound on Eert,i is Eext,j max{_l, LP}. A typographical error is present in equation (14) of [12] (4.20) Chapter 4. Bounds on the Weight Distributions of BCH Codes The upper bound on Aext,j, = 28 and the lower bound on Aexi,i, are —(n—k)+1 2 (). (i. + LPei) (4.21) —(n—k)+1 2 (:) (i + (4.22) and = respectively. From (1.1), the upper and lower bounds on the probability of undetected error of extended BCH codes, F(e) and F(e), are given as follows: A?(1 F() — E)fh (4.23) e)fl_i (4.24) = and A?(1 — = To obtain A, given we can use the following relationships between A and Aext,i where i is even [12]: 1 A_ (4.25) Aext,i = and A 4.2 Computation of —i t 2 m = 2’ (4.26) Aext,i. and The MAPLETM package of “Simplex” [14, p.317] was used to evaluate the upper and lower bounds, LF and LPei for the following extended BCH codes: 1. triple-error-correcting codes with 8 i 2— for 2. four-error-correcting codes with 10 i 28 for 6 m 20; 3. five-error-correcting codes with 12 i 30 for 6 m 20; 4. six-error-correcting codes with 14 i <32 for 7 < 5. seven-error-correcting codes with 16 < 34 for 8 m = 7, 8; 20; and, m m 20. Chapter 4. Bounds on the Weight Distributions of BCH Codes 29 Tables 4.8 and 4.9 contain the LF and LP of the extended BCH codes for 4<t<7,6 m w 2 l2form and2t+2i2t+l log 0. FromTable4.8,the following comments on LF on Eext,i can be made: 1. For fixed values of m and i, LPf is relatively tight for small t. 2. For fixed values of in and t, LP is relatively tight for large i, except when (t=5, m=6) and (=5, m=7). 3. For fixed values of t, and i, In Table 4.9, if LF <—1 is relatively tight for large m. , we set = —1 due to (4.20). The approximate value of LPeLi is given in brackets to one decimal place. The following comments on LP Ofl Eext,i can be made: 1. For fixed values of m and i, LP is relatively tight for small t. 2. For fixed values of m and t, LP is relatively tight for large i, except when (t=4, m=6), (t=5, m=6), (t=5, m=7) and (t=6, m=7). 3. For fixed values of t and i, LF is relatively tight for large in, except when (t = 6, m = 7, i = 10) and (t = 6, m = From (4.16), 1 is defined in the range 0 < 1 8, i = 10). t. The total number of equations available to solve for the nonzero 3 b ’ s of (4.15) is thus t + 1. The total number of nonzero b ’s of 3 rm/1 (4.15) in the interval corresponds to the number of multiples of 2 1 in that interval and is given by #of nonzero = [ 2m-1 21m/rl—1 j + 1 (4.27) where min = (n — w)/2. (4.28) Chapter 4. Bounds on the Weight Distributions of BCH Codes 4 5 m w i 6 48 1.39E1 7 66 8 7 i i=14 i16 i18 1.43E0 1.26E0 2.74E-1 1.09E-1 4.76E0 2.95E-1 9.36E-2 1.17E-2 2.62E-3 96 2.15E0 5.1OE-2 7.05E-3 4.45E-4 3.36E-5 9 134 1.08E0 1.48E-2 1.12E-3 3.27E-5 162E-6 10 192 4.80E-l 2.80E-3 9.OOE-5 1.42E-6 2.52E-8 11 270 2.53E-1 8.57E-4 l.62E-5 1.15E-7 1.41E-9 12 384 1.54E-1 2.1OE-4 2.17E-6 7.03E-9 4.35E-10 i=12 i=14 i=16 i=18 i=20 = = 12 6 64 1.90E2 6.69E1 1.24E2 9.99E1 1.10E2 7 90 6.44E1 3.31E0 4.56E0 5.88E-1 2.13E-1 8 128 2.38E1 8.28E-1 3.80E-1 2.36E-2 3.58E-3 9 180 1.22E1 1.31E-1 3.66E-2 5.22E-4 4.69E-5 10 256 5.06E0 3.37E-2 4.13E-3 4.47E-5 1.58E-6 11 362 2.81E0 6.99E-3 4.81E-4 1.60E-6 3.25E-8 12 512 1.48E0 2.12E-3 7.34E-5 1.54E-7 1.65E-9 14 i=16 i=18 i=20 i=22 i 6 10 30 = 7 110 3.56E2 7.43E1 6.78E1 2.97E1 1.53E1 8 160 2.38E2 2.96E1 1.41E1 3.37E0 9.37E-1 9 266 1.67E2 2.13E1 5.47E0 1.07E0 2.14E-1 10 320 4.79E1 1.22E0 1.40E-1 6.88E-3 4.08E-4 11 452 2.57E1 2.77E-1 1.69E-2 3.69E-4 1.05E-5 12 640 1.41E1 7.99E-2 2.43E-3 2.76E-5 4.O1E-7 i=16 i=18 i=20 i=22 i=—24 8 192 2.58E3 6.37E2 4.13E2 1.83E2 8.66E1 9 270 1.22E3 1.10E2 3.43E1 5.99E0 1.18E0 10 384 3.55E2 6.12E0 1.20E0 5.56E-2 4.04E-3 11 542 2.64E2 5.38E0 4.08E-1 1.53E-2 7.37E-4 12 768 1.51E2 1.80E0 6.79E-2 1.50E-3 3.62E-5 Table 4.8 Upper bounds LP on Eetj for the extended BCH codes for 4< t <7,6 m w and 2t+2 < i < 2t+12. 2 10 form >log Chapter 4. Bounds on the Weight Distributions of BCH Codes rn 4 5 = 7 = 12 i=14 i=16 i=18 6 -1(-2.1EO) -1(-2.6E0) -6.64E-1 -3.OOE-1 -1.1OE-1 7 -9.O1E-1 -6.07E-l -6.29E-2 -1.65E-2 -2.05E-3 8 -3.26E-1 -1.O1E-1 -5.11E-3 -5.51E4 -3.69E-5 9 -1.89E-1 -3.29E-2 -7.45E-4 -4.45E-5 -1.36E-6 10 -7.31E-2 -5.56E-3 -6.77E-5 -1.76E-6 -2.82E-8 11 -4.44E-2 -l.94E-3 -l.07E-5 .-l.56E-7 -l.17E-9 12 -2.17E-2 -5.02E-3 -l.31E-6 -l.1OE-8 -3.60E-ll i=12 i=14 i=16 z=18 20 6 -1(-1.8E1) -l(-3.3E1) -1(-9.6E0) -l(-7.1EO) -1(-2.5E0) 7 -1(-4.2E0) -l(-5.4E0) -3.62E-l -2.27E-l -l.21E-2 8 -1(-2.4E0) -l(.1.OEO) -5.83E-2 -9.38E-3 -6.18E-.4 9 -1(-1.2E0) -2.93E-1 -7.40E-3 -6.85E-4 -1.98E-5 10 -5.24E-1 -5.40E-2 -7.35E-4 •2.82E-5 -4.45E-7 11 -2.83E-1 -1.69E-2 -1.03E-4 -2.37E-6 -1.64E-8 12 -1.54E-1 -4.48E-3 -1.42E-5 -1.54E-7 -5.69E-10 i=16 i=18 i=20 i=22 i 6 10 31 = 14 7 -1(-1.4E1) -1(-2.6E1) -1(-1.3E0) -1(-1.1EO) -3.15E-2 8 -1(-1.8E1) -1(-1.OE1) -7.21E-1 .-1.42E-1 -1.20E-2 9 -1(-9.5E0) -1(-2.8E0) -9.48E-2 -9.65E-3 -3.83E-4 10 -1(-3.7E0) -5.06E-1 -8.48E-3 -4.08E-4 -7.92E-6 11 -1(-2.2E0) -1.57E-1 -1.28E-3 3.19E-5 -3.07E-7 12 -1(-1.2E0) -4.31E-2 -1.73E-4 -2.21E-6 -1.03E-8 i=16 i=18 i=20 i=22 i=24 8 -1(-1.5E2) -1(-1.2E2) -1(-9.9E0) -1(-2.7E0) -2.51E-1 9 -1(-7.9E1) -1(-3.3E1) -1(-1.2E0) -1.72E-1 -6.87E-3 10 -1(-2.9E1) -1(-5.7E0) -1.06E-1 -6.97E-3 -L47E-4 11 -1(-1.8E1) -1(-1.8E0) -1.59E-2 -5.49E-4 -5.26E-6 12 -1(-9.1EO) -4.73E-1 -2.12E-3 -3.67E-5 -1.82E-7 Table 4.9 Lower bounds LP 1 on 4< <7,6 m < 10 form for the extended BCH codes for w and 2t +2 <i 2 log 2+ 12. Chapter 4. Bounds on the Weight Distributions of BCH Codes 32 In Table 4.10, we tabulate parameters in computing LP and LP for the extended BCH codes in Tables 4.8, 4.9 and also for the extended BCH codes for t rn = 7,8. The quantity minA = 3 is defined as = Jmi7z + (_jrnin rm/r]_1). mod 2 Due to the restriction on the nonzero weights of (r, m), (4.29) minA is used in computing LFeUi and LFei. After investigating the relationship between (4.27) and t+ 1 in Table 4.10, Table 4.11 is tabulated for the t = 3, m = 7, 8 and t = 4, m = 6, 7, 8 extended BCH codes. Table 4.11 contains the information of the ratio of the number of 3 b ’ s to I + 1, the relative deviations of (Aext,i and and, (Aext,i and A) which are denoted as Ratio, RDUB and RDLB, respectively. The parameters Ratio, RDUB and RDLB are defined as Ratio = #of nonzero t+1 A ext,: RDUB AUB ezt,: — Aext,i Eezt,j (4.30) — < wo (4.31) LFf x 1 + Eext,i 100 and ALB A ext,z RDLB Eexi,i = ezt,i < 100 (4.32) — xlOO, 1+ respectively. Eextj is computed from (4.12). In Table 4.11, we found that in one case when t in = = 3 and m = 7, = 8, for a given value of i either = Aezj,i. It was found that when I = Aext,j or = = 3 and Aext,i. Generally a lower Ratio results in tighter bounds on the weight distribution of the code. Since I is a constant, one method of getting tighter bounds is to reduce the number of nonzero b, ‘S in (4.27). In the next Section, we consider two methods to tighten LP 1 and Chapter 4. Bounds on the Weight Distributions of BCH Codes rrnIri —1 2 33 t m w 3 7 44 42 2 8 48 3 4 8 64 96 2 8 96 5 4 6 48 8 3 2 8 13 5 7 66 31 3 4 32 9 5 8 96 80 3 4 80 13 5 9 134 189 3 4 192 17 5 10 192 416 3 8 416 13 5 11 270 889 3 8 896 17 5 12 384 1856 3 8 1856 25 5 6 64 0 3 2 0 17 6 7 90 19 3 4 20 12 6 8 128 64 3 4 64 17 6 9 180 166 3 4 168 23 6 10 256 384 3 8 384 17 6 11 362 843 3 8 848 23 6 12 512 1792 3 8 1792 33 6 7 112 8 3 4 8 15 7 8 160 48 3 4 48 21 7 9 226 143 3 4 144 29 7 10 320 352 3 8 352 21 7 11 452 798 3 8 800 29 7 12 640 1728 3 8 1728 41 7 8 192 32 3 4 32 25 8 9 270 121 3 4 124 34 8 10 384 320 3 8 320 25 8 11 542 753 3 8 760 34 8 12 768 1664 3 8 1664 49 8 4 5 6 7 # of b 3 0 0 t + 1 Table 4.10 Parameters to compute LP and LPf for the extended BCH codes in Tables 4.8 and 4.9. Chapter 4. Bounds on the Weight Distributions of BCH Codes (n, k) (128,106) (256,231) (64,39) (128,99) (256,223) 34 m I Ratio i RD(%) RD’(%) 7 3 0.75 8 0 0 10 0 0 12 0 0 14 0 0 16 0 0 8 0 8.O1EO 10 5.31E-1 0 12 0 1.77E-2 14 2.35E-4 0 16 1.77E-5 0 10 8.68E2 1.69E2 12 1.76E2 2.83E2 14 1.24E2 6.67E1 16 2.70E1 3.02E1 18 1.09E1 1.1OE1 10 5.12E2 8.95E1 12 2.69E1 6.15E1 14 9.61E0 6.50E0 16 1.16E0 1.66E0 18 2.61E-1 2.06E-1 10 2.09E2 3.39E1 12 5.06E0 1.O1E1 14 7.09E-1 5.15E-1 16 4.42E-2 5.52E-2 18 3.35E-3 3.70E-3 8 6 7 8 3 4 4 4 1.25 2.6 1.8 2.6 Table 4.11 Ratio, RDUB d RDLB for the t = 3, m = 7,8 and t = 4, m = 6, 7, 8 extended BCH codes. Chapter 4. Bounds on the Weight Distributions of BCH Codes 35 4.3 Two Methods for Improving Kasami’s Bounds on the Weight Distribution of BCH Codes In this Section, two methods are proposed to tighten LFf and LF of Section 4.2. The extended dual (64,39), (64,36), (128,99), (128,92) and (256,223) BCH codes whose weight distributions were computed in Chapter 2 are used as examples to illustrate the improvements. 4.3.1 Method 1: Using the Minimum Distance of an Extended Dual BCH Code Let dmin,ext and djn ext be the minimum distance of Cext and From (2.9), dmjn,ext = din,ext• In Table 4.12, we tabulate din ext’ respectively. min, w’ and w for the extended dual (64,39), (64,36), (128,99), (128,92) and (256,223) BCH codes, where w’ is given as = n — 2dinext• ( n, k) m t dn,e,t J,nmA WI (64,39) 6 4 14 8 36 48 (64,36) 6 5 14 0 36 64 (128,99) 7 4 44 32 40 66 (128,92) 7 5 32 20 64 90 (256,223) 8 4 96 80 64 96 Table 4.12 The djnea,t, jmin’ WI and w for the extended dual (64,39), (64,36), (128,99), (128,92) and (256,223) BCH codes. Table 4.12 shows that djn ext > mi By replacing (4.19), we compute the new LP for 2t + 2 miw 2m_1. by in (4.15)- Let LPeB’ and be the maximal and minimal solutions to the objective function (4.15) subject to the constraints (4. 16)-(4. 19) with min replaced by respectively. The superscripts 1 and LB’ denote the improved upper and lower bounds of Method 1, respectively. UB Chapter 4. Bounds on the Weight Distributions of BCH Codes 36 4.3.2 Method 2: Using the Number of Codewords at the Minimum Distance of an Extended Dual BCH Code In Section 4.3.1, LF and LF were improved by replacing the value of m j by din,ext. In this Section, we improve the tightness of LP and LP on Eezt,i by using the minimum distance of an extended dual BCH code and the number of codewords at the minimum distance. Let LF and LF be the maximal and minimal values of (4.15) under the constraints of (4.16) -(4.19), respectively, with min replaced by djn,ext and bjmjn set to Bext dmInext where ‘ d. m:ri,e.rt is the number of codeword at ext The superscripts 2 and LB UB 2 denote the improved upper and lower bounds of Method 2. Table 4.13 tabulates exact Eexi,i, codes in Table 4.12 with 2t + 2 i LPf and LPf for the extended BCH 2t + 10. Table 4.15 contains the results of LPei LF and LF for the codes in Table 4.12. Table 4.14 lists the relative deviations of (Aexi,i and and and, and A) computed from (4.31) using the upper bounds in Table 4.13 for the extended B CH codes in Table 4.12. Similarly, Table 4.16 list the relative deviations of (Aevj,j and (Aext,j and A’), and, (Aext,i and A) computed from (4.32) using the lower bounds in Table 4.15 for the codes in Table 4.12. Figure 4.2 to 4.6 are curves of the probability of undetected error of the extended BCH codes in Table 4.12 for 0 <e 0.5. The following curves are included: 1. The exact Fext,u() evaluated from (1.1) in Figure 4.2 to 4.6. 2. The F.(E) and computed from (4.23) and (4.24) by using LPf and LFej, respectively, in Figure 4.2 to 4.6. 3. The Pj(e) and P(e) computed by using LPCB and Figure 4.2a to 4.6a. respectively, in Chapter 4. Bounds on the Weight Distributions of BCH Codes k) m t i (64,39) 6 4 10 (n, (64,36) (128,99) (128,92) (256,223) 6 7 7 8 5 4 5 4 37 LPJ LP 5.38E-1 1.39E1 5.61E0 3.80E0 12 -1.18E-1 1.43E0 1.43E0 8.65E-1 14 7.85E-3 1.26E0 7.83E-1 7.59E-1 16 3.16E-3 2.74E-1 2.74E-1 2.30E-1 18 -3.71E-4 1.09E-1 1.09E-1 1.04E-1 12 8.89E0 1.90E2 2.85E1 1.30E1 14 6.96E0 6.69E1 1.59E1 1.57E1 16 6.88E0 1.24E2 1.26E1 9.56E0 18 7.08E0 9.99E1 5.OOEO 4.97E0 20 6.94E0 1.10E2 2.90E0 2.90E0 10 -5.74E-2 4.76E0 5.45E-1 -5.74E-2 12 2.03E-2 2.95E-1 2.95E-1 2.03E-2 14 -2.24E-3 9.36E-2 4.11E-2 -2.24E-3 16 9.98E-5 1.17E-2 1.17E-2 9.98E-5 18 1.29E-5 2.62E-3 1.48E-3 1.29E-5 12 7.30E-1 6.44E1 2.37E1 L36E1 14 -9.81E-2 3.31E0 1.54E0 1.14E0 16 1.29E-2 4.56E0 9.75E-1 8.05E-1 18 -2.71E-3 5.88E-1 7.03E-2 5.59E-2 20 5.58E-4 2.13E-1 3.20E-2 2.37E-2 10 2.OOE-2 2.15E0 5.06E-1 2.66E-1 12 3.66E-4 5.1OE-2 5.1OE-2 3.23E-2 14 4.05E-5 7.05E-3 5.61E-3 4.1OE-3 16 2.09E-6 4.45E-4 4.45E-4 3.40E-4 18 1.49E-7 3.36E-5 3.36E-5 3.31E-5 Table 4.13 Exact Eea,tj and LPef j, LPf, LP for the extended BCH codes listed in Table 4.12 for 2 + 2 i < 2t + 10. Chapter 4. Bounds on the Weight Distributions of BCH Codes 38 (n,k) m t i RD(%) RD’(%) RD ( 2 %) (64,39) 6 4 10 8.68E2 3.30E2 2.12E2 12 1.76E2 1.76E2 1.12E2 14 1.24E2 7.69E1 7.45E1 16 2.70E1 2.70E1 2.26E1 — 18 1.09E1 1.09E1 1.04E1 5 12 1.83E3 1.98E2 4.16E1 14 7.53E2 1.12E2 1.10E2 16 1.49E3 7.26E1 3.40E1 18 1.15E3 2.57E1 2.61E1 20 1.30E3 5.10E2 5.10E2 10 5.12E2 6.39E1 0 12 2.69E1 2.69E1 0 14 9.61E0 4.34E0 0 16 1.16E0 1.16E0 0 18 2.61E-1 1.47E-1 0 12 3.68E3 1.33E3 7.44E2 14 3.78E2 1.82E2 1.37E2 16 4.49E2 9.50E1 7.82E1 18 5.92E1 7.32E0 5.88E0 20 2.12E1 3.14E0 2.31E0 10 2.09E2 4.76E1 2.41E1 12 5.06E0 5.06E0 3.19E0 14 7.09E-1 5.57E-1 4.06E-1 16 4.42E-2 4.42E-2 3.38E-2 18 3.35E-3 3.35E-3 3.30E-3 (64,36) (128,99) (128,92) (256,223) 6 7 7 8 4 5 4 RDUB for the Table 4.14 Relative deviations RDUB, RDUB’ jjd 2 extended BCH codes listed in Table 4.12 for 21 + 2 j < 21 + 10. Chapter 4. Bounds on the Weight Distributions of BCH Codes k) t i (64,39) 4 10 (iij, (64,36) (128,99) (128,92) (256,223) 5 4 5 4 39 LP LP LP 5.38E-1 -1.(-2.06E0) -1.(-2.06E0) -8.15E-1 12 -1. 18E- 1 -1 .(-2.61E0) -1 .(-2.47E0) -1 .(-2.O1EO) 14 7.85E-3 -6.64E-1 -6.64E-1 -4.91E-1 16 3.16E-3 -3.OOE-1 -2.63E-1 -2.59E-1 18 -3.71E-4 -1.1OE-1 -1.1OE-1 -1.O1E-1 12 8.89E0 -1.(-1.77E1) -1.(-1.77E1) -1.(-1.74E1) 14 6.96E0 -1 .(-3.27E 1) -1 .(-2.32E 1) -1 .(- 1.39E 1) 16 6.88E0 -1.(-9.57E0) -1.(-9.57E0) .-1.(-9.48E0) 18 7.08E0 -1.(-7.05E0) -1.(-5.99E0) -1.(5.49E0) 20 6.94E0 -1 (-2.48E0) -1 .(-2.48E0) -1 .(-2.47E0) 10 -5.74E-2 -9.O1E-1 -9.O1E-1 -5.74E-2 12 2.03E-2 -6.07E-1 -1.76E-1 2.03E-2 14 -2.24E-3 -6.29E-2 -6.29E-2 -2.24E-3 16 9.98E-5 -1.65E-2 -8.17E-3 9.98E-5 18 1.29E-5 -2.05E-3 -2.05E-3 1.29E-5 12 7.30E-1 -1.(-4.17E0) -1.(-4.17E0) -1(-2.57E0) 14 -9.81E-2 -1 .(-5.36E0) -1 .(-5.36E0) -1 (-4.03E0) 16 1.29E-2 -3.62E-1 -3.62E-1 -2.85E-1 18 -2.71E-3 -2.27E-1 -1.80E-1 -1.41E-1 20 5.58E-4 -1.21E-2 -1.21E-2 -9.53E-3 10 2.OOE-2 -3.26E-1 -3.26E-1 -1.78E-1 12 3.66E-4 -1.O1E-1 -6.33E-2 -3.83E-2 14 4.05E-5 -5.11E-3 -5.11E-3 -3.56E-3 16 2.09E-6 -5.50E-4 -4.31E-4 -3.81E-4 18 1.49E-7 -3.68E-5 -3.69E-5 -3.1OE-5 ‘Iãble 4.15 Exact Ee,j and LPei, LP, LP for the extended BCH codes listed in Table 4.12 for 2t + 2 < i 2t + 10. Chapter 4. Bounds on the Weight Distributions of BCH Codes (n,k) m t (64,39) 6 4 (64,36) (128,99) (128,92) (256,223) 6 7 7 8 40 RDLB(%) RD(%) RD ( 2 %) 10 1.69E2 1.69E2 8.80E1 12 2.83E2 2.67E2 2.15E2 14 6.67E1 6.67E1 4.95E1 16 3.02E1 2.65E1 2.61E1 — 18 1.1OE1 1.1OE1 1.O1E1 5 12 2.69E2 2.69E2 2.66E2 14 4.98E2 3.79E2 2.62E2 16 2.08E2 2.08E2 2.08E2 18 1.75E2 1.62E2 1.56E2 — 20 1.19E2 1.19E2 1.19E2 4 10 8.95E1 8.95E1 0 12 6.15E1 1.92E1 0 14 6.50E0 6.50E0 0 16 1.66E0 8.27E-1 0 — 18 2.06E-1 2.06E-1 0 5 12 2.83E2 2.83E2 1.91E2 14 5.83E2 5.83E2 4.36E2 16 3.70E1 3.70E1 2.94E1 18 2.25E1 1.78E1 1.38E1 — 20 1.27E0 1.27E0 1.O1EO 4 10 3.39E1 3.39E1 1.94E1 12 1.O1E1 6.36E0 3.87E0 14 5.15E-1 5.15E-1 3.60E-1 16 5.52E-2 4.33E-2 3.83E-2 18 3.70E-3 3.70E-3 3.12E-3 1 d RDLB 2 for the Table 4.16 Relative deviations RDLB, RDLB extended BCH codes listed in Table 4.12 for 2t + 2 < i 2t + 10. Chapter 4. Bounds on the Weight Distributions of BCH Codes 4. The FJB (e) and 41 (e) computed by using LFeB and LFe’ respectively, in Figures 4.2b to 4.6b. For LFX —1, LP’ <—1 and LF’ <—1, < of (4.22) is assumed to be zero. It can be seen in Figures 4.2 to 4.6 that the curves of Ff() and F(e) computed from using Methods 1 and 2 are better than those [12]. Generally, Method 2 gives significantly better results than Method 1. For the extended (128, 99) BCH code, Pefu(E) and F(e) computed by Method 2 are equal to We tabulate in Table 4.17 the ratio of the number of 3 b ’ s to t + 1 computed from [12] and Method 1 for the extended BCH codes in Table 4.12. A comparison of Figures 4.la to 4.5a and Table 4.17 shows the changes in Ratio and the corresponding improvements pUB ext,u) ,jjLBi an ext,u . k) m t Ratio Ratio’ (64,39) 6 4 2.60 2.00 (64,36) 6 5 2.83 1.67 (128,99) 7 4 1.80 1.20 (128,92) 7 5 2.00 1.50 (256,223) 8 4 2.60 1.80 (n, Table 4.17 Comparison of Ratio. Chapter 4. Bounds on the Weight Distributions of BCH Codes 42 lSe-07 I 12e07 9e-08 6e-O8 3e-08 0 0 5 10 15 20 25 30 35 45 40 50 Error Rate x 0.01 Figure 4.2a Comparison of P(&), Peffr), P(r) With Pext,u(e) for the extended (64,39) BCH code. 15e-07 12e-07 9e-08 I 6c-0 3c08 0 0 5 10 15 20 25 30 35 40 45 50 Error Rate x 0.01 Figure 4.2b Comparison of P(r), P(r), P.(r), P(r) with ( 0 , 2 P€ t for the extended (64,39) BCH code. r) Chapter 4. Bounds on the Weight Distributions of BCH Codes 43 Se-07 C 4e-07 Low Bound by Method 1 Upp Bound by Method 1 Kasaini a LowaiBound Kasaini’s Uppa Bound Exact / / / — — — -— — —-— - / 2e-07 Ii - / II le-07 _/ 0 5 0 10 / / • 15 20 25 30 35 45 40 50 Error Rate x 0.01 Figure 4.3a Comparison of 0 F . (r), 0 P ( r), P(r), P(r) With P€,(e) for the extended of (64,36) BCH code. 5e.07 0 4e-07 - // O 3e-07 / / / / / Lower Bound by Method 1 UpperBoundbyMethodl Kasuini’s Lower Bound Kasami’s Upper Bound Exact — — - - / / I 2e-07 Error Rate x 0.01 Figure 4.3b Comparison of 0 P ( e), P(e), P(e), P(r) with (e) for the extended of (64,36) BCH code. Chapter 4. Bounds on the Weight Distributions of BCH Codes 44 49 1 I I I I I Lower Bound by Method 1 Upper Bound by Method 1 Kasarni’s Lower Bound Kasasni’s UpperBound Exact — — — — - - - 29 1e09 0 • f 0 5 10 15 20 25 30 . . I... .1. 35 .1. 45 40 50 Error Rate x 0.01 Figure 4.4a Comparison of P(e) with Pert,u(e) for the extended (128,99) BCH code. 409 I Lower Bound by Method 2 Upper Bound By Method 2 Kasami’s Lower Bound Kasami’s UpperBound Exact 3e419 — — - — - - 2c-09 le-09 0 - (3 5 10 15 20 25 30 35 I I 40 45 50 Error Rate x 0.01 Figure 4.4b Comparison of P(e), P(e), Pfr) with Pj,(e) for the extended (128,99) BCH code. 45 Chapter 4. Bounds on the Weight Distributions of BCH Codes 3e-10 I 2 0 Lower Bound by Method 1 Upper Bound br Method I Kasami’s Lower Bound Kasanii’s Upper Bound Exact 1’’’ I 2e-10 — I — le-lO /\ ii ‘ I, \. \ \‘ Ii 0 0 5 10 15 20 I,.. .1,.., I,. • .1.,., I 25 30 35 40 45 50 Error Rate x 0.01 Figure 4.5a Comparison of with P() for the extended (128,92) BCH code. 3e-10 I LowerBoundbyMethod2 Upper Bound by Method 2 Kacami’s Lower Bound Kasami’s Upper Bound Exact 1’ I’ 2e-10 - — - 1 le-lO I I •1 I /•% I I / I / ‘. \ I, 0 o 5 10 15 20 I.... I.... I.... I 25 30 35 40 45 50 Error Rate x 0.01 Figure 4.5b Comparison of P(&), P 2 eat,u(,, P(&), P) with Pe,u() for the extended (128,92) BCH code Chapter 4. Bounds on the Weight Distributions of BCH Codes 46 iSo-jO I’ I’ I’ I’ l. o I’/” if le-lo if / : 0 Low Bound by Method 1 UppBoundbyMethod1 — — — - Kasami’sUpp&Bound Error Rate x 0.01 Figure 4.6a Comparison of .(e), P() 1 P with Pe,(&) for the extended (256,223) BCH code. iSo-jO I’ I’ I” I’ o - 1! le-lO . I I 0 5e-11 ;i. Low Bound by Method 2 Upp Bound by Method 2 Kasami’s Lowa Bound Kasami’sUppBound — — — — - - . . Error Rate x 0.01 Figure 4.6b Comparison of P(e), Pf(e), P() with Fei,t,(E) for the extended (256,223) BCH code Chapter 5. Conclusions 5.1 Summary In this thesis, we have considered the behavior of the probability of undetected error for certain BCH codes used for error detection on the binary symmetric channel. The weight distributions of the BCH codes listed in Table 2.1 were obtained by computer search. These were then used to determine those codes which are not proper. It was also proved that any code with weight distribution {A 0 = A = 1, 2m A _ 1 = 2 A 1 m = — 1} is proper. Fourier’s and Sturm’s Theorems on the number of real roots of a polynomial in a given interval were used to determine the properness of linear block codes for which the weight distributions are known. The application of Fourier’s Theorem may be somewhat easier. However, it only gives an upper bound on the number of roots and may not always provide a definite answer as to whether a code is proper. Sturm’s Theorem can be used to determine the exact number of real roots that a polynomial equation has, but, it is only applicable to polynomial equations with no multiple roots. Both theorems were applied to the BCH codes listed in Table 2.1. The results confirm the usefulness of the algorithms. The linear programming approach proposed by Kasami et al [121 to establish upper and lower bounds on the weight distributions of 4- and 5-error-correcting BCH codes is used to obtain results for 6- and 7-error-correcting BCH codes. We also investigated two methods for improving these upper and lower bounds. The results show that our methods give tighter upper and lower bounds. 5.2 Suggestions for Future Work Below is a list of work related to the area of the undetected error probability of BCH codes which deserve further investigation: 47 Chapter 5. Conclusions 1. 48 A general expression for the minimum distance of a dual BCH code for t > 3 would be useful as this would allow improved upper and lower bounds to the weight distribution for any BCH code to be obtained. 2. Derive a general expression for the number of codewords at the minimum distance for a dual BCH code for I > 3. Bibliography Bibliography [11 C.E. Shannon, “A Mathematical Theory of Communication,” Bell Syst. Tech. J., vol. 27, pp. 379—423 (Part I), pp.623—656 (Part II), July 1948. [2] S. Lin and D.J. Costello, Jr., Error Control Coding: Fundamentals and Applications. Englewood Cliffs, NJ: Prentice-Hall, 1983. [3] F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes. Amsterdam: North Holland, 1977. [4] S.K. Leung-Yan-Cheong and M.E. Heilman, “Concerning a Bound on Undetected Error Probability,” IEEE Trans. on Inform. Theory, vol. IT-22, pp. 235—237, March 1976. [5] S.K. Leung-Yan-Cheong, E.R. Barnes and D.U. Friedman, “On Some Properties of the Undetected Error Probability of Linear Codes,” IEEE Trans. on Inform. Theory, vol. IT-25, pp. 110—112, January 1979. [6] C. Leung, “Evaluation of the Undetected Error Probability of Single Parity-Check Product Codes,” IEEE Trans. Commun., vol. COM-31, pp. 250—253, February 1983. [7] T. Kasami and S. Lin, “On the Probability of Undetected Error for the Maximum Distance Separable Codes,” IEEE Trans. Commun., vol. COM-32, pp. 998—1006, September 1984. [8] K.A. Witzke and C. Leung, “A Comparison of Some Error Detecting CRC Code Standards,” IEEE Trans. Commun., vol. COM-33, pp. 996—998, September 1985. [9] C.T. Ong and C. Leung, “On the Undetected Error Probability of Triple-ErrorCorrecting BCH Codes,” IEEE Trans. on Inform. Theory, vol. 37, pp. 673—678, May 1991. [10] E.R. Berlekamp, Algebraic Coding Theory. New York: McGraw-Hill, 1968. [11] W.W. Peterson and E.J. Weldon, Jr., Error-Correcting Codes. Cambridge, MA: MIT Press, 2nd ed., 1972. Bibliography 50 [12] T. Fujiwara, T. Takata, T. Kasami and S. Lin, “An Approximation to the Weight Distribution of Binary Primitive BCH Codes with Designed Distances 9 and 11,” IEEE Trans. on Inform. Theory, vol. IT-32, pp. 706—709, September 1986. [13] T. Kasami, “Weight Distributions of Bose-Chaudhuri-Hocquenghem Codes,” Proc. Conf. Combinatorial Mathematics and Its Applications, pp. 335—357,R.C. Bose and T.A. Dowling, ecis., University of North Carolina Press, Chapel Hill, N.C., 1968. [14] B.W. Char, K.O. Geddes, G.H. Gonnet, M.B. Monagan and S.M. Watt, MAPLE Reference Manual. Watcom, 5th ed., 1988. [15] A.G. Akritas, Elements of Computer Algebra with Applications. John Wiley and Sons, 1989. [16] D.E. Knuth, The Art of Computer Programming, vol. 1, Fundamental Algorithms. Addison-Wesley, Reading, MA, 1969. [17] F. Cajori, An Introduction to the Modern Theory of Equations. New York: The MacMillan Company, 1912. [18] L. Dickson, First Course in the Theory of Equations. New York: John Wiley and Sons, Inc., 1922. [19] W.S. Burnside and A. W. Panton, The Theory of Equations, vol. 1. Longmans, 5th ed., 1904. [20] J.E. Levy, “A Weight Distribution Bound for Linear Codes,” IEEE Tran. on Inform. Theory, vol. IT-14, pp. 487—490, May 1968. [21] V.M. Sidel’nikov, “Weight Spectrum of Binary Bose-Chaudhuri-Hocquenghem Codes,” Problemy Peredachi Informatsii, vol. 7, pp. 14—22, January-March 1971. [22] T. Kasami, T. Fujiwara and S. Lin, “An Approximation to the Weight Distribution of Binary Linear Codes,” IEEE Trans. on Inform. Theory, vol. IT-31, pp. 769—780, November 1985. Bibliography 51 [23] W.W. Peterson, “On the Weight Structure and Symmetry of BCH Codes,” J. Ins. Elec. Commun. Engrs. (Japan), vol. 50, pp. 1183—1190, 1967. [24] J.K. Wolf, A.M. Michelson and A.H. Levesque, “On the Probability of Undetected Error for Linear Block Codes,” IEEE Trans. Commun., vol. COM-30, pp. 3 17—324, February 1982. Appendix A The weight distributions of the BCH codes listed in Table 2.1 are given in this Appendix. For A , only the weight for 0 2 i 2-’ — 1 are given. A.1 The Weight Distribution of the BCH Codes for n = 31 i 0 11 12 15 A, 1 186 310 527 Table A. 18 The weight clisthbution of the (31,11) BCH code. A.2 The Weight Distribution of the BCH Codes for n = 63 i B, i B i B, 0 1 26 1455552 40 286272 14 450 28 2041416 42 115632 16 189 30 3525732 44 22680 18 8694 32 2874627 46 3402 20 49896 34 3110940 48 63 22 220752 36 1587768 50 126 24 477120 38 995904 Table A.19 The weight distribution of the dual (63,39) BCH code. i B, i 1 B i B 0 1 26 11711448 40 2413656 14 450 28 15966432 42 897336 16 11025 30 28175868 44 151200 18 89838 32 23400531 46 35154 20 332640 34 24861060 48 3675 22 1713096 36 12418336 50 126 24 4022760 38 8013096 Table A.20 The weight disthbution of the dual (63,36) BCH code. 52 Appendix A. 53 i A, i 1 A i 0 1 19 352800 26 62378064 13 1764 20 776160 27 28457632 14 6300 21 4820112 28 36588384 15 7707 22 9202032 29 132625080 16 23121 23 5486040 30 150308424 17 177660 24 9143400 31 53382483 18 454020 25 42679728 Table A.21 The weight distribution of the (63,30) BCH code. i A i A, i 1 A 0 1 22 142128 28 499968 15 651 23 109368 29 2071440 16 1953 24 182280 30 2347632 17 3024 25 668304 31 914067 18 7728 26 976752 21 74448 27 388864 Table A.22 The weight distribution of the (63,24) BCH code. i A i A i A 0 1 24 3150 28 7056 21 1452 25 9828 29 32760 22 2772 26 14364 30 37128 23 1890 27 5488 31 15183 Table A.23 The weight distribution of the (63,18) BCH code. i 0 23 24 27 28 31 1 A 1 1890 3150 5488 7056 15183 Table A.24 The weight distribution of the (63,16) BCH code. Appendix A. 54 i 0 27 28 31 1 A 1 196 252 63 Table A.25 The weight distribution of the (63,10) BCH code. A.3 The Weight Distribution of the BCH Codes for n 127 i B, i B, i 1 B 0 1 56 31729680 72 24678640 44 245364 60 62023752 76 6518148 48 1591310 64 76311887 80 954786 52 9526524 68 54726840 84 128524 Table A.26 The weight disthbution of the dual (127,99) BCH code. i B i B, i 1 B 0 1 52 1204193172 76 823921644 32 8001 56 4059076464 80 132560568 36 11684 60 7959170772 84 12220956 40 1408176 64 9742397203 88 640080 44 23330916 68 7022797740 92 4572 48 220934280 72 3157059472 96 2667 Table A.27 The weight disthbution of the dual (127,92) BCH code i A i 1 A i A 0 1 51 6518148 60 62023752 43 128524 52 9526524 63 76311887 44 245364 55 24678640 47 954786 56 31729680 48 1591310 59 54726840 Table A.28 The weight distribution of the (127,29) BCH code. Appendix A. 55 j 0 47 48 55 56 63 1 A 1 16002 26670 384048 493776 1176655 Table A.29 The weight distribution of the (127,22) BCH code. A 1 3556 4572 8255 Table A.30 The weight distribution of the (127,15) BCH code. A..4 The Weight Distribution of the BCH Codes for n 255 i B, i B, i B, 0 1 116 305877600 140 253441440 96 377910 120 555624464 144 100683520 100 2227680 124 774718560 148 31065120 104 11860560 128 859276815 152 8115120 108 42570720 132 727765920 156 1428000 112 129450240 136 490256880 160 226746 Table A.3 1 The weight distribution of the dual (255,223) BCH code i A i 1 A i A 0 1 111 16345840 120 60153344 95 134946 112 21016080 127 117483855 96 224910 119 53076480 Table A.32 The weight distribution of the (255,29) BCH code i 0 111 112 119 120 127 A 1 73780 94860 175200 198560 506175 Table A.33 The weight distribution of the (255,21) BCH code Appendix A. 56 A 0 119 120 127 1 1800 2040 255 Table A.34 The weight distribution of the (255,13) BCH code A.5 The Weight Distribution of the BCH Codes for n 511 j A: j A, j 1 A 0 1 228 12190416 244 161050848 219 2137520 235 51132704 251 243121536 220 2837072 236 59799264 252 250839680 223 1216180 239 26244960 255 75448639 224 1563660 240 29744288 227 9786672 243 146628384 Table A.35 The weight distribution of the (511,31) BCH code i 0 223 224 239 240 255 A. 1 1216180 1563660 26244960 29744288 75448639 Table A.36 The weight distribution of the (511,28) BCH code • i 0 239 240 255 A 1 61320 69496 131327 Table A.37 The weight distribution of the (511,19) BCH code A.6 The Weight Distribution of the BCH Codes for n • A, = 1023 0 479 480 495 496 511 1 2577960 2921688 5596864 5957952 16499967 Table A.38 The weight distribution of the (1023,26) BCH code Appendix A. 57 i 0 495 496 511 A, 1 15376 16368 1023 Table A.39 The weight distribution of the (1023,16) BCH code Appendix B B.1 Proof of (3.11) We begin with (3.10). Let (i VA(S) — = 1)(2)l1_2 (B.1) l=2t and VB(E) (n 1) 6 ) 1 (_ 1 _2t 1 (B.2) = l=2t then (3.10) becomes v(e) = (—2) iBvA(e) + 2nvB(E) (B.3) iBjv5(e) + 2nv(e) (B.4) mm and the d-th derivative for d > = 0 is (—2) nun First we find the d-th derivative for = VA(6) ( ) 2 2iQ v(e). _1) Rewrite (i + vA(6) as 1)(2)ll_2 (B.5) l=2t+L then the first derivative of (B.5), denotes z-1 (i v(e) v(E), 1) with respect to e is (—2)’(l — ’, 2t 2t)e (B.6) l—2t+1 which is also equal to v) = (_2)2t+1 (:‘) + (i 12t+2 58 1)(_2)1(l — . 12t1 2t) (B.7) Appendix B. 59 The derivative of (B.7) with respect to e is (i v(e) — 1) = (_2)’(l — 2t)(l — 2t — l) 1 6 _2t_2 (B.8) 1=2t+2 which is also equal to (_2)2t+22(+) = i—i 1) (_2)l(l > + (B.9) — 2t)(l — 2t — 1)e)_2t_2 1=2t+3 The derivative of (B.9) with respect to e is (i v) — 1) (—2)’(l — 2t)(l — 2t — 1)(l — 2t — 2 2 6 ) t_3. (B.lO) 1=2t+3 We repeat this procedure for d times. Thus, in general, the d-th derivative of v(e) (i (1— 2t = VA(E) is (B.1l) — j=O l=2t+d We use the same method to find the d-th derivative for (n = 1) (_i)i fl(l_ 2t vB(e). — Thus, we obtain j)el_2t_d (B.12) j=O l=2i+d As a result, @) (e) of (B.4) with respect to e is (4 (E) —2) iBj> 1) ( 2)’e 2d (1 — mm (n — l=2+d — j) (B.13) — +2n 2t 1)(l)ll_2_d(l t 2 .)
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On the undetected error probability of BCH codes
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
On the undetected error probability of BCH codes Chong, William 1992
pdf
Page Metadata
Item Metadata
Title | On the undetected error probability of BCH codes |
Creator |
Chong, William |
Date Issued | 1992 |
Description | The undetected error probability, Pu(ε), for a variety of Bose-Chaudhuri-Hocquenghem (BCH) codes, used solely for error detection on a binary symmetric channel (BSC) with cross-over probability, is studied. The undetected error probability can be evaluated if the weight distribution of the code or its dual is available. Unfortunately, no general expression for the weight distribution of BCH codes which correct more than 3 errors is known. A few BCH codes for which it is computationally feasible to determine the weight clisiribution are studied. A proper code is one for which Pu(ε) increases monotonically with for 0 ≤ε≤0.5 Algorithms for determining the properness of linear block codes based on Fourier’s and Sturm’s Theorems for finding the number of real roots of a polynomial in a given interval are investigated. They are useful in cases where the weight distribution is known. Kasami et al have studied linear programming methods for obtaining upper and lower bounds on the weight distributions of 4- and 5-error-correcting BCH codes. Here, two methods which can be used to improve these bounds are presented. The first method uses the minimum distance of a dual BCH code. The second method requires, in addition, the number of codewords at the minimum distance. Comparisons between the improved bounds and the Kasami bounds are given for several BCH codes. |
Extent | 1079156 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2008-12-23 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065187 |
URI | http://hdl.handle.net/2429/3314 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1992-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1992_spring_chong_william.pdf [ 1.03MB ]
- Metadata
- JSON: 831-1.0065187.json
- JSON-LD: 831-1.0065187-ld.json
- RDF/XML (Pretty): 831-1.0065187-rdf.xml
- RDF/JSON: 831-1.0065187-rdf.json
- Turtle: 831-1.0065187-turtle.txt
- N-Triples: 831-1.0065187-rdf-ntriples.txt
- Original Record: 831-1.0065187-source.json
- Full Text
- 831-1.0065187-fulltext.txt
- Citation
- 831-1.0065187.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065187/manifest