EXAMINATION OF THE UNDETECTED ERROR PROBABILITY OF LINEAR BLOCK CODES By KENNETH ALFRED WITZKE B.A.Sc, The University of B r i t i s h Columbia, 1983 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES Department of E l e c t r i c a l Engineering We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA August 1984 © Kenneth Al f r e d Witzke, 1984 I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r a n a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l m a k e i t f r e e l y a v a i l a b l e f o r r e f e r e n c e a n d s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s m a y b e g r a n t e d b y t h e h e a d o f m y d e p a r t m e n t o r b y h i s o r h e r r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t b e a l l o w e d w i t h o u t m y w r i t t e n p e r m i s s i o n . D e p a r t m e n t o f E l e c t r i c a l Engineering T h e U n i v e r s i t y o f B r i t i s h C o l u m b i a 1956 Main Mall V a n c o u v e r , C a n a d a V6T 1Y3 D a t e August 31st 1984 i i ABSTRACT The undetected error p r o b a b i l i t y , P(e), of linear (n,k) block codes used for transmission over a binary symmetric channel i s examined. A class of codes referred to as proper codes i s seen to possess certain desirable c h a r a c t e r i s t i c s . A family of increasingly better tests for determining when a code is not proper i s derived. Some known improper codes are examined to assess the r e l a t i v e strengths of the tests. For c y c l i c redundancy codes (CRC), P(e) i s shown to be " P asymptotically equal to 2 . For s p e c i f i c values of k, P(e) was evaluated using the dual code weights. This greatly reduces the computational burden. The even CRC subclass consisting of generator polynomials, g(x)'s, with an even number of terms i s shown to have the a b i l i t y to detect a l l odd weight errors. It was observed that the P(e) c h a r a c t e r i s t i c s of a code generated by g(x) i s cl o s e l y related to the exponent of g(x). In p a r t i c u l a r , a low exponent i s a good indicator of an improper code. It was also found that by examination of a number of primitive g(x) that the resu l t i n g codes are proper. For k < 150, a code referred to as CRC-12R i s shown to have better P(e) c h a r a c t e r i s t i c s than the CRC-12 standard. Three CRC-16 standards: CRC-ANSI, CRC-CCITT and CRC-CCIR are compared. It was shown that CRC-CCIR has a very high P(e) and CRC-CCITT has the best o v e r a l l P(e) c h a r a c t e r i s t i c s of the three standards. i i i TABLE OF CONTENTS Page ABSTRACT i i LIST OF TABLES v LIST OF FIGURES v i ACKNOWLEDGEMENT ix 1. INTRODUCTION 1 1 .1 Motivation 1 1.2 D e f i n i t i o n of Proper Codes 2 1.3 Summary of Previous Results 3 1 .4 Overview 4 2. ON DETERMINING WHETHER A CODE IS IMPROPER 7 2.1 Benefit of Using Proper Codes 7 2.2 Family of Tests for Improper Codes 7 2.3 Determining Improper Codes using the VGO Bound 11 2.4 Comparison of the Family of Tests for Improper Codes 11 2.4.1 BCH(63,24) Code 11 2.4.2 Square SPCP Codes 13 2.4.3 CRC Codes 15 3. CRC CLASS PROPERTIES 26 3.1 Brief Description 26 3.2 P(e) Behaviour 27 3.3 Detection C a p a b i l i t i e s of the CRC Class 29 3.4 Proper Code g(x) Construction 34 iv Page 4. CRC STANDARD EXAMINATION 55 4.1 CRC-12 Analysis 55 4.2 CRC-16 Analysis 63 5. CONCLUSIONS 75 5.1 Summary of Results 75 5.2 Suggestions for Further Work 77 BIBLIOGRAPHY 78 V LIST OF TABLES Table Page I L i s t of Improper Codes for p, d and k < kO 12 II Square SPCP Codes: VGO and VG1 Bound Values 14 III CRC-12: P(e*) {2 < k < 50};2"12=2.44140625E-04 17 IV CRC-ANSI: P(e*) {2 < k < 50};2"16=1.52587891E-04 ... 18 V CRC-CCITT: P(e*) {2 < k < 50};2'16=1.52587891E-04 .. 19 VI CRC-12: VGO and VG1 Bound Values 21 VII CRC-ANSI: VGO and VG1 Bound Values 22 VIII CRC-CCITT: VGO and VG1 Bound Values 24 IX CRC-6: Proper Code g(x) for 2 < k < 50 36 X CRC-9: Proper Code g(x) for 2 < k < 50 36 XI CRC-7: Proper Code g(x) for 2 £ k < 50 37 XII CRC-8: Proper Code g(x) for 2 < k < 50 37 XIII Even CRC-6 subclass polynomial exponents 45 XIV Even CRC-9 subclass polynomial exponents 45 XV Even CRC-7 subclass polynomial exponents 46 XVI Even CRC-8 subclass polynomial exponents 46 XVII CRC-16 Standard Comparison 74 v i LIST OF FIGURES Figure Page 1 P(e): Proper Code Example 8 2 P(e): Improper Code Example 8 3 P(e): Pseudo-proper Code Example 8 4 P(e): Proper CRC-8 {g(x)=(111100011),0 < e < 1/2,2 < k < 100} 39 5 P(e): Improper CRC-8; non-symmetric g(x) {g(x)=(100100011),0 < e < 1/2,2 < k < 100} 40 6 P(e): Improper CRC-8; symmetric g(x) {g(x)=(110000011),0 < e < 1/2,2 < k < 100} 41 7 P(e): Proper CRC-8 {g(x)=(111100011),10"5 < e < 1/2,2 < k < 100} 42 8 P(e): Improper CRC-8; non-symmetric g(x) {g(x)=(100100011),10-5 < e < 1/2,2 < k < 100} 43 9 P(e): Improper CRC-8; symmetric g(x) {g(x)=(110000011),10"5 < e < 1/2,2 < k < 100} 44 10 P(e): Proper even CRC-6 subclass {g(x)=(1101111),10" 5 < e < 1/2,2 < k ^ 100} 48 11 P(e): Primitive CRC-6 {g(x)=(1110011),10" 5 < e < 1/2,2 < k < 100} 49 12 P.(e): Proper even CRC-7 subclass {g(x) = ( 1 10101 11), 10"5 <• e < 1/2,2 <, k < 100} 50 13 P(e): Primitive CRC-7 {g(x)=(10001001),10"5 < e £ 1/2,2 < k < 100} 51 14 P(e): Proper even CRC-8 subclass {g(x) = ( 10101101 1 ), 10"5 <: e < 1/2,2 <, k < 100} 52 v i i Figure Page 15 P(e): Primitive CRC-8 {g(x)=(101101001),10"5 < e < 1/2,2 < k < 100} 53 16 P(e): CRC-12S; g(x)=(1111000000011) {0 < e < 1/2,2 < k < 150} 57 17 P(e): CRC-12R; g(x)=(1111010100011) {0 < e < 1/2,2 < k < 150} . 58 18 P(e): CRC-12S; g(x)=(1111000000011) {0 < e < 1/2,50 < k < 2000} 59 19 P(e): CRC-12R; g(x)=(1111010100011) {0 < e < 1/2,50 < k < 2000} 60 20 P(e): CRC-12S; g(x)=(1111000000011) {10"5 < e < 1/2,50 < k < 2000} 61 21 P(e): CRC-12R; g(x)=(1111010100011) {10"5 £ e <• 1/2,50 < k < 2000} 62 22 P(e): CRC-ANSI Standard {0 < e < 1/2,50 £ k < 2000} 66 23 P(e): CRC-CCITT Standard {0 < e < 1/2,50 < k < 2000} 67 24 P(e): CRC-CCIR Standard {0 < e <, 1/2,50 < k < 2000} 68 25 P(e): CRC-ANSI Standard {10"5 < e <, 1/2,50 < k < 2000} 69 26 P(e): CRC-CCITT Standard {10"5 < e < 1/2,50 < k < 2000} 70 27 P(e): CRC-CCIR Standard {10-5 < e < 1/2,50 < k < 2000} 71 v i i i Figure Page 28 P(e): CRC-15 polynomial from CRC-CCIR {0 < e < 1/2,50 < k < 2000} 72 29 P(e): CRC-15 polynomial from CRC-CCIR {10"5 < e < 1/2,50 < k < 2000} 73 ix ACKNOWLEDGEMENT The author wishes to express grateful thanks and his deepest gratitude to Dr. C. Leung, the supervisor of t h i s project who was continuously avai l a b l e for consultation and provided helpful suggestions and guidance during the research work of t h i s t h e s i s . The f i n a n c i a l support received by the author: a Postgraduate Scholarship from the Natural Sciences and Engineering Research Council of Canada and a Teaching Assistantship from the Department of E l e c t r i c a l Engineering at U.B.C. i s g r a t e f u l l y acknowledged. This research work was also p a r t i a l l y supported by NSERC Grant A1731. The author also wishes to give h e a r t f e l t thanks to his parents for the i r continuous support and encouragement. 1 1. INTRODUCTION 1.1 MOTIVATION Channel errors commonly occur in data transmission. To achieve r e l i a b l e communications i t cannot normally be assumed that the message sent i s redundant enough such that the errors occurring can be ignored. Therefore, consideration must be given to designing a communications system with some form of error c o n t r o l . There are two basic methods used for error control in data transmission systems: the automatic-repeat-request (ARQ) method and the forward-error correction (FEC) method. FEC schemes use error-correcting codes to detect, locate and then correct errors. These codes have been studied extensively, [15]-[20]. ARQ protocols, however, use error-detecting block codes along with a data retransmission strategy, [12], [16], [17] and [30]. When errors are detected by the code, a retransmission of the data block can be requested. For packet-switching data networks, computer communications/storage networks and s a t e l l i t e systems, ARQ protocols are favoured because of their high r e l i a b i l i t y and simple implementation, [13], [16] and [17]. The decoder complexity and cost w i l l often make FEC schemes impractical for many applications, [15]—[18]. FEC schemes are, therefore, used mainly in situations where no return channel exists to send requests for retransmission. Hybrid ARQ/FEC schemes have also been investigated, [12], [16] and [30], where FEC of the most frequent error patterns i s used to reduce the number of retransmissions. But the hybrid ARQ/FEC scheme 2 involves the tradeoff between the advantage of added error correction versus the disadvantage of increased complexity. Only recently has there been s i g n i f i c a n t interest in investigating the problems of error detection, [1]~[6], which i s an integral part of the ARQ system. In the past, either the error detection code was said to be able to detect up to x channel errors or the undetected pr o b a b i l i t y of error, P(e), was assumed to be upper bounded by " P P(e) < 2 (1) where p i s the number of pa r i t y b i t s . These are generally very conservative measures of the error detecting c a p a b i l i t i e s of a code. Therefore, this thesis examines the undetected error p r o b a b i l i t y of linear block codes. 1.2 DEFINITION OF PROPER CODES The p r o b a b i l i t y of undetected error, P(e), i s one measure of how e f f e c t i v e an error detecting code i s . Consideration w i l l be given to error detecting (n,k) block codes used for transmission over the standard binary symmetric channel (BSC) with b i t error rate, e. A code i s termed proper, [4], when P(e) is monotonically increasing in e, for 0 ^ e ^ 1/2. This condition on the b i t error rate i s very often taken for granted k in communications problems. Since at e = 1/2, P(e) = (2 -n -p l)/2 < 2 , for any (n,k) code, i t follows that a proper code always obeys the bound (1). It had long been an accepted belief that a l l codes when used s o l e l y for error detection over a BSC 3 s a t i s f y ( l ) , but thi s was shown not to be true by Leung and Hellman in [5], A code that i s not proper is to be termed improper,[4]. 1.3 SUMMARY OF PREVIOUS RESULTS A summary of the various known results pertaining to proper codes i s now presented. (i) Neither linear block codes nor c y c l i c codes nor BCH codes are necessarily proper, [5]. ( i i ) Binary perfect codes are proper, [4], ( i i i ) The duals and extensions of binary perfect codes are proper, [4]. (iv) Shortened Hamming codes are not necessarily proper, [4], (v) The extension of a proper code containing odd-weight codewords i s not necessarily proper, [4]. (vi) The dual of a proper code i s not necessarily proper, [4]. ( v i i ) Double error-correcting BCH codes are proper, [5]. m ( v i i i ) Distance-8 extended primitive BCH codes of length n=2 with odd m and m £ 5 are proper, [3]. (ix) Square single parity-check product (SPCP) codes of size (m*m) are proper for 2 ^ m ^ 4, [ 2 ] . (x) Square SPCP codes of size (m«m) are improper for m > 4, [ 2 ] . (xi) Binary (n,k) group codes not s a t i s f y i n g the asymptotic Varshamov-Gilbert (V-G) bound ( 2 ) are improper. R > 1 - h(d/n) ( 2 ) 4 R i s the code rate (=k/n), d i s the minimum Hamming distance of the code and h(») is the binary entropy function. 1.4 OVERVIEW The problem of determining whether a code i s improper w i l l be examined in chapter two. The benefits of using proper codes for error detection are given. A family of increasingly better tests for improper codes w i l l then be presented. A general bound expression for the family of tests i s obtained. It w i l l be shown that the V-G bound (2) i s a c t u a l l y a s p e c i a l case of the family of tests for improper codes. By u t i l i z i n g the V-G bound, a table l i s t i n g improper codes for various values of p, d and k w i l l be presented. Some known improper codes w i l l then be examined to assess the r e l a t i v e strengths of the bounds in the family of improper code te s t s . One of the most commonly used error-detecting codes i s the c y c l i c redundancy code (CRC), also named the polynomial code, [7], [9], [10], [20] and [22]-[26]. The CRC i s not a true c y c l i c code which by d e f i n i t i o n has i t s n generator polynomial, g(x), divide (x +1), [20], but true c y c l i c codes are a subclass of the CRC c l a s s . The properties of the CRC class are examined in chapter three. F i r s t a brief description of the CRC class w i l l be given. Then i t w i l l be shown that as the block size, n, 5 increases and the number of parity b i t s , p, remains fixed, P(e) w i l l be asymptotically bounded by (1). The CRC c l a s s can thus be termed asymptotically proper. To examine P(e) of a code, the obvious method i s to cal c u l a t e the weights {Ai} of the primal (n,k) code. However, since the number of p a r i t y b i t s i s fixed for the CRC code, i t i s much easier to compute the weights {Bi} of the dual (n,p) code when varying k. This involves P k generating 2 codewords as opposed to 2 codewords, a much larger number. The expression using the primal code weights i s given by (3) and that using the dual code i s given by (4). n i n-i P(e) = V Ai*e *(1-e) (3) i=d P n P(e) = B(1-2e)/2 - (1-e) (4) The basis for using (4) to calculate P(e) i s explained in [4] and the t h e o r e t i c a l background i s given in [19]. The weight d i s t r i b u t i o n , B(x), of the dual code i s given by (5). n i B(x) = y Bi*x (5) i - 0 The subset of the CRC class with only even weight codewords w i l l then be examined. It w i l l be shown that t h i s subset has certain nice properties for error 6 detection such as the detection of a l l odd number of errors. A simple computational method for finding the r smallest value of r at which g(x) divides (x +1) is also presented. This method can be used to construct true c y c l i c codes. Not a l l codes in the CRC class are proper and, therefore, the problem of finding a g(x) to construct a proper code i s examined. There are some CRC standards that are in present use or being proposed, [13], [14] and [22]-[25], In the fourth chapter i s an examination of some of these standards. Included i s a comparison of three CRC standards from ANSI, CCITT and CCIR, each with sixteen pa r i t y b i t s but d i f f e r e n t generator polynomials as well as methods of generation. The CCIR standard i s presently being proposed and i s actually a non-linear code, but P(e) can be calculated by using a representative linear code. It i s found that of the three, the CCITT standard has the best o v e r a l l P(e) c h a r a c t e r i s t i c s . A summary of the results as well as some suggestions for future work are given in the f i n a l chapter. 7 2. ON DETERMINING WHETHER A CODE IS IMPROPER 2.1 BENEFIT OF USING PROPER CODES There are two clear benefits that can be derived by using proper codes for error detection. The f i r s t i s simply that P(e) i s upperbounded by (1) which can be made a r b i t r a r i l y small by choosing a proper code with a large p. The second benefit is that since a proper code i s monotonically increasing over e, then at smaller e values the code w i l l also have smaller P(e) values as shown in figure 1. Thus the problem of codes having P(e) maximum at any other value of e other than one-half, figure 2, i s eliminated by using a proper code. Note that some codes with a P(e) l o c a l maximum at e < 1/2 w i l l s t i l l s a t i s f y (1), but are not termed proper. These codes, of which an example i s given in figure 3, w i l l be termed pseudo-proper codes in t h i s thesis. 2.2. FAMILY OF TESTS FOR IMPROPER CODES Since a proper code i s monotonically increasing over 0 ^ e ^ 1/2, a code w i l l be improper i f i t s P(e) i s greater than k n P(l/2)=(2 -1)/2 . Therefore, a family of bounds for improper code testing can be obtained by truncating the terms of the primal code P(e) expression (3) and upper bounding the remaining P(e) terms by P(1/2). When the bounds are vio l a t e d , the code is improper. Each successive bound of the family uses an additional weight term from the set of {Ai}. The VG1 bound that u t i l i z e s only the minimum weight term of P(e) w i l l now be derived. The 8 9 maximum of the f i r s t term of P(e) occurs at e=d/n. This value of e w i l l be used in the family of bounds because the f i r s t term i s usually the most s i g n i f i c a n t . k n -n k -k d n-d (2 - l ) / 2 =2 2(1-2 ) £ Ad(d/n) (1-d/n) (6.a) Taking the nth root of both sides y i e l d s -1 k/n -k 1/n 1/n d/n 1-d/n 2 2 (1-2 ) > Ad (d/n) (1-d/n) (6.b) Taking logarithms of both sides we obtain (6.c). A l l logarithms are base 2 in t h i s t h e s i s . -k -1 + R + 1/n log(1-2 ) > 1/n log(Ad) - h(d/n) (6.c) Rearranging to the f i n a l form of the VG1 bound, (6.d). -k R £ 1 - h(d/n) + 1/n log(Ad/(1-2 )) (6.d) -k It i s seen that by setting Ad to one and dropping the 2 term, the la s t term of the VG1 bound i s zero and the V-G bound i s obtained. The V-G bound referred to hereafter as the VGO bound i s thus a weaker bound than the VG1 bound. The rest of the bounds in the family require a s l i g h t l y d i f f e r e n t derivation so that the VG2 bound i s now derived before the general bound expression i s given. Ar i s taken to be the next highest non-zero weight term above Ad. 10 -n k -k d n-d r n-r 2 2(1-2 ) > Ad(d/n) (1-d/n) + Ar(d/n) (1-d/n) (7.a) The RHS i s now factored below. d n-d r-d RHS=Ad(d/n) (1-d/n) {1 + Ar/Ad(d/(n-d)) } (7.b) As before the nth roots and then logarithms are taken of both sides, with a rearrangement giving the VG2 bound, (7.c). -k R > 1 - h(d/n) + 1/n log(Ad/(l-2 )) r-d + 1/n l o g d + Ar/Ad(d/(n-d)) ) (7.c) The general bound expression i s now given u t i l i z i n g a l l the weight terms of the primal code. -k R £ 1 - h(d/n) + 1/n log(Ad/(l-2 )) n i-d + 1/n l o g d + Ad" 1 T Ai(d/(n-d)) ) (8) i=d+1 A l l the bounds of the family are v a l i d only over the range 0 £ d/n £ 1/2 because e was r e s t r i c t e d to the same range in section 1.2 . Note that even i f a l l the {Ai} are used in (8), the test i s not d e f i n i t i v e since the test involves examination of P(e) only at e=d/n. Some codes might be improper at values of e not including e=d/n. 11 2.3 DETERMINING IMPROPER CODES USING THE VGO BOUND The VGO bound can be used to c l a s s i f y some codes as improper by only considering the parameters p, d and k. By f i x i n g p to a certain value, pO, and setting k to one i t was possible to fi n d the maximum d=dmax that produces an improper code for pO. Then for pO, each d ^ dmax was examined with respect to a range of k that produced an improper code. Table I shows the res u l t s of these cal c u l a t i o n s for a l l p ^ 18. 2.4 COMPARISON OF THE FAMILY OF TESTS FOR IMPROPER CODES In t h i s section i s a comparison of the effectiveness of the family of tests used to determine i f a code i s improper. It i s shown that there i s a clear benefit in using the successive bounds in the family when the relevant {Ai} are known. In many cases i t i s easy to calculate Ad and therefore, the VG1 bound should be used because of i t s s i g n i f i c a n t improvement over the simple VGO bound. The codes examined are known to be improper for various codeword lengths. 2.4.1 BCH(63,24) Code This code i s shown to be improper in [5]. The parameters of the code, k=24, n=63, p=39 and d=l5, are used in the VGO bound (9). R=24/63=0.380952381 > 0.2081416474=1 - h(!5/63) (9) 1 2 p d kO P d kO 4 1 3 1 4 3 16 5 1 8 14 4 5 6 1 19 1 4 5 2 7 1 41 1 5 1 1 2041 7 2 3 1 5 2 120 8 1 87 15 3 22 8 2 5 15 4 7 9 1 180 15 5 3 9 2 9 16 1 24094 9 3 2 1 6 2 174 10 1 368 16 3 31 10 2 15 16 4 10 10 3 3 16 5 4 11 1 743 16 6 2 1 1 2 24 17 1 48203 1 1 3 5 17 2 251 12 1 1496 17 3 41 12 2 37 17 4 14 12 3 8 17 5 5 12 4 2 17 6 2 13 1 3002 18 1 96420 13 2 55 18 2 360 13 3 1 1 18 3 55 13 4 4 18 4 18 14 1 6014 18 5 7 14 2 82 18 6 3 Table I - L i s t of Improper Codes for p, d and k < kO. 1 3 Using Ad=65l, [32], the VG1 bound (6.d) can be evaluated to obtain R=0.380952381 > 0.356499096 (10) Both (9) and (10) are s a t i s f i e d , but the code i s known to be improper. Use of the additional terms, A16=1953, A17=3024, A18=7728, A21=74448, A22=142128, [32], in (8) i s necessary to show that the code i s improper, as indicated below. R=0.380952381 < 0.3810652147 (11) 2.4.2 Square SPCP Codes In [2] i t i s shown that single parity-check product (SPCP) codes of size (m«m) are improper for m > 5. The parameters of the code, k=(m-l) 2, n=m2, p=2m-1 and d=4, are used in the VGO bound (12) below. (m-1)2/m2 ^ 1 - h(4/m2) (12) It i s not v a l i d to use the bound (12) for m=2, but a l l greater values of m can be considered. Table II shows the calculated values for the bound over 3 £ m < 50. It i s observed that the VGO bound i s vi o l a t e d for m £ 15. This implies that square SPCP codes of size 225 or larger are improper. Now consider the VG1 bound using the additional term containing Ad. For t h i s code, Ad=A4 i s calculated as follows. 14 m k n Ad Code Rate VGO Bound VG1 Bound 3 4 9 9 0 .4444444 0. 0089244 0. 3714837 4 9 16 36 0 .5625000 0. 1887224 0. 5120189 5 16 25 100 0 .6400000 0. 3656913 0. 6314464 6 25 36 225 0 .6944444 0. 4967430 0. 7137924 7 36 49 441 0 .7346938 0. 5920953 0. 7713735 8 49 64 784 0 .7656250 0. 6627102 0. 8129401 9 64 81 1296 0 .7901234 0. 7162318 0. 8438843 10 81 100 2025 0 .8099999 0. 7577088 0. 8675458 1 1 1 00 121 3025 0 .8264462 0. 7904989 0. 8860585 1 2 121 1 44 4356 0 .8402777 0. 8168785 0. 9008284 13 144 169 6084 0 .8520710 0. 8384308 0. 9128142 14 169 196 8281 0 .8622448 0. 8562744 0. 9226804 15 196 225 1 1025 0 .87111 1 1 0. 8712265 0. 9309087 16 225 256 14400 0 .8789063 0. 8838851 0. 9378451 17 256 289 18496 0 .8858131 0. 8947059 0. 9437541 18 289 324 23409 0 .8919753 0. 9040299 0. 9488286 19 324 361 29241 0 .8975069 0. 9121282 0. 9532242 20 361 400 36100 0 .9025000 0. 9192078 0. 9570571 21 400 441 44100 0 .9070294 0. 9254366 0. 9604218 22 441 484 53361 0 .9111570 0. 9309459 0. 9633911 23 484 529 64009 0 .9149338 0. 9358464 0. 9660278 24 529 576 76176 0 .9184027 0. 9402260 0. 9683806 25 576 625 90000 0 .9216000 0. 9441552 0. 9704874 26 625 676 105625 0 .9245562 0. 9476972 0. 9723845 27 676 729 123201 0 .9272977 0. 9509003 0. 9740973 28 729 784 142884 0 .9298469 0. 9538081 0. 9756505 29 784 841 164836 0 .9322235 0. 9564558 0. 9770629 30 841 900 189225 0 .9344444 0. 9588746 0. 9783521 31 900 961 216225 0 .9365245 0. 9610913 0. 9795327 32 961 1024 246016 0 .9384766 0. 9631256 0. 9806142 33 1024 1089 278784 0 .9403122 0. 9650007 0. 9816112 34 1089 1 156 314721 0 .9420415 0. 9667310 0. 9825300 35 1 156 1225 354025 0 .9436734 0. 9683303 0. 9833781 36 1225 1296 396900 0 .9452160 0. 9698144 0. 9841650 37 1296 1369 443556 0 .9466764 0. 9711932 0. 9848957 38 1369 1444 494209 0 .9480609 0. 9724759 0. 9855748 39 1444 1521 549081 0 .9493754 0. 9736722 0. 9862078 40 1521 1600 608400 0 .9506249 0. 9747882 0. 9867973 41 1600 1681 672400 0 .9518144 0. 9758334 0. 9873497 42 1681 1764 741321 0 .9529478 0. 9768127 0. 9878669 43 1764 1849 815409 0 .9540292 0. 9777319 0. 9883523 44 1849 1936 894916 0 .9550620 0. 9785963 0. 9888088 45 1936 2025 980100 0 .9560494 0. 9794080 0. 9892364 46 2025 21 16 1071225 0 .9569943 0. 9801744 0. 9896407 47 21 16 2209 1168561 0 .9578995 0. 9808956 0. 9900202 48 2209 2304 1272384 0 .9587674 0. 9815784 0. 9903800 49 2304 2401 1382976 0 .9596002 0. 9822237 0. 9907199 50 2401 2500 1500625 0 .9604000 0. 9828338 0. 9910406 Table II - Square SPCP Codes: VGO and VG1 Bound Values. 15 A4 = (m choose 2 ) 2 = m2(m-1)2/4 = n*k/4 Thus the VG1 bound (13) i s shown below. -k (m-l) 2/m 2 > 1 - h(4/m2) + log(n*k/4*(1-2 ))/m2 (13) Table II also shows the VG1 bound values for 3 < m < 15. Now i t i s seen that square SPCP codes of size m £ 6 are improper. To show that the code i s improper for m=5, the A5 term i s zero so the A6 term w i l l be calculated as follows. The VG2 bound (14) i s violated, confirming that square SPCP codes are improper for m > 4. 2.4.3 CRC Codes These codes are more f u l l y examined in chapter three. It w i l l be shown that the codes are improper for some values of k depending on the generator polynomial that i s used. The CRC class i s in fact asymptotically proper. For reference purposes, computer programs were written to obtain the P(e) d i s t r i b u t i o n for three CRC standards. The three standard CRC generator polynomials are l i s t e d below. A6=2(m choose 2)(m choose 3)(m-2)=2(10)(10)(3)=600 R=0.64 < 0.6428121 (14) 16 CRC-12 g(x)=1+x+x 2+x 3+x 1'+x 1 2 CRC-ANSI g(x)=1+x 2+x 1 5+x 1 6 CRC-CCITT g(x)=1+x 5+x 1 2+x 1 6 For each CRC standard, P(e) was examined over 2 ^ k < 50. The method used was that of c a l c u l a t i n g the weight d i s t r i b u t i o n , B(x), of the dual code from the systematic code generator matrix. Then equation (5) allowed c a l c u l a t i o n of P(e). Using the systematic matrix to represent the code s i m p l i f i e d the calculations greatly because the matrix size could be reduced from (k*n) to (k»p). The i d e n t i t y portion of the matrix did not have to be stored. It should be stressed that using the dual code to cal c u l a t e P(e) d i f f e r s from the usual method of k c a l c u l a t i n g a l l the possible 2 codewords of the primal code. Since p i s constant, using the dual code affords an easy P c a l c u l a t i o n of only 2 codewords for any k. For each value of k and each CRC polynomial i t was observed that by p l o t t i n g over the entire range there existed only one maximum P(e*) at e*. Therefore, a program was written to find P(e*) such that e* was within 0.0001. Tables I I I , IV and V show the P(e*) and e* values for each CRC polynomial over 2 ^ k £ 50. From these tables i t can be c l e a r l y seen that none of these standard CRC polynomials w i l l produce proper codes over the range 2 £ k £ 50. For use in c a l c u l a t i n g the VG1 bound, the Ad=A4 term was calculated for each code. Since the systematic code generator matrix, G, of each CRC contains an identity portion, only the remainder portion had to be examined. When x number of rows of G are added, the weight w i l l be at least x 17 k e* P(e*) 2 0.3333 0.321139435E-03 3 0.3075 0.444029955E-03 4 0.2915 0.497216784E-03 5 0.2777 0.507702964E-03 6 0.2647 0.498239403E-03 7 0.2517 0.471908937E-03 8 0.2391 0.437709580E-03 9 0.2264 0.444429281E-03 10 0.2148 0.434696788E-03 1 1 0.2026 0.474829312E-03 12 0.1931 0.492904790E-03 1 3 0.1846 0.515872186E-03 14 0.1772 0.522761450E-03 15 0.1702 0.532493516E-03 .16 0.1641 0.532168354E-03 17 0.1587 0.525552797E-03 18 0.1539 0.524102890E-03 19 0.1494 0.516139585E-03 20 0.1451 0.511365042E-03 21 0.1409 0.501021240E-03 22 0.1367 0.502705835E-03 23 0.1326 0.498250569E-03 24 0.1290 0.495408412E-03 25 0.1255 0.488145251E-03 26 0.1224 0.479257173E-03 27 0.1196 0.468967487E-03 28 0.1169 0.457258208E-03 29 0.1145 0.447772634E-03 30 0.1121 0.436575324E-03 31 0.1100 0.427552495E-03 32 0.1078 0.416986323E-03 33 0.1057 0.413106268E-03 34 0.1038 0.407554148E-03 35 0.1019 0.403060253E-03 36 0.1002 0.398553616E-03 37 0.0986 0.394649259E-03 38 0.0971 0.389937352E-03 39 0.0957 0.384785637E-03 40 0.0944 0.379043787E-03 41 0.0931 0.373512956E-03 42 0.0919 0.368207383E-03 43 0.0907 0.362499709E-03 44 0.0896 0.357807948E-03 45 0.0884 0.353279445E-03 46 0.0874 0.348489916E-03 47 0.0863 0.344934396E-03 48 0.0853 0.340974622E-03 49 0.0844 0.336815351E-03 50 0.0836 0.332276709E-03 Table III - CRC-12: P(e*) {2 £ k < 50};2" 1 2 =2.44140625E-04. 18 k e* P(e*) 2 0.2268 0. 150654029E-03 3 0.2207 0. 187078647E-03 4 0.2135 0. 205152042E-03 5 0.2061 0. 21 1267765E-03 6 0.1985 0. 209564372E-03 7 0.1910 0. 203059640E-03 8 0.1836 0. 193778075E-03 9 0.1766 0. 183061878E-03 10 0.1700 0. 171779543E-03 1 1 0.1636 0. 160479803E-03 12 0.1577 0. 149497882E-03 13 0.1521 0. 139028102E-03 14 0.1464 0. 137334592E-03 15 0.1409 0. 149435544E-03 16 0.1359 0. 163272940E-03 17 0.1314 0. 177705194E-03 18 0. 1275 0. 187672767E-03 19 0.1240 0. 193737685E-03 20 0.1206 0. 196620564E-03 21 0.1174 0. 196955688E-03 22 0.1143 0. 195326371E-03 23 0.1113 0. 192244023E-03 24 0.1084 0. 188110195E-03 25 0.1057 0. 183237937E-03 26 0.1030 0. 177894848E-03 27 0. 1005 0. 172350345E-03 28 0.0982 0. 168454993E-03 29 0.0960 0. 165783465E-03 30 0.0938 0. 166609101E-03 31 0.0917 0. 167837432E-03 32 0.0899 0. 168211020E-03 33 0.0881 0. 167740334E-03 34 0.0864 0. 166476378E-03 35 0.0847 0. 164509852E-03 36 0.0831 0. 161975108E-03 37 0.0814 0. 159000560E-03 38 0.0799 0. 155695118E-03 39 0.0783 0. 152149695E-03 40 0.0769 0. 148455870E-03 41 0.0754 0. 144679145E-03 42 0.0741 0. 140940754E-03 43 0.0728 0. 137754443E-03 44 0.0716 0. 135077161E-03 45 0.0704 0. 134157900E-03 46 0.0694 0. 133429372E-03 47 0 . 0 6 8 3 0. 132810889E-03 48 0.0673 0. 131913843E-03 49 0.0663 0. 131053719E-03 50 0.0654 0. 129915008E-03 Table IV - CRC-ANSI: P(e*) {2 < k < 50};2'16=1.52587891E-04. 9 k e* P(e*) 2 0. 2230 0. 145082327E-03 3 0. 21 16 0. 170857760E-03 4 0. 2012 0. 181218248E-03 5 0. 1 927 0. 184317981E-03 6 0. 1853 0. 182571298E-03 7 0. 1778 0. 17636611 0E-03 8 0. 1712 0. 168755027E-03 9 0. 1648 0. 159587268E-03 10 0. 1587 0. 149835850E-03 1 1 0. 1528 0.140004555E-03 12 0. 1477 0.131108736E-03 13 0. 1432 0.122962603E-03 14 0. 1388 0.114947191E-03 15 0. 1345 0. 107280791E-03 16 0. 1304 0. 100034176E-03 17 0. 1266 0.988955214E-04 18 0. 1230 0.968045141E-04 19 0. 1 195 0.941654920E-04 20 0. 1 1 62 0.911743047E-04 21 0. 1 132 0.880828071E-04 22 0. 1 103 0.848346025E-04 23 0. 1076 0.815235041E-04 24 0. 1050 0.782445308E-04 25 0. 1026 0.750797172E-04; 26 0. 1003 0.719221628E-04 27 0. 0981 0.689410139E-04 28 0. 0961 0.660500281E-04 29 0. 0941 0.632355828E-04 30 0. 0922 0.605393376E-04 31 0. 0904 0.580094120E-04 32 0. 0887 0.555637826E-04 33 0. 0871 0.532930357E-04 34 0. 0856 0.511186757E-04 35 0. 0841 0.490669673E-04 36 0. 0827 0.471277254E-04 37 0. 0814 0.452710702E-04 38 0. 0802 0.435295404E-04 39 0. 0790 0.418904365E-04 40 0. 0778 0.403147068E-04 41 0. 0768 0.388405621E-04 42 0. 0758 0.374421915E-04 43 0. 0748 0.361386336E-04 44 0. 0739 0.348991385E-04 45 0. 0729 0.341087714E-04 46 0. 0720 0.333221165E-04 47 0. 071 1 0.325496262E-04 48 0. 0703 0.317809110E-04 49 0. 0693 0.313366181E-04 50 0. 0685 0.308847539E-04 Table V - CRC-CCITT: P(e*) {2 <, k £ 50} ; 2 ' 1 6 = 1 .52587891E-04. 20 because of the i d e n t i t y portion of G. Therefore, only combinations of one, two, three and four rows of the p-bit remainder portion of G had to be examined. This allowed the determination of A4 without c a l c u l a t i n g the entire primal weight 4 d i s t r i b u t i o n for each k. This method uses only Y (k choose i) k i = 1 operations considerably less than the 2 operations required to calculate the entire weight d i s t r i b u t i o n . For k=50, only 251175 operations were performed as opposed to 2 5 0 > 10 1 5 operations. (i) CRC-12 Standard Table VI shows the VGO bound and the VG1 bound values for the CRC-12 polynomial over 2 £ k < 50. For a l l the given k values, the VGO bound i s s a t i s f i e d implying nothing can be said about the code. However, the VG1 bound i s violated for 2 < k < 46 such that the code i s determined to be improper for these k values. Thus, even the VG1 bound i s not strong enough to confirm the code to be improper for a l l the k values. It can be observed in table III that the P(e*) values decrease with increasing k suggesting that the code could become proper for larger k. The CRC-12 polynomial was a c t u a l l y examined over the range 2 ^ k ^ 250 for P(e*) values. The codes were found to be improper for k < 172 and proper for 172 < k £ 250. It is suspected that for k > 250 the codes w i l l remain proper. ( i i ) CRC-ANSI Standard The CRC-ANSI code VGO and VG1 bound values are presented in table VII. The VGO bound i s s a t i s f i e d for a l l values of k 21 k n Ad Code Rate VGO Bound VG1 Bound 2 1 4 1 0. 1428571 0. 1368795 0. 1665250 3 15 2 0. 2000000 0. 1633593 0. 2428690 4 16 3 0. 2500000 0. 1887219 0. 2936014 5 17 4 0. 2941176 0. 2128734 0. 3332148 6 18 5 0. 3333333 0. 2357955 0. 3660537 7 19 6 0. 3684210 0. 2575125 0. 3941587 8 20 7 0. 4000000 0. 2780719 0. 4187220 9 21 9 0. 4285714 0. 2975335 0. 4486166 10 22 1 1 0. 4545454 0. 3159617 0. 4732726 1 1 23 15 0. 4782608 0. 3334217 0. 5033172 12 24 19 0. 5000000 0. 3499777 0. 5269893 13 25 24 0. 5200000 0. 3656905 0. 5490961 14 26 29 0. 5384615 0. 3806178 0. 5674666 15 27 35 0. 5555555 0. 3948135 0. 5847886 16 28 41 0. 5714285 0. 4083272 0. 5996692 17 29 47 0. 5862069 0. 4212055 0. 6127434 18 30 54 0. 6000000 0. 4334905 0. 6253203 19 31 61 0. 6129032 0. 4452218 0. 6365360 20 32 69 0. 6250000 0. 4564356 0. 6473270 21 33 77 0. 6363636 0. 4671651 0. 6570677 22 34 88 0. 6470588 0. 4774406 0. 6674239 23 35 99 0. 6571428 0. 4872909 0. 6767011 24 36 1 1 1 0. 6666666 0. 4967417 0. 6854755 25 37 123 0. 6756756 0. 5058171 0. 6934526 26 38 135 0. 6842105 0. 5145394 0. 7007714 27 39 147 0. 6923077 0. 5229287 0. 7075357 28 40 159 0. 7000000 0. 5310045 0. 7138266 29 41 172 0. 7073171 0. 5387841 0. 7199125 30 42 185 0. 7142857 0. 5462837 0. 7256023 31 43 199 0. 7209302 0. 5535187 0. 7311146 32 44 213 0. 7272727 0. 5605031 0. 7362920 33 45 231 0. 7333333 0. 5672499 0. 7417332 34 46 249 0. 7391304 0. 5737714 0. 7468149 35 47 268 0. 7446808 0. 5800789 0. 7516979 36 48 288 0. 7500000 0. 5861832 0. 7563900 37 49 309 0. 7551020 0. 5920942 0. 7608995 38 50 330 0. 7600000 0. 5978209 0. 7651473 39 51 351 0. 7647058 0. 6033722 0. 7691630 40 52 372 0. 7692307 0. 6087565 0. 7729710 41 53 394 0. 7735849 0. 6139813 0. 7766615 42 54 417 0. 7777777 0. 6190536 0. 7802370 43 55 440 0. 7818182 0. 6239802 0. 7836413 44 56 465 0. 7857143 0. 6287678 0. 7870015 45 57 491 0. 7894737 0. 6334221 0. 7902568 46 58 517 0. 7931034 0. 6379488 0. 7933630 47 59 546 0.7966101 0. 6423534 0. 7964679 48 60 575 0. 8000000 0. 6466407 0. 7994310 49 61 604 0. 8032787 0. 6508157 0. 8022650 50 62 633 0. 8064516 0. 6548827 0. 8049805 Table VI - CRC-12: VGO and VG1 Bound Values. 22 k n Ad Code Rate VGO Bound VG1 Bound 2 18 2 0. 1111111 0. 2357955 0. 3144087 3 19 3 0. 1578947 0. 2575125 0. 3510708 4 20 4 0. 2000000 0. 2780719 0. 3827274 5 21 5 0. 2380952 0. 2975335 0. 4102826 6 22 6 0. 2727273 0. 3159617 0. 4344927 7 23 7 0. 3043478 0. 3334217 0. 4559726 8 24 8 0. 3333333 0. 3499777 0. 4752129 9 25 9 0. 3600000 0. 3656905 0. 4926003 10 26 10 0. 3846154 0. 3806178 0. 5084385 1 1 27 1 1 0. 4074074 0. 3948135 0. 5229667 1 2 28 12 0. 4285714 0. 4083272 0. 5363742 1 3 29 13 0. 4482758 0. 4212055 0. 5488129 14 30 15 0. 4666666 0. 4334905 0. 5637231 15 31 19 0. 4838709 0. 4452218 0. 5822532 1 6 32 24 0. 5000000 0. 4564356 0. 5997163 1 7 33 30 0. 5151515 0. 4671651 0. 6158591 18 34 36 0. 5294117 0. 4774406 0. 6294974 19 35 42 0. 5428571 0. 4872909 0. 6413572 20 36 48 0. 5555555 0. 4967417 0. 6518796 21 37 54 0. 5675675 0. 5058171 0. 6613546 22 38 60 0. 5789474 0. 5145394 0. 6699839 23 39 66 0. 5897436 0. 5229287 0. 6779132 24 40 72 0. 6000000 0. 5310045 0. 6852526 25 41 78 0. 6097561 0. 5387841 0. 6920866 26 42 84 0. 6190476 0. 5462837 0. 6984817 27 43 90 0. 6279069 0. 5535187 0. 7044920 28 44 97 0. 6363636 0. 5605031 0. 7105011 29 45 105 0. 6444444 0. 5672499 0. 7164553 30 46 116 0. 6521739 0. 5737714 0. 7228580 31 47 128 0. 6595744 0. 5800789 0. 7290151 32 48 140 0. 6666666 0. 5861832 0. 7347099 33 49 152 0. 6734694 0. 5920942 0. 7400110 34 50 164 0. 6799999 0. 5978209 0. 7449719 35 51 176 0. 6862745 0. 6033722 0. 7496356 36 52 188 0. 6923077 0. 6087565 0. 7540370 37 53 200 0. 6981132 0. 6139813 0. 7582050 38 54 212 0. 7037037 0. 6190536 0. 7621632 39 55 224 0. 7090909 0. 6239802 0. 7659321 40 56 236 0. 7142857 0. 6287678 0. 7695293 41 57 248 0. 7192982 0. 6334221 0. 7729694 42 58 260 0. 7241379 0. 6379488 0. 7762655 43 59 273 0. 7288135 0. 6423534 0. 7795188 44 60 287 0. 7333333 0. 6466407 0. 7827225 45 61 305 0. 7377049 0. 6508157 0. 7861053 46 62 324 0. 7419354 0. 6548827 0. 7893964 47 63 344 0. 7460317 0. 6588461 0. 7925964 48 64 364 0. 7500000 0. 6627099 0. 7956442 49 65 385 0. 7538461 0. 6664780 0. 7986121 50 66 406 0. 7575758 0. 6701539 0. 8014469 Table VII - CRC-ANSI: VGO and VG1 Bound Values. 23 greater than nine. This implies the code to be improper for 2 < k < 9. The VGO bound i s c l e a r l y too loose. However, the VG1 bound i s not s a t i s f i e d for a l l given k values thus confirming the fact that the code i s improper for a l l these k values. ( i i i ) CRC-CCITT Standard Shown in table VIII are the VGO bound and VG1 bound values. Again the VGO bound is s a t i s f i e d for 10 ^ k ^ 50 since t h i s code has sixteen parity b i t s as in the CRC-ANSI standard code. Thus the CRC-CCITT code would seem to be improper only for 2 £ k < 9. The VG1 bound, however, i s v i o l a t e d for a l l the given k values thus showing the code to be improper for a l l these k values as can be seen from table V. In examining the CRC class a general expression for the VGO bound can be written as (15) using p the number of parity b i t s . k/n=(n-p)/n £ 1 - h(d/n) (15) Re-arranging (15) to a more convenient form gives (16). p/n < h(d/n) (16) It can be shown that i f (16) i s s a t i s f i e d for any n=n0 then since the LHS of (16) i s linear with respect to 1/n and the RHS is concave down, a l l values of n greater than nO w i l l s a t i s f y the bound (16). For a fixed p, the CRC class has many possible generator polynomials each of which could be improper at 24 k n Ad Code Rate VGO Bound VG1 Bound 2 18 2 0 .1111111 0. 2357955 0. 3144087 3 19 3 0 . 1578947 0. 2575125 0. 3510708 4 20 4 0 .2000000 0. 2780719 0. 3827274 5 21 5 0 .2380952 0. 2975335 0. 4102826 6 22 6 0 .2727273 0. 3159617 0. 4344927 7 23 7 0 .3043478 0. 3334217 0. 4559726 8 24 8 0 .3333333 0. 3499777 0. 4752129 9 25 9 0 .3600000 0. 3656905 0. 4926003 10 26 10 0 .3846154 0. 3806178 0. 5084385 1 1 27 1 1 0 .4074074 0. 3948135 0. 5229667 12 28 12 0 .4285714 0. 4083272 0. 5363742 13 29 13 0 .4482758 0. 4212055 0. 5488129 14 30 14 0 .4666666 0. 4334905 0. 5604053 15 31 15 0 .4838709 0. 4452218 0. 5712520 16 32 16 0 .5000000 0. 4564356 0. 5814362 17 33 18 0 .5151515 0. 4671651 0. 5935268 18 . 34 20 0 .5294117 0. 4774406 0. 6045563 19 35 22 0 .5428571 0. 4872909 0. 6147033 20 36 24 0 .5555555 0. 4967417 0. 6241018 21 37 26 0 .5675675 0. 5058171 0. 6328560 22 38 28 0 .5789474 0. 5145394 0. 6410487 23 39 30 0 .5897436 0. 5229287 0. 6487464 24 40 32 0 .6000000 0. 5310045 0. 6560045 25 41 34 0 .6097561 0. 5387841 0. 6628685 26 42 36 0 .6190476 0. 5462837 0. 6693771 27 43 38 0 .6279069 0. 5535187 0. 6755635 28 44 40 0 .6363636 0. 5605031 0. 6814560 29 45 42 0 .6444444 0. 5672499 0. 6870791 30 46 44 0 .6521739 0. 5737714 0. 6924547 31 47 46 0 .6595744 0. 5800789 0. 6976015 32 48 48 0 .6666666 0. 5861832 0. 7025366 33 49 50 0 .6734694 0. 5920942 0. 7072749 34 50 52 0 .6799999 0. 5978209 0. 71 18297 35 51 54 0 .6862745 0. 6033722 0. 7162132 36 52 56 0 .6923077 0. 6087565 0. 7204364 37 53 58 0 .6981132 0. 6139813 0. 7245093 38 54 60 0 .7037037 0. 6190536 0. 7284404 39 55 62 0 .7090909 0. 6239802 0. 7322383 40 56 64 0 .7142857 0. 6287678 0. 7359107 41 57 66 0 .7192982 0. 6334221 0. 7394641 42 58 68 0 .7241379 0. 6379488 0. 7429051 43 59 70 0 .7288135 0. 6423534 0. 7462395 44 60 72 0 .7333333 0. 6466407 0. 7494728 45 61 75 0 .7377049 0. 6508157 0. 7529275 46 62 78 0 .7419354 0. 6548827 0. 7562601 47 63 81 0 .7460317 0. 6588461 0. 7594787 48 64 84 0 .7500000 0. 6627099 0. 7625899 49 65 88 0 .7538461 0. 6664780 0. 7658539 50 66 92 0 .7575758 0. 6701539 0. 7689958 Table VIII - CRC-CCITT: VGO and VG1 Bound Values. 25 d i f f e r e n t values of k. However, the VGO bound gives the same result regardless of the p a r t i c u l a r g(x) used for a given p. When the g(x) i s known, the Ad term could be computed using the method discussed e a r l i e r in t h i s section. In t h i s case, the VG1 bound could be used to give a clearer indication of the values of k which would result in an improper code. 26 3. CRC CLASS PROPERTIES 3.1 BRIEF DESCRIPTION Each CRC i s represented by i t s generator polynomial, g(x). Polynomial codes treat b i t strings as representations of polynomials with binary c o e f f i c i e n t s only. The polynomial arithmetic i s ca r r i e d out by modulo 2 arithmetic which is equivalent to exclusive-or operations. The highest degree term P of g(x) i s x which implies the CRC has p parity b i t s . Note that P g(x) must contain the terms 1 and x . Otherwise, g(x) and a l l the codewords would be d i v i s i b l e by x such that a p a r t i c u l a r b i t of each codeword i s i d e n t i c a l l y zero. The block length can be r chosen as any n, but only when n=r and g(x) divides (x +1) i s the CRC a true c y c l i c code. Depending on n w i l l also be the error detection c a p a b i l i t i e s of the code as discussed in a l a t e r section. The CRC i s , however, generated the same as a true c y c l i c code by using the c y c l i c code generator matrix. Not every codeword of the CRC i s a c i r c u l a r s h i f t of another codeword as is the case for a true c y c l i c code. More detailed descriptions of true c y c l i c codes as well as the CRC class are given in [9], [10], [13], [19] and [20]. The CRC class i s one of the most commonly used error detection codes because of i t s easy c y c l i c generating structure and i t s simple implementation using s h i f t r e g i s t e r s , [15]-[21] and [27]. 27 3.2 P(e) BEHAVIOUR In many communication systems the p r o b a b i l i t y of undetected error, P(e), i s a very important parameter. An example i s that of a banking network concerning the c r e d i t i n g of a c l i e n t ' s account. If P(e) i s high enough to allow the error of c r e d i t i n g an account with two thousand d o l l a r s when only two d o l l a r s should be credited, then serious problems would a r i s e . Therefore, codes are much more e f f e c t i v e for error detection i f their P(e) i s very low. The asymptotic behaviour of P(e) can be used to i l l u s t r a t e the strength of a certai n code c l a s s . P(e) of the CRC class i s now considered for the BSC with 0 < e < 1/2. Theorem 1; For a fixed value of p, as k increases, P(e) of the CRC class as defined e a r l i e r approaches 2 Proof: Consider the dual code expression for P(e), (4). The three cases: e=0, e=1/2 and 0 < e < 1/2 w i l l be treated separately. Note that k becoming i n f i n i t e implies n does also. -p n -p p (i) e=0 P(0)=2 B(1) - (1) =2 2 - 1=0 -p n -p ( i i ) e=1/2 lim{P(1/2)}=2 B(0) - lim{(l/2) }=2 n->co n->co ( i i i ) 0 < e < 1/2 <=> 0 < 1-2e < 1 <=> 1/2 < 1-e < 1 -p n lim{P(e)}=lim{2 B(1-2e)} - lim{(1-e) } n->co n->oo n->co 28 "P =2 lim{B(1-2e)} n->co Define: minimum Hamming distance of dual code =s -p n i = 2 lim{ 1 + Y. B i ( 1 _ 2 e ) } n->co i=s -p n i = 2 + lim{ £ Bi(l-2e) } n->coi=s In order for the second term to vanish, we need to show that s increases without bound as n increases. The generator matrix of the dual code, H, i s composed of a (p«p) identity portion, Ip, and k columns of p-bit remainders i d e n t i f i e d as Hr. For s to increase with increasing k, no combination of the rows of Hr can add to a zero row. Otherwise, s would be equal to the number of rows of Hr that were added to produce the zero row. With increasing k, the remainders w i l l eventually repeat and i f no zero row i s obtained by adding rows of Hr, s w i l l also increase. Therefore, i t must be shown that the rows of Hr are l i n e a r l y independent. It i s s u f f i c i e n t to show that in any section of Hr the rows are l i n e a r l y independent. A square matrix, P, i s formed by taking the f i r s t p b i t s of the rows of Hr. Since P i s square, i t i s s u f f i c i e n t to show that the columns are l i n e a r l y independent. These p columns are the f i r s t p remainders: p p+1 2p-1 x mod g(x), x mod g(x), x mod g(x). Therefore, the following equation (17) in mod g(x) arithmetic can be examined. p p+1 2p-1 a x + a x +...+a x =0 mod g(x) (17) 0 1 p-1 29 If the p remainders are l i n e a r l y independent, then the c o e f f i c i e n t s of the LHS of (17) must a l l be zero. Since x does not divide g(x), from section 3.1, both sides of (17) are P divided by x to obtain (18). p-1 a + a x + . . . + a x =0 mod g(x) (18) 0 1 p-1 Since the LHS i s of degree (p-1) < p, a l l the c o e f f i c i e n t s are zero and therefore, the remainders are l i n e a r l y independent. Q.E.D. 3.3 DETECTION CAPABILITIES OF THE CRC CLASS Many authors have c l a s s i f i e d error detection codes according to their a b i l i t i e s to detect a certain number or pattern of errors instead of their r e l a t i v e P(e). The detection c a p a b i l i t i e s of the CRC class are given as a contrast to P(e). A certain subclass of the CRC class i s shown to be able to detect a l l odd weight errors. Therefore, t h i s subclass detects at least half of a l l the errors. The error pattern w i l l be represented by an error polynomial denoted by E(x). If g(x) does not divide E(x) then the error represented by E(x) can be detected. Property 1; A generator polynomial, g(x), with at least two terms w i l l allow the generated CRC to detect a l l single errors. i Proof: For a single error in the i t h b i t po s i t i o n , E(x)=x . A necessary condition to assure the detection of single errors i s i that g(x) not divide x . This i s s a t i s f i e d by any g(x) with more 30 P i than one term. A simple example i s that (1+x ) cannot divide x for any i . Q.E.D. De f i n i t i o n : The exponent, r, of a polynomial f(x) i s the least r p o s i t i v e integer such that f(x) divides (x +1), [8]. Fact: A primitive polynomial of degree m w i l l have an exponent m of 2 -1 which i s the maximum exponent for any polynomial of degree m, [20]. A primitive polynomial i s ir r e d u c i b l e and tables are available in [20]. Fact: An irre d u c i b l e polynomial of degree m w i l l have an m exponent that i s a factor of 2 -1, [21]. The generally accepted, [21], method to f i n d the exponent of a polynomial, f ( x ) , i s to factor f(x) into irreducible polynomials. The exponent of each irreducible factor can be found using the previous f a c t s . Then the exponent of f(x) i s calculated as the least common multiple of a l l the exponents of the factors, [21]. To f i n d the exponent of a non-primitive irr e d u c i b l e polynomial a l l the factors of the maximum exponent must be examined. However, there are mathematical functions that state how many irreducible polynomials have a certa i n exponent although the identity of the polynomials must be found separately, [21]. It must also be noted that factoring a polynomial i s usually not t r i v i a l . Therefore, a simple computational method for finding the exponent of g(x) i s presented. This method involves the easy c a l c u l a t i o n of the 31 remainder portion of the systematic code generator matrix. Successive remainders are calculated u n t i l one i s found to be i d e n t i c a l to the f i r s t remainder. The number of d i s t i n c t remainders i s equal to the exponent of the generator polynomial. By finding the exponent, r, a true c y c l i c (r,k) code can be constructed. As w i l l be shown in property two, the a b i l i t y of a CRC to detect a l l double errors w i l l depend on the exponent of g(x). The exponent w i l l also be used in the following section to examine the construction of a proper code g(x). The basis for ca l c u l a t i n g the exponent i s given in the following theorem. Theorem 2: The (r+l)st remainder, l ( x ) , generated for the remainder portion of the systematic code generator matrix, G, i s equal to the f i r s t remainder, m(x). Proof: Three equations in mod g(x) arithmetic can be written, r (i) x =h(x)g(x)+1 P ( i i ) x =h1 (x)g(x) .+ m(x) p+r ( i i i ) x =h2(x)g(x) + l(x) To show that m(x)=l(x), we simply form the product of equations (i) and ( i i ) , and then equate to ( i i i ) . p+r (i)»(ii)=x ={h(x)g(x) + 1}{h1(x)g(x) +m(x)} =h(x)h1(x)g(x) + h1(x)g(x) + m(x)h(x)g(x) + m(x) =h3(x)g(x) + m(x) (i)»(ii)=(iii)=h2(x)g(x) + l(x)=h3(x)g(x) + m(x) Therefore, m(x)=l(x). Q.E.D. 32 From the above theorem i t i s e a s i l y seen that i f k > r the minimum distance of the primal code i s two. Also, when k > r-p for some g(x), the minimum distance could be two because the p-1 sequence of remainders would contain 1, x, x . Thus the minimum distance asymptotically approaches two for the CRC cl a s s . Property 2: A CRC of blocklength n ^ r where r i s the exponent of g(x), can detect a l l double errors i f i t can detect a l l single errors. i D i j - i Proof; For any double error, E(x)=x +x =x (1+x ), with i < j < n. The condition that the CRC detect a l l single errors i guarantees that g(x) w i l l not divide x . Thus a s u f f i c i e n t condition that a l l double errors be detected i s that g(x) not j - i divide (1+x ). But ( j - i ) < n < r and thus, since g(x) belongs to the exponent r, then obviously g(x) cannot divide E(x). Q.E.D. Fact: When (x+1) i s a factor of the g(x) of a CRC, then the primal code w i l l consist only of even weight codewords, [8]. A l l of the present CRC standard polynomials, that are known to the author, contain the (x+1) factor. This subset of the CRC class has some nice properties that are presented below and t h i s subclass w i l l from now on be referred to as the even CRC subclass. Theorem 3: A CRC in the even CRC subclass w i l l always have a symmetric weight d i s t r i b u t i o n for i t s dual code. 33 Proof: A necessary and s u f f i c i e n t condition for a code to have a symmetric weight d i s t r i b u t i o n i s that i t have the a l l ones codeword, [ 4 ] , Therefore, i t must be shown that for the even CRC subclass a l l the dual codes contain the a l l ones codeword. Consider the systematic dual code generator matrix, H. The f i r s t P column i s ac t u a l l y the f i r s t remainder, r1(x)=g(x) - x . Since g(x) has an even number of terms then r1(x) w i l l have an odd number. The second remainder r2(x)=xr1(x) mod g(x) equals either g(x) + xr1(x) or xr1(x) depending on whether xr1(x) i s of degree p or not, respectively. Thus an odd number of terms plus an even number always results in an odd number of terms. Therefore, by induction i t i s seen that a l l the remainder polynomials consist of an odd number of terms. The matrix H consists of columns of remainders and an id e n t i t y portion. Therefore, adding a l l the rows together results in the dual codeword of a l l ones. Thus the dual code always has a symmetric weight d i s t r i b u t i o n . Q . E . D . Property 3: For a CRC in the even CRC subclass a l l odd number of errors can be detected. Proof: This i s e a s i l y shown by restating an e a r l i e r fact that here the CRC w i l l contain only even weight codewords. Therefore, g(x) w i l l not divide any polynomial consisting of an odd number of terms. A l l odd number of errors are thus detected. Q . E . D . The a b i l i t y of the even CRC subclass to detect any odd number of errors as well as the dual code's symmetric weight 34 d i s t r i b u t i o n make t h i s subclass a very structured code class for error detection. Since at least one half the errors are detected, P(e) might also be lower for t h i s subclass. Therefore, in the next section where the problem of constructing a g(x) to obtain a proper code i s considered, emphasis i s placed on the even CRC subclass. 3.4 PROPER CODE q(x) CONSTRUCTION Examination was made of the even CRC subclass for 6 ^ p ^ 9, because these values of p afforded reasonable computational complexity and the results could e a s i l y be extended to larger p values. Fact: When the binary representation of g(x) is reversed, a di f f e r e n t polynomial, f ( x ) , i s obtained but the weight d i s t r i b u t i o n of a CRC using either g(x) or f(x) w i l l be i d e n t i c a l . This i s seen i f we consider the code generator matrix, G, corresponding to g(x). F i r s t reverse a l l the columns in G and then reverse a l l the rows. The resul t i n g matrix i s actu a l l y the code generator matrix, F, corresponding to f ( x ) . But the code i s l i n e a r , so in ef f e c t G and F w i l l produce the same weight d i s t r i b u t i o n even though they w i l l produce a di f f e r e n t code. By r e s t r i c t i n g the analysis to the even CRC subclass p+1 (i e . g(x)=(x+1)g1(x) ) only a small subset of the t o t a l 2 binary sequences represented by polynomials of degree p had to P be examined. The polynomial g(x) requires the terms 1 and x 35 p-1 implying a t o t a l of 2 p o s s i b i l i t i e s . However, with t h i s constraint, the polynomial g1 (x) then requires the terms 1 and p-1 x . This reduces the number of polynomials to be examined down p-2 to 2 . B y using the above fact t h i s number was again reduced p-2 to s l i g h t l y more than half of 2 since some g(x) were symmetric about their center term. Since i t i s known from section 3.2 that for large k P(e) i s asymptotically bounded by (1), each CRC was examined over the range 2 < k < 50. The f i r s t l o c a l maximum P(e*) of the P(e) d i s t r i b u t i o n was calculated for each k value. If a code was found to be proper the maximum would always occur at e*=1/2. The lesser known method of using the dual code weights to calculate P P(e) was employed. Since p i s fixed, a computation of 2 codewords was e a s i l y made for every k whereas the c a l c u l a t i o n of k the 2 codewords of the primal code would c l e a r l y have been unrealizable for the larger k values. Tables IX, X, XI and XII show the r e s u l t i n g generator polynomials, for each p, in binary representation that produce proper codes for the given k range. These polynomials are expected to produce proper codes for a l l values of k. For each p the proper g(x) were examined over a wider k range. It was observed that for k £ 100 there was n e g l i g i b l e difference in P(e), even though the differences were more noticeable with increasing p. It would be unfeasible to examine the large c o l l e c t i o n of polynomials for any larger value of p. For k < 100 there was no clear best proper g(x) for a given p. The proper g(x) that had the better P(e) c h a r a c t e r i s t i c depended highly on 36 CRC-6 g(x) Binary Form Exponent of g(x) 1 0 0 1 0 11 28 1 0 1 1 1 1 1 30 1 1 1 1 0 11 31 1 0 0 0 1 1 1 31 1 0 0 1 1 0 1 31 Table IX - CRC-6:Proper Code g(x) for 2 < k < 50. CRC-9 g(x) Binary Form Exponent of g(x) 1 0 1 1 0 1 0 0 1 1 51 1 0 1 0 1 0 0 1 1 1 60 1 0 0 1 0 1 1 0 1 1 63 1 1 1 1 1 0 1 0 1 1 63 1 0 1 1 1 0 0 0 1 1 84 1 0 0 1 1 0 0 1 1 1 85 1 0 1 1 0 0 0 1 1 1 85 1 1 1 0 0 0 1 0 1 1 124 1 0 1 1 0 1 1 1 1 1 124 1 0 0 1 1 1 0 1 0 1 124 1 1 1 0 1 0 0 0 1 1 186 1 0 0 1 1 1 1 1 1 1 186 1 1 1 1 0 1 1 0 1 1 210 1 0 0 1 0 0 1 1 1 1 217 1 0 0 0 1 1 1 1 0 1 217 1 0 0 1 1 0 1 0 1 1 252 1 0 0 0 1 0 1 1 1 1 252 1 0 1 0 1 1 0 0 1 1 254 1 1 0 1 0 1 0 0 1 1 254 1 0 0 0 1 1 1 0 1 1 254 1 0 1 0 0 0 1 1 1 1 254 1 1 1 0 0 1 1 1 1 1 254 1 0 1 1 0 1 0 1 0 1 254 1 0 0 1 0 1 1 1 0 1 254 1 1 1 0 0 1 0 0 1 1 255 1 0 1 1 1 1 1 0 1 1 255 1 1 1 0 1 1 1 0 1 1 255 1 1 1 0 1 0 1 1 1 1 255 1 0 1 0 0 1 0 1 1 1 255 Table X - CRC-9:Proper Code g(x) for 2 < k £ 50. 37 CRC-7 g(x) Binary Form Exponent of g(x) 1 0 1 0 1 1 1 1 42 1 0 0 1 0 0 11 62 1 1 1 0 1 0 11 62 1 0 0 0 1 1 0 1 62 1 0 1 0 0 0 11 63 1 0 1 1 0 1 1 1 63 1 0 0 10 1 0 1 63 Table XI - CRC-7:Proper Code g(x) for 2 < k < 50. CRC-8 g(x ) Binary Form Exponent of g(x) 1 0 0 0 1 1 1 1 1 84 1 1 1 1 0 0 0 1 1 93 1 0 1 0 1 0 1 1 1 93 1 1 1 0 1 1 1 1 1 105 1 0 0 1 0 0 1 0 1 105 1 1 1 0 1 0 0 1 1 1 24 1 0 1 0 1 1 0 1 1 124 1 0 0 1 1 1 1 0 1 124 1 1 1 1 1 1 0 1 1 126 1 0 1 0 0 1 1 1 1 126 1 0 0 1 1 0 1 1 1 126 1 1 0 1 1 a 0 1 1 127 1 1 1 0 0 1 0 1 1 127 1 0 0 1 0 1 1 1 1 127 1 0 1 1 1 i 1 1 1 127 1 0 1 1 1 0 1 0 1 127 Table XII - CRC -8:Proper Code g(x) for 2 < k < 50. 38 k. A certain g(x) would be better for one value of k < 100, but on the otherhand that same g(x) would be worse for a d i f f e r e n t value of k < 100. The polynomials that consistently gave improper codes were those symmetric about th e i r center term. This implies that reversing the binary representation of g(x) results in the same g(x). These symmetric g(x) produced P(e*) values that were s i g n i f i c a n t l y higher than even the values from the non-symmetric polynomials that gave improper codes. A comparison of the P(e) c h a r a c t e r i s t i c s of three CRC polynomials with p=8 i s given. Figures 4, 5 and 6 show P(e) for k < 100 over 0 < e < 1/2 for: a proper g(x), an improper non-symmetric g(x) and an improper symmetric g(x), respectively. For more detailed comparison, figures 7, 8 and 9 show the same g(x) but over the range of 10"5 £ e < 1/2. There does not seem to be any obvious c h a r a c t e r i s t i c that gives a c e r t a i n g(x) the a b i l i t y to produce a proper code for a l l k. The exponents of the various g(x) were calculated by u t i l i z i n g the simple computational method presented in the previous section. It was found that there was a high degree of co r r e l a t i o n between the exponent of a cert a i n g(x) and whether or not i t produced a proper code. The values of the exponents of the examined g(x) are grouped together in four categories: improper symmetric g(x), improper non-symmetric g(x), pseudo-proper g(x) and proper g(x). Tables XIII, XIV, XV and XVI show the c l a s s i f i e d exponents for the range of p examined. The improper symmetric g(x) have very small exponents. The reason FIGURE 6- P(e): Improper CRC-8; symmetric g(x),{g(x)=(110000011),0 < e < 1/2,2 < k < 100}. FIGURE 7- P(e): Proper CRC-8, {g(x)=(111100011),10'5 < e < 1/2,2 < k < 100}. FIGURE 8- P(e): Improper CRC-8; non-symmetric g(x){g(x) = ( 100100011 ), 10"5 < e < 1/2,2 < k < 100} 44 45 impi symn •oper codes netric g(x) imp: •oper codes g(x) psei code ido-proper ;s g(x) prof ?er codes g(x) # exponent # exponent # exponent # exponent 1 1 1 1 6 8 10 12 2 21 --2 2 6 28 30 31 Table XIII - Even CRC-6 subclass polynomial exponents. improper codes improper codes pseudo-proper proper codes symn le t r i c g(x) g(x) code ;s g(x) g(x) # exponent # exponent # exponent # exponent 1 9 2 15 2 84 2 51 1 10 2 21 2 1 20 2 60 2 12 2 28 2 186 4 63 1 15 4 30 2 210 2 84 1 16 4 42 2 254 4 85 2 17 2 51 6 255 6 124 1 21 2 56 - - 4 186 2 24 2 63 - - 2 210 1 28 2 70 - - • 4 217 1 30 4 85 - - 4 252 1 36 8 218 - - 14 254 1 40 2 252 - - 10 255 1 60 2 254 Table XIV - Even CRC-9 subclass polynomial exponents. 46 improper codes symmetric g(x) improper codes g(x) pseudo-proper codes g(x) proper codes g(x) # exponent # exponent exponent exponent 1 1 1 2 1 1 1 7 8 9 12 15 20 24 2 2 2 2 1 4 1 5 21 28 60 2 6 6 42 62 63 Table XV - Even CRC-7 subclass polynomial exponents. improper codes symmetric g(x) exponent 1 2 8 12 14 18 20 24 30 improper codes g(x) exponent 2 2 2 2 2 2 2 14 30 42 35 56 60 127 pseudo-proper codes g(x) exponent 2 2 6 42 93 127 proper codes g(x) exponent 2 4 4 6 6 10 84 93 105 124 126 127 Table XVI - Even CRC-8 subclass polynomial exponents. 47 these symmetric g(x) produce improper codes could be due to the fact that reasonable values of k are a l l greater than the exponent r. As shown in the previous section, when k > r the primal code's minimum distance is two. Therefore, for k much larger than the small r, the number of minimum weight two codewords increases more rapidly making P(e) larger. The proper g(x) always have very large exponents, many of which are maximal. The maximum possible exponent of a g(x) of the even CRC p-1 subclass i s (2 -1) which implies that gl(x) i s a primitive polynomial. The exponents of the pseudo-proper g(x) have a very wide range. On the other hand, the improper g(x) generally have exponents less than one half of the maximum although there are a few exceptions. One example i s that of a CRC-8 g(x) that has maximum exponent but i s improper for 2 < k < 5. Overall, i t can be stated that proper codes are more l i k e l y to be formed by using a g(x) with a large exponent. Also, a g(x) with a small exponent w i l l always produce improper codes for values of k much greater than r. The standard CRC polynomials examined in the next chapter are improper for many small values of k although they have maximum exponents. For completeness, some primitive polynomials were examined over the range P 6 £ p ^ 8 because of their maximum exponent, (2 -1). A l l the primitive g(x) were observed to produce proper codes. A comparison was made between the even CRC subclass proper g(x)'s and the primitive g(x)'s for each p. Figures 10 through 15 show the P(e) c h a r a c t e r i s t i c s that are representative of thi s comparison for 2 £ k <. 100. For p=6, P(e) for the primitives i s - P(e): Proper even CRC-6 subclass, {g (x) = (110111 1), 1 0"5 < e < 1/2,2 < k < 100} FIGURE 11 - P(e) : Pr imit ive CRC-6, {g(x) = ( 1110011), 10" 5 <S e £ 1/2,2 < k < 100}. FIGURE 12- P(e): Proper even CRC-7 subclass,{g(x) = (11010111),10-5 < e < 1/2,2 < k < 100}. FIGURE 13- P(e): Primitive CRC-7, {g(x)=(10001001),10" 5 < e < 1/2,2 < k ^ 100}. FIGURE 14- P(e): Proper even CRC-8 subclass, {g(x)=(101011011),10"5 < e < 1/2,2 < k < 100}. FIGURE 15- P(e): Primitive CRC-8,{g(x)=(101101001),10'5 £ e < 1/2,2 < k £ 100}. 54 lower for most k than that of the other proper g(x). However, with p=7 the primitive g(x) has i t s P(e) c h a r a c t e r i s t i c s closely packed together and therefore, P(e) i s lower for larger k but higher for smaller k. When p=8, P(e) is generally lower for the even CRC subclass proper g(x)'s for large k values. For lower k, P(e) i s roughly the same. A small sample of primitive CRC-12 polynomials were also examined. The even CRC-12 subclass generally had better or similar P(e) c h a r a c t e r i s t i c s . It might be mentioned that the primitive polynomials do not possess the a b i l i t y to detect a l l odd weight errors. For large k values P(e) i s e f f e c t i v e l y the same for a l l g(x) when the b i t error rate i s high. Thus the following rule of thumb i s suggested with regards to any CRC g(x): For k > 100 and e ^ 0.1, P(e) i s approximately 2 . Thus when a large block size i s used over a r e l a t i v e l y noisy channel, P(e) w i l l quickly approach i t s asymptotic l i m i t . When e < 0.1, a proper CRC g(x) "P w i l l give a P(e) that i s much lower than 2 55 4. CRC STANDARD EXAMINATION 4.1 CRC-12 ANALYSIS The CRC-12 international standard polynomial i s given as follows: 1+x+x 2+x 3+x , 1+x 1 2, [13] and [22]-[27] and referred to as the CRC-12S g(x). This g(x) i s within the even CRC subclass discussed in the preceding chapter. The polynomial is factored as: g(x)=(1+x)(1+x 2+x 1 1). Using theorem 2, the exponent of g(x) was calculated to be (2 1 1-1)=2047 which i s maximal considering the factor g1(x) i s a primitive polynomial. By using the properties given in chapter three, the detection c a p a b i l i t i e s are presented below. 1. A l l single errors are detected. 2. If n < r=2047, a l l double errors are detected. 3. A l l odd number of errors can be detected. By examining the P(e) c h a r a c t e r i s t i c over a wide range of k i t was found that t h i s CRC-12S g(x) produced an improper code for k < 172 and a proper code for 172 ^ k < 250. For any k < (r+1-p)=2036 the minimum distance, d, of the primal code created by the standard g(x) i s four. For larger k, d becomes two. For comparison purposes there exists no other CRC-12 standard. In chapter 3 i t was stated that maximal exponent g(x) are more l i k e l y to form proper codes. Therefore, examination was made of a l l even CRC subclass maximum exponent polynomials. By using the methods of the previous chapter to calculate P(e*) 56 over a range of 2 £ k < 50, i t was found that some g(x) gave proper codes for a l l these k values. The P(e) c h a r a c t e r i s t i c s of these proper g(x) were then compared to that of the standard. For k values greater than 150 i t was observed that there was neg l i g i b l e difference between the P(e). However, for k < 150 the proper even CRC subclass maximum exponent polynomials generally had much better P(e) c h a r a c t e r i s t i c s . As a representative of these proper g(x), 1+x+x 2+x 3+x 5+x 7+x 1 1+x 1 2, i s used and referred to as the CRC-12R g(x). Figures 16 and 17 show the P(e) for both polynomials over the range 2 ^ k < 150. For more p r a c t i c a l blocklengths, figures 18 through 21 show P(e) of both g(x) over 50 < k < 2000. Overall, the CRC-12R g(x) has much better P(e) ch a r a c t e r i s t i c s than the CRC-12S g(x). The detection c a p a b i l i t i e s of the CRC-12R g(x) also include those stated for the CRC-12S g(x), [13]. Therefore, i f P(e) i s an important system parameter, then use of the CRC-12R g(x) i s advantageous. It might be noted that P(e) of a number of g(x) from the even CRC subclass of maximal exponent are similar to that of the CRC-12R g(x). FIGURE 17- P(e): CRC-12R; g(x) = ( 1 1 1 101010001 1 ) , {0 < e < 1/2,2 < k < 150}. 69 09 61 FIGURE 21- P (e ) : CRC-12R; g(x)=(1111010100011), {1Q-5 < e < 1/2 r50 < k < 2000}. 63 4.2 CRC-16 ANALYSIS There are two CRC-16 international standard polynomials as shown below, [13] and [22]-[27], CRC-ANSI g(x)=1+x 2+x' 5+x' 6=(x+1)(1+x+x 1 5) CRC-CCITT g(x)=1+x 5+x 12+x 1 6=(x+1)(1+x+x 2+x 3+x"+x 1 2+x 1 3+x 1"+x 1 5) Both g(x)'s were calculated to have exponent r=(2 1 5-1)=32767 which i s maximal since both have g1(x) as a primitive polynomial. U t i l i z i n g the properties presented in chapter three, the detection c a p a b i l i t i e s of these two standards are the same and are given below. 1. A l l single errors are detected. 2. If n < r=32767, a l l double errors are detected. 3. A l l odd number of errors can be detected. The minimum distance of the codes produced by both standard g(x) i s four when k < (r+1-p)=32752. For larger k the minimum distance becomes two as for any CRC g(x) with k > r. By examining the l i s t of improper codes in table I i t can be seen that for p=16 and d=4 the code w i l l be improper for a l l k ^ 9. This result comes from the weak VGO bound test for improper codes. Thus, neither CRC-16 standard i s proper for k ^ 9. Since the two standard g(x) both meet the stated detection c a p a b i l i t i e s , they w i l l be compared so l e l y with respect to their P(e). These two g(x) w i l l also be compared with a proposed CCIR standard, [14]. 64 The CCIR code i s not generated the same as the other CRC-16 standards. It uses a CRC-15 polynomial given by, 1+x 2+x"+x 1 1+x 1 3+x 1"+x 1 5, to generate f i f t e e n parity b i t s . The f i f t e e n t h p a r i t y b i t i s inverted to protect against misframing in the decoder and one overa l l even parity b i t i s added to the codeword. Because the f i f t e e n t h parity b i t i s inverted, the a l l zeros codeword no longer exists thus making the CCIR code non-l i n e a r . However, inverting one b i t does not affect the distance spectrum because now the distances are simply r e l a t i v e to a codeword other than the a l l zeros one. This implies that their r e l a t i v e distances do not change. Therefore, P(e) can be calculated by simply ignoring the inversion. The remainders of the systematic code generator matrix are generated using the CRC-15 polynomial and even parity b i t s are added in the last column of the matrix. The resulting representative li n e a r code matrix can then be used to calculate P(e) of the CCIR standard. A p r a c t i c a l range of 50 ^ k < 2000 i s chosen for examination since the codes are improper for small k values. Figures 22 to 24 show P(e) of a l l three standards for 0 < e < 1/2. Note that figure 24 for the CCIR standard i s shown on a scale twenty f i v e to one hundred times greater than that for the plots of the other two standards because of i t s obvious i n f e r i o r P(e) c h a r a c t e r i s t i c s . The same scale i s used for each of the log-log plots given in figures 25 to 27 which compare the three standards for 10"5 £ e ^ 1/2. It seemed an obvious choice to blame the bad P(e) c h a r a c t e r i s t i c s on the CRC-15 polynomial and not on the addition of the single even parity b i t . The exponent of the CRC-15 polynomial was calculated to be r=63, 65 which i s much less than the maximum exponent of (2 1 5-1 ) = 32767 that could be obtained by using a primitive polynomial. The examination of chapter 3, indicates that because of i t s low exponent, the CRC-15 polynomial w i l l almost surely be improper. This i s shown to be the case in figure 28 where P(e) i s plotted for the CRC-15 polynomial over 0 £ e ^ 1/2. Figure 29 i s a log-log plot of the P(e) for the CRC-15 polynomial over the range 10"5 < e < 1/2. By comparing figures 27 and 29 i t can be seen that the plots d i f f e r only for e near 0.1 at which they go to their d i f f e r e n t 2 l i m i t s . Thus the chosen CRC-15 polynomial seriously degrades the P(e) c h a r a c t e r i s t i c s of the CCIR standard. For the largest k values the two CRC-16 standards are almost i d e n t i c a l . Table XVII shows some highlighted P(e) values of the two standards as well as the r a t i o of the two. By comparing figures 25 and 26, from which table XVII i s derived, i t i s seen that the CRC-CCITT polynomial has much better P(e) c h a r a c t e r i s t i c s for k < 1000. Thus o v e r a l l the CRC-CCITT standard i s s i g n i f i c a n t l y the best of the three with respect to error detection. 1 6 BIT :(R°ROR RATE 3-0 „ , ( X l O " 1 FIGURE 22- P(e): CRC-ANSI Standard, {0 < e £ 1/2,50 < k < 2000} 67 89 69 FIGURE 26- P(e): CRC-CCITT Standard, (tO" 5 < e S 1/2,50 <• k < 2000}. FIGURE 27- P(e): CRC-CCIR Standard, {10"5 < e < 1/2,50 < k < 2000}. ZL 73 74 # Info. Bit Error Undetected Errc >r Probability Rat i o : Bits,k Rate , e (1) ANSI (2) CCITT (1)/(2) 50 0. 5E-04 0. 224820E- 1 4 0. 360822E- 15 6 .231 50 0. 1E-03 0. 397737E- 1 3 0. 863198E- 14 4 .608 50 0. 5E-03 0. 245999E- 10 0. 557400E- 1 1 4 .413 50 0. 1E-02 0. 381591E-09 0. 864690E- 10 4 .413 50 0. 5E-02 0. 186099E-06 0. 421746E-07 4 .413 50 0. 1E-01 0. 218351E-05 0. 494993E-06 4 .411 50 0. 5E-01 0. 114393E-03 0. 264169E-04 4 .330 50 0. 1E+00 0. 894400E-04 0. 249243E-04 3 .588 100 0. 5E-04 0. 107692E- 13 0. 234535E- 1 4 4 .592 100 0. 1E-03 0. 176706E- 1 2 0. 417860E- 1 3 4 .229 100 0. 5E-03 0. 106078E-09 0. 254116E- 10 4 .174 100 0. 1E-02 0. 160488E-08 0. 384499E-09 4 .174 100 0. 5E-02 0. 641578E-06 0. 154124E-06 4 .163 100 0. 1E-01 0. 588515E-05 0. 142602E-05 4 . 127 100 0. 5E-01 0. 509232E-04 0. 179816E-04 2 .832 100 0. 1E+00 0. 178116E-04 0. 154109E-04 1 .156 200 0. 5E-04 0. 547756E- 13 0. 185407E- 13 2 .954 200 0. 1E-03 0. 873981E- 12 0. 298941E- 12 2 .924 200 0. 5E-03 0. 502718E-09 0. 172459E-09 2 .915 200 0. 1E-02 0. 723685E-08 0. 248410E-08 2 .913 200 0. 5E-02 0. 195751E-05 0. 684774E-06 2 .859 200 0. 1E-01 0. 112374E-04 0. 417165E-05 2 .694 200 0. 5E-01 0. 162630E-04 0. 152778E-04 1 .064 200 0. 1E+00 0. 152593E-04 0. 152588E-04 1 .000 500 0. 5E-04 0. 903375E- 12 0. 525358E- 12 1 .720 500 0. 1E-03 0. 141010E- 10 0. 820184E- 1 1 1 .719 500 0. 5E-03 0. 719129E-08 0. 418700E-08 1 .718 500 0. 1E-02 0. 894150E-07 0. 522035E-07 1 .713 500 0. 5E-02 0. 820509E-05 0. 520604E-05 1 .576 500 0. 1E-01 0. 163210E-04 0. 126146E-04 1 .294 500 0. 5E-01 0. 152588E-04 0. 152588E-04 1 .000 500 0. 1E+00 0. 152588E-04 0. 152588E-04 1 .000 1000 0. 5E-04 0. 928387E- 1 1 0. 808040E- 1 1 1 .149 1000 0. 1E-03 0. 141257E-09 0. 122950E-09 1 .149 1000 0. 5E-03 0. 593097E-07 0. 516767E-07 1 .148 1000 0. 1E-02 0. 584761E-06 0. 511141E-06 1 .144 1000 0. 5E-02 0. 134820E-04 0. 126827E-04 1 .063 1000 0. 1E-01 0. 152834E-04 0. 152035E-04 1 .005 1000 0. 5E-01 0. 152588E-04 0. 152588E-04 1 .000 1000 0. 1E+00 0. 152588E-04 0. 152588E-04 1 .000 2000 0. 5E-04 0. 121625E-09 0. 1 19659E-09 1 .016 2000 0. 1E-03 0. 176150E-08 0. 173305E-08 1 .016 2000 0. 5E-03 0. 507996E-06 0. 500046E-06 1 .016 2000 0 . 1E-02 0. 328047E-05 0. 323398E-05 1 .014 2000 0. 5E-02 0. 152085E-04 0. 151994E-04 1 .001 2000 0. 1E-01 0. 152588E-04 0. 152588E-04 1 . 0 0 0 2000 0. 5E-01 0. 152588E-04 0. 152588E-04 1 . 0 0 0 2000 0. 1E+00 0. 152588E-04 0. 152588E-04 1 . 0 0 0 Table XVII - CRC-16 Standard Comparison. 75 5. CONCLUSIONS 5.1 SUMMARY OF RESULTS This thesis has examined the use of proper block codes for error detection. Clear benefits are derived from using proper codes. It was shown that the V-G bound test for improper codes is a special case of a family of increasingly better tests. The V-G bound was used to l i s t improper codes depending only on p, d and k. By examining some known improper codes i t was shown that the f i r s t bound of the family, the VG1 bound, produced a s i g n i f i c a n t improvement over the V-G bound in testing for improper codes. However, in some cases the successive bounds of the family had to be used to confirm a code as improper. One of the most common class of error detecting codes, the CRC c l a s s , was then examined. The asymptotic value of i t s P(e) -P was shown to be 2 as k was increased with p fixed. A simple computational method was presented to allow the easy calculation of the exponent, r. It involves the simple generation of the d i s t i n c t sequence of remainders in the systematic code generator matrix. The CRC subclass consisting of g(x)'s with only an even number of terms was defined as the even CRC subclass. It was shown that t h i s subclass has the a b i l i t y to detect a l l odd weight errors as well as having a symmetric dual code weight d i s t r i b u t i o n for a l l values of k. Because of i t s structure, the even CRC subclass was examined for 6 £ p ^ 9. The method for evaluating P(e) was that 7 6 P u t i l i z i n g the dual code with a c a l c u l a t i o n of 2 codewords. With k the increasing k values, a c a l c u l a t i o n of the 2 primal codewords would have been t o t a l l y unfeasible. It was found that over the range of p examined and k > 100, there was n e g l i g i b l e difference in the P(e) of the proper g(x). There was no clear best proper g(x) for a given p with respect to P(e). It was observed that a g(x) with a low exponent gave a very high P(e) and produced improper codes. The symmetric g(x) a l l had very small exponents and consequently poor P(e) c h a r a c t e r i s t i c s . If a g(x) had a large or maximal exponent i t s P(e) was most l i k e l y to be that of a proper code. More s p e c i f i c a l l y , i t was found by examination of a number of primitive g(x) that the resulting codes were proper. Due to the examination of the many g(x), the following rule of thumb i s "P given: For k > 100 and e > 0.1, P(e) i s approximately 2 F i n a l l y , some international CRC standards were examined. It was found that for k > 150, many of the even CRC-12 subclass maximal exponent generator polynomials had similar P(e) c h a r a c t e r i s t i c s . For smaller values of k, a code referred to as CRC-12R was shown to have better P(e) c h a r a c t e r i s t i c s than the standard CRC-12. It was also shown that the CRC-CCIR standard has a very high P(e) mainly because the chosen CRC-15 polynomial has a low exponent. The CRC-ANSI and CRC-CCITT standards have similar P(e) for very large k, but the CRC-CCITT has the best o v e r a l l P(e) c h a r a c t e r i s t i c s . 77 5.2 SUGGESTIONS FOR FURTHER WORK Below i s a l i s t of some problems which deserve further study. 1. Determine i f a primitive generator polynomial, g(x), always produces proper codes. 2. Examine a larger range of p for the CRC class to determine more s p e c i f i c relationships between the exponent of a g(x) and the re s u l t i n g codes. 3. Search for a possible CRC-16 g(x) with better P(e) c h a r a c t e r i s t i c s than the present standards. 4. Look for strong and yet simple-to-evaluate tests for proper codes. 5. Develop more detailed guidelines on the construction of proper codes. 6. Examine the problems of combined error correction and detection. Some preliminary results appear in [28] and [29], 78 BIBLIOGRAPHY T.Kasami, T.Klove and S.Lin, " Linear block codes for error detection ," IEEE Trans. Inform. Theory, vol.IT-29, pp.131-136, January 1983. C.Leung, " Evaluation of the undetected error p r o b a b i l i t y of single parity-check product codes ," IEEE Trans. Comm., vol.COM-31, pp.250-253, February 1983. J.K.Wolf, A.M.Michelson and A.H.Levesque, " On the proba b i l i t y of undetected error for lin e a r block codes ," IEEE Trans. Comm., vol.COM-30, pp.317-324, February 1982. C.Leung, E.R.Barnes and D.U.Friedman, " On some properties of the undetected error p r o b a b i l i t y of 1inear>codes ," IEEE Trans. Inform. Theory, vol.IT-25, pp.110-112, January 1979. C.Leung and M.E.Hellman, " Concerning a bound on undetected error p r o b a b i l i t y ," IEEE Trans. Inform. Theory, vol.IT-22, pp.235-237, March 1976. . R.Padovani and J.K.Wolf, " Poor error correction codes are poor error detection codes ," IEEE Trans. Inform. Theory, vol.IT-30, pp.110-111, January 1984. T.Kasami, S.Lin and W.W.Peterson, " Polynomial codes ," IEEE Trans. Inform. Theory, vol.IT-14, pp.807-814, November 1968. W.W.Peterson and D.T.Brown, " Cy c l i c codes for error detection ," Proceedings of the IRE, pp.228-235, January 1961 . M.J.Miller and S.Lin> " Coding schemes for error detection in data transmission and storage ," J . E l e c t . Electron. Eng., A u s t r a l i a , vol.3, no.3, pp.195-203, September 1983. J.D.Martin, " Using polynomial codes Electronic Engineering, vol.48, no.581,pp.46-49, July 1976. M.W.Williard, " Introduction to redundancy coding ," IEEE Trans. On Vehicular Technol., vol.VT-27, pp.86-98, August 1978. H.O.Burton and D.D.Sullivan, " Errors and error control ," Proceedings of the IEEE, vol.60, pp.1293-1301, November 1972. 79 13] A.S.Tanenbaum, " Computer networks ," Englewood C l i f f s , N.J.: Prentice-Hall, pp.125-133, 1981. 14] CCIR," Formats for data transmission ," CCIR Green Book, vol.8, part E, rep.903, 1982. 15] R.E.Blahut, " Theory and practice of error control codes Massachusetts: Addison-Wesley, 1983. 16] S.Lin and D.J.Costello,Jr., " Error control coding: fundamentals and applications ," Englewood C l i f f s , N.J.: Prentice-Hall, 1983. 17] F.F.Kuo,ed., " Protocols and techniques for data communication networks ," Englewood C l i f f s , N.J.: Prentice-Hall, 1981. 18] E.R.Berlekamp, " The technology of error-correcting codes ," Proceedings of the IEEE, vol.68, pp.564-593, May 1980. 19] F.J.MacWilliams and N.J.A.Sloane, " The theory of error- correcting codes, part I_ and part 11 ," New York: North-Holland, 1977. 20] W.W.Peterson and E.J.Weldon,Jr., " Error-correcting codes, 2nd ed. ," Cambridge, MA: MIT Press, 1972. 21] S.W.Golomb, " Shi f t register sequences ," San Francisco: Holden-Day, 1967. 22] R.L.Freeman, " Telecommunication transmission handbook ," New York: John Wiley and Sons, pp.366-370, 1981. 23] R.L.Freeman, " Telecommunication system engineering ," New York: John Wiley and Sons, pp.293-302, 1980. 24] J.Puzman and R.Porizek, " Communication control in computer networks New York: John Wiley and Sons, pp.120-124, 1980. 25] J.Martin, " Teleprocessing network organization ," Englewood C l i f f s , N.J.: Prentice-Hall, pp.76-95, 1970. 26] A.Perez and Wismer and Becker, " Byte-wise crc cal c u l a t i o n s ," IEEE Micro, pp.40-50, June 1983. 27] P.Cavell, " Implementation of c y c l i c redundancy check c i r c u i t s ," Electronic Engineering, vol.49, no.588, pp.51-55, February 1977. 80 [28] T.Klove, " The probability of undetected error when a code is used for error correct ion and detect ion , " IEEE Trans. Inform. Theory, vol.IT-30, pp.388-392, March 1984. [29] T.Klove and M.Miller, " The detection of errors a f t e r error-correction decoding ," IEEE Trans. Comm., vol.COM-32, pp.51 1-517, May 1984. [30] Y.Chang and C.Leung, " A performance comparison of some speci f ic ARQ schemes including error correction ," International E l e c t r i c a l , E lectronics Conference, Toronto, September 1983. [31] E.R.Berlekamp, " Key papers in the development of coding theory ," New York: IEEE Press, 1974. [32] C.Leung, private communication.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Examination of the undetected error probability of...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Examination of the undetected error probability of linear block codes Witzke, Kenneth Alfred 1984
pdf
Page Metadata
Item Metadata
Title | Examination of the undetected error probability of linear block codes |
Creator |
Witzke, Kenneth Alfred |
Publisher | University of British Columbia |
Date Issued | 1984 |
Description | The undetected error probability, P(e), of linear (n,k) block codes used for transmission over a binary symmetric channel is examined. A class of codes referred to as proper codes is seen to possess certain desirable characteristics. A family of increasingly better tests for determining when a code is not proper is derived. Some known improper codes are examined to assess the relative strengths of the tests. For cyclic redundancy codes (CRC), P(e) is shown to be asymptotically equal to 2[sup –p]. For specific values of k, P(e) was evaluated using the dual code weights. This greatly reduces the computational burden. The even CRC subclass consisting of generator polynomials, g(x)'s, with an even number of terms is shown to have the ability to detect all odd weight errors. It was observed that the P(e) characteristics of a code generated by g(x) is closely related to the exponent of g(x). In particular, a low exponent is a good indicator of an improper code. It was also found that by examination of a number of primitive g(x) that the resulting codes are proper. For k < 150, a code referred to as CRC-12R is shown to have better P(e) characteristics than the CRC-12 standard. Three CRC-16 standards: CRC-ANSI, CRC-CCITT and CRC-CCIR are compared. It was shown that CRC-CCIR has a very high P(e) and CRC-CCITT has the best overall P(e) characteristics of the three standards. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-05-24 |
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. |
IsShownAt | 10.14288/1.0096199 |
URI | http://hdl.handle.net/2429/24959 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1984_A7 W58.pdf [ 4.49MB ]
- Metadata
- JSON: 831-1.0096199.json
- JSON-LD: 831-1.0096199-ld.json
- RDF/XML (Pretty): 831-1.0096199-rdf.xml
- RDF/JSON: 831-1.0096199-rdf.json
- Turtle: 831-1.0096199-turtle.txt
- N-Triples: 831-1.0096199-rdf-ntriples.txt
- Original Record: 831-1.0096199-source.json
- Full Text
- 831-1.0096199-fulltext.txt
- Citation
- 831-1.0096199.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-0096199/manifest