Abstract:
Cyclic redundancy codes are obtained to verify the integrity of a message transmitted between a sender and a receiver. One method for obtaining a cyclic redundancy code includes separating the message into segments. Remainders are obtained for those segments based on a generator polynomial. The remainders for those segments are multiplied by a segment-constant to obtain segment-remainders for each segment. The segment-remainders are accumulated into an accumulated-remainder. The accumulated-remainder is moduloed by the generator polynomial to obtain a remainder for the accumulated-remainder. The remainder for the accumulated-remainder is the cyclic redundancy code for the message.

Description:
TECHNICAL FIELD 
   This application relates to verifying the integrity of data transmissions, and more particularly, to verifying the integrity of digital data transmissions using cyclic redundancy codes. 
   BACKGROUND 
   Data transmission  10  ( FIG. 1 ) involves a transfer of information known as data between a sender  12  and a receiver  14 . Often, data transmission  10  includes information transmitted as digital bits of ones and zeros, represented here by m n−1  to m 0 , and referred to as a message M. 
   In a perfect world, message M transmits free of errors. Unfortunately, errors are often introduced though medium  16  by which message M travels from sender  12  to receiver  14  (e.g., medium  16  may be any combination of wire, cable, fiber-optic, air, or link layer devices). One method for detecting the presence of errors in message M employs cyclic redundancy codes. 
   Cyclic redundancy codes treat groupings of digital bits like message M as a polynomial where each bit in the grouping represents a coefficient in the polynomial X n−1 +X n−2 +X 0 . For example, a group of eight bits 11001101 may be represented by polynomial X 7 +X 6 +X 3 +X 2 +1 (i.e., 1*X 7 +1*X 6 +0*X 5 +0*X 4 +1*X 3 +1*X 2 +0*X 1 +1*X 0 ). 
   These polynomials form an algebraic object known as a commutative ring with coefficients in Z/p where Z are the integers and p is a prime number, here 2, also known as {0,1} modulo 2. A non empty set R together with two binary operations {+*} is called a ring if (R+) is an abelian group, (R*) is a semi group and the distributive laws are obeyed, (i.e. a*(b+c)=a*b+a*b). 
   In polynomial rings, there are no carries or borrows from one coefficient to the next. In arithmetic modulo 2, addition and subtraction are identical and may be implemented with exclusive-or. 
   
     
       
         
           
             
               10111011 
             
             
               10110011 
             
             
               11110000 
             
             
               00010101 
             
           
           
             
               
                 
                   
                     + 
                     11001110 
                   
                   ⁢ 
                   
                       
                   
                 
                 _ 
               
             
             
               
                 
                   
                     + 
                     11000101 
                   
                   ⁢ 
                   
                       
                   
                 
                 _ 
               
             
             
               
                 
                   
                     - 
                     00100110 
                   
                   ⁢ 
                   
                       
                   
                 
                 _ 
               
             
             
               
                 
                   
                     - 
                     10101111 
                   
                   _ 
                 
                 ⁢ 
                 
                     
                 
               
             
           
           
             
               01110101 
             
             
               01110110 
             
             
               11010110 
             
             
               10111010 
             
           
         
       
     
   
   Division of polynomials represented as groups of bits is completed in a manner similar to binary division except subtraction is done in modulo2. A divisor will ‘go into’ a dividend if the dividend polynomial is of the same degree as the divisor polynomial (i.e., the divisor and dividend share at least the same most significant bit). 
   A cyclic redundancy code may be obtained by calculating the remainder for message M divided by a generator polynomial P. This remainder is called a cyclic redundancy code (“CRC”). 
   To obtain a CRC for a message M, the group of bits to be divided by generator polynomial P may include appended zero-bits  17 . Zero-bits  17  are equal in number to the degree of generator polynomial P. Thus, the CRC of a message M=10111000 having three appended zero-bits  17  based on a generator polynomial P=X 3 +1=1001 of degree three (i.e., where X 3  is the most significant bit of polynomial P) may be calculated as follows: 
   
     
               
       
           
           
       
    
   
   The resulting remainder, shown as CRC  18 , may be appended to message M, replacing zero bits  17 , to create a message M′. Sender  12  transmits message M′ via medium  16  to receiver  14  as data transmission  10 . 
   Upon receipt, receiver  14  divides message M′ by the same generator polynomial P to obtain a CRC for M′ and check the validity of data transmission  10 . If the resulting remainder is zero (i.e., CRC=M′(modulo)P=0), the integrity of data transmission  10  is confirmed. For example: 
   
     
               
       
           
           
       
    
   
   If the remainder of message M′ divided by polynomial P is not zero (i.e., CRC=M′(modulo)P≠0), data transmission  10  contains one or more errors. For example: 
   
     
               
       
           
           
       
    
   

   
     DESCRIPTION OF DRAWINGS 
       FIG. 1  shows a prior art block diagram of a data transmission employing cyclic redundancy codes. 
       FIG. 2  shows a process for obtaining a CRC where a message M is separated into a plurality of segments. 
       FIG. 3  shows a CRC generator for obtaining a CRC of a message according to the process in  FIG. 2 . 
       FIG. 4  shows the CRC generator of  FIG. 3  separated into four segments. 
       FIG. 5  shows a CRC generator for obtaining a CRC of a message M according to the process in  FIG. 2 . 
       FIG. 6  shows a modulo unit for obtaining a remainder of a message using a reciprocal approximation of a generator polynomial. 
       FIG. 7  shows the CRC generator in  FIG. 3  using the modulo unit in  FIG. 6 . 
       FIG. 8  shows a CRC generator for updating a CRC of a message M where a portion of message M has been adjusted. 
       FIG. 9  shows the CRC generator in  FIG. 8  operating on an adjusted segment of message M. 
       FIG. 10  is a view of computer hardware used to implement an embodiment of the invention. 
   

   Like reference symbols in the various drawings indicate like elements. 
   DETAILED DESCRIPTION 
   Process  20  ( FIG. 2 ) obtains a CRC for a message M based on a generator polynomial P. 
   Process  20  includes separating ( 201 ) a message M into a plurality of message segments M s ; moduloing (defined below) ( 203 ) the message segments by a generator polynomial P, if needed, to obtain a remainder R for each segment; multiplying ( 205 ) the remainder R for each segment by an appropriate segment-constant C to obtain a segment-remainder SR for each segment M s ; accumulating ( 207 ) the segment-remainders SR for each segment M s  to obtain an accumulated-remainder AR for message M; and moduloing ( 209 ) the accumulated-remainder by generator polynomial P, if needed, to obtain the CRC for message M. 
   Separating ( 201 ) message M into a plurality of message segments M s  includes parsing message M so that:
 
 M=M   s−1   *X   n*(s−1)   +M   s−2   *X   n*(s−2)    . . . +M   1   *X   n(1)   +M   0   *X   n(0) ;
 
where s is the number of segments into which message M is separated, n is the number of bits in each segment, X is the position of each segment in message M, and M s  are the individual segments of message M. If the number of bits is n, then X is of the form X=[1000 . . . 0] where there are n zeroes, n+1 elements, and X is of degree n. Multiplying M by X will shift the message left by n bits. Multiplying M by X 2  will shift the message by 2n bits (and so on).
 
   Moduloing ( 203 ) includes obtaining a remainder R for each message segment M s  by dividing segment M s  by generator polynomial P if the degree of the most significant bit of segment M s  is the same as or greater than the degree of the most significant bit of polynomial P. If the degree of segment M s  is less than the degree of polynomial P (i.e., where the most significant bit of M s  is smaller than the most significant bit of polynomial P) moduloing ( 203 ) is not needed since the remainder for message segment M s  equals segment M s  itself. In alternate embodiments moduloing ( 203 ) may be accomplished by multiplying message segment M s  by a reciprocal approximation for polynomial P, rather than dividing segment M s  by polynomial P. to obtain remainder R for message segment M s . The operation of multiplication by reciprocal approximation to obtain a remainder R is discussed in connection with  FIG. 6  below. 
   Multiplying ( 205 ) includes obtaining segment-constant C (defined below) for each message segment M s  and multiplying each segment-constant C by its remainder R to obtain a segment-remainder SR for each message segment. Segment-constants C may be obtained based on the position X of message segment M s  in message M modulo generator polynomial P or modulo a field extension of P. 
   Accumulation ( 207 ) includes adding the segment-remainders SR for each message segment M s  to obtain an accumulated-remainder AR for message M. 
   Moduloing ( 209 ) includes dividing accumulated-remainder AR by generator polynomial P, or multiplying AR by a reciprocal approximation of generator polynomial P, to obtain a CRC for message M. However, if the degree of accumulated-remainder AR is less than the degree of polynomial P, moduloing ( 209 ) is not needed since the remainder (i.e., the CRC) of message M is accumulated-remainder AR. 
     FIG. 3  shows an implementation of process  20  for calculating a CRC of message M based on generator polynomial P. For example:
         if
           M=10111000, (Message 10111 with with 3 zero-bits appended)   s=2,   n=4, and   P=1001=(Deg(P)=3);   
           then M may be separated as
           M s−1 =M 1 =1011=segment  33 ,   X n*(s−1) =X 4 =10000,   M s−2 =M 0 =1000=segment  35 ,   X n*(s−2) =X 0 =00001;   
           where
           M=1011*10000+1000*00001=10111000.   
               
   CRC generator  30  obtains a CRC for message M based on generator polynomial P, where the CRC for message M is the remainder of message M divided by polynomial P (i.e., CRC=M(modulo)P=MOD(M, P). 
   Typically, generator polynomials P are selected because they are irreducible (i.e., they have no factors). Several examples of well-known generator polynomials include: 
                 LRCC8   =       ⁢       X   8     +   1                   =       ⁢   100000001     ;               CRC16   =       ⁢       x   16     +     x   15     +     X   2     +   1                   =       ⁢     11000000000000   ⁢           ⁢   101       ;               SDLC   =       ⁢       x   16     +     x   12     +     X   5     +   1                   =       ⁢     1000100000010000   ⁢           ⁢   1       ;               LRCC   =       ⁢       x   16     +   1                   =       ⁢     1000000000000000   ⁢           ⁢   1       ;               CRC12   =       ⁢       x   12     +     x   11     +     X   3     +     X   2     +   X   +   1                   =       ⁢   1100000001111     ⁢           ;   and               ETHERNET   =       ⁢       x   32     +     x   26     +     X   23     +     X   22     +     x   16     +     x   11     +     X   10     +     X   8     +     x   7     +                     ⁢       X   5     +     X   4     +     X   2     +   X   +   1                   =       ⁢     100000100   ⁢           ⁢   110000010000   ⁢           ⁢   110   ⁢           ⁢   110110111       ;               
where LRCC stands for Last Registration Control Channel.
 
   CRC generator  30  includes modulo unit  32 , multiplier  34 , accumulator  36 , and modulo unit  38 . Here, modulo unit  32  has modulo units  32   a  and  32   b  implemented in hardware. 
   Modulo unit  32   a  divides message segment  33  by generator polynomial P to obtain remainder R i+1  (i.e., R i+1 =M s−1 (modulo)P=MOD(M s−1 , P)). Modulo unit  32   b  divides message segment  35  by generator polynomial P to obtain remainder R i  (i.e., R i =M s−2 (modulo)P=MOD(M s−2 , P)). For example:
         if
           M=10111000,   M s−1 =M 1 =1011=segment  33 ,   M s−2 =M 0 =1000=segment  35 , and   P=1001;   
           then       

   
     
       
         
           
             
               
                 
                   R 
                   
                     i 
                     + 
                     1 
                   
                 
                 = 
                   
                 ⁢ 
                 
                   
                     R 
                     1 
                   
                   = 
                   
                     
                       
                         
                           M 
                           
                             s 
                             - 
                             1 
                           
                         
                         ⁡ 
                         
                           ( 
                           modulo 
                           ) 
                         
                       
                       ⁢ 
                       P 
                     
                     = 
                     
                       MOD 
                       ⁡ 
                       
                         ( 
                         
                           
                             M 
                             
                               s 
                               - 
                               1 
                             
                           
                           , 
                           P 
                         
                         ) 
                       
                     
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       1011 
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                     = 
                     010 
                   
                 
                 , 
                 and 
               
             
           
           
             
               
                 
                   R 
                   i 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     R 
                     0 
                   
                   = 
                   
                     
                       
                         
                           M 
                           
                             s 
                             - 
                             2 
                           
                         
                         ⁡ 
                         
                           ( 
                           modulo 
                           ) 
                         
                       
                       ⁢ 
                       P 
                     
                     = 
                     
                       MOD 
                       ⁡ 
                       
                         ( 
                         
                           
                             M 
                             
                               s 
                               - 
                               2 
                             
                           
                           , 
                           P 
                         
                         ) 
                       
                     
                   
                 
               
             
           
           
             
               
                   
                 ⁢ 
                 
                   
                     
                       1000 
                       ⁢ 
                       
                         ( 
                         mudulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                     = 
                     001 
                   
                   ; 
                 
               
             
           
         
       
     
       
       
         
           where 
         
       
     
  
   
     
               
       
           
           
       
    
   
   Multiplier  34  multiplies remainders R i+1  and R i  by segment-constants C i+1  and C i  to obtain segment-remainders SR i+1  and SR i . Here, segment-constants C i+1  and C i  are obtained by moduloing the position X of segments  33  and  35  in message M by generator polynomial P (i.e., C i+1 =X n*(i+1) (modulo)P and C i =X n*i (modulo)P). For example:
         if
           M=10111000,   P=1001,   s=2, and   n=4;   
           then for       

   
     
       
         
           
             
               
                 
                   SR 
                   
                     i 
                     + 
                     1 
                   
                 
                 = 
                   
                 ⁢ 
                 
                   SR 
                   1 
                 
               
             
           
           
             
               
                 
                   C 
                   
                     i 
                     + 
                     1 
                   
                 
                 = 
                   
                 ⁢ 
                 
                   
                     C 
                     1 
                   
                   = 
                   
                     
                       
                         X 
                         
                           4 
                           * 
                           1 
                         
                       
                       ⁡ 
                       
                         ( 
                         modulo 
                         ) 
                       
                     
                     ⁢ 
                     P 
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       10000 
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                     = 
                     010 
                   
                 
                 , 
                 and 
               
             
           
           
             
               
                 
                   SR 
                   i 
                 
                 = 
                   
                 ⁢ 
                 
                   SR 
                   0 
                 
               
             
           
           
             
               
                 
                   C 
                   i 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     C 
                     0 
                   
                   = 
                   
                     
                       
                         X 
                         
                           4 
                           * 
                           0 
                         
                       
                       ⁡ 
                       
                         ( 
                         modulo 
                         ) 
                       
                     
                     ⁢ 
                     P 
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       0001 
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                     = 
                     001 
                   
                 
                 ; 
               
             
           
         
       
     
       
       
         
           where 
         
       
     
  
   
     
               
       
           
           
       
    
   
   Segment-constants C i+1  and C i  may be obtained in advance, based on a known segmentation of message M and stored in memory unit  39 , which is accessible to CRC generator  30 . In other embodiments, segment-constants C i+1  and C i  may be obtained ‘on the fly’ within CRC generator  30  upon receipt of message M. 
   Multiplier  34  includes multipliers  34   a  and  34   b . Multiplier  34   a  multiplies remainder R i+1  by segment-constant C i+1  to obtain segment-remainder SR i+1 . Multiplier  34   b  multiplies remainder R i  by segment constant C i  to obtain segment-remainder SR i . For example:
         if
           R i+1 =010, C i+1 =010 and (from above)   R i =001, C i =001;   
           then
           SR i+1 =R i+1 *C i+1 =010*010=00100, and   SR i =R i *C 1 =001*001=00001;   
           where       

   
     
       
         
           
             
               010 
             
             
               001 
             
           
           
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     * 
                     
                         
                     
                     ⁢ 
                     010 
                   
                   ⁢ 
                   
                       
                   
                 
                 _ 
               
             
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     * 
                     
                         
                     
                     ⁢ 
                     001 
                   
                   ⁢ 
                   
                       
                   
                 
                 _ 
               
             
           
           
             
               
                 
                   + 
                   000 
                 
                 ⁢ 
                 
                     
                 
               
             
             
               
                 
                   + 
                   001 
                 
                 ⁢ 
                 
                     
                 
               
             
           
           
             
               
                 
                   + 
                   010 
                 
                 ⁢ 
                 
                     
                 
               
             
             
               
                 
                   + 
                   000 
                 
                 ⁢ 
                 
                     
                 
               
             
           
           
             
               
                 
                   
                     + 
                     000 
                   
                   _ 
                 
                 ⁢ 
                 
                     
                 
               
             
             
               
                 
                   
                     + 
                     000 
                   
                   _ 
                 
                 ⁢ 
                 
                     
                 
               
             
           
           
             
               
                 
                     
                 
                 ⁢ 
                 
                   00100 
                   ⁢ 
                   
                       
                   
                   = 
                   
                     SR 
                     
                       i 
                       + 
                       1 
                     
                   
                 
                 ⁢ 
                 
                     
                 
               
             
             
               
                 
                     
                 
                 ⁢ 
                 
                   00001 
                   ⁢ 
                   
                       
                   
                   = 
                   
                     
                       SR 
                       i 
                     
                     . 
                   
                 
                 ⁢ 
                 
                     
                 
               
             
           
         
       
     
   
   Accumulator  36  adds segment-remainders SR i+1  and SR i  together to obtain accumulated-remainder AR. For example:
         if
           SR i+1 =SR 1 =00100, (from above)   SR i =SR 0 =00001;   
           then
           AR=00100+00001=00101,   
           where       

   
     
       
         
           
             
               
                 00100 
                 ⁢ 
                 
                     
                 
               
             
           
           
             
               
                 
                   
                     
                       + 
                       00001 
                     
                     ⁢ 
                     
                         
                     
                   
                   _ 
                 
                 ⁢ 
                 
                     
                 
               
             
           
           
             
               
                 00101 
                 = 
                 
                   AR 
                   . 
                 
               
             
           
         
       
     
   
   Modulo unit  38  obtains the CRC for message M by moduloing accumulated-remainder AR by generator polynomial P (i.e., CRC=AR(modulo)P=MOD(AR, P)). For example:
         if
           AR=00101, and (from above)   P=1001;   
           then       

   
     
       
         
           
             
               
                 CRC 
                 = 
                   
                 ⁢ 
                 
                   
                     
                       AR 
                       ⁡ 
                       
                         ( 
                         modulo 
                         ) 
                       
                     
                     ⁢ 
                     P 
                   
                   = 
                   
                     MOD 
                     ⁡ 
                     
                       ( 
                       
                         AR 
                         , 
                         P 
                       
                       ) 
                     
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       00101 
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                     = 
                     101 
                   
                 
                 , 
               
             
           
         
       
     
       
       
         
           where 
         
       
     
  
   
     
               
       
           
           
       
    
   
   Hence, process  20  implemented on CRC generator  30  obtains the same CRC for message M, here 10111000. In this example, moduloing AR by polynomial P is not needed since the degree of AR was less than the degree of P. 
   CRC generator  30  may be expanded to include enough components for obtaining the CRC for message M separated into N segments.  FIG. 4  shows CRC generator  40  capable of operating on message M separated into four (4) segments 43, 45, 47 and 49. For example:
         if
           M=M′=10111101, (e.g., message M in the example for  FIG. 3  above having the obtained CRC appended to it)   s=4,   n=2, and   p=2;   
           then M may be separated as
           M s−1 =M 3 =10=segment  43 ,   X n*(s−1) =X 6 =1000000,   M s−2 =M 2 =11=segment  45 ,   X n*(s−2) =X 4 =10000,   M s−3 =M 1 =11=segment  47 ,   X n*(s−3) =X 2 =100,   M s−4 =M 0 =01=segment  49 ,   X n*(s−4) =X 0 =001;   
           where
           M=10*1000000+11*10000+11*100+01*001=10111101.   
               

   CRC generator  40  includes modulo unit  42 , multipliers  44 , accumulator  46 , and modulo unit  48 . Modulo unit  42  includes modulo units  42   a ,  42   b ,  42   c  and  42   d . Modulo units  42   a ,  42   b ,  42   c  and  42   d  each operate to divide message segment  43 ,  45 ,  47  and  49  by generator polynomial P to obtain remainders R 3 , R 2 , R 1  and R 0 . For example:
         if
           M=10111101=M′, (from above)   M s−1 =M 3 =10=segment  43 ,   M s−2 =M 2 =11=segment  45 ,   M s−3 =M 1 =11=segment  47 ,   M s−4 =M 0 =01=segment  49 , and   P=1001;   
           then       

   
     
       
         
           
             
               
                 
                   R 
                   
                     i 
                     + 
                     3 
                   
                 
                 = 
                   
                 ⁢ 
                 
                   
                     R 
                     3 
                   
                   = 
                   
                     
                       
                         
                           M 
                           
                             s 
                             - 
                             1 
                           
                         
                         ⁡ 
                         
                           ( 
                           modulo 
                           ) 
                         
                       
                       ⁢ 
                       P 
                     
                     = 
                     
                       10 
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   10 
                 
                 , 
               
             
           
           
             
               
                 
                   R 
                   
                     i 
                     + 
                     2 
                   
                 
                 = 
                   
                 ⁢ 
                 
                   
                     R 
                     2 
                   
                   = 
                   
                     
                       
                         
                           M 
                           
                             s 
                             - 
                             2 
                           
                         
                         ⁡ 
                         
                           ( 
                           modulo 
                           ) 
                         
                       
                       ⁢ 
                       P 
                     
                     = 
                     
                       11 
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   11 
                 
                 , 
               
             
           
           
             
               
                 
                   R 
                   
                     i 
                     + 
                     1 
                   
                 
                 = 
                   
                 ⁢ 
                 
                   
                     R 
                     1 
                   
                   = 
                   
                     
                       
                         
                           M 
                           
                             s 
                             - 
                             3 
                           
                         
                         ⁡ 
                         
                           ( 
                           modulo 
                           ) 
                         
                       
                       ⁢ 
                       P 
                     
                     = 
                     
                       11 
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   11 
                 
                 , 
                 and 
               
             
           
           
             
               
                 
                   R 
                   1 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     R 
                     0 
                   
                   = 
                   
                     
                       
                         
                           M 
                           
                             s 
                             - 
                             4 
                           
                         
                         ⁡ 
                         
                           ( 
                           modulo 
                           ) 
                         
                       
                       ⁢ 
                       P 
                     
                     = 
                     
                       01 
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                   
                 
               
             
           
           
             
               
                 = 
                   
                 ⁢ 
                 01. 
               
             
           
         
       
     
   
   Multiplier  44  multiplies remainders R 3  to R 0  by segment-constants C 3  to C 0  to obtain segment-remainders SR 3  to SR 0 . Segment-constants C 3  to C 0  correspond to each particular segment  43 ,  45 ,  47  and  49  and may be obtained by moduloing the position of segments in message M by polynomial P. (i.e., C 3 =X n*(3) (modulo)P, C 2 =X n*2 (modulo)P, C 1 =X n*1 (modulo)P, C 0 =X n*0 (modulo)P). For example:
         if
           M=10111101, (from above)   P=1001,   s=4, and   n=2;   
           then       

   
     
       
         
           
             
               
                 
                   SR 
                   3 
                 
                 = 
                   
                 ⁢ 
                 
                   SR 
                   
                     i 
                     + 
                     3 
                   
                 
               
             
           
           
             
               
                 
                   C 
                   3 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     C 
                     
                       i 
                       + 
                       3 
                     
                   
                   = 
                   
                     
                       
                         X 
                         
                           2 
                           * 
                           3 
                         
                       
                       ⁡ 
                       
                         ( 
                         modulo 
                         ) 
                       
                     
                     ⁢ 
                     P 
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       1000000 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                     = 
                     001 
                   
                 
                 ; 
               
             
           
           
             
               
                 
                   SR 
                   2 
                 
                 = 
                   
                 ⁢ 
                 
                   SR 
                   0 
                 
               
             
           
           
             
               
                 
                   C 
                   2 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     C 
                     
                       i 
                       + 
                       2 
                     
                   
                   = 
                   
                     
                       
                         X 
                         
                           2 
                           * 
                           2 
                         
                       
                       ⁡ 
                       
                         ( 
                         modulo 
                         ) 
                       
                     
                     ⁢ 
                     P 
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       10000 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                     = 
                     010 
                   
                 
                 ; 
               
             
           
           
             
               
                 
                   SR 
                   1 
                 
                 = 
                   
                 ⁢ 
                 
                   SR 
                   1 
                 
               
             
           
           
             
               
                 
                   C 
                   1 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     C 
                     
                       i 
                       + 
                       1 
                     
                   
                   = 
                   
                     
                       
                         X 
                         
                           2 
                           * 
                           1 
                         
                       
                       ⁡ 
                       
                         ( 
                         modulo 
                         ) 
                       
                     
                     ⁢ 
                     P 
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       100 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                     = 
                     100 
                   
                 
                 ; 
                 and 
               
             
           
           
             
               
                 
                   SR 
                   0 
                 
                 = 
                   
                 ⁢ 
                 
                   SR 
                   i 
                 
               
             
           
           
             
               
                 
                   C 
                   0 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     C 
                     
                       i 
                       + 
                       0 
                     
                   
                   = 
                   
                     
                       
                         X 
                         
                           4 
                           * 
                           0 
                         
                       
                       ⁡ 
                       
                         ( 
                         modulo 
                         ) 
                       
                     
                     ⁢ 
                     P 
                   
                 
               
             
           
           
             
               
                 = 
                   
                 ⁢ 
                 
                   
                     001 
                     ⁢ 
                     
                       ( 
                       modulo 
                       ) 
                     
                     ⁢ 
                     1001 
                   
                   = 
                   001. 
                 
               
             
           
         
       
     
   
   Segment constants C 3  to C 0  may be obtained in advance based on the segmentation of message M and stored in a memory unit  39  ( FIG. 3 ) accessible to CRC generator  40 . In other embodiments C 3  to C 0  may be obtained ‘on the fly’ (i.e., in real-time)within CRC generator  40  as it receives message M. 
   Multiplier  44  multiplies R 3  by C 3 , R 2  by C 2 , R 1  by C 1 , and R 0  by C 0  to obtain segment-remainders SR 3  to SR 0 . For example:
         if
           R i+3 =R 3 =10, C i+3 =C 3 =001; (from above)   R i+2 =R 2 =11, C i+2 =C 2 =010;   R i+1 =R 1 =11, C i+1 =C 1 =100; and   R i=R   0 =01, C i =C i0 =001;   
           then
           SR 3 =R 3 *C 3 =10*001=0010;   SR 2 =R 2 *C 2 =11*010=0110;   SR 1 =R 1 *C 1 =11*100=1100; and   SR 0 =R 0 *C 0 =01*001=0001.   
               

   Accumulator  46  adds segment-remainders SR 3  to SR 0  together to obtain accumulated-remainder AR. Here, accumulator  46  includes accumulators  46   a ,  46   b  and  46   c , where accumulators  46   a  and  46   b  compute temporary accumulations T 1  and T 0  and accumulator  46   c  combines temporary accumulations T 1  and T 0  to obtain accumulated-remainder AR. For example:
         if
           SR i+3 =SR 3 =0010, (from above)   SR i+2 =SR 2 =0110,   SR i+1 =SR 1 =1100, and   SR i =SR 0 =0001;   
           then
           T 1 =0010+0110=0100,   T 0 =1100+0001=1101, and   AR=0100+1101=1001.   
               

   Finally, modulo unit  48  obtains the CRC for message M, here message M′ having the CRC obtained as described in  FIG. 3  above, by moduloing accumulated-remainder AR by polynomial P (i.e., CRC=AR(modulo)P=MOD(AR, P). For example:
         if
           AR=1001, and (from above)   P=1001;   
           then
           CRC=AR(modulo)P=1001(modulo)1001=0   
           where       

   
     
               
       
           
           
       
    
   
   Thus, CRC generator  40  verifies the integrity of message M from the example in  FIG. 3  where the CRC of message M was appended to form M′ and transmitted to a receiver  14  who confirmed the transmission using CRC generator  40  ( FIG. 4 ). 
   According to process  20 , CRC generators  30  and  40  may be further simplified where the degree of message segments M s  are less than the degree of generator polynomial P (i.e., Deg(M s )&lt;Deg(P)). As shown in the example for  FIG. 4  above, the remainder R of M s (modulo)P equals M s  when the degree of M s  is less than the degree of P. Thus, CRC generator  50  ( FIG. 5 ) does not need an initial modulo unit (e.g.,  32  or  42 ) for obtaining a remainder R i  of message segments M s  that are of a degree less than the degree of generator polynomial P. For segments of degree equal to P (i.e., Deg(M s )=Deg(P)) modulo units  32  or  42  may be replaced by an xor, as M s (modulo)P equals M s −P. 
   Here, CRC generator  50  includes multiplier  54 , accumulator  56 , and modulo unit  58 , which operate to obtain a CRC for message M separated into four segments  53 ,  55 ,  57  and  59  of a degree less than the degree of generator polynomial P (i.e., Deg(M s )&lt;Deg(P)). For example:
         if
           M=10111000, (M including 3 appended zero bits as in  FIG. 3  above)   s=4,   n=2, and   P=1001;   
           then
           M s−1 =M 3 =10=segment  53 ,   X n*(s−1) =X 6 =1000000,   M s−2 =M 2 =11=segment  55 ,   X n*(s−2) =X 4 =10000,   M s−3 =M 1 =10=segment  57 ,   X n*(s−3) =X 2 =100,   M s−4 =M 0 =00=segment  59 ,   X n*(s−4) =X 0 =001;   
           and       

   
     
       
         
           M 
           = 
           
             
               
                 10 
                 * 
                 1000000 
               
               + 
               
                 11 
                 * 
                 10000 
               
               + 
               
                 10 
                 * 
                 100 
               
               + 
               
                 00 
                 * 
                 001 
               
             
             = 
             10111000. 
           
         
       
     
   
   Multiplier  54  multiplies segments  53  to  59  by segment-constants C 3  to C 0  to obtain segment-remainders SR 3  to SR 0 . Segment-constants C 3  to C 0  may be obtained in advance or calculated ‘on the fly’ as described above. For example:
         if
           M=10111000, (from above)   P=1001,   s=4, and   n=2;   
           then       

   
     
       
         
           
             
               
                 
                   SR 
                   3 
                 
                 = 
                   
                 ⁢ 
                 
                   SR 
                   
                     i 
                     + 
                     3 
                   
                 
               
             
           
           
             
               
                 
                   C 
                   3 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     C 
                     
                       i 
                       + 
                       3 
                     
                   
                   = 
                   
                     
                       
                         X 
                         
                           2 
                           * 
                           3 
                         
                       
                       ⁡ 
                       
                         ( 
                         modulo 
                         ) 
                       
                     
                     ⁢ 
                     P 
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       1000000 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                     = 
                     001 
                   
                 
                 ; 
               
             
           
           
             
               
                 
                   SR 
                   2 
                 
                 = 
                   
                 ⁢ 
                 
                   SR 
                   
                     i 
                     + 
                     2 
                   
                 
               
             
           
           
             
               
                 
                   C 
                   2 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     C 
                     
                       i 
                       + 
                       2 
                     
                   
                   = 
                   
                     
                       
                         X 
                         
                           2 
                           * 
                           2 
                         
                       
                       ⁡ 
                       
                         ( 
                         modulo 
                         ) 
                       
                     
                     ⁢ 
                     P 
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       10000 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                     = 
                     010 
                   
                 
                 ; 
               
             
           
           
             
               
                 
                   SR 
                   1 
                 
                 = 
                   
                 ⁢ 
                 
                   SR 
                   
                     i 
                     + 
                     1 
                   
                 
               
             
           
           
             
               
                 
                   C 
                   1 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     C 
                     
                       i 
                       + 
                       1 
                     
                   
                   = 
                   
                     
                       
                         X 
                         
                           2 
                           * 
                           1 
                         
                       
                       ⁡ 
                       
                         ( 
                         modulo 
                         ) 
                       
                     
                     ⁢ 
                     P 
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       100 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                     = 
                     100 
                   
                 
                 ; 
                 and 
               
             
           
           
             
               
                 
                   SR 
                   0 
                 
                 = 
                   
                 ⁢ 
                 
                   SR 
                   i 
                 
               
             
           
           
             
               
                 
                   C 
                   0 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     C 
                     
                       i 
                       + 
                       0 
                     
                   
                   = 
                   
                     
                       
                         X 
                         
                           4 
                           * 
                           0 
                         
                       
                       ⁡ 
                       
                         ( 
                         modulo 
                         ) 
                       
                     
                     ⁢ 
                     P 
                   
                 
               
             
           
           
             
               
                 = 
                   
                 ⁢ 
                 
                   
                     001 
                     ⁢ 
                     
                       ( 
                       modulo 
                       ) 
                     
                     ⁢ 
                     1001 
                   
                   = 
                   001. 
                 
               
             
           
         
       
     
   
   Multiplier  54  multiplies M 3  by C 3 , M 2  by C 2 , M 1  by C 1 , and M 0  by C 0  to obtain segment-remainders SR 3  to SR 0 , since each message segment M s  equals its remainder R. For example:
         if
           M s−1 =M 3 =10, C i+3 =C 3 =001,   M s−2 =M 2 =11, C i+2 =C 2 =010,   M s−3 =M 1 =10, C i+1 =C 1 =100, and   M s−4 =M 0 =00, C i =C i0 =001;   
           then
           SR 3 =M 3 *C 3 =10*001=0010,   SR 2 =M 2 *C 2 =11*010=0110,   SR 1 =M 1 *C 1 =10*100=1000, and   SR 0 =M 0 *C 0 =00*001=0000.   
               

   Accumulator  56  adds segment-remainders SR 3  to SR 0  together to obtain accumulated-remainder AR. Here, accumulator  56  includes accumulators  56   a ,  56   b  and  56   c , where accumulators  56   a  and  56   b  compute temporary accumulations T 1  and T 0  and accumulator  56   c  combines temporary accumulations T 1  and T 0  to obtain accumulated-remainder AR. For example:
         if
           SR i+3 =SR 3 =0010, (from above)   SR i+2 =SR 2 =0110,   SR i+1 =SR 1 =1000, and   SR i =SR 0 0000;   
           then
           T 1 =0010+0110=0100;   T 0 =1000+0000=1000; and   AR=0100+1000=1100.   
               

   Finally, modulo unit  58  obtains a CRC for message M by moduloing accumulated-remainder AR by polynomial P. For example:
         if
           AR=1100, and (from above)   P=1001;   
           then
           CRC=AR(modulo)P=1100(modulo)1001=101;   
           where       

   
     
               
       
           
           
       
    
   
   Thus, CRC generator  50  obtains the same CRC for message M as calculated in the example in  FIG. 3  above without needing modulo units  32  or  42  of  FIGS. 3 and 4 . 
   Moduloing (e.g., ( 203 ) and ( 209 )) may also be accomplished by multiplying message M (or message segment M s ) by a reciprocal approximation D of generator polynomial P and subtracting that result from message M (or message segment M s ) to obtain a remainder R. Moduloing by multiplication by reciprocal approximator RA may be obtained based upon the following relationships:
         RA=X p+d /P;   M/P=M*RA*1/X p+ra  (for 0&lt;=Deg(M)&lt;=p+ra);   M=(M/P)*P+M(modulo)P;   R=M(modulo)P=M−(M/P)*P;   R=M(modulo)P=M−(M*D/X p+ra )*P
 
where X p+ra  is a polynomial having a most significant bit of degree p+ra (i.e. Deg(X p+ra )=p+ra); p is the degree of generator polynomial P (i.e., Deg(P)=p); ra is the degree of reciprocal-approximator RA (i.e., Deg(RA)=ra); and the degree of message M, for which remainder R is sought, is greater than zero and less than or equal to p+ra (i.e., 0&lt;Deg(M)&lt;=p+ra). For example:
   if
           M=10111000 (i.e., Deg(M)=7), and   P=1001 (i.e., Deg(P)=3).
 
then reciprocal-approximator RA would have a degree of at least four (4) for p+ra to be greater than or equal to the degree of M, here seven (7). Thus:
   
           if
           M=10111000 (i.e., Deg(M)=7),   P=1001 (i.e., Deg(P)=3); and;   ra=4;   
           then       

   
     
       
         
           
             
               X 
               
                 p 
                 + 
                 ra 
               
             
             = 
             
               10000000 
               ⁢ 
               
                 ( 
                 
                   
                     i 
                     . 
                     e 
                     . 
                   
                   , 
                   
                     
                       Deg 
                       ⁡ 
                       
                         ( 
                         
                           X 
                           
                             p 
                             + 
                             ra 
                           
                         
                         ) 
                       
                     
                     = 
                     7 
                   
                 
                 ) 
               
             
           
           , 
           and 
         
       
     
     
       
         
           
             
               
                 D 
                 = 
                   
                 ⁢ 
                 
                   
                     
                       X 
                       
                         p 
                         + 
                         ra 
                       
                     
                     / 
                     P 
                   
                   = 
                   
                     
                       X 
                       
                         3 
                         + 
                         4 
                       
                     
                     / 
                     1001 
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       10000000 
                       / 
                       1001 
                     
                     = 
                     10010 
                   
                 
                 ⁢ 
                 
                     
                 
                 ; 
               
             
           
         
       
     
       
       
         
           where 
         
       
     
  
   
     
               
       
           
           
       
    
   
   Modulo unit  60  may calculate reciprocal-approximator RA prior to receiving message M and store RA in memory  69  since both generator polynomial P and the degree of message M are known prior to receiving message M. In other embodiments, reciprocal-approximator RA may be built in or obtained ‘on-the fly’ by modulo unit  60  after receiving message M. Once the form of the polynomial is fixed, the implementation of the corresponding hardware may be simplified considerably. 
   To obtain remainder R for message M modulo unit  60  includes multiplication unit  62 , truncation unit  64 , multiplication unit  66  and subtraction unit  68  where:
         T 0 =M*RA is performed by unit  62 ,   T 1 =T 0 /X p+ra  is performed by unit  64 ,   T 2 =T 1 *P is performed by unit  66 , and   R=M−T 2  is performed by unit  68 .       

   Multiplication unit  62  receives message M and multiplies M by reciprocal-approximator RA to obtain temporary result T 0 . For example:
         if
           M=10111000, (from  FIG. 3  above)   P=1001, and   RA=10010;   
           then       

   
     
       
         
           
             
               T 
               0 
             
             = 
             
               
                 M 
                 * 
                 RA 
               
               = 
               
                 
                   10111000 
                   * 
                   10010 
                 
                 = 
                 101011110000 
               
             
           
           ⁢ 
           
               
           
           ; 
         
       
     
       
       
         
           where 
         
       
     
  
   
     
               
       
           
           
       
    
   
   Multiplication unit  62  provides temporary result T 0  to truncation unit  64 , which divides T 0  by X p+ra , here 10000000, to obtain truncated result T 1 . In other embodiments, truncation unit  64  may remove the p+ra least significant bits of temporary result T 0  without dividing by X p+ra  to obtain truncated result T 1 . For example:
         if
           P=3,   ra=4, and   T 0 =101011110000;   
           then
           p+ra=7, and   T 1 =10101.
 
Thus for p+ra equaling seven (7), the seven (7) least significant bits, here 1110000, are removed from T 0  to obtain T 1 .
   
               

   Truncation unit  64  provides truncated result T 1  to multiplication unit  66 , which multiplies T 1  by generator polynomial P to obtain temporary result T 2 . For example;
         if
           P=1001, and   T 1 =10101;   
           then
           T 2 =T 1 *P=10101*1001
               =10111101   
               
           where       

   
     
               
       
           
           
       
    
   
   Multiplication unit  66  provides temporary result T 2  to subtraction unit  68 , which subtracts T 2  from message M to obtain remainder R. For example:
         if
           M=10111000, and (from above)   T 2 =10111101;   
           then
           R=M−T 2 =101   
           where       

   
     
               
       
           
           
       
    
   
   Thus, modulo unit  60  obtains remainder R for message M using multiplication by reciprocal approximation. Hence, modulo unit  60  may calculate the CRC for the entire message M on its own, or may be incorporated into CRC generators  30  and  40  to obtain remainders R for message segments M s . 
   For example,  FIG. 7  shows an implementation of the CRC generator in  FIG. 3  employing modulo unit  60  in  FIG. 6 . Here, modulo units  60  are show as MH (M, RA, P). For example:
         if
           M=10111000, (Same as in  FIG. 3  above)   s=2,   n=4, and   P=1001;   
           then M may be separated as
           M s−1 =M 1 =1011=segment  73     X n*(s−1) =X 4 =10000,   M s−2 =M 0 =1000=segment  75     X n*(s−2) =X 0 =00001;   
           where
           M=1011*10000+1000*00001=10111000.   
               

   CRC generator  70  obtains a CRC for message M based on generator polynomial P, where the CRC for message M is the remainder of message M divided by polynomial P. 
   CRC generator  70  includes modulo unit  72 , multiplier  74 , accumulator  76 , and modulo unit  78 . Here, modulo unit  72  includes modulo units  72   a  and  72   b , which multiply message segments  73  and  75  by a reciprocal approximation of generator polynomial P to obtain remainders R i+1  and R i . 
   Modulo unit  72   a  multiplies message segment  73  by reciprocal-approximator RA of generator polynomial P to obtain a remainder R as shown in  FIG. 6 . For example:
         if
           M=10111000,   M s−1 =M 1 =1011=segment  73 ,   M s−2 =M 0 =1000=segment  75 ,   Deg(M s−1 )=3   Deg(M s−2 )=3   P=1001, and   RA=X p+ra /P=X 3+1 /P, so that p+ra is greater than or equal to the degree of each message segment M s−1  and M s−2 ;   
           then
           RA=X 3+1 /P=10000/1001=10;   
           where       

   
     
               
       
           
           
       
    
       
       
         
           and
           T 0(i+1) =M s−1 *RA=1011*10=10110,   T 0(i) =M s−2 *RA=1000*10=10000,   T 1(i+1) =T 0(i+1) /X 3+1 =10110/10000=1,   T 1(i) =T 0(i) /X 3+1 =10000/10000=1,   T 2(i+1) =T 1(i+1) *P=1*1001=1001,   T 2(i) =T 1(i) *P=1*1001=1001,   R i+1 =M s−1 −T 2(i+1) =1011−1001=010   R i =M s−2 −T 2(i) =1000−1001=001.   
         
         
       
     
  
   Hence, modulo units  72   a  and  72   b  obtain the same remainders R i+1  and R i  as modulo units  32   a  and  32   b  in  FIG. 3  above. 
   Multiplier  34  multiplies R i+1  and R i  by segment-constants C i+1  and C i  to obtain segment-remainders SR i+1  and SR i . Here, segment-constants C i+1  and C i  are obtained ‘on the fly’ by moduloing the position X of segments 33 and 35 in message M by generator polynomial P (i.e., C i+1 =X n*(i+1) (modulo)P and C i =X n*i (modulo)P) using modulo unit  60  described in  FIG. 6 . For example:
         if
           X n*(i+1) =X 4*(1) =M 1 =10000,   X n*i =X 4*(0) =M 0 =00001,   Deg(X 4*(1) )=4,   Deg(X 4*(0) )=0,   P=1001, and   RA=X p+ra /P=X 3+1 /P, so that p+ra is greater than or equal to the degree of each message segment X 4*(1)  and X 4*(0) ;   
           then
           RA=10000/1001=10;   
           and
           T 0(i+1) =M 1 *RA=10000*10=100000,   T 0(i) =M 0 *RA=00001*10=000010,   T 1(i+1) =T 0(i+1) /X 3+1 =100000/10000=10,   T 1(i) =T 0(i) /X 3+1 =000010/10000=0,   T 2(i+1) =T 1(i+1) *P=10*1001=10010,   T 2(i) =T 1(i) *P=0*1001=00000,   C i+1 =M 1 −T 2 (i+1) =10000−10010=010,   C i=M   0 −T 2(i) =00001−00000=001.   
               

   In other embodiments segment-constants C i+1  and C i  may be obtained in advance in stored in a memory unit (e.g.  39 ). 
   Multiplier  74  includes multipliers  74   a  and  74   b . Multiplier  74   a  multiplies remainder R i+1  by segment-constant C i+1  to obtain segment-remainder SR i+1 . Multiplier  74   b  multiplies R i  by segment constant C i  to obtain segment-remainder SR i . For example:
         if
           R i+1 =010, C i+1 =010 and (from above)   R i =001, C i =001;   
           then
           SR i+1 =R i+1 *C i+1 =010*010=00100, and   SR i =R i *C i =001*001=00001;   
               

   Accumulator  76  adds segment-remainders SR i+1  and SR i  together to obtain accumulated-remainder AR. For example:
         if
           SR i+1 =SR 1 =00100,   SR i =SR 0 =00001;   
           then
           AR=00100+00001=00101.   
               

   Modulo unit  78  obtains a CRC for message M by moduloing accumulated-remainder AR by generator polynomial P. Here, modulo unit  78  obtains the CRC by using multiplication by reciprocal approximation shown in  FIG. 6 . For example:
         if
           AR=M=00101,   Deg(AR)=2   P=1001, and   RA=X p+ra /P=X 3+1 /P so that p+ra is greater than or equal to the degree of the message for which a remainder is desired, here AR;   
           then
           RA=10000/1001=10;   
           and
           T 0 =M*RA=00101*10=1010,   T 1 =T 0 /X 3+1 =1010/10000=0,   T 2 =T 1 *P=0*1001=0,   R=CRC=M−T 2 =00101−0=101.   
               

   Thus CRC generator  70  obtains the same CRC the example for CRC generator  30 . Likewise, CRC generator  70  may also be expanded to include enough components for obtaining the CRC for message M separated into N segments. 
   CRC generator  80  ( FIG. 8 ) includes subtraction unit  82 , modulo unit  84  and accumulator  86  for updating a CRC of a message M adjusted during transmission. Subtraction unit  82  subtracts old message  83  from new message  85  to obtain difference D. For example:
         if       

   
     
               
       
           
           
       
    
       
       
         
           then
           D=M new −M old =00110000   
         
           wherein 
         
       
     
  
   
     
               
       
           
           
       
    
   
   Modulo unit  84  modulos difference D by generator polynomial P to obtain a difference-remainder DR. For example:
         if
           P=1001, and   D=00110000;   
           then
           DR=D(modulo)P=MOD(D, P)=   
           wherein       

   
     
               
       
           
           
       
    
   
   In other embodiments, difference-remainder DR may be obtained using multiplication by reciprocal-approximator RA (i.e. MH (D, RA, P)). 
   Accumulator  86  adds difference-remainder DR and CRC old  to obtain a CRC new . For example:
         if
           CRC old =101 and   DR=110;   
           then       

   
     
       
         
           
             
               
                 
                   CRC 
                   new 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     
                       CRC 
                       old 
                     
                     + 
                     DR 
                   
                   = 
                   
                     101 
                     + 
                     110 
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   011 
                 
                 ; 
               
             
           
         
       
     
       
       
         
           where 
         
       
     
  
   
     
               
       
           
           
       
    
   
   The accuracy of this CRC new  may be confirmed by replacing CRC old  in the adjusted message M new  with CRC new  and determining whether M new (modulo)CRC new  equals zero. For example: 
   
     
       
         
           
             
               
                 
                     
                 
                 ⁢ 
                 101 
               
             
           
           
             
               
                 
                   + 
                   110 
                 
                 _ 
               
             
           
         
       
     
     
       
         
           
               
           
           ⁢ 
           
             011 
             = 
             
               
                 CRC 
                 new 
               
               . 
             
           
         
       
     
   
   CRC generator  90  ( FIG. 9 ) includes subtraction unit  92 , modulo unit  94 , multiplier  96 , modulo unit  98  and accumulator  99  for updating a CRC of a message M adjusted during transmission. CRC generator  90  differs from generator  80  in that it adjusts the CRC of a message M based on the adjusted segment of the message. 
   Subtraction unit  92  subtracts old message segment  93  from new message segment  95  to obtain difference-segment DS. For example:
         if
           P=1001,   n=2   s=4   
               

   
     
               
       
           
           
       
    
       
       
         
           then
           DS=M s−2(new) −M s−2(old) =00−11=11.   
         
         
       
     
  
   Modulo unit  94  modulos difference-segment DS by generator polynomial P to obtain a difference-segment-remainder DSR. For example:
         if
           P=1001, and   DS=11;   
           then
           DSR=DS(modulo)P=MOD(DS, P)=11   
           wherein       

   
     
               
       
           
           
       
    
   
   Here, as above, if the difference-segment DS is of a lesser degree than polynomial P, modulo unit  94  is not needed since the modulo of DS equals DS. 
   Multiplier  96  multiplies difference-segment-remainder DSR by an appropriate segment-constant C i  to obtain an expanded segment-remainder ESR. Segment-constants C 3  to C 0  for this example may be obtained as described above. For example:
         if
           DSR=(M 2new −M 2old )(modulo)P=11   
           and       

   
     
       
         
           
             
               
                 
                   C 
                   i 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     C 
                     2 
                   
                   = 
                   
                     
                       
                         X 
                         
                           2 
                           * 
                           2 
                         
                       
                       ⁡ 
                       
                         ( 
                         modulo 
                         ) 
                       
                     
                     ⁢ 
                     P 
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       10000 
                       ⁢ 
                       
                         ( 
                         modulo 
                         ) 
                       
                       ⁢ 
                       1001 
                     
                     = 
                     010 
                   
                 
                 ; 
               
             
           
         
       
     
       
       
         
           then
           EDR=DSR*C i =11*010=110.   
         
         
       
     
  
   Modulo unit  98  obtains message difference-remainder DR by moduloing the extended difference-remainder by generator polynomial P. For example:
         if
           P=1001 and   EDR=110;   
           then
           DR=110.   
               

   Again, for extended difference-remainders of a degree less than the degree of polynomial P the DR is the EDR. 
   Finally, accumulator  99  adds the message difference-remainder DR and CRC old  to obtain a CRC new . For example:
         if
           CRC old =101 and   DR=110;   
           then       

   
     
       
         
           
             
               
                 
                   CRC 
                   new 
                 
                 = 
                   
                 ⁢ 
                 
                   
                     
                       CRC 
                       old 
                     
                     + 
                     DR 
                   
                   = 
                   
                     101 
                     + 
                     110 
                   
                 
               
             
           
           
             
               
                 
                   = 
                     
                   ⁢ 
                   011 
                 
                 ; 
               
             
           
         
       
     
       
       
         
           wherein 
         
       
     
  
   
     
       
         
           
             
               
                 
                     
                 
                 ⁢ 
                 101 
               
             
             
               
                   
               
             
             
               
                   
               
             
           
           
             
               
                 
                   + 
                   
                       
                   
                   ⁢ 
                   110 
                 
                 _ 
               
             
             
               
                   
               
             
             
               
                   
               
             
           
           
             
               
                 
                     
                 
                 ⁢ 
                 011 
               
             
             
               = 
             
             
               
                 
                   CRC 
                   new 
                 
                 . 
               
             
           
         
       
     
   
   All of the above algorithms may be affected by embedding generator polynomial P in a larger ring. For example, let
 
 F=P*Q; 
 
   where F is a field extension of P, Q is an extender, and the greatest common denominator between P and Q is one (1). Segment-constants C may now be calculated using field extension F, instead of p, and message segments Ms increased in size (by bit) accordingly without requiring the additional modulos  42  and  42  in  FIGS. 3 and 4  above. Rather, only modulo by P, as shown in  FIG. 5  may be needed. 
     FIG. 10  shows a general-purpose computer  100  for obtaining a CRC using process  20  or any of the operations of the CRC generator units  30 ,  40 ,  50 ,  60 ,  70 ,  80  and  90  shown above. Computer  100  includes a processor  102  (e.g. a CPU), a storage medium  104  (e.g., a random access memory) and communication interface  106  (e.g., a network card) having one or more external connections  106   a ,  106   b  and  106   c  for sending and receiving data transmissions. Storage medium  104  stores computer instructions  108  for obtaining a CRC via process  20  or the operations of the CRC generator units described above. In one embodiment, computer  100  obtains a CRC for a message M based on multiplication by reciprocal approximation. 
   Process  20  and the operations of the CRC generators shown above, however, are not limited to use with any particular hardware or software configuration; they may find compatibility in any computing or processing environment. Process  20  may be implemented in hardware, software, or any combination of the two. So too, may the operations of the CRC generator units  30 ,  40 ,  50 ,  60 ,  70 ,  80  and  90 . 
   Process  20  and the CRC generators described above may be implemented in computer programs executing on programmable computers that each include a processor, a storage medium readable by the processor (e.g. volatile memory, non-volatile memory, etc.), one or more input devices, and one or more out devices. Program code may be applied to data entered using an input device to perform process  20  or any of the operations of the CRC generators described above. The output information may be applied to one or more output devices, such as screen  110 . 
   Each such program may be implemented in a high level procedural or object-oriented programming language to communicate with a computer system. However, the programs can be implemented in assembly or machine language. The language may be a compiled or an interpreted language. 
   Each computer program may be stored on an article of manufacture, such as a CD-ROM, hard disk, or magnetic diskette, that is readable by computer  100  to obtain a CRC for message M in the manners described above. Process  20  and the operations for implementing the CRC generators above may also be implemented as a machine-readable storage medium, configured with one or more computer programs, where, upon execution, instructions in the computer program(s) cause the processor  102  to operate as described above. 
   A number of embodiments of the invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. For example, message M may be divided into an odd number of segments or segment sizes or field extensions F may be substituted for generator polynomial P were appropriate. Accordingly, other embodiments are within the scope of the following claims.