UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Examination of the undetected error probability of linear block codes Witzke, Kenneth Alfred 1984

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

Item Metadata

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

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

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-0096199/manifest

Comment

Related Items