UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On the undetected error probability of linear codes Ong, Chong Tean 1990

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

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.  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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

Comment

Related Items