ON T H E UNDETECTED ERROR PROBABILITY OF LINEAR CODES Chong Tean Ong B. E . (Hons.) University of Western Australia A T H E S I S 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 REQUIREMENTS FOR T H E DEGREE OF M A S T E R OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL ENGINEERING 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 COLUMBIA March 1990 © Chong Tean Ong, 1990 In presenting degree freely this at the thesis in University of available for reference copying of department publication this or of partial fulfilment of British Columbia, I agree and study. thesis for scholarly by this his or her the requirements that the I further agree purposes representatives. may be It thesis for financial gain shall not £le-cm \ c-A-u The University of British Columbia Vancouver, Canada Date DE-6 (2/88) <2~7 Ai°k\L. l°l°ic> g ^ / ^ g ^ e ^ ^ - advanced Library shall make it by the understood be an permission for extensive granted is permission. Department of that for head that allowed without of my copying or my written Abstract The probability of undetected error P {t) for the primitive triple-error-correcting BCH codes u of blocklength 2 — 1, used solely for error detection on a binary symmetric channel with crossm over probability e < 1/2, is examined. It is shown that for odd values of m, P {e) increases u monotonically with €. For even values of m, this is not necessarily true. However, for a fixed c, as m increases, P {t) approaches 2~ where p is the number of parity bits. The extended p u 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 ii List o f Tables v List o f Figures vi Acknowledgement 1 2 S vii 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 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 16 Method Used in the Proof of Proposition 4 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 iii 26 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 2 - 1, m even 9 m 2.2 Comparison of P (e ) 2.3 Value of 6 for Various m 2.4 Comparison of c 2.5 Weight Distribution of the Dual of a Triple-Error-Correcting Primitive Binary u BCH 3.1 and 2~ m o x 9 p max 10 and e x 10 ma Code of Length 2 - 1, m odd 13 m Weight Distribution of the Dual of the Double-Error-Correcting Primitive BCH Code of Length 2 - 1, m odd 21 m 3.2 Weight Distribution of the Dual of the Extended Double-Error-Correcting Primitive BCH 3.3 Code of Length 2 , m odd 21 m Weight Distribution of the Dual of the Double-Error-Correcting Primitive BCH Code of Length 2 - 1, ro even 24 m 3.4 Weight Distribution of the Dual of the Extended Double-Error-Correcting Primitive BCH 3.5 Code of Length 2 , m even 24 m Weight Distribution of the Dual of the Extended Triple-Error-Correcting Primitive Binary BCH Code of Length 2 , m odd m 3.6 Comparison of P (e ) 3.7 Comparison of e u m a max and 2~ for C t * and e p ex m o a , for C 27 29 29 ext 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(\, 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 P) 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 F i g u r e 1.1: B i n a r y S y m m e t r i c C h a n n e l w i t h B i t E r r o r R a t e e E x a m p l e s of various types of h y b r i d A R Q schemes can be f o u n d i n [13], [22], [21]. A n i m p o r t a n t measure of the performance of a code used i n a n A R Q scheme is the p r o b a b i l i t y of u n d e t e c t e d error. It is c o m m o n l y assumed that for a block code used over a b i n a r y s y m m e t r i c c h a n n e l ( B S C ) w i t h bit error rate, e, (see F i g u r e 1.1) the undetected error p r o b a b i l i t y , P ( e ) , u is u p p e r b o u n d e d b y ^u(e) < 2~ , p 0 < e < 1/2 (1.1) where p is the n u m b e r of p a r i t y bits i n each codeword. T h i s a s s u m p t i o n , however, is not v a l i d for a l l codes [1], T h e search for good codes, i.e. those that satisfy (1.1), is a n on-going topic of research. So far o n l y a h a n d f u l of papers [1]-[12] dealing w i t h undetected error p r o b a b i l i t y have b e e n p u b l i s h e d . I n this thesis, some n e w results concerning the undetected error p r o b a b i l i t y of linear codes are presented. 3 Chapter 1. Introduction 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\,... ,^4 } are referred to as the weight enumerators or weight distribution of n 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 n (1.2) »=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\,..., n B n j: (1.3) 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 P (e) is monotonically increasing in e, 0 < e < 1/2. Codes which are not proper are referred u 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 2*-l < 2" . p Hence, proper codes are desirable codes for error detection. (1.4) Chapter 1. Introduction Chapter 1. Introduction 1.3 5 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 2 with m odd and m > 5 m 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]. 6 Chapter 1. Introduction 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 2 — 1 m 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. Thefinalchapter 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 B C H 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) B C H 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 A = 1, A = 15, A» = 15 and An = 1. From (1.2), we can write 0 7 P (e) = 15€ (1 - c) + 15e (l - e) + £ . (2.1) = 105 [e(l - c)] (l - 2c) + 15e . (2.2) 7 s 8 7 15 u Differentiating (2.1) gives 6 For 0 < € < 1/2, 14 > 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 - 1 for m = 6, 8, 10, ... is given in [13], [24] and reproduced in Table 2.1. These Bi m Chapter 2. Primitive Triple-Error-Correcting BCH Codes values were used in (1.3) to compute P«(c) for m = 6,8,..., 30. to seven decimal places) which maximize P«(e) The values of c, e were determined. The 12 and 14, are shown in Table 2.2, which also lists the values of 2 can 8 _p „x> (accurate results for m = 6, 8, 10, = 2~ . From Table 2.2, it 3m be seen that for m = 6, 8 and 10, the codes do not satisfy the 2~ bound and proper. For m p hence are not m > 12, the difference between the maximum Pti(e) and 2~ is not discernible to p 20 significant figures. It was found numerically, using the Infinite Precision package of Maple [23], that the 2~ bound is not satisfied for even values of m up to 30. However the difference, p 6, between the maximum value of P«(c) and 2~ decreases exponentially with m. Table 2.3 p 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 P (e) and 2~ . p u A reasonably accurate empirical value for e e™* Table 2.4 lists the values of e Proposition 2: For mox max is given by = 1.726 x 2~ and e m/2 . (2.3) for m = 6,8,..., 30. mox 0 < e < 1/2, P (e) < 2 j l + o(m)j where o(m) denotes a positive quan_ p u 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 Since there is a total of 2 — 1 = 2 P 3m m _ 1 - 2( ^. m+2 — 1 non-zero codewords in the dual code, we can use (1.3) to obtain the following upperbound, Pu(e) = 2" p -2 3m 1 + £i?.-(l i=l (2.4) 2 )» -(1-e)* C (2.5) J l + (l-2€)' (2 -l)] r 3m ^ 2^[l + (l-2er~ .2-] (2.6) 2 = ^[i {8(i-2,r-^} ]. m + (2.7) 2 9 Chapter 2. Primitive Triple-Error-Correcting BCH Codes Even ro > 6 Number of vectors with weight i, Bi Weight, i 0 m - i _ (m+2)/2 m - 1 _ m/2 2 2 2 ( m-i + 2( ( m-1 2 2 m - l _ (m-2)/2 2 2 " m-i m-i m-i m 2 1 m+2 2 7 2 (2 + 2 2 (m-2)/2 m/2 ( )/ 2 2 + 2 2 + 2 m + 2 2 m + m 2 (m-2)/2^ m 3 2 + g^ m _ 2 y 15 (29.2 -4.2 + 64)(2 -l)/64 - 2( - )/ )(3.2 + 8)(2 - 1)/15 7(2 - 2 ) 2 ( 2 - l)/48 (2 - 2( >/ )(2 - 4)(2 - l)/960 2m + m m 2 m _ 1 1 )/ )(2 - 4)(2 - l)/960 m/2 )2 ( 2 - 1)/48 2(2 m_1 m m 2 m_1 m _ 1 2 m m / 2 m+2 m 2 m m m m m Table 2.1: Weight Distribution of the Dual of a Triple-Error-Correcting Primitive Binary B C H Code of Length 2 — 1, ro even. m 2-P ro •Pu(^mox) 6 .38387957094447481442 X 10" 8 .59604652319622973182 X 10~ 10 .93132257461547851907 X 10" 12 .14551915228366851807 X I O 14 .22737367544323205948 x IO" 5 7 9 - 1 0 12 .38146972656250000000 x IO" 5 .59604644775390625000 X 10" 7 .93132257461547851562 x 10" 9 .14551915228366851807 x I O " .22737367544323205948 x IO" Table 2.2: Comparison of P ( e u ) and 2 . _ p mox 12 10 Chapter 2. Primitive Triple-Error-Correcting BCH Codes m m 6 .2409844382 x 10~ 8 .7544232348 X IO" 10 .3347748801 X I O 12 .1750417004 x IO" 14 .5271866721 x 10"" 7 16 .5271866721 x I O 14 -26 50 -195 18 .3353968609 x IO" 10 6 20 .2702835677 x IO" 22 .3479690645 x IO" 24 .1152280255 x IO" 26 .4056821807 x IO" 28 .1758246702 x IO" 30 .4555271512 x IO" 771 1539 3074 6146 12292 24659 387 Table 2.3: Value of 8 for Various ro ro Cmax Cmax ro Cmax ^max 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, 11 Chapter 2. Primitive Triple-Error-Correcting BCH Codes For any 0 < e < 1/2, the term |8(1 - 2e) 2m J / TO j clearly goes to 0 as m increases. Q.E.D. Proposition 8: For 0 < e < 1/2, -P„(e) > 2~ [l - o(m)] where o(m) is a positive quantity p which goes to 0 as m increases. Proof: Using (1.3) but ignoring all terms involving Bi, i ^ 0, we have P*{t) > 2" 3m - (1 - c) ™2 (2.8) 1 = ^[i-a^U-^r- ] (2-9) 1 = ^[i-K-r- ^}" ]. 1 For any 0 < e < 1/2, the term J8(l — e)( 2ra_1 (2.io) 1 )/ j clearly goes to 0 as m increases. m 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 maYimnm 2.3 at e max cannot be easily identified due to the scale used. Case Where m is Odd and > 5 Proposition 4: Primitive triple-error-correcting BCH codes of blocklengths 2 — 1 are proper, m 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 1E-03 I I I | I I I I I I I I I | I I I I M 12 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 | 1E-04 1E-05 m = 6 1E-06 co o 1E-07 t 1E-08 n m = 8 k •o <D O B 1E-09 m= 10 QJ T3 C 3 1E-10 1E-11 m = 12 1E-12 1E-13 ' ' ' ' ' 111' I 0.05 t i l l 0.1 i I I I I I I I I I i I I I >I I I I I I I I i 0.15 0.2 l u l l 0.25 0.3 I I I I I 0.35 Bit Error Rate Figure 2.1: Undetected Error Rate for m = 4, 6, 8, 10 and 12 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.4 0.45 0.5 13 Chapter 2. Primitive Triple-Error-Correcting BCH Codes Odd m > 5 Number of vectors with weight i, Bi Weight, i 0 2 m - l _ (m+l)/2 2 m - l _ ("»-l)/2 2 m-i 2 m-l 2 2 2 m-l 2 2 + 2 2 (m-l)/2 2 1 2 (m-3)/2( (m-l)/2 2 l)(5. m-l 2 + 4 m 4)(2 - m + 3 l)/3 m m (m-3)/2( (m-l)/2 1 m 2 m_1 (m+l)/2 - l)/3 m (9.2 - + 3.2 " + l)(2 - 1) _ l)(5.2 ~ + 4)(2 - l)/3 (m-5)/2( (m-3)/2 _ l ) ( 2 - l)(2 - l)/3 2m + 1 l)(2"»- - l)(2 (m-5)/2( (m-3)/2 + 2 m 2 Table 2.5: Weight Distribution of the Dual of a Triple-Error-Correcting Primitive Binary BCH Code of Length 2 - 1, m odd. m reproduced in Table 2.5. With this weight distribution, using (1.3) and the fact that p = 3m, we can write P (e) v = 1 2 2("- )/ (2(™- >/ + l)(2 - - l)(2 5 1 + 2 3 2 m 1 - 1) m _ (1 2^2—i_ (m ,)/ 2 + 3 3m 2 (m-3)/2 (m-l)/2 (2 ) ( . " * - I + 4)(2 1 5 2 +(9.2 ~ + 3.2 " + l)(2 2m + m 3 m - 1)(1 - 2e) ^m-l.^m-! 2 3 2 m 1 2 _ j —i («-i)/a 1 (m-5)/2^ (m-3)/2 _ 1)( "»-1 _ ) ( m _ 2 1 2 )/2 2ra_1 2( - )/ (2( - )/ - 1X5.2"- + 4)(2" - 1) 3 m | 4 - 1) ^ m + 2£ (1 - 2c) 2 2 +2 jm-1^2('»+l)/2 -(l-e) "- . 2 1 (2-11) Defining / = 2^ m 1 ^ , and grouping some common terms, we obtain 2 ,(, -l)(2, -l) | I 2 x + ( /(5/ -M)(2/ -l) 6 2 + + (^+^ _ 2 2 { ( / + + _ + lX2f -l)(l-2€)' 2 _, 2 e f 2 2 e f + ( / -» + m _ _ (1 - e)2/ -l 2 _ 2 e ) , + 2 ,j 2 c ) J J + l } (2.12) 14 Chapter 2. Primitive Triple-Error-Correcting BCH Codes Differentiating (2.13) with respect to e, we obtain ( i + 1)(/ -!)(/-2) _ f_ _ 2 u (i de ~ { n x M(8/«) U (j -1)(/ -!)(/ + 2) _ ^JP+M-! 2 ( j5/ 4 ) ( / 2 + - ( £ + ^ 2 - l ) { ( 1 _ I 2 e ) l 2 _ , _ + 2)(l-2e) p 1 + ( _ 1 2 £ f + I - a } + (l- ) ' - }. 2 1 2 2 € (2.13) ^ 1 ^dt^' ^ ^ * We will show that the expression in (2.13) is non-negative. Let /i(e) = Tie calculation shows that (1 -&)/[(«) = _(2Z 2 (Z 2 2/ -3 2 ) ^ ( 6 ) + 2(/ -1)6(1-6) 2 - 1) 12/ 3 2 ( ^ - ^ { ( i - ^ - ^ - a - ^ 2 ' - } 1 +(5Z + 4) {(1 - 2 e f - (1 - 2€)' '- } 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(Z - 1) (1 - 6) "- 2 2 C 3 ^2#f(y " 2) {(1 - 26)' " '- - (1 - 26)<+'-} 2 2 1 2 2 1 +(5/ + 4) {(1 - 26)' -'" - (1 - 26) '- } 2 2 1 ,2+ 1 > 0. (2.15) Inequality (2.15) can be simplified to Me) £ 24/ 6(l - 6) ' " - ( L __ ) [(1 - 26)' - '" - (1 - 26)^ '- ] 3 2 2 3 2 2 1 2 1 2 _ ( / 2 + 4) [ ( l - 26)' -'" - (1 2 5 1 2 6 f > (2.16) 15 Chapter 2. Primitive Triple-Error-Correcting BCH Codes We can now repeat the above procedure using /2(c) in place of /i(e), and write = -2(/ -2Z-l)/ (€)-4K/ -4)(l-2e)' '- (l-2e)fi(e) 2 2 2+2 1 2 +2/(5/ + 4) [(1 - 2 )' -'- - 3(1 - 2e)' '- ] 2 2 1 2+ 1 € +24/ (l - e) * - [2(/ + 21- l)e - 2(2/ + l)c + l] . 3 2 2 4 2 2 (2.17) Since /*2(0) = 0, from Lemma A.l it is sufficient to show that /3(c) = -2(f - 4)(1 - 2e)' '" + (5/ + 4) [(1 - 26)' -'- - 3(1 2 2+2 1 2 2 2ef ~ } +l 1 1 +12/ (1 - c) ' " [2(/ + 21- l)e - 2(2/ + l)e + l] > 0. 2 2 2 4 2 2 (2.18) Repeating this procedure three more times, wefindthat to establish that * non-negative, s it is sufficient to show that the fourth degree polynomial /,(e) = (4/ - 36/ + 80/ - 36/ + 4)e 8 6 4 2 4 +(76/ - 260/ + 104)c - (34Z - 110/ - 84)e 4 2 3 4 2 2 -(4/ - 20/ + 136)€ + (/ - 5/ + 34) 4 2 4 2 (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 / j( ) ^ 0. We can write /21(e) as € 2 Me) = (1024/ - 2304Z + 1280/ - 144/ + 4)e + (1216/ - 1040Z + 104)e 8 6 4 2 4 4 2 3 -(544/ - 440/ - 84)e - (64/ - 80/ + 136)c + 16/ - 20/ + 34. 4 2 2 4 2 4 2 (2.20) 16 Chapter 2. Primitive Triple-Error-Correcting BCH Codes This can be expressed as the sum of /j(e) and l gi(e) where 2 gi(e) = (1020Z - 2268/* + 1200/ - 108)e + (1140Z - 780)e 6 2 4 2 3 -(510/ - 330)e - (60/ - 60)e + 15/ - 15. 2 2 2 2 (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 — 1 are m proper for odd values of m. The undetected error rate curves for m = 5, 7, 9, 11 and 13 are shown infigure2.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 This is achieved by eliminating a power term each time a recursion is performed. > 0. de Chapter 2. Primitive Triple-Error-Correcting BCH Codes F i g u r e 2.2: U n d e t e c t e d E r r o r R a t e for m-5,7, 17 9, 11 a n d 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 B C H 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 extended codes. Proposition 5: be the weight distribution of the dual of a ( n , k) B C H code, Let {.Bi} L ) i=0 C. The weight distribution of the dual of the extended ( n + l , A;) B C H code, C t is |£.\ext J ex where B i<ext i = 0 , l , . . . , n + 1. = Bi + Bn+Lt (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 Pfc-l,l ••• Pfc-l,n--fc-1 1 0 0 0 ... 1,0 (3.2) and H= 1 0 0 ... 0 Poo PlO ••• 0 1 0 ... 0 P01 Pll • •• Pfc-i.i 0 0 1 ... 0 P02 Pl2 • • • Pfc-1,2 Pi ,n-fc-1 • • • Pfc-l,n Pfc-1,0 (3.3) 1 1 0 0 0 ... 1 1 P0,n-fc-l respectively. The generator matrix of the extended code, G t, is a k X (n + 1) matrix of the ex following form : | 1 0 0 . . 0 PO.x Poo Poi •• PlO Pll • • Pl,n-fc-l P20 P21 P2,n-fc-l 1 o0 Pfc-l,n-fc-l 1 P0,n-fc-l 1 G xt — 01 0 . . 0 Pl.x 1 . . 0 P2,x (3.4) e • . Pfc-1,0 Pfc-l,l • •• 00 0 . . 1 Pfc-l,x . where {p»,*}._ £ {0>1} such that each row of G t has even weight. Using the fact that the 0 inner product of every row of G ex e x t with each row of H ext must be zero and G • H r = 0, H ext 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 0 1 0 .. 0 Poi Pll 0 0 1 .. 0 P02 Pl2 •• •• Pfc-1,0 0 Pfc-1,1 0 Pfc-1,2 0 . 0 • 0 0 0 0 ... 1 PO,n-fc-l Pi ,n-fc-1 1 1 1 ... 1 1 1 The presence of the all l's vector as a row of H t ex • Pfc-l,n-fc-l .. 1 (3.5) 0 1 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 B C H 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 ofroand Section 3.2.2 examines the case forroeven. 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 2 m - i _ (m-i)/2 2 m-l 2 m - l _j_ ( m - l ) / 2 2 (2 m_2 + 2( ( m-l 2 2 + 1 )/ )(2 - 1) m-3 2 m j ^ m_ ^ ^ m-2 _ (m-3)/2^ ?n _ 2 2 2 Table 3.1: Weight Distribution of the Dual of the Double-Error-Correcting Primitive BCH Code of Length 2 - 1, m odd. m Odd m > 3 Weight, i 0 2 m - l _ (m-l)/2 2 2 m-l 2 m-l 2 m Number of vectors with weight i, Bi 1 (2 - l)(2 ) (2 + 2)(2 - 1) (2 -l)(2 ) 1 m m + 2 (m-l)/2 m_1 m m m_1 Table 3.2: Weight Distribution of the Dual of the Extended Double-Error-Correcting Primitive BCH Code of Length 2 , m odd. m Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 22 Case Where m is odd 3.2.1 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 2lmTT 1 + (2 + 2)(2 m W = - 1)(1 - 2e) m 2 +(2 - l)(2 ~ ){(l - 2e) ~ - ~ m m 1 2n 1 2(m + (1 - 2c) 1),i 2 m-l + 2 (m-l)/2' +(1 - 2c) 2 (3.6) Making the substitution I = 2^ ~ ^ m ™ = sF 1 2 gives 1 + (2Z - 1) j / ( l - 2e)' "' + (2Z + 2)(1 - 2e) 2 2 2 2 -(1-6) +/ (1 - 2e)' '} + (1 - 2e) 2 1 2+ (3.7) Taking the derivative, we obtain dPu(e) d £ = - 21' (1 - e) -* 2p - J y ]^2l - 1){(Z - 0(1 - 26) -'" + (2Z + 2)(1 - 2ef "> 2 2 12 1 2 +(Z + /)(1 - 26)' '" J + 2(1 - 26) ' " . 2 2+ 1 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(2Z 2 l)/ (6) + x @LJlf ( ) 2 e (3.9) Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes where Me) = 4Z (1 - e) ' " - (2/ + 2)(1 - 2c)' " 2 2 2 2 2 2 1 - ( / - l ) [(l-2e)' -'- + (l-26)' '- ]. 2 2 1 2+ 1 (3.10) Since /i(0) > 0, it follows from Lemma A.l that /i(c) > 0 over [0,1/2] if / (e) > 0 over the 2 same interval. Moreover, (1 - 2e)/-(c) = -2(/ - l)/ (e) + 8/ (Z - l)e(l - c ) ^ " 2 2 2 2 3 2 -2Z(/ - 1) [(1 - 2c)' -'" - (1 - 26)' - ] . 2 2 1 2+z 1 (3.11) Since 2/(Z — 1) > 0 and / (0) > 0, to prove that / (c) and hence / (e) are non-negative, it is 2 2 2 x sufficient to show that 4/e(l - e) 2p 3 > (1 - 2c)' -'- - (1 - 2 e f - . 2 1 +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. 23 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 _ m/2 2 m - l _ (m-2)/2 2 m-l 2 m-l + 2 m-l + 2 2 (m-4)/2( (m-2)/2 2 j ^ m _ ^ 3 + - m/2( m/2 2 1)/3 2 2 2 (m-2)/2 m/2^m/2 _ j j ^ m _ ^ 3 2 m/2 + ( m-2 2 2 2 _ y + (m-4)/2J (m-2)/2 _ j ^ ^ m _ l)/3 2 Table 3.3: Weight Distribution of the Dual of the Double-Error-Correcting Primitive BCH Code of Length 2 — 1, m even. m Even m > 4 Weight, i Number of vectors with weight i, Bi 0 1 2 m - 1 _ m/2 m - l _ (m-2)/2 m-l 2 m-l 2 2 2 2 2 2 m-l 2 2 m + 2 (m-2)/2 + 2 m/2 m-2( m + 1 ( m-l 2 2 2 l)/3 (2 -l)/3 + m 2 )( m _ ^ 2 (2 -l)/3 ( 2 - l)/3 1 m + 1 m-2 - m 2 m m Table 3.4: Weight Distribution of the Dual of the Extended Double-Error-Correcting Primitive BCH Code of Length 2 , m even. m Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 25 Case Where m is even 3.2.2 The weight distribution of the dual of the double-error-correcting BCH code of length 2 — 1, m for even values ofTO> 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 P (e) = u 1 1+ ( 2 - l ) { m 22m+l 2 +(2 " + 2)(1 - 2e) m 1 >m-2 + -T-(l~2e) 2 m+l + 2 m-l^. m/2 (1 " 2c) } + (l-2c) 2 2 m-l + 2 (m-2)/2 - (1 - c) 2 2 (3.13) By making the substitution I = 2^ )/ , we obtain m 2 32/" 2 1 + (4/2 - l)\t(l - 2c) ' " ' + §£(1 - 2c) ' "' 2 2 2 2 +(2Z + 2)(1 - 2c) ' + ^ ( 1 - 2 c ) 2 2 2 + ^(l-2c) ' + '} + ( l - 2 c ) ' 2 2 2 4 2l2+ 2 ' - (1 - c)4P 2 (3.14) Taking the derivative of P (c) with respect to c yields u dP (e) de (4p - u +2(/ + 1)(1 - 2c) ' " + 2 2 2 (i!±i)(l_2c) ' 2 + 1 2 + 2 i){£fi!(i 4 ( 2 * 2 + < ) (l - - ) - '-'+ 2 2c) ' '" 2 '- } + 2(l-2c) ' 1 2 p 2 £ 4 2 2+ 4 ( 2 ' -''(i ; ur 1 . 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/ - l)/ (c) + (4/ - l)/ (c), 2 2 x 2 (3.16) Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes 26 where /2(€) = 4Z (1 - e) " - \ ^ 3 ^ { ( 1 - 2c) - '- + (1 - 2e) ' '" } 2 412 2 212 2 1 2 2+2 1 +2(Z + 1)(1 - 26) ' " + ^ " ^ { ( l ~ 26) ' '" + (1 - 26) ' -'- } 2 2 2 1 2 2+ 1 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 ( 2 Z - l ) / ( ) + 8/ (2/ -l)e(l-2€) 4J -3 = 2 2 2 2_ 4 _ ( i 2 2 € / 2 ) | ( 1 _ ) 2 ' - 2 ' - i _ (1 2 t 2 '3/ _ 2e) ' '- } 2 2+2 1 +(4Z - I ) {(1 - 2e) -'- - (1 - 2e) ' '- } 4 2 2f2 1 2 2+ 1 (3.18) Moreover, since / (0) > 0, a sufficient condition for 2 4(2Z - l)e(l - e)4J -3 2 2 (Z - 1) {(1 - 26) * - '- - (1 - 2e) ' 2 * 37 > 0 is that de 2 2 2 1 2 2+21 -} 1 +(4Z - 1) {(1 - 2c) -'- - (1 - 2€) ' '- } 2 212 1 2 2+ 1 (3.19) Inequality (3.19) is the same as (D.3) which is proved in Appendix D. 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 2 m-i _ ( 2 m-l _ ("»-i)/2 2 m-i 2 m-l 2 m-l 2 m + 1 2 )/ 1 2 (2 - l)(2 - l)/3 2 - (5.2 + 4)(2 - l)/3 2(9.2 " + 3.2 " + l)(2 - 1) 2 (5.2 + 4)(2 - l)/3 2 (2 - l)(2 - l)/3 1 m_3 2 m 2 1 2m + + 2 2 m m_1 m_3 (m+l)/2 m m 4 m m-1 (m-l)/2 m_1 3 m m_1 m m m_1 Table 3.5: Weight Distribution of the Dual of the Extended Triple-Error-Correcting Primitive Binary BCH Code of Length 2 , m odd. m 3.3.1 Case Where m is odd Kasami et al [4] have shown that these codes satisfy the 2~ bound. Here we shall prove that p these codes are proper. Proposition 7: Extended primitive triple-error-correcting BCH codes of blocklengths 2 are m 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( P «< > £ m-1 )/ we can write 2 1 = 16/* +(|I + \l + 2)(1 - 2ef + Q«l±i)(l - * f « 4 2 ^ ! _ ^ ( l _ 2 ) ' + ' } + (l-26) ' 2 + £ 2 2 2 (1-er. (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- '-' + (5! + 4)(1 - lef- -' 2 -(5/ + 4)(1 - 2ef- ~ 2 l - ( £ - 2)(1 - 2e)' 1 1 2 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) B C H 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 B C H code for even values of m > 6 also satisfies the 2~ bound. Using (1.3), (2.1) and Proposition 5, the probability of p undetected error for these codes for m = 6,8,10, ...,30 was evaluated . It was found that the 2~ bound is not satisfied in all cases. However, as for the non-extended codes, the difference p between the maximum value of P (() and 2~ decreases exponentially with m. The values p u of Pu(€max) and 2~ for m = 6,8,10,12 and 14 are listed in Table 3.6. p For m > 12, the difference between the maximum P (e) and 2~ is not discernible up to 20 significant figures. p u A reasonably accurate empirical value for e max Cmox for is again given by (2.3). The values of e m = 6,8,..., 30 are listed in Table 3.7. max and Chapter 3. Extended Double and Triple-Error-Correcting Primitive BCH Codes m Pu(£max) 6 .19189455522645475728 xlO" 8 .29802325760494439858 x l O 10 .46566128730773925924 X l O " 2 -P .19073486328125000000 xlO" 5 .29802322387695312500 X l O -7 - 7 .46566128730773925781 xlO" 9 12 .72759576141834259033 xlO" 10 .72759576141834259033 x l O 14 .11368683772161602974 xlO" 12 .11368683772161602974 xlO" Table 3.6: Comparison of P (e ) u m (•max (•max 5 max m and 2~ for C . p ext 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 0 x and l max for C . ext 9 - 1 0 12 29 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 minimum 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) < J /f x (4.1) £ ("W-€)-'. 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=k Xl (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 30 for 0 < e < x. (4.5) Chapter 4. An Improved Upper Bound on Undetected Error Probability 31 The ChernofF inequality [14] states that J2 ( n ) ~ -P) n_i < 2- ^' ) n£ provided A > P. p (4.6) Using this inequality, (4.3) and (4.5), Kasami et al derived the final form of the upper bound as , ^ 2t+l 1 for 0 < c < — — < n I _ -nE((2t+l)/n,t)^ n 2 J°u(6) < { l 'n - k + t" t 1 • + -«*((fc/«).«) 2 f o r H£±I< <*<I. n n~2 (4.7) £ k From Figure 4.1, we know that E((k/n),e) increases with k. Hence 2~ ^ ^'^ decreases nE h with increasing values of k. The term l/( ~* )> however, is a decreasing function in k. Hence n +t 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 A n Improved Upper Bound Proposition 9: The probability of undetected error for any linear code is bounded by 1 2 -»«((2t l)/n,«) + ) f o r 0 < € < 2 l ± i < I. n t for r n - \ne] + ^ f i t 2t + 1 \ne] ^ 1 <c< < -. n n 2 L (4.8) F i g u r e 4.1: G e o m e t r i c a l Interpretation of E(\, P). Chapter 4. An Improved Upper Bound on Undetected Error Probability 33 Proof: The new upper bound is obtained by observing that (4.9) * E^a-o-' ^-«r* = [(l-c) + c] = 1. (4.10) n (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 < e < - < -. n n 2 (4.13) ' l t v Using this fact, we can express (4.12) as P M * , i- 1 . A 1 / n - [ne I + M ^ < ' < ^ i \ - 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 tripleerror-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 Figure 4.2: Upper Bounds of Hamming Code, m = 4. 34 Chapter 4. An Improved Upper Bound on Undetected Error Probability 1E-05 < 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0.05 0.1 1 1 1 1 1 1 1 1 1 1 1 1 ) 0.15 0.2 i [ 111 0.3 1111111111 0.25 35 i 0.35 Bit Error Rate Figure 4.3: Upper Bounds of Hamming Code, m = 5. 11 0.4 i 0.45 Chapter 4. An Improved Upper Bound on Undetected Error Probability 1E-01 36 rr 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 1E-02 O £ 1 E " 0 3 "D CD o B CD T3 Actual Prob. of Undetected Error Kasami Upper Bound New Upper Bound 1E-04 •) E-05 ' 1 11111 0.05 111111111111111111111111111111111111111111111 0.1 0.15 0.2 0.25 Bit 0.3 1111111111111111111111 0.35 Error R a t e Figure 4.4: Upper Bounds of Hamming Code, m = 6. 0.4 0.45 0.5 Chapter 4. An Improved Upper Bound on Undetected Error Probability 1E-01 ' I > I I ' I ' I | I ' ' ' I | I I I I I I I M | II I I I I I I I | I I I I I I I I I | I I 1 1 37 I I I I I [ I I II M I I I | II I II I I I I | I I II I I I I I J I I | | I | I | | 1E-02 O I 1E-03 & O c5 T 3 C 3 Actual Prob. of Undetected Error Kasami Upper Bound 1E-04 1E-05 New Upper Bound 11 M 11111111111111111 M 111111111111 0.05 0.1 0.15 111111111111 0.2 0.25 11111 M 11111111111! 1111111 1111111111 L 0.3 0.35 Bit Error Rate Figure 4.5: Upper Bounds of Hamming Code, m = 7. 0.4 0.45 0.5 Chapter 4. An Improved Upper Bound on Undetected Error ProbabiUty Figure 4.6: Upper Bounds of Double-Error-Correcting Primitive B C H code, m = 4. 38 39 Chapter 4. An Improved Upper Bound on Undetected Error Probability 1E-10 ' 0.05 1 1 1 1 1 1 1 1 1 1 1 0.1 1 1 1 1 1 1 1 1 1 1 0.15 1 1 1 1 1 1 1 1 1 1'''''' '' 0.25 0.3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0.2 1 1 0.35 0.4 0.45 Bit Error Rate Figure 4.7: Upper Bounds of Double-Error-Correcting Primitive BCH code, m = 5. Chapter 4. An Improved Upper Bound on Undetected Error Probability 1E-01 pr I IIII M | II I I I II I I j M I I M I I I j IIIIIIIII j 40 | I II 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 I I I II I M 1E-02 1E-03 1E-04 ns _o o £ 1E-05 UJ S 1E-06 z\ CD T3 C 1E-07 1E-08 Actual Prob. of Undetected Error Kasami Upper Bound 1E-09 1E-10 New Upper Bound 1111111111) 111111 0.05 0.1 11 0.15 ''•'ii 0.2 ''' 0.25 ' • ' i l l ' 0.3 I 0.35 ' i i ' 0.4 0.45 Bit Error Rate F i g u r e 4.8: U p p e r B o u n d s o f D o u b l e - E r r o r - C o r r e c t i n g P r i m i t i v e B C H code, m = 6. 0.5 Chapter 4. An Improved Upper Bound on Undetected Error Probability 1E-01 41 j 1111111111111 I I iII111II1111111111111111MII1111111111111111 H 1111111111 M 11 M 11111111111111111II 1E-02 1E-03 1E-08 Actual Prob. of Undetected Error Kasami Upper Bound 1E-09 1E-10 New Upper Bound 1 I i 1 I I III'I' I' I' ' 1' ' 1• ' l 0.05 0.1 111111111 0.15 11111111111111111111111111111111 0.2 0.25 0.3 0.35 1111111111111111 0.4 0.45 Bit Error Rate F i g u r e 4.9: U p p e r B o u n d s of D o u b l e - E r r o r - C o r r e c t i n g P r i m i t i v e B C H code, m = 7. I, 0.5 42 Chapter 4. An Improved Upper Bound on Undetected Error ProbabiHty 1E-01 M F I I I I I I | I I II 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 | ||||||n | | || I I I | I I I 1E-02 1E-03 1E-04 J2 CO O £ 1E-05 LU T 3 2 o 1E-06 CD «—* CD T3 C 1E-07 1E-08 Actual Prob. of Undetected Error Kasami Upper Bound 1E-09 1E-10 - New Upper Bound i l i i i i i i i I i i i i 0.05 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.1 0.15 0.2 i ; i i i I i i i I 0.25 0.3 I i i i i i i i i i I 0.35 i iii 0.4 i i i i i I 0.45 Bit Error Rate F i g u r e 4.10: U p p e r B o u n d s o f D o u b l e - E r r o r - C o r r e c t i n g P r i m i t i v e B C H code, ro = 8. i 0.5 I Chapter 4. An Improved Upper Bound on Undetected Error Probability F i g u r e 4.11: U p p e r B o u n d s of T r i p l e - E r r o r - C o r r e c t i n g P r i m i t i v e B C H code, m = 5. 43 Chapter 4. An Improved Upper Bound on Undetected Error ProbabiHty 1E-11 I I I I I I I I I I I 0.05 I I I I I I 0.1 I I I I I I I I I I I I I 0.15 I I I I I II I 0.2 I I II I 0.25 I I I I 0.3 44 I II II I I II II I I I I I ! 0.35 0.4 0.45 Bit Error Rate F i g u r e 4.12: U p p e r B o u n d s of T r i p l e - E r r o r - C o r r e c t i n g P r i m i t i v e B C H code, m = 6. ||I I I • Chapter 4. An Improved Upper Bound on Undetected Error Probability F i g u r e 4.13: U p p e r B o u n d s o f T r i p l e - E r r o r - C o r r e c t i n g P r i m i t i v e B C H code, m = 7. 45 Chapter 4. An Improved Upper Bound on Undetected Error Probability 1E-05 J l I i i i I i T~p i I i ri M I | i ii I I i1 i V| i i i i n i i i p"T M 1 M M 46 rfi i i ii ii i i j i ii i i ii i i [ i i i i rr i i r) i ITT I I I ri j i A 11 1E-06 /1 ' I b- 1E-07 JQ CO .Q O fc 1E-08 T3 & O t» Actual Prob. of Undetected Error CD X3 C Kasami Upper Bound 1E-09 New Upper Bound 1E-10 1E-11 ' I ' ' '' ' ' '' 'I 0.05 0.1 0.15 I I 0.2 I I i r I I I I 1 II I 0.25 Ill 0.3 0.35 0.4 0.45 Bit Error Rate F i g u r e 4.14: U p p e r B o u n d s of T r i p l e - E r r o r - C o r r e c t i n g P r i m i t i v e B C H code, m = 8. 0.5 47 Chapter 4. An Improved Upper Bound on Undetected Error Probabihty I I I I I I I I | I I II I I I II | 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 X3 O 1E-08 LU "O gj o oj o> x> c 3 Actual Prob. of Undetected Error Kasami Upper Bound 1E-09 New Upper Bound 1E-10 1E-11 0.05 0.1 ii'i'i'i'' 0.15 0.2 i ' ' ' ' ' ' i' i ' ' i ' ' ' i ' i ' ' 0.25 0.3 0.35 ' 1 1 ' ' ' 0.4 111111 0.45 Bit Error Rate Figure 4.15: Upper Bounds of Triple-Error-Correcting Primitive BCH code, m = 9. 0.5 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 2 — 1, with m odd and > 5 m 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 characteristics 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 improvement 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 5.2 49 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 Standards," 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 Hamming 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, PrenticeHall, 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. 385393, 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. Theory 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 0 < e < 1/2 > -a(e)/(e), (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>Ja I*a(s)f(s)ds>0, a<e<e (A.4) Ja 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 is non-negative. /(e) is non-positive, its gradient, /'(e), must be non-negative since Under these conditions and the fact that /(0) > 0, /(e) once it reaches 0; therefore, /(e) can never be negative. 53 a(e) must be increasing 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(/ + 21- l)/ (e) + 6//(e) (B.l) 2 3 4 where f (e) 4 £ (5p + 4)[(l-26)' -'- -(l-2 )' '- ] 2 1 2+ 1 e +4/(1 - e) ' - €[2(/ - 6/ + l)e + 2(5/ + 4)e - (5/ + 4)]. 2 2 5 4 2 2 2 2 (B.2) Repeating this procedure, we can write (1 - 2e)/ ( ) = -2(/ - / - l)/ (e) + 4Z/(e) (B.3) 2 4 C 4 5 where Me) £ (5/ + 4)(1 - 26)' '" + (1 - €) ' " [-[hi 2 2+ 1 2 2 + 4) 2 6 +(10/ + 20/ + 8/ + 16)e - (4/ + 30/ + 44/ + 24/ - 6)e 3 2 4 3 2 2 +(-4/ + 8/ + 44/ + 48/ + 12/ - 44)c 5 4 3 2 3 +(4/ + 4/ - 28/ - 24/ + 28/ + 4/ - 4)e ]. 6 5 4 3 2 4 (B.4) Repeating this procedure again, we obtain (1 - 2e)f' {e) = -2(/ + / - l)/ (e) + (1 - e) ~ efx{e) 2l2 2 h 5 54 7 (B.5) 55 Appendix B. where A fi(e) = (41 - 36Z + 80Z - 36Z + 4)e 6 s 4 2 4 +(76Z - 260Z + 104)e - (34/ - 110Z - 84)e 4 2 3 4 2 2 -(4Z - 20Z + 136)e + (I - 5Z + 34). 4 2 4 2 (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/ - 2268/ + 1200/ - 180)e + (1140/ - 780)e 6 4 2 4 2 3 -(510/ - 330)c - (6G7 - 60)e + 15/ - 15 > 0 2 2 2 2 (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 g (e) = (65280/6 - 36288/4 + 4800/2 - 108)e4 + (4560/2 - 780)e3 2l -(2040Z - 330)e - (240/ - 60)e + 60/ - 15 > 0. 2 2 2 2 (C.2) We can express 521(e) as Me) = gi(e) + 15l hi(e) (C.3) 2 where hi{e) = (4284/ - 2268Z + 240)e + 228e - 102e - 12e + 3. 4 2 4 3 2 (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 57 Appendix C. hi(e) > 0. We now assume that /ij(c) > 0 and prove that /i /( ) ^ € 2 h i(e) 2 From (C.4) we have = (68544/ - 9072/ + 240)c + 228e - 102c - 12c + 3 (C.5) = hi(€) + n{€) (C.6) 4 2 4 3 2 where r,(c) = (64260/ - 6804/ )e . 4 2 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 f o l l o w i n g theorems are taken f r o m [16] a n d are reproduced here t o a i d the reader i n u n d e r s t a n d i n g the m a t e r i a l i n this thesis. Theorem D.l: For m odd and > 3, (l-2e) ' " 2 Theorem D.2: B 1 2 ( m " 1 ) / 2 - -(l-2e) 1 2 m " " 1 + 2 ( m 1 ) / 2 - < 1 2< m + 3 >/ e(l - c ) " " . 2 2 F o r m even a n d > 2, 2 m-l_ (1 - 2 e ) - 1 2 — 4 — — (1 - 2 6 ) - 2 ( r a - 2 ) / 2 - (1 - 2 e ) 2 ( T "- (D.2) 2 ) / 2 m (2 m -l) + 2 ( m " 2 ) / 2 + (1 - 2 e ) " 2 ( m 2 ) / 2 | < (2 -2)e(l-e) m I n order t o prove these theorems, we need t o establish a few useful inequalities L e m m a D.l: (D.l) 3 2 -3 m first. If m is a n y positive even integer, then (l-2e) 2 m - 1 2 ( T O - 2 ) / 2 + (l-2e) 2 m - 1 + 2 ( m - 2 ) / 2 < 2(1 - e ) " * (D.3) < 2(1 - e ) (D.4) 2 for 0 < € < 1 / 2 . If m is any positive o d d integer t h e n (l-2€) 3 Proof: 2 m - 1 2 ( m - 1 ) / 2 + (l-2e) ' 3 2 m " 1 + 2 ( m " - - (1 - 1 ) / 2 3 2 "\ F i r s t consider ( D . 3 ) . L e t / ( e ) = 2(1 - e ) " - (1 - 2 e ) 2 2 T O - 1 58 2 ( m 2 ) / 2 2 e) 2 m - 1 + 2 ( m " 2 ) / 2 (D.S) Appendix D. 59 We shall show that /(e) > 0. A brief calculation shows that (l-2e)/'(e) = -2 /(e) + 2 m m+1 e(l - e) " " 2 1 - 2 / [(1 - 2< ? - -* -' m 2 n 1 n (D.6) 1 - (l - 2e)*"~ + 2 )l2 2 i 1 ( r a - 2 ) / 2 ]. /(0) = 0, therefore by Lemma A l , 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"/ e(l - e) ™" . 2 ) / 2 2 2 1 (D.7) We shall prove (D.7) by induction on m. For m = 2, the requirement is that l-2e-(l-2e) 3 < 4e(l - e) . (D.8) 3 This simplifies to the condition e < e 4 (D.9) 3 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-2e) 2 m + 1 - 2 W 2 -(l-2e) < 2 • 2< + )/ e(l - e) *" " . 2 m + 1 + 2 r a / 2 m 2 2 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) - - [(l-2e)3 2m 1 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) (D.12) 2m+1 which holds since (1 - e) 2ro+1 = (1 - 2e + e ) ™ > (1 - 2e) This completes the proof of (D.3) for m > 2. 2 2 2m (D.13) 60 Appendix D. Q.E.D. Now consider (D.4). Since m + 1 is even and > 2, we have (l-2e) 2 m 2 ( m - 1 ) / 2 + (l-26) < 2(l-e) 2 m + 2 ( m _ 1 ) / 2 (D.14) 2 m + 1 by (D.3). If we multiply this inequality by (l-2e) < (l-c) ™ 2 m - 1 (D.15) 2 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+10e -10e + 4e ] 2 3 4 and the right hand side is given by 8e [l - 5e + 10e - 10e + 5c - <r ]. 2 3 4 5 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-2e) 2 m + 1 - 2 ( m + 1 ) / 2 - -(l-2e) 1 2 m + 1 + 2 ( m + 1 ) / 2 - 1 < 2< )/ e(l - e ) m+5 2 2m+2 " . (D.16) 3 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. 61 Appendix D. 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 . m/2 ^ ^(l-2 r -[(l-2 -^-(l-2 ) + 1 2 e e ) € •|(2 -l) + ( 2 - l ) [ ( l - 2 e ) m+2 (D.17) 2 m 2m/2 + (l-2€) 2 ]} 2m/2 < (2 - m + 2 2)e(l - c ) -3 2 m + (D.17) can be obtained by multiplying (D.3) by the inequality 1(1 - 26)-"-1(1 - 26)- 3 2 1 1 2(m fry** - l) 2)/2 + (1 - 2c) 2(m + (2- - 1) [(1 - 2e)- " { ( - - 1) + 2^1 [(i - 2e)-*~M + (1 - 2e)2 (ra 2 (D.18) 2)/2 2)/s + (1 - 2e) 2m/2 ]} " 2m/2 ]} < 2^-2 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) - " [(1 - 2e)- 3 2m 1 2(m 2)/2 2)/2 ] {(2 + - 1) + (1 - 2e) 2m/2 ] }(2 - - 1) 2(m +(2 - 1) [(1 - 2€)" m + (1 - 26) 2ra/2 m 2 m J < { ( - _ l) + ( 2 " - 1)[(1 - 2 c ) m 2 2(m_2)/2 2 +(1 - 2e) " ]}2(1 - 6 ) 2(m 2)/2 3 2 m (2 m + 1 - 1). (D.19) (D.19) is the product of inequality (D.3) and the inequality (1 - 2 e ) { ( 2 2m - 1) + (2 - 1)[(1 - 2e)- m+2 m < (2 m + 1 - l){(2 m 2m/2 + (1 - 26) 2ra/2 ]}(2 " - 1) m 1 - 1) + ( 2 " - 1) [(1 - 2e)" ~ m 2 2(m 2)/2 +(l-26) - ]}(l-c) . 2(m 2)/2 2ra+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(2 - 1)(1 - ) ™ m 2 € +1 + 2(2 ~ - l)(2 - 1)(1 - 2 ) (2-2 _ i ) m 1 m 2m € m + 1 - 1) _ 2~*' [ _ 2e)-*"-> > + (1 - 26) V ( 1 + (2 £) 2( 2)/2 (1 >(2 -l)(2 - -l)(l-2 0 m+2 m 1 < 2m ] (D.21) M . 62 Appendix D. and ( 2 m-i _ 1 ) ( 2 m _ x ) [ 4(1 _ 6 )3«+* _ 2(1 _ ) 2e •(2 - 1) [(1 - 2 e ) - ™ TO 2m 2 /2 2m ] > (2" " - 1) 1 + (1 - 2 e ) 1 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 and (1 - 2 e ) - 2 < m " 2 ) / 2 + (1 - 2 e ) 2 ( m _ 2 ) / 2 are replaced by the smaller quantities (1 - 2 e ) 2m 1 1 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 - 1). This completes the proof of the theorem. m 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 |
Aggregated Source Repository | 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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065497/manifest