ON THE UNDETECTED ERROR PROBABILITY OF LINEAR CODES Chong Tean Ong B. E . (Hons.) University of Western Australia A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F A P P L I E D S C I E N C E in T H E F A C U L T Y O F G R A D U A T E S T U D I E S D E P A R T M E N T O F E L E C T R I C A L E N G I N E E R I N G We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y O F BRITISH C O L U M B I A March 1990 © Chong Tean Ong, 1990 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 £le-cm \ c-A-u g ^ / ^ g ^ e ^ ^ -The University of British Columbia Vancouver, Canada Date <2~7 Ai°k\L. l°l°ic> DE-6 (2/88) Abstract The probability of undetected error Pu{t) for the primitive triple-error-correcting BCH codes of blocklength 2 m — 1, used solely for error detection on a binary symmetric channel with cross-over probability e < 1/2, is examined. It is shown that for odd values of m, Pu{e) increases monotonically with €. For even values of m, this is not necessarily true. However, for a fixed c, as m increases, Pu{t) approaches 2~p where p is the number of parity bits. The extended double and triple-error-correcting primitive BCH codes are also examined. The undetected error probability of these codes is shown to have similar characteristics as the non-extended cases. An improved upper bound on the probability of undetected error which is valid for any linear code is derived. Comparison of this improved upper bound with the Kasami upper bound for some classes of codes is shown. ii Table of Contents Abstract i i List of Tables v List of Figures vi Acknowledgement v ii 1 Introduction 1 1.1 Detennining The Undetected Error Rate 3 1.2 Definition of Proper and Improper Codes 3 1.3 Summary of Known Results 5 1.4 Overview of Thesis 6 2 Primitive Triple-Error-Correcting B C H Codes 7 2.1 The (15,5) BCH Code 7 2.2 Cases Where m is Even and > 6 7 2.3 Case Where m is Odd and > 5 11 2.3.1 Method Used in the Proof of Proposition 4 16 S Extended Double and Triple-Error-Correcting Primitive B C H Codes 18 3.1 Deterniining the Weight Distribution of the Dual Code 18 3.2 Extended Double-Error-Correcting Primitive BCH Codes 20 3.2.1 Case Where m is odd 22 3.2.2 Case Where m is even 25 3.3 Extended Triple-Error-Correcting Primitive BCH Codes 26 iii 3.3.1 Case Where m is odd 27 3.3.2 Cases Where m is even 28 4 An Improved Upper Bound on Undetected Error Probability 30 4.1 The Kasami Upper Bound 30 4.2 An Improved Upper Bound 31 5 Conclusions 48 5.1 Summary 48 5.2 Suggestions for Future Work 49 References 50 A 53 B 54 C 56 D 58 iv List of Tables 2.1 Weight Distribution of the Dual of a Triple-Error-Correcting Primitive Binary BCH Code of Length 2m - 1, m even 9 2.2 Comparison of Pu(emax) and 2~p 9 2.3 Value of 6 for Various m 10 2.4 Comparison of c m o x and emax 10 2.5 Weight Distribution of the Dual of a Triple-Error-Correcting Primitive Binary BCH Code of Length 2m - 1, m odd 13 3.1 Weight Distribution of the Dual of the Double-Error-Correcting Primitive BCH Code of Length 2m - 1, m odd 21 3.2 Weight Distribution of the Dual of the Extended Double-Error-Correcting Prim-itive BCH Code of Length 2m, m odd 21 3.3 Weight Distribution of the Dual of the Double-Error-Correcting Primitive BCH Code of Length 2m - 1, ro even 24 3.4 Weight Distribution of the Dual of the Extended Double-Error-Correcting Prim-itive BCH Code of Length 2m, m even 24 3.5 Weight Distribution of the Dual of the Extended Triple-Error-Correcting Primi-tive Binary BCH Code of Length 2m, m odd 27 3.6 Comparison of Pu(emax) and 2~p for Cext 29 3.7 Comparison of e m a * and e m o a , for Cext 29 v List of Figures 1.1 Binary Symmetric Channel with Bit Error Rate e 2 1.2 Undetected Error Probability of a Proper Code 4 1.3 Undetected Error Probability of an Improper Code 4 2.1 Undetected Error Rate for m = 4, 6, 8, 10 and 12 12 2.2 Undetected Error Rate for m = 5, 7, 9, 11 and 13 17 4.1 Geometrical Interpretation of E(\, P) 32 4.2 Upper Bounds of Hamming Code, m = 4 34 4.3 Upper Bounds of Hamming Code, m = 5 35 4.4 Upper Bounds of Hamming Code, m = 6 36 4.5 Upper Bounds of Hamming Code, m = 7 37 4.6 Upper Bounds of Double-Error-Correcting Primitive B C H code, m = 4 38 4.7 Upper Bounds of Double-Error-Correcting Primitive B C H code, m = 5 39 4.8 Upper Bounds of Double-Error-Correcting Primitive B C H code, m = 6 40 4.9 Upper Bounds of Double-Error-Correcting Primitive B C H code, TO = 7 41 4.10 Upper Bounds of Double-Error-Correcting Primitive B C H code, m = 8 42 4.11 Upper Bounds of Triple-Error-Correcting Primitive B C H code, m = 5 43 4.12 Upper Bounds of Triple-Error-Correcting Primitive B C H code, m = 6 44 4.13 Upper Bounds of Triple-Error-Correcting Primitive B C H code, m = 7 45 4.14 Upper Bounds of Triple-Error-Correcting Primitive B C H code, m = 8 46 4.15 Upper Bounds of Triple-Error-Correcting Primitive B C H code, m = 9 47 vi Acknowledgement I would like to express my sincere thanks and appreciation to my supervisor Dr. Cyril Leung for his support and guidance during this project. His suggestions and comments have been most helpful to the completion of this work. It is a privilege to be working with him and I have learned under his supervision. I am also indebted to the many friends that I have made during my studies here. They have made my stay at UBC an enjoyable one. My family has been a constant source of love and support. My wife, Bee Chin, has been a cheerful companion and has always been encouraging. Financial support from UBC in the form of UGF and teaching assistantship is also greatly appreciated. vii Chapter 1 Introduction To achieve reliable communication over a noisy channel, parity check bits are added to the information bits to form a codeword which is then transmitted over the channel. There are two basic methods for controlling transmission errors: the forward-error correction (FEC) method and the automatic repeat request (ARQ) method. In an FEC system, an error-correcting code is used to detect, locate and subsequently correct the errors. In an ARQ system, error detection combined with requests for retransmission of erroneous blocks are used to achieve high system reliability. A wide variety of ARQ and FEC schemes have been studied [13], [17] and [18]. Apart from being easier to implement, the ARQ protocol is also more reliable. This is because the error correcting capability of a practical code is usually quite limited and the probability of a decoding error in an FEC system is normally significantly higher than in an ARQ system. As a result, ARQ is often preferred over FEC for error control in data communication systems, such as packet-switching data networks, computer communication networks, and satellite communications [4]. An example of a practical system that uses the ARQ scheme is ARPANET [17]. The FEC schemes are used mainly in situations where no return channel is available to request retransmissions and in real-time applications such as speech transmission. In such situations, the added cost and decoder complexity is justifiable. It should be mentioned that there are systems which combine features of FEC and ARQ. Such systems are referred to as hybrid ARQ [20], [19]. Frequently occurring error patterns are corrected to reduce the frequency of retransmission and retransmission is requested when less frequent error patterns occur. As a result, a good hybrid ARQ scheme would provide higher reliability than a pure FEC scheme and a higher throughput than a simple ARQ scheme. 1 Chapter 1. Introduction 2 1 - e Figure 1.1: B i n a r y Symmetr ic Channe l w i th B i t E r ro r Ra te e Examp les of various types of hyb r i d A R Q schemes can be found in [13], [22], [21]. A n impor tan t measure of the performance of a code used i n an A R Q scheme is the probabi l i ty of undetected error. It is commonly assumed that for a block code used over a b inary symmetr ic channe l ( B S C ) w i th bit error rate, e, (see F igure 1.1) the undetected error probabi l i ty , P u ( e ) , is upper bounded by ^u(e) < 2~p, 0 < e < 1/2 (1.1) where p is the number of par i ty bits i n each codeword. Th is assumpt ion, however, is not va l id for a l l codes [1], T h e search for good codes, i.e. those that satisfy (1.1), is an on-going topic of research. So far only a hand fu l of papers [1]-[12] deal ing w i th undetected error probabi l i ty have been publ ished. In this thesis, some new results concerning the undetected error probabi l i ty of l inear codes are presented. Chapter 1. Introduction 3 1.1 Determining The Undetected Error Rate Let C be an (n,k) linear code. Let Ai be the number of codewords of weight i in C. The numbers {Ao, A\,... ,^ 4n} are referred to as the weight enumerators or weight distribution of the code, C. If C is used solely for error detection over a BSC, an undetected error occurs only when the error pattern is identical to a nonzero codeword of C. Therefore, given |-<4»}._ , the undetected error probability can be written as »=i Alternatively, by using the Mac Williams identity [15], the undetected error probability can also be expressed in terms of the weight distribution of the dual code, <.Bq,B\,..., Bn j : t=0 Depending on the code being studied, either (1.2) or (1.3) may be more convenient to use in the analysis of the undetected error probability. 1.2 Definition of Proper and Improper Codes A (n, k) linear block code, used solely for error detection over a BSC, is said to be proper if Pu(e) is monotonically increasing in e, 0 < e < 1/2. Codes which are not proper are referred to as improper codes [2]. Figures 1.2 and 1.3 illustrate the definition of proper and improper codes. We note that all proper codes satisfy (1.1) since the undetected error probability of such codes is maximum at e = 1/2 and its maximum value is n (1.2) n (1.3) 2 * - l < 2"p. (1.4) Hence, proper codes are desirable codes for error detection. Chapter 1. Introduction Chapter 1. Introduction 5 1.3 Summary of Known Results A summary of various known results concerning the undetected error probability of block codes is listed below. • Linear block codes are not necessarily proper. [1] • Binary perfect codes are proper. [2] • Dual and extensions of binary perfect codes are proper. [2] • Shortened Hamming codes are not necessarily proper. [2] • The extension of a proper code containing odd-weight codewords is not necessarily proper. [2] • The dual of a proper code is not necessarily proper. [2] • The undetected error probability of any code that has no parity digit which is identically zero has a positive slope at e = 1/2. [3] • Square single parity-check product (SPCP) codes of size (m-m) are proper for 2 < m < 4. For m > 4, these codes are improper. [5] • Extended triple-error-correcting primitive BCH codes of length 2m with m odd and m > 5 satisfy the 2'? bound. [4] • Maximum Distance Separable codes are proper. [7] • CCIR recommendation 476-2 nonlinear error detecting code is improper. [9] • The undetected error probability of various CRC codes have been studied in [10], [8], [11] and [12]. Chapter 1. Introduction 6 1.4 Overview of Thesis The methods used to determine if a code is proper will be examined in chapter 2. Results from the analysis of the primitive triple-error-correcting BCH codes with blocklengths 2m — 1 will then be presented. It will be shown that contrary to the conjectures given in [4] and [13], primitive triple-error-correcting BCH codes do not necessarily satisfy (1.1). In particular, it will be shown that whether the code is proper or not is dependent on the parameter m. For odd values of m > 5, the code is proper and for even m > 6, the code is improper. It will also be shown that for even m > 6, the code is asymptotically proper, i.e. (1.1) is nearly satisfied for large values of m. Chapter 3 examines the undetected error probability of extended primitive BCH codes. These codes are obtained by adding an overall parity bit to the primitive BCH codes. It will be shown that the extended primitive double and triple-error-correcting BCH codes exhibit similar undetected error probability characteristics to their non-extended counterparts. It is often useful to upper bound the undetected error probability. In chapter 4, an improved version of the upper bound for linear codes, given in [4], is derived. The original and improved bounds are plotted for various codes and compared. It is found that the value of the improved bound is about half that of the original bound for values of e near 1/2. The final chapter gives a summary of results and contributions of this work. Suggestions for future work are also given in this chapter. Chapter 2 Primitive Triple-Error-Correcting BCH Codes In this chapter, the undetected error probability of primitive triple-error-correcting BCH codes is exarnined. It is shown that these codes are proper for odd values of m > 5. For even values of m, these codes are not necessarily proper. 2.1 The (15,5) BCH Code Proposition 1: The (15,5) BCH code is proper. Proof: Since this is a triple-error-correcting code, the minimum distance must be 7. Moreover, the all zeros and the all ones vectors are codewords. The weight distribution of the code is therefore given by A0 = 1, A7 = 15, A» = 15 and An = 1. From (1.2), we can write Pu(e) = 15€7(1 - c)s + 15e8(l - e)7 + £15. (2.1) Differentiating (2.1) gives = 105 [e(l - c)]6(l - 2c) + 15e14. (2.2) For 0 < € < 1/2, > 0 and hence the (15,5) BCH code is proper. Q.E.D. 2.2 Cases Where m is Even and > 6 The weight distribution of the dual code of the primitive triple-error-correcting BCH code of length 2 m - 1 for m = 6, 8, 10, ... is given in [13], [24] and reproduced in Table 2.1. These Bi Chapter 2. Primitive Triple-Error-Correcting BCH Codes 8 values were used in (1.3) to compute P«(c) for m = 6,8,..., 30. The values of c, em„x> (accurate to seven decimal places) which maximize P«(e) were determined. The results for m = 6, 8, 10, 12 and 14, are shown in Table 2.2, which also lists the values of 2 _ p = 2~3m. From Table 2.2, it can be seen that for m = 6, 8 and 10, the codes do not satisfy the 2~p bound and hence are not proper. For m > 12, the difference between the maximum Pti(e) and 2~p is not discernible to 20 significant figures. It was found numerically, using the Infinite Precision package of Maple [23], that the 2~p bound is not satisfied for even values of m up to 30. However the difference, 6, between the maximum value of P«(c) and 2~p decreases exponentially with m. Table 2.3 lists the values of S for values of m up to 30. For m = 30, approximately 25,000 decimal places were used in order to show the small difference between the maximum value of Pu(e) and 2~p. A reasonably accurate empirical value for em a x is given by e™* = 1.726 x 2~m / 2. (2.3) Table 2.4 lists the values of em o x and em o x for m = 6,8,..., 30. Proposition 2: For 0 < e < 1/2, Pu(e) < 2 _ p j l + o(m)j where o(m) denotes a positive quan-tity which goes to 0 as m increases. Proof: From Table 2.1, it can be seen that the minimum distance of the dual code is d* = 2 m _ 1 - 2(-m+2^2. Since there is a total of 2P — 1 = 2 3 m — 1 non-zero codewords in the dual code, we can use (1.3) to obtain the following upperbound, Pu(e) = 2"p - 2 3 m 1 + £i?.-(l - 2C)» -(1-e)* i=l J l + (l - 2 € ) ' r ( 2 3 m-l)] ^ 2^[l + (l-2er~ 2.2-] = ^ [ i + { 8 ( i - 2 , r - ^ } m ] . (2.4) (2.5) (2.6) (2.7) Chapter 2. Primitive Triple-Error-Correcting BCH Codes 9 Even ro > 6 Weight, i Number of vectors with weight i, Bi 0 1 2 m - i _ 2(m+2)/2 ( 2m-i + 2(m + 2)/ 2)(2m - 4)(2m - l)/960 2 m - 1 _ 2m/2 7 ( 2 m - 1 + 2m/2 )2m ( 2 m - 1)/48 2 m - l _ 2(m-2)/2 2 ( 2 m _ 1 + 2(m-2)/2^3 2m + g^2m _ y15 2m" 1 (29.2 2 m -4.2 m + 64)(2m-l)/64 2 m - i + 2(m-2)/2 2(2 m _ 1 - 2(m-2)/2)(3.2m + 8)(2m - 1)/15 2 m - i + 2m/2 7(2 m _ 1 - 2 m / 2 )2 m (2 m - l)/48 2 m - i + 2 ( m + 2 ) / 2 ( 2 m _ 1 - 2(m + 2>/2)(2m - 4)(2m - l)/960 Table 2.1: Weight Distribution of the Dual of a Triple-Error-Correcting Primitive Binary BCH Code of Length 2 m — 1, ro even. ro •Pu(^ mox) 2-P 6 .38387957094447481442 X 10"5 .38146972656250000000 x IO"5 8 .59604652319622973182 X 10~7 .59604644775390625000 X 10"7 10 .93132257461547851907 X 10"9 .93132257461547851562 x 10"9 12 .14551915228366851807 X I O - 1 0 .14551915228366851807 x IO" 1 0 14 .22737367544323205948 x IO" 1 2 .22737367544323205948 x IO" 1 2 Table 2.2: Comparison of P u (e m o x ) and 2 _ p . Chapter 2. Primitive Triple-Error-Correcting BCH Codes 10 m m 6 6 .2409844382 x 10~7 20 .2702835677 x IO"771 8 .7544232348 X IO"14 22 .3479690645 x IO" 1 5 3 9 10 .3347748801 X IO - 2 6 24 .1152280255 x IO" 3 0 7 4 12 .1750417004 x IO"50 26 .4056821807 x IO" 6 1 4 6 14 .5271866721 x 10"" 28 .1758246702 x IO" 1 2 2 9 2 16 .5271866721 x IO - 1 9 5 30 .4555271512 x IO" 2 4 6 5 9 18 .3353968609 x IO"387 Table 2.3: Value of 8 for Various ro ro Cmax Cmax ro ^max Cmax 6 0.1930891 0.2157500 20 0.0016827 0.0016855 8 0.0994196 0.1078750 22 0.0008421 0.0008428 10 0.0514498 0.0539375 24 0.0004212 0.0004214 12 0.0262962 0.0269687 26 0.0002107 0.0002107 14 0.0133096 0.0134844 28 0.0001054 0.0001054 16 0.0066976 0.0067422 30 0.0000527 0.0000527 18 0.0033599 0.0033711 Table 2.4: Comparison of Cmax and Cm, Chapter 2. Primitive Triple-Error-Correcting BCH Codes 11 For any 0 < e < 1/2, the term |8(1 - 2e)2m J / T O j clearly goes to 0 as m increases. Q.E.D. Proposition 8: For 0 < e < 1/2, -P„(e) > 2~ p[l - o(m)] where o(m) is a positive quantity which goes to 0 as m increases. Proof: Using (1.3) but ignoring all terms involving Bi, i ^ 0, we have P*{t) > 2"3 m - (1 - c)2™-1 (2.8) = ^ [ i - a ^ U - ^ r - 1 ] (2-9) = ^[i-K-r-1^}"1]. (2.io) For any 0 < e < 1/2, the term J8(l — e)( 2 r a _ 1)/ m j clearly goes to 0 as m increases. Q.E.D. It should be noted that Proposition 3 applies to any primitive triple-error-correcting BCH code, i.e. for m odd or even. From Propositions 2 and 3, it follows that primitive triple-error-correcting BCH codes for even m > 6 is asymptotically proper. The undetected error rate curves for m = 4, 6, 8, 10 and 12 are plotted in Figure 2.1. The m a Y i m n m at emax cannot be easily identified due to the scale used. 2.3 Case Where m is Odd and > 5 Proposition 4: Primitive triple-error-correcting BCH codes of blocklengths 2m — 1 are proper, for odd values of m > 5. Proof: The weight distribution of the dual code for odd values of m > 5 is given in [13], [24] and Chapter 2. Primitive Triple-Error-Correcting BCH Codes 12 co n o 1E-03 1E-04 1E-05 1E-06 1E-07 I I I | I I I I I I I I I | I I I I M I I I | I I I I I I I I I | I I I I I I I I I | I I I I I I I I I | I I I | I I | m = 6 m = 8 t 1E-08 k •o <D O B QJ T3 C 3 1E-09 1E-10 1E-11 1E-12 1E-13 m= 10 m = 12 ' ' ' ' ' 1 1 1 ' I t i l l i I I I I I I I I I i I I I > I I I I I I I I i l u l l I I I I I i t I I I I h i I I I I I I I I I I I I I I I I 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Bit Error Rate Figure 2.1: Undetected Error Rate for m = 4, 6, 8, 10 and 12 Chapter 2. Primitive Triple-Error-Correcting BCH Codes 13 Odd m > 5 Weight, i Number of vectors with weight i, Bi 0 1 2 m - l _ 2(m+l)/2 2 (m -5 ) /2( 2 (m -3 ) /2 + l)(2"»-1 - l)(2m - l)/3 2 m - l _ 2("»-l)/2 2 (m -3 ) /2( 2 (m-l ) /2 + l)(5.2m-l + 4)(2m - l)/3 2 m - i (9.22m-4 + 3.2m"3 + l)(2m - 1) 2 m - l + 2 (m-l ) /2 2 (m -3 ) /2( 2 (m-l ) /2 _ l)(5.2m~1 + 4)(2m - l)/3 2 m - l + 2(m+l)/2 2 (m -5 ) /2( 2 (m -3 ) /2 _ l)(2 m _ 1 - l)(2m - l)/3 Table 2.5: Weight Distribution of the Dual of a Triple-Error-Correcting Primitive Binary BCH Code of Length 2m - 1, m odd. reproduced in Table 2.5. With this weight distribution, using (1.3) and the fact that p = 3m, we can write 1 + 2("- 5)/ 2(2(™- 3>/ 2 + l)(2m- 1 - l)(2m - 1) ( 1 _ 2 ^ 2 —i_ 2 ( m + , ) / 3 Pv(e) = 1 2 3 m 2 (m -3 ) /2 ( 2 (m-l ) /2 + 1 ) ( 5 . 2 " * - I + 4)(2m - 1) ^ ^ m - l . ^ m - ! +(9.22m~4 + 3.2m"3 + l)(2m - 1)(1 - 2e)2ra_1 | 2(m-3)/2(2(m-1)/2 - 1X5.2"-1 + 4)(2" - 1) _ 2£j2—i+2(«-i)/a 3 2(m-5)/2^ 2(m-3)/2 _ 1)( 2"»-1 _ 1 ) ( 2 m _ ) /2 + (1 - 2c) j m - 1 ^ 2 ( ' » + l ) / 2 - ( l -e ) 2 "- 1 . (2-11) Defining / = 2^m 1 ^ 2 , and grouping some common terms, we obtain x + , ( , 2 - l ) (2 , 2 - l ) | ( I + _ 2 e f - » + m _ 2 e ) , + 2 , j + /(5/ 2-M)(2/ 2-l) { ( / + _ 2 e f _ , + ( / _ _ 2 c ) J J + l } 6 + ( ^ + ^ + lX2f 2 - l)( l-2€)' 2 (1 - e) 2/2-l (2.12) Chapter 2. Primitive Triple-Error-Correcting BCH Codes 14 Differentiating (2.13) with respect to e, we obtain de ~ { U M(8/«) (i+ 1)(/ 2-!)(/-2) ( i _ uf_n_x (j -1)(/2 -!)(/ + 2) ( I _ ^JP+M-! j 5 / 2 + 4 ) ( / 2 - l ) { ( 1 _ 2 e ) l 2 _ , _ 1 + ( 1 _ 2 £ f + I - a } + ( l - € ) 2 ' 2 - 2 } . - ( £ + ^ + 2 ) ( l - 2 e ) p - 1 (2.13) We will show that the expression in (2.13) is non-negative. Let /i(e) = ^ 1 ^ dt^' ^ ^Tie* calculation shows that (1 -&)/[(«) = _(2Z2 - 2)^(6)+ 2(/ 2-1)6(1-6) 2 / 2 - 3 (Z 2 - 1) 12/3 ( ^ - ^ { ( i - ^ - ^ - a - ^2 ' - 1 } +(5Z2 + 4) {(1 - 2 e f - (1 - 2€)'2+'-1} (2.14) Since /i(0) = 0, it follows from Lemma A.l (see Appendix A) that f\(e) > 0 provided that 2(Z2 - 1)C(1 - 6) 2"- 3 - ^2#f(y " 2) {(1 - 26)'2"2'-1 - (1 - 26)<2+2'-1} +(5/2 + 4) {(1 - 26)'2-'"1 - (1 - 26),2+'-1} > 0. (2.15) Inequality (2.15) can be simplified to Me) £ 24/36(l - 6)2'2"3 - ( L __ 2) [(1 - 26)'2-2'"1 - (1 - 26)^2'-1] _ ( 5 / 2 + 4) [ ( l - 26)'2-'"1 - (1 - 2 6 f > (2.16) Chapter 2. Primitive Triple-Error-Correcting BCH Codes 15 We can now repeat the above procedure using /2(c) in place of /i(e), and write (l-2e)fi(e) = -2(/2-2Z-l)/2(€)-4K/2-4)(l-2e)'2+2'-1 +2/(5/2 + 4) [(1 - 2€)'2-'-1 - 3(1 - 2e)'2+'-1] +24/3(l - e)2*2-4 [2(/2 + 21- l)e2 - 2(2/ + l)c + l] . Since /*2(0) = 0, from Lemma A.l it is sufficient to show that /3(c) = -2(f2 - 4)(1 - 2e)'2+2'"1 + (5/2 + 4) [(1 - 26)'2-'-1 - 3(1 - 2ef+l~1} +12/2(1 - c) 2' 2" 4 [2(/2 + 21- l)e2 - 2(2/ + l)e + l] > 0. (2.17) (2.18) Repeating this procedure three more times, we find that to establish that *s non-negative, it is sufficient to show that the fourth degree polynomial /,(e) = (4/8 - 36/6 + 80/4 - 36/2 + 4)e4 +(76/4 - 260/2 + 104)c3 - (34Z4 - 110/2 - 84)e2 -(4/4 - 20/2 + 136)€ + (/4 - 5/2 + 34) (2.19) is non-negative. The details of deriving (2.19) as a sufficient condition can be found in Appendix B. We prove that /j(c) is non-negative by using mathematical induction. For / = 4, //(c) > 0 since the polynomial has no real roots [26] and is positive for c = 0. Assuming /i(e) > 0, we now proceed to show that / 2j( €) ^ 0. We can write /21(e) as Me) = (1024/8 - 2304Z6 + 1280/4 - 144/2 + 4)e4 + (1216/4 - 1040Z2 + 104)e3 -(544/4 - 440/2 - 84)e2 - (64/4 - 80/2 + 136)c + 16/4 - 20/2 + 34. (2.20) Chapter 2. Primitive Triple-Error-Correcting BCH Codes 16 This can be expressed as the sum of /j(e) and l2gi(e) where gi(e) = (1020Z6 - 2268/* + 1200/2 - 108)e4 + (1140Z2 - 780)e3 -(510/2 - 330)e2 - (60/2 - 60)e + 15/2 - 15. (2.21) It is proved in Lemma C l (see Appendix C) that this last expression is non-negative. Hence /i(e) is positive, for / = 4,8,16,... . It follows, therefore, that is non-negative. This completes the proof that primitive triple-error-correcting BCH codes of blocklength 2 m — 1 are proper for odd values of m. The undetected error rate curves for m = 5, 7, 9, 11 and 13 are shown in figure 2.2. 2.3.1 Method Used in the Proof of Proposition 4 A necessary and sufficient condition for Proposition 4 to be true is that (2.13) be non-negative in the interval [0,1/2]. Equation (2.13), however, is a cumbersome equation with a large number of power terms. To prove directly that such an equation is non-negative is difficult. The technique used in the proof of Proposition 4 is a recursive method based on Lemma A.l. The idea behind this method is to derive a sufficient condition, in the form of a simpler equation, for > 0. de This is achieved by eliminating a power term each time a recursion is performed. Chapter 2. Primitive Triple-Error-Correcting BCH Codes 17 F igure 2.2: Undetected Er ro r Rate for m-5,7, 9, 11 and 13 Chapter S Extended Double and Triple-Error-Correcting Primitive BCH Codes In this chapter, we consider the extended codes obtained by the addition of an overall parity check bit to the double and triple-error-correcting primitive BCH codes. These extended codes have blocklength 2 m . 3.1 Determining the Weight Distribution of the Dual Code The following result will be used in determining the undetected error probability of the ex-tended codes. Proposition 5: Let {.Bi} be the weight distribution of the dual of a ( n , k) BCH code, L ) i=0 C. The weight distribution of the dual of the extended (n + l , A;) BCH code, Cext is |£. \ext J where Bi<ext = Bi + Bn+Lt i = 0 , l , . . . , n + 1. (3.1) Proof: We shall give the proof for the more general case where C is any ( n , k) linear code. Let the 18 Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 19 systematic generator matrix and parity-check matrix of C be G = Poo P01 • • • P0,n-fc-l | 1 0 0 . . 0 PlO Pll ••• Pl,n-fc-l 1 0 1 0 . . 0 P20 P21 ••• P2,n-fc-l 1 0 0 1 . . 0 and H = 1,0 Pfc-l,l ••• Pfc-l,n--fc-1 1 0 0 0 . . . 1 0 0 . . . 0 Poo PlO ••• Pfc-1,0 0 1 0 . . . 0 P01 Pll • •• Pfc-i.i 0 0 1 . . . 0 P02 1 Pl2 • • • Pfc-1,2 0 0 0 . . . 1 1 1 P0 ,n-fc-l Pi ,n-fc-1 • • • Pfc-l,n (3.2) (3.3) respectively. The generator matrix of the extended code, Gext, is a k X ( n + 1) matrix of the following form : Poo Poi • • P0 ,n-fc-l | 1 0 0 . . 0 PO.x PlO Pll • • Pl,n-fc-l 1 0 1 0 . . 0 Pl.x P20 P21 P2 ,n-fc-l 1 o 0 1 . . 0 P2,x (3.4) Gext — • . Pfc-1,0 Pfc-l,l • •• Pfc-l,n-fc-l 1 0 0 0 . . 1 Pfc-l,x . where {p»,*}._ 0 £ {0>1} such that each row of G e xt has even weight. Using the fact that the inner product of every row of G e x t with each row of H e x t must be zero and G • H r = 0, H e x t Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 20 must be a (n — k + 1) x (n + 1) matrix as shown. 1 0 0 . . 0 Poo PlO •• Pfc-1,0 0 0 1 0 . . 0 Poi Pll Pfc-1,1 0 0 0 1 . . 0 P02 Pl2 • • Pfc-1,2 0 . 0 • 0 0 0 0 . .. 1 PO,n-fc-l Pi ,n-fc-1 • Pfc-l,n-fc-l 0 1 1 1 . .. 1 1 1 .. 1 1 (3.5) The presence of the all l's vector as a row of Hext means that the weight distribution of the dual of the extended code is symmetric. Q.E.D. 8.2 Extended Double-Error-Correcting Primitive B C H Codes Proposition 6: Extended Double-Error-Correcting Primitive BCH codes are proper. Proof: The proof will be completed in two parts, for odd and even values of m. Section 3.2.1 gives the proof for odd values of ro and Section 3.2.2 examines the case for ro even. Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 21 Odd m > 3 Weight, i Number of vectors with weight i, Bi 0 1 2 m - i _ 2 ( m - i ) / 2 (2 m _ 2 + 2(m - 3)/2)(2m - 1) 2 m - l ( 2 m - l + j ^ m _ ^ 2 m - l _j_ 2 ( m - l ) / 2 ^ 2 m - 2 _ 2 (m-3)/2^ 2 ?n _ Table 3.1: Weight Distribution of the Dual of the Double-Error-Correcting Primitive BCH Code of Length 2m - 1, m odd. Odd m > 3 Weight, i Number of vectors with weight i, Bi 0 1 2 m - l _ 2 ( m - l ) / 2 (2m - l)(2m _ 1) 2 m - l (2m + 2)(2m - 1) 2 m - l + 2 ( m - l ) / 2 (2 m - l ) (2 m _ 1 ) 2m 1 Table 3.2: Weight Distribution of the Dual of the Extended Double-Error-Correcting Primitive BCH Code of Length 2m, m odd. Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 22 3.2.1 Case Where m is odd The weight distribution of the dual of the double-error-correcting primitive BCH code for odd values of m > 3 is listed in Table 3.1 [13]. Using Proposition 5, the weight distribution of the dual of the extended code can be easily obtained and is given in Table 3.2. Using this weight distribution and (1.3), the probability of undetected error can be written as W = 2lmTT 1 + (2m + 2)(2m - 1)(1 - 2e)2 +(2m - l)(2m~1){(l - 2e)2n~1-2(m~1),i + (1 - 2c) 2m - l + 2 ( m - l ) / 2 ' +(1 - 2c)2 (3.6) Making the substitution I = 2^m~1^2 gives ™ = sF 1 + (2Z2 - 1) j / 2 ( l - 2e)'2"' + (2Z2 + 2)(1 - 2e)1 +/2(1 - 2e)'2+'} + (1 - 2e) - ( 1 - 6 ) (3.7) Taking the derivative, we obtain dPu(e) = 21' d £ - (1 - e)2p-* - Jy ]^2l2 - 1){(Z2 - 0(1 - 26)12-'"1 + (2Z2 + 2)(1 - 2ef "> +(Z2 + /)(1 - 26)'2+'"1 J + 2(1 - 26)2'2"1 . (3.8) We will now show that the expression in (3.8) is non-negative. Let fi{e) = ^Mll, A brief calculation shows that (1 - 2e)/J(e) = -2(2Z2 - l ) / x ( 6 ) + @LJlf2(e) (3.9) Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 23 where Me) = 4Z2(1 - e)2'2"2 - (2/2 + 2)(1 - 2c)'2"1 - ( / 2 - l ) [(l-2e)'2-'-1 + (l-26)' 2 +'- 1]. (3.10) Since /i(0) > 0, it follows from Lemma A.l that /i(c) > 0 over [0,1/2] if /2(e) > 0 over the same interval. Moreover, (1 - 2e)/2-(c) = -2(/2 - l)/2(e) + 8/2(Z2 - l)e(l - c ) ^ " 3 -2Z(/2 - 1) [(1 - 2c)'2-'"1 - (1 - 26)'2+z-1] . (3.11) Since 2/(Z2 — 1) > 0 and /2(0) > 0, to prove that /2(c) and hence /x(e) are non-negative, it is sufficient to show that 4/e(l - e)2p-3 > (1 - 2c)'2-'-1 - (1 - 2ef + z- 1. (3.12) With a little algebraic manipulation, it can be shown that (3.12) is identical to (D.l) in Appendix D. Q.E.D. Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 24 Even m > 4 Weight, i Number of vectors with weight i, Bi 0 1 2 m - l _ 2m/2 2 (m-4)/2( 2 (m-2)/2 + j ^ m _ ^ 3 2 m - l _ 2(m-2)/2 2 m/2( 2 m/2 + - 1)/3 2 m - l ( 2 m-2 + _ y 2 m - l + 2(m-2)/2 2 m/2^m/2 _ j j ^ m _ ^ 3 2 m - l + 2m/2 2(m-4)/2J 2(m-2)/2 _ j ^ ^ m _ l)/3 Table 3.3: Weight Distribution of the Dual of the Double-Error-Correcting Primitive BCH Code of Length 2m — 1, m even. Even m > 4 Weight, i Number of vectors with weight i, Bi 0 1 2 m - 1 _ 2m/2 2 m - 2 ( 2 m - l)/3 2 m - l _ 2(m-2)/2 2 m + 1 (2 m - l ) /3 2 m - l ( 2 m - l + 2 ) ( 2 m _ ^ 2 m - l + 2(m-2)/2 2 m + 1 (2 m - l ) /3 2 m - l + 2m/2 2 m - 2 (2 m - l)/3 2m 1 Table 3.4: Weight Distribution of the Dual of the Extended Double-Error-Correcting Primitive BCH Code of Length 2m, m even. Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 25 3.2.2 Case Where m is even The weight distribution of the dual of the double-error-correcting BCH code of length 2m — 1, for even values of TO > 4 is given in [13] and listed in Table 3.3. The weight distribution of the dual of the extended code can be easily obtained using Proposition 5 and is given in Table 3.4. Using this weight distribution and (1.3), the probability of undetected error for the extended double-error-correcting BCH code can be written as 1 Pu(e) = 22m+l 1 + ( 2 m - l ) { +(2m"1 + 2)(1 - 2e)2 + 2 m+l (1 " 2c) 2 m - l + 2 ( m - 2 ) / 2 >m-2 + -T-(l ~ 2 e ) 2 m - l ^ . 2 m / 2 } + (l - 2 c ) 2 - (1 - c)2 (3.13) By making the substitution I = 2^m 2)/ 2, we obtain 32/" 1 + (4/2 - l)\t(l - 2 c ) 2 ' 2 " 2 ' + § £ ( 1 - 2 c ) 2 ' 2 " ' +(2Z2 + 2)(1 - 2c) 2 ' 2 + ^(1 - 2 c ) 2 l 2 + ' + ^ (l-2c) 2' 2+ 2'} + (l - 2 c ) 4 ' 2 Taking the derivative of Pu(c) with respect to c yields - (1 - c) 4P (3.14) dPu(e) de (4p - i){£fi!(i - 2 £)2 p - 2 ' - ' + 4 ( 2 ' ; - ' ' ( i - ur +2(/2 + 1)(1 - 2c)2'2"1 + 4 ( 2 * 2 - + < ) ( l - 2c)2'2+'"1 + ( i ! ± i)(l _ 2 c ) 2 ' 2 + 2 ' - 1 } + 2(l - 2 c ) 4 ' 2 - 1 . (3.15) We will now show that (3.15) is non-negative. Letting /i(c) = it can be shown that (1 - 2c)/i(c) = -2(4/2 - l)/x(c) + (4/2 - l)/2(c), (3.16) Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 26 where /2(€) = 4Z2(1 - e)412"2 - \ ^3^{(1 - 2c)2 1 2-2'-1 + (1 - 2e)2'2+2'"1} +2(Z2 + 1)(1 - 26)2'2"1 + ^ " ^ { ( l ~ 26)2'2+'"1 + (1 - 26)2'2-'-1} (3.17) Since /i(0) > 0, /i(e) > 0 over [0,1/2] provided that /2(c) > 0 over the same interval A brief calculation shows that the following relationship holds between /2(e) and /^{f), (l-2e)ft(e) = -2 (2Z 2-l)/ 2( €) + 8/ 2(2/ 2-l)e(l-2€) 4J2-3 2_ '3/ ( i 4 _ / 2 ) | ( 1 _ 2 t ) 2 ' 2 - 2 ' - i _ (1 _ 2e)2'2+2'-1} +(4Z4 - I2) {(1 - 2e)2f2-'-1 - (1 - 2e)2'2+'-1} Moreover, since /2(0) > 0, a sufficient condition for > 0 is that de 4(2Z2 - l)e(l - e) 4J2-3 * 37 (Z2 - 1) {(1 - 26)2*2-2'-1 - (1 - 2e)2'2+21-1} +(4Z2 - 1) {(1 - 2c)212-'-1 - (1 - 2€)2'2+'-1} Inequality (3.19) is the same as (D.3) which is proved in Appendix D. (3.18) (3.19) Q.E.D. 3.3 Extended Triple-Error-Correcting Primitive BCH Codes The analysis of the undetected error probability of these codes will also be done in two parts. Section 3.3.1 deals with the case of odd values of m and Section 3.3.2 examines the even m case. It will be shown that for odd m, these codes are proper. For even values of m > 6, the codes are not proper. Chapter 3. Extended Double and Triple-Error- Correcting Primitive BCH Codes 27 Odd m > 5 Weight, i Number of vectors of weight i, Bi 0 1 2 m - i _ 2 ( m + 1 ) / 2 2 m _ 3 (2 m - l)(2 m _ 1 - l)/3 2 m - l _ 2 ("»- i)/2 2m- 1(5.2m _ 1 + 4)(2m - l)/3 2 m - i 2(9.22m"4 + 3.2m"3 + l)(2m - 1) 2 m - l + 2 (m-l)/2 2 m - 1 (5.2 m _ 1 + 4)(2m - l)/3 2 m - l + 2(m+l)/2 2 m _ 3 (2 m - l)(2 m _ 1 - l)/3 2m 1 Table 3.5: Weight Distribution of the Dual of the Extended Triple-Error-Correcting Primitive Binary BCH Code of Length 2m, m odd. 3.3.1 Case Where m is odd Kasami et al [4] have shown that these codes satisfy the 2~p bound. Here we shall prove that these codes are proper. Proposition 7: Extended primitive triple-error-correcting BCH codes of blocklengths 2m are proper, for odd values of m > 5. Proof: Using Proposition 5 and Table 2.5, the weight distribution of the dual of the extended code for odd values of m > 5 can be obtained and is given in Table 3.5. Using Table 3.5, equation (1.3) and making the substitution / = 2(m - 1)/ 2 we can write 1 P«< £> = 16/* +(|I4 + \l2 + 2)(1 - 2ef + Q«l±i)(l - * f « + ^!_^(l_2 £)' 2+ 2'} + (l-26) 2' 2 ( 1 - e r . (3.20) Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 28 By using the same method as in Section 3.2.1 and 3.2.2, a sufficient condition for Proposition 7 to be true is - 2)(1 - 2ef-2'-' + (5!2 + 4)(1 - lef-1-' -(5/2 + 4)(1 - 2ef-l~1 - ( £ - 2)(1 - 2e)' 2 + 2'- 1 > 0. (3.21) This inequality is the same as (2.16). Q.E.D. 3.3.2 Cases Where m is even Proposition 8: The extended (16,5) BCH code is proper. Proof: This follows immediately from the weight distribution Aq = 1, Ag = 30 and A\§ = 1. Q.E.D. It has been conjectured [4] that the distance-8 extended primitive BCH code for even values of m > 6 also satisfies the 2~p bound. Using (1.3), (2.1) and Proposition 5, the probability of undetected error for these codes for m = 6,8,10, ...,30 was evaluated . It was found that the 2~p bound is not satisfied in all cases. However, as for the non-extended codes, the difference between the maximum value of Pu(() and 2~p decreases exponentially with m. The values of Pu(€max) and 2~p for m = 6,8,10,12 and 14 are listed in Table 3.6. For m > 12, the difference between the maximum Pu(e) and 2~p is not discernible up to 20 significant figures. A reasonably accurate empirical value for emax is again given by (2.3). The values of emax and Cmox for m = 6,8,..., 30 are listed in Table 3.7. Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 29 m Pu(£max) 2 - P 6 .19189455522645475728 xlO"5 .19073486328125000000 xlO"5 8 .29802325760494439858 xlO - 7 .29802322387695312500 X l O - 7 10 .46566128730773925924 XlO" 9 .46566128730773925781 xlO" 9 12 .72759576141834259033 xlO" 1 0 .72759576141834259033 xlO - 1 0 14 .11368683772161602974 xlO" 1 2 .11368683772161602974 xlO" 1 2 Table 3.6: Comparison of Pu(emax) and 2~p for Cext. m (•max (•max m Cmax Cmax 6 0.1991162 0.2157500 20 0.0016837 0.0016855 8 0.1018183 0.1078750 22 0.0008423 0.0008428 10 0.0522102 0.0539375 24 0.0004213 0.0004214 12 0.0265112 0.0269687 26 0.0002107 0.0002107 14 0.0133668 0.0134844 28 0.0001054 0.0001054 16 0.0067124 0.0067422 30 0.0000527 0.0000527 18 0.0033636 0.0033711 Table 3.7: Comparison of c m 0x and lmax for Cext. Chapter 4 An Improved Upper Bound on Undetected Error Probability In this chapter, we derive an improved upper bound on the probability of undetected error which is valid for any linear code of length n and m i n i m u m distance > 2t + 1 where t is a positive integer. This upper bound is an improvement over the bound proposed by Kasami et al[4\. 4.1 The Kasami Upper Bound By considering (1.2) as a linear programming problem and using the duality theorem [25], Kasami et al [4] showed that the undetected error probability of a /-error correcting linear block code of length n is upperbounded by Pu(e) < /fJ x £ ("W-€)-'. (4.1) ( 2 + A «=2t+l t J The binomial coefficients in (4.1) can be bounded as fc-i i=2t+l W i=2l+1 \ 7 i=kXl (4.3) Define the entropy function H(x) as ff(x) = — xlogx - (1 - x)log(l - x) (4.4) and the function E(x, e) as E(x, e) = H{e) + (x - e)H'(e) - H{x) > 0 for 0 < e < x. (4.5) 30 Chapter 4. An Improved Upper Bound on Undetected Error Probability 31 The ChernofF inequality [14] states that J2 ( n ) ~ -P) n _ i < 2-n£^'p) provided A > P. (4.6) Using this inequality, (4.3) and (4.5), Kasami et al derived the final form of the upper bound as J°u(6) < { l 'n - k + t" k t _2-nE((2t+l)/n,t)^ , n ^ 2t+l 1 for 0 < c < — — < -n I • + 1 2-«*((fc/«).«) f o r H £ ± I < £ < * < I . n n ~ 2 (4.7) From Figure 4.1, we know that E((k/n),e) increases with k. Hence 2~nE^h^'^ decreases with increasing values of k. The term l/(n~*+t)> however, is a decreasing function in k. Hence the optimum value of A;, which gives the tightest upper bound in (4.7), must be selected over the interval ne < k < n/2. There is no obvious way of selecting this optimum k value. 4.2 An Improved Upper Bound Proposition 9: The probability of undetected error for any linear code is bounded by 1 2 - » « ( ( 2 t + l ) / n , « ) ) f o r 0 < € < 2 l ± i < I. t fn - \ne] + ^ i t n r 2t + 1 \ne] ^ 1 for < c < L < - . n n 2 (4.8) Figure 4.1: Geometr ica l Interpretat ion of E(\, P). Chapter 4. An Improved Upper Bound on Undetected Error Probability 33 Proof: The new upper bound is obtained by observing that ^-«r* * E^a-o-' (4.9) = [(l-c) + c] n (4.10) = 1. (4.11) Substituting (4.11) into (4.1) for (2t + l)/n < e < k/n < 1/2, we obtain In - k + t\ The value of which gives the tightest bound is the smallest value which satisfies 2*+ 1 A: 1 l t < e < - < -. (4.13) n n 2 v ' Using this fact, we can express (4.12) as P M * , i - 1 1 . A - ^ < ' < ^ i \ - <««> / n - [ne I + M n 2 Q.E.D. At c = 1/2, the value of the improved upper bound is half that of the bound proposed by Kasami et aL The plots of these upper bounds together with the actual probability of undetected error for Hamming codes, double-error-correcting primitive BCH codes and triple-error-correcting BCH codes are shown in Figures 4.2-4.5, 4.6-4.10 and 4.11-4.15 respectively. Chapter 4. An Improved Upper Bound on Undetected Error Probability 34 Figure 4.2: Upper Bounds of Hamming Code, m = 4. Chapter 4. An Improved Upper Bound on Undetected Error Probability 35 1E-05 < 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ) i 1111111111 [ 111 i 11 i 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 Bit Error Rate Figure 4.3: Upper Bounds of Hamming Code, m = 5. Chapter 4. An Improved Upper Bound on Undetected Error Probability 36 1E-01 r r 1E-02 O £ 1 E " 0 3 "D CD o B CD T3 i i i i i i i I | M I I I I I i I I I i I I i [ i i i i i i i i i j I I I I I I M I j I i i i i i I I I j I i I I M i I I | I i I I I I I I I | i i i i i i I I I | I I I I I I I 1E-04 Actual Prob. of Undetected Error Kasami Upper Bound New Upper Bound •) E-05 ' 1 11111 111111111111111111111111111111111111111111111 1111111111111111111111 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Bit Error Rate Figure 4.4: Upper Bounds of Hamming Code, m = 6. Chapter 4. An Improved Upper Bound on Undetected Error Probability 37 1E-01 1E-02 O I 1E-03 & O c5 T 3 C 3 1E-04 ' I > I I ' I ' I | I ' ' ' I | I I I I I I I M | I I I I I I I I I | I I I I I I I I I | I I 1 1 I I I I I [ I I I I M I I I | I I I I I I I I I | I I I I I I I I I J I I | | I | I | | Actual Prob. of Undetected Error Kasami Upper Bound New Upper Bound 1E-05 11 M 11111111111111111 M 111111111111 111111111111 11111 M 11111111111! 1111111L1111111111 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Bit Error Rate Figure 4.5: Upper Bounds of Hamming Code, m = 7. Chapter 4. An Improved Upper Bound on Undetected Error ProbabiUty 38 Figure 4.6: Upper Bounds of Double-Error-Correcting Primitive BCH code, m = 4. Chapter 4. An Improved Upper Bound on Undetected Error Probability 39 1E-10 1 1 1 1 1 1 1 1 1 1 ' 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ' ' ' ' ' ' 1 1 ' ' 0.05 0.1 0.15 0.2 0.25 0.3 Bit Error Rate 0.35 0.4 0.45 Figure 4.7: Upper Bounds of Double-Error-Correcting Primitive BCH code, m = 5. Chapter 4. An Improved Upper Bound on Undetected Error Probability 40 1E-01 pr 1E-02 1E-03 1E-04 ns _o o £ 1E-05 U J S 1E-06 z\ I I I I I M | I I I I I I I I I j M I I M I I I j I I I I I I I I I j I I I II I M I | I I M I I I I I | I I I I I I I I I | I I I I I I I I I | I I I I I I I I I | I I I I I I I I I CD T3 C 1E-07 1E-08 1E-09 1E-10 Actual Prob. of Undetected Error Kasami Upper Bound New Upper Bound 1111111111) 111111 11 ' ' • ' i i ' ' ' ' • ' i l l ' I ' i i ' 0.05 0.1 0.15 0.2 0.25 0.3 Bit Error Rate 0.35 0.4 0.45 0.5 F igure 4.8: Uppe r Bounds of Double-Er ror -Correc t ing Pr im i t i ve B C H code, m = 6. Chapter 4. An Improved Upper Bound on Undetected Error Probability 41 1E-01 1E-02 1E-03 j 1111111111111 I I iII111II1111111111111111MII1111111111111111 H 1111111111 M 11 M 11111111111111111II 1E-08 1E-09 1E-10 1 I i 1 I I I I I I I 1 1 Actual Prob. of Undetected Error Kasami Upper Bound New Upper Bound I ' ' ' ' ' ' ' • ' l 111111111 11111111111111111111111111111111 1111111111111111 I, 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 Bit Error Rate 0.5 Figure 4.9: Upper Bounds of Double-Er ror -Correc t ing Pr im i t i ve B C H code, m = 7. Chapter 4. An Improved Upper Bound on Undetected Error ProbabiHty 42 1E-01 F 1E-02 1E-03 1E-04 J2 CO O £ 1E-05 LU T 3 2 1E-06 o CD «—* CD T3 C 1E-07 1E-08 1E-09 1E-10 M I I I I I I | I I II I I I I I | I I I I | I I I I I I I I I | I I I I I I I I I | I I I I I I I I I | I I I | | | | | | | n | | || I I I | I I I I | I I II I I Actual Prob. of Undetected Error Kasami Upper Bound - New Upper Bound i l i i i i i i i I i i i i I i i i i i i i i i I i i i i i i i i i I i i i i i ; i i i I i i i I I i i i i i i i i i I i i i i i i i i i I i 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 Bit Error Rate 0.5 F igure 4.10: Upper Bounds of Doub le-Er ror -Cor rec t ing Pr im i t i ve B C H code, ro = 8. Chapter 4. An Improved Upper Bound on Undetected Error Probability 43 F igure 4.11: Upper Bounds of Tr ip le-Er ror -Correc t ing P r im i t i ve B C H code, m = 5. Chapter 4. An Improved Upper Bound on Undetected Error ProbabiHty 44 1E-11 I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I ! | | I I I • I . I M I I I I I I I I I I I 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 Bit Error Rate Figure 4.12: Uppe r Bounds of Tr ip le -Er ror -Cor rec t ing P r im i t i ve B C H code, m = 6. Chapter 4. An Improved Upper Bound on Undetected Error Probability 45 F igu re 4.13: Upper Bounds of Tr ip le -Er ror -Cor rec t ing P r im i t i ve B C H code, m = 7. Chapter 4. An Improved Upper Bound on Undetected Error Probability 46 1E-05 J l I i i i I i T~p i I i ri M I | i i i I I i11 i V| i i i i n i i i p"T M M M rfi i i ii ii i i j i ii i i ii i i [ i i i i rr i i r) i I T T I I I ri j i 1E-06 A 11 /1 b- ' I JQ CO . Q O 1E-07 fc 1E-08 T3 & O t » CD X3 C 1E-09 Actual Prob. of Undetected Error Kasami Upper Bound New Upper Bound 1E-10 1E-11 ' I ' ' ' ' ' ' ' ' ' I I I I I i r I I I I 1 I I I I l l 0.05 0.1 0.15 0.2 0.25 0.3 Bit Error Rate 0.35 0.4 0.45 0.5 F igu re 4.14: Uppe r Bounds of Tr ip le-Error -Correct ing P r im i t i ve B C H code, m = 8. Chapter 4. An Improved Upper Bound on Undetected Error Probabihty 47 I I I I I I I I | I I II I I I I I | I I I I I I M I | I I I I I I I I I | I I I I I II I I | i I I I I I I I I | I I I I I I I I I | | I I I I I I I I I I 1E-06 1E-07 CO X 3 O LU "O gj o oj o> x> c 3 1E-08 1E-09 Actual Prob. of Undetected Error Kasami Upper Bound New Upper Bound 1E-10 1E-11 i i ' i ' i ' i ' ' i ' ' ' ' ' ' i' i ' ' i ' ' ' i ' i ' ' ' 1 1 ' ' ' 111111 0.05 0.1 0.15 0.2 0.25 0.3 Bit Error Rate 0.35 0.4 0.45 0.5 Figure 4.15: Upper Bounds of Triple-Error-Correcting Primitive BCH code, m = 9. Chapter 5 Conclusions 5.1 Summary This thesis has examined the undetected error probability of some classes of linear codes. It was proved that • the (15,5) BCH code is proper. • triple-error-correcting primitive BCH codes, of blocklength 2m — 1, with m odd and > 5 are proper. For even m > 6, counter-examples were given to show that these codes are not necessarily proper. • triple-error-correcting primitive BCH codes are asymptotically proper. • extended double and triple-error-correcting primitive BCH codes have similar character-istics to their non-extended counterparts. A method for deriving a sufficient condition for a code to be proper was developed and used in the above proofs. This is based on using Lemma A.l successively. An improved upper bound valid for any linear code was obtained. This bound is an im-provement over the bound derived by Kasami et al These upper bounds for the Hamming codes and double and triple-error-correcting primitive BCH codes were plotted. For bit error rates near 1/2, the improved upper bound is approximately half of the Kasami upper bound. 48 Chapter 5. Conclusions 49 5.2 Suggestions for Future Work Below is a list of topics related to the area of undetected error probability which deserve further examination. 1. Determine if shortened BCH codes are proper. 2. Determine if extending a proper code with odd minimum distance and no parity bits that are identically zero always result in another proper code. If this is true, it will be a more general result than those in chapter 3. 3. Improve on the upper bound (4.8) for the undetected error probability of any linear code. 4. Find an upper bound for commonly used codes such as the BCH codes. This bound should be significantly better than the bound for all linear codes. References [1] C. Leung and M.E. Hellman, "Concerning a Bound on Undetected Error Probability," IEEE Trans. Inform. Theory, vol. IT-22, pp. 235-237, Mar. 1976. [2] C. Leung, E.R. Barnes and D.U. Friedman, "On Some Properties of the Undetected Error Probability of Linear Codes," IEEE Trans. Inform. Theory, vol. IT-22, pp. 235-237, Mar. 1979. [3] 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. 317-324, Feb. 1982. [4] T. Kasami, T. Klove and S. Lin, "Linear Block Codes for Error Detection," IEEE Trans. Inform. Theory, vol IT-29, pp. 131-136, Jan. 1983. [5] C. Leung, "Evaluation of the Undetected Error Probability of Single Parity-Check Products Codes," IEEE Trans. Commun., vol. COM-31, pp. 250-253, Feb. 1983. [6] K.A. Witzke, "Examination of the Undetected Error Probability of Linear Block Codes," MASc Thesis, University of British Columbia, Aug. 1984. [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, Sept. 1984. [8] T. Fujiwara, T. Kasami, A. Kitai and S. Lin, "On the Undetected Error Probability for Shortened Hamming Codes," IEEE Trans. Commun., voL COM-33, pp. 570-574, June 1985. [9] R.C. Sornmer, "A Note Upon Another Error Detecting Code That is Not Proper," IEEE Trans. Commun., voL COM-33, pp. 719-721, July 1985. 50 .References 51 [10] K.A. Witzke and C. Leung, "A Comparison of Some Error Detecting CRC Code Stan-dards," IEEE Trans. Commun., vol. COM-33, pp. 996-998, Sept. 1985. [11] T. Fujiwara, T. Kasami and S. Lin, "Error Detecting Capabilities of the Shortened Ham-ming Codes Adopted for Error Detection in IEEE Standard 802.3," IEEE Trans. Commun., voL 37, No. 9, pp. 986-989, Sept. 89. [12] G. Castagnoli, J. Ganz and P. Graber, "Optimum Cyclic Redundancy-Check Codes with 16-Bit Redundancy," IEEE Trans. Commun., vol. 38, No. 1, pp. 111-114, Jan. 1990. [13] S. Lin and D.J. Costello, Error Control Coding: Fundamentals and Applications, Prentice-Hall, 1983. [14] W.W. Peterson and E.J. Weldon Jr., Error-Correcting Codes, Second Edition. MIT Press, 1972. [15] F.J. Mac Williams, "A Theorem on the Distribution of Weights in a Systematic Code," Bell Syst. Tech. J., vol. 42, pp. 79-94, Jan. 1963. [16] C. Leung, E.R. Barnes and D.U. Friedman, "On Some Properties of the Undetected Error Probability of Linear Codes," IBM Research Report, RC 7194(#30940), June 1978. [17] D. Bertsekas and R. Gallager, Data Networks, Prentice-Hall, 1983. [18] A.S. Tanenbaum, Computer Networks, Prentice-Hall, 1981. [19] H.O. Burton and D.D. Sullivan, "Errors and Error Control," Proc. IEEE, 60(11), pp. 1293-1301, Nov. 1972. [20] K. Brayer, "Error Control Techniques Using Binary Symbol Burst Codes," IEEE Trans. Commun., vol COM-16, pp. 199-214, Apr. 1968. [21] D. Chase, "Code Combining - A Maximum-Likelihood Decoding Approach for Combining an Arbitrary Number of Noisy Packets," IEEE Trans. Commun., vol. COM-33, pp. 385-393, May 1985. References 52 [22] J. Hagenauer, "Rate-Compatible Punctured Convolutional Codes (RCPC Codes) and their Applications," IEEE Trans. Commun., vol. 36, No. 4, pp. 389-400, Apr. 1988. [23] B.W. Char, K.O. Geddes, G.H. Gonnet, M.B. Monagan and S.M. Watt, Maple Reference Manual, 5th Edition, Watcom, 1988. [24] T. Kasami, "Weight Distribution of Bose-Chaudhuri-Hocquenghem Codes," Proc. Conf. Combinatorial Mathematics and Its Applications, University of North Carolina Press, Chapel Hill, N.C., 1968. [25] J. Massey, "Coding Techniques for Digital Data Networks," Proc. Int. Conf. Inform. The-ory Syst., NTG-Fachberichte, vol.65, Berlin, Germany, Sept. 18-20,1978. [26] S.M. Selby, Standard Mathematical Tables, 21'* edition, p. 106, CRC press 1973. Appendix A Lemma A.l:(see [16]). Let /(e) be a continuously differentiable function denned on [0,1/2] and satisfying /(0) > 0. If > -a(e)/(e), 0 < e < 1/2 (A.l) for some non-negative function a(e), then /(e) > 0, 0 < e < 1/2 (A.2) Proof: If /(e) < 0 at some point 0 < e < 1/2 we can find a zero, a, of / such that /(e) < 0, a < e < e (A.3) But this condition implies that /(e) = f f\s)ds>- I*a(s)f(s)ds>0, a<e<e (A.4) J a J a This contradicts the original condition that /(e) < 0 so Lemma A l holds. Q.E.D. It is helpful to explain intuitively why Lemma A . l is true. A closer examination of (A.l) reveals that once the function /(e) is non-positive, its gradient, /'(e), must be non-negative since a(e) is non-negative. Under these conditions and the fact that /(0) > 0, /(e) must be increasing once it reaches 0; therefore, /(e) can never be negative. 53 Appendix B In this appendix we show that a sufficient condition for (2.18) to be non-negative is that (2.19) is non-negative. Using /3(e) as denned in (2.18) we can show that (1 - 2e)&(e) = -2(/2 + 21- l)/3(e) + 6//4(e) (B.l) where f4(e) £ (5p + 4)[(l-26)' 2-'- 1-(l-2 e)' 2 +'- 1] +4/(1 - e)2'2-5€[2(/4 - 6/2 + l)e2 + 2(5/2 + 4)e - (5/2 + 4)]. (B.2) Repeating this procedure, we can write (1 - 2e)/4(C) = -2(/2 - / - l)/4(e) + 4Z/5(e) (B.3) where Me) £ (5/2 + 4)(1 - 26)'2+'"1 + (1 - €)2'2"6 [-[hi2 + 4) +(10/3 + 20/2 + 8/ + 16)e - (4/4 + 30/3 + 44/2 + 24/ - 6)e2 +(-4/5 + 8/4 + 44/3 + 48/2 + 12/ - 44)c3 +(4/6 + 4/5 - 28/4 - 24/3 + 28/2 + 4/ - 4)e4]. (B.4) Repeating this procedure again, we obtain (1 - 2e)f'h{e) = -2(/2 + / - l)/5(e) + (1 - e)2l2~7efx{e) (B.5) 54 Appendix B. 55 where A fi(e) = (41s - 36Z6 + 80Z4 - 36Z2 + 4)e4 +(76Z4 - 260Z2 + 104)e3 - (34/4 - 110Z2 - 84)e2 -(4Z4 - 20Z2 + 136)e + (I4 - 5Z2 + 34). (B.6) Since /s(0),/4(0) and /a(0) are all non-negative, by Lemma A.l , a sufficient condition for /3(e) > 0 is that (B.6) be non-negative. \ Appendix C Lemma C.l: For/= 4,8,16,..., 51(e) = (1020/6 - 2268/4 + 1200/2 - 180)e4 + (1140/2 - 780)e3 -(510/2 - 330)c2 - (6G72 - 60)e + 15/2 - 15 > 0 (C.l) Proof: We will use mathematical induction for the proof. At e = 0, 54(e) is positive. Moreover, by using the formula for the roots of a quartic equation [26], it can be shown that 54(e) has no real roots. Hence 54(e) > 0. We now assume that 51(e) > 0 and prove that 521(e) > 0. From (C.l) we can write g2l(e) = (65280/6 - 36288/4 + 4800/2 - 108)e4 + (4560/2 - 780)e3 -(2040Z2 - 330)e2 - (240/2 - 60)e + 60/2 - 15 > 0. (C.2) We can express 521(e) as Me) = gi(e) + 15l2hi(e) (C.3) where hi{e) = (4284/4 - 2268Z2 + 240)e4 + 228e3 - 102e2 - 12e + 3. (C.4) Since 51(e) > 0 by assumption, it is sufficient to show that hi(e) > 0. For this we again use mathematical induction. At e = 0, /14(e) is positive. Moreover, /14(e) has no real roots. Hence 56 Appendix C. 57 hi(e) > 0. We now assume that /ij(c) > 0 and prove that / i 2/( €) ^ From (C.4) we have h2i(e) = (68544/4 - 9072/ 2 + 240)c4 + 228e3 - 102c2 - 12c + 3 (C.5) = hi(€) + n{€) (C.6) where r,(c) = (64260/4 - 6804/ 2)e 4. (C.7) Since hi(e) > 0 by assumption, and rj(e) > 0, it follows that /121(c) > 0. Q.E.D. Appendix D T h e fo l lowing theorems are taken f rom [16] and are reproduced here to a id the reader i n un-derstanding the mater ia l i n this thesis. Theorem D.l: For m odd and > 3, ( l - 2 e ) 2 ' B " 1 - 2 ( m " 1 ) / 2 - 1 - ( l - 2 e ) 2 m " 1 + 2 ( m " 1 ) / 2 - 1 < 2< m + 3 >/ 2 e( l - c ) 2 " " 3 . ( D . l ) Theorem D.2: For m even and > 2, 2 m - l _ 1 2 m — 4 ( 2 m - l ) + — — (1 - 2 e ) - 2 ( r a - 2 ) / 2 - (1 - 2 e ) 2 ( T " - 2 ) / 2 (1 - 2 6 ) - 2 ( m " 2 ) / 2 + (1 - 2 e ) 2 ( m " 2 ) / 2 | < ( 2 m - 2 ) e ( l - e ) (D.2) 2 m-3 In order to prove these theorems, we need to establ ish a few useful inequali t ies first. L e m m a D.l: I f m is any posi t ive even integer, then ( l - 2 e ) 2 m - 1 - 2 ( T O - 2 ) / 2 + ( l - 2 e ) 2 m - 1 + 2 ( m - 2 ) / 2 < 2(1 - e) 2"* (D.3) for 0 < € < 1/2. If m is any posi t ive odd integer then ( l - 2 € ) 3 - 2 m - 1 - 2 ( m - 1 ) / 2 + ( l - 2 e ) 3 ' 2 m " 1 + 2 ( m " 1 ) / 2 < 2(1 - e ) 3 2 " \ (D.4) Proof: F i r s t consider (D.3). Let / (e ) = 2(1 - e ) 2 " - (1 - 2 e ) 2 T O - 1 - 2 ( m - 2 ) / 2 - (1 - 2 e ) 2 m - 1 + 2 ( m " 2 ) / 2 (D.S) 58 Appendix D. 59 We shall show that /(e) > 0. A brief calculation shows that (l-2e)/'(e) = -2m/(e) + 2m + 1e(l - e)2"1"1 (D.6) -2 m / 2 [(1 - 2<i?n-1-*n-')l2 - (l - 2e)2*"~ 1 + 2 ( r a - 2 ) / 2 ] . /(0) = 0, therefore by Lemma Al , in order to show that /(e) > 0, we need only to prove that ( l - 2e ) 2 m - 1 - 2 ( m - J ) / 2 - ( l - 2e ) 2 m - 1 + 2 ( m - 2 ) / 2 < 2 • 2"/2e(l - e)2™"1. (D.7) We shall prove (D.7) by induction on m. For m = 2, the requirement is that l - 2 e - ( l - 2 e ) 3 < 4e(l - e)3. (D.8) This simplifies to the condition e4 < e3 (D.9) which is true for 0 < e < 1/2. Thus we may assume that (D.7), and hence (D.3), is true for some m > 2. If we replace m by m + 2 in (D.7) we obtain the inequality ( l - 2 e ) 2 m + 1 - 2 W 2 - ( l - 2 e ) 2 m + 1 + 2 r a / 2 < 2 • 2<m+2)/2e(l - e)2*"42"1. (D.10) In order to complete the induction step we must prove this inequality. (D.10) can be obtained by multiplying (D.7) by the inequality (l-2e) 3 - 2 m - 1 [(l-2e)- 2 ( m - 2 ) / 2 + (l-2e) 2 ( m- 2 ) / 2] < 2(1 - e)3'2". (D.ll) Thus (D.10) is true provided (D.ll) is true. But (D.ll) can be obtained by multiplying (D.3) by the inequality (1 - 2e)2m < (1 - e) 2 m + 1 (D.12) which holds since (1 - e)2 r o + 1 = (1 - 2e + e2)2™ > (1 - 2e)2m (D.13) This completes the proof of (D.3) for m > 2. Appendix D. 60 Q.E.D. Now consider (D.4). Since m + 1 is even and > 2, we have ( l - 2 e ) 2 m - 2 ( m - 1 ) / 2 + ( l - 2 6 ) 2 m + 2 ( m _ 1 ) / 2 < 2 ( l - e ) 2 m + 1 (D.14) by (D.3). If we multiply this inequality by ( l - 2 e ) 2 m - 1 < (l-c)2™ (D.15) we obtain (D.4), (D.15) is valid for m > 1 and the proof is exactly the same as the proof of (D.13). Q.E.D. We shall now prove (D.l) for m odd and > 3 by induction. For m = 3, the left hand side of (D.l) is given by 8e[l-5e+10e2-10e3 + 4e4] and the right hand side is given by 8e [l - 5e + 10e2 - 10e3 + 5c4 - <r5]. Thus (D.l) holds for m = 3 and 0 < e < 1. Assume that (D.l) holds for some odd m > 3 and 0 < € < 1/2. The inequality obtained by replacing m by m + 2 in (D.l) is ( l - 2 e ) 2 m + 1 - 2 ( m + 1 ) / 2 - 1 - ( l - 2 e ) 2 m + 1 + 2 ( m + 1 ) / 2 - 1 < 2<m+5)/2e(l - e) 2 m + 2" 3. (D.16) This inequality can be obtained by multiplying (D.l) by (D.4). Thus (D.l) implies (D.16) and so the proof that (D.l) is an increasing function of c on [0,1/2] is complete by induction on odd m > 3. Q.E.D. Appendix D. 61 Now consider (D.3). This inequality is trivially true for m = 2. Assume it to be true for m > 2. The inequality obtained by replacing m by m + 2 in (D.3) is . 2 m / 2 ^ 2 ^ ( l - 2 e r + 1 - [ ( l - 2 e ) - ^ - ( l - 2 € ) • | ( 2 m + 2 - l ) + ( 2 m - l ) [ ( l - 2 e ) - 2 m / 2 + (l-2€) 2 m / 2]} < ( 2 m + 2 - 2)e(l - c ) 2 m + (D.17) can be obtained by multiplying (D.3) by the inequality (D.17) 2-3 1(1 - 26)3-2"1-11(1 - 26)- 2 ( m- 2 ) / 2 + (1 - 2c) 2 ( m- 2 ) / 2 (D.18) fry** - l) + (2- - 1) [(1 - 2e)- 2 m / 2 + (1 - 2e)2m/2]} < 2 ^ - 2 M . " {( 2- - 1) + 2^1 [(i - 2e)-*~M + (1 - 2e)2 ( r a- 2 ) / s]} " 2-- 2 Thus (D.3) is true for all even m > 2 provided that (D.18) is true for all even m > 2. If we clear (D.18) effractions we obtain the equivalent inequality (1 - 2e)3-2m"1 [(1 - 2e)- 2 ( m- 2 ) / 2 + (1 - 26)2(m-2)/2] {(2m+2 - 1) +(2m - 1) [(1 - 2€)"2ra/2 + (1 - 2e)2m/2] }(2 m- J - 1) < {( 2 - _ l) + (2 m" 2 - 1)[(1 - 2c)- 2 ( m _ 2 ) / 2 +(1 - 2e)2(m"2)/2]}2(1 - 6 ) 3 2 m ( 2 m + 1 - 1). (D.19) (D.19) is the product of inequality (D.3) and the inequality (1 - 2e) 2 m{(2 m + 2 - 1) + (2 m - 1)[(1 - 2e)- 2 m / 2 + (1 - 26) 2 r a / 2]}(2 m" 1 - 1) < ( 2 m + 1 - l){(2 m - 1) + (2 m" 2 - 1) [(1 - 2e)" 2 ( m~ 2 ) / 2 + ( l - 2 6 ) 2 ( m - 2 ) / 2 ] } ( l - c ) 2 r a + 1 . (D.20) Thus in order to complete the proof of theorem B2, we need only to verify that (D.20) is true for all even integers m > 2. (D.20) is the sum of two inequalities 3(2m - 1)(1 - €) 2™ + 1 + 2(2m~1 - l)(2 m - 1)(1 - 2 €) 2 m + ( 2 m + 1 - 1) (2-2 _ i ) ( 1 _ £)2~*' [ ( 1 _ 2e)-*"->V> + (1 - 26) 2 (- 2 ) / 2] > ( 2 m + 2 - l ) ( 2 m - 1 - l ) ( l - 2 < 0 2 m (D.21) Appendix D. 62 and ( 2 m - i _ 1 ) ( 2 m _ x ) [ 4 ( 1 _ 6 ) 3 « + * _ 2(1 _ 2 e) 2 m] > (2"1"1 - 1) •(2T O - 1) [(1 - 2 e ) 2 m - 2 ™ / 2 + (1 - 2 e ) 2 m + 2 m / 2 ] . (D.22) To see that (D.21) is true, note that the left hand side reduces to the right hand side if (l-c)2""1"1 and (1 - 2 e ) - 2 < m " 2 ) / 2 + (1 - 2 e ) 2 ( m _ 2 ) / 2 are replaced by the smaller quantities (1 - 2 e ) 2 m and 2 respectively. To see that (D.22) is true, square each side of (D.3) and multiply the resulting inequality by ( 2 m _ 1 - l ) ( 2 m - 1). This completes the proof of the theorem. Q.E.D.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On the undetected error probability of linear codes
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
On the undetected error probability of linear codes Ong, Chong Tean 1990
pdf
Page Metadata
Item Metadata
Title | On the undetected error probability of linear codes |
Creator |
Ong, Chong Tean |
Publisher | University of British Columbia |
Date Issued | 1990 |
Description | The probability of undetected error P[formula omitted](є) for the primitive triple-error-correcting BCH codes of blocklength 2[formula omitted] 1, used solely for error detection on a binary symmetric channel with crossover probability є ≤ 1/2, is examined. It is shown that for odd values of m, P[formula omitted(є) increases monotonically with є. For even values of m, this is not necessarily true. However, for a fixed є, as m increases, P[formula omitted](є) approaches 2‾[formula omitted] where p is the number of parity bits. The extended double and triple-error-correcting primitive BCH codes are also examined. The undetected error probability of these codes is shown to have similar characteristics as the non-extended cases. An improved upper bound on the probability of undetected error which is valid for any linear code is derived. Comparison of this improved upper bound with the Kasami upper bound for some classes of codes is shown. |
Subject |
Data transmission systems Error-correcting codes (Information theory) |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-11-02 |
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.0065497 |
URI | http://hdl.handle.net/2429/29722 |
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 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1990_A7 O64.pdf [ 3.04MB ]
- Metadata
- JSON: 831-1.0065497.json
- JSON-LD: 831-1.0065497-ld.json
- RDF/XML (Pretty): 831-1.0065497-rdf.xml
- RDF/JSON: 831-1.0065497-rdf.json
- Turtle: 831-1.0065497-turtle.txt
- N-Triples: 831-1.0065497-rdf-ntriples.txt
- Original Record: 831-1.0065497-source.json
- Full Text
- 831-1.0065497-fulltext.txt
- Citation
- 831-1.0065497.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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0065497/manifest