Abstract:
The specification relates to a method and an apparatus for generating cyclical redundancy code (CRC) by analyzing segmented groups of bits from a message concurrently, producing a temporary remainder value as a result of a multiple bit lookup from a generating CRC lookup table, using the temporary remainder or a portion thereof along with the next sequential segmented group of message bits as exclusive-or inputs, taking the result of the exclusive-or output and applying the result as a lookup value from the generating CRC lookup table. The process is repeated until the message groups have been depleted, at which time the message is completely coded and the temporary remainder existing at the time represents the CRC checkbits for the message. The recursive method developed in association with the present invention is called a Recursive Syndrome Expansion (RSE).

Description:
FIELD OF THE INVENTION 
     The present invention relates to the field of data transmission error control coding, and more particularly to methods for generating cyclical redundancy code (CRC) in message groups rather than bitwise. 
     BACKGROUND OF THE INVENTION 
     Digital information transmitted from a sending station to a receiving station may be protected from errors by developing code related to the individual bits comprising a message, appending the code to the original message and transmitting the message and the code to the receiving station, and then generating code at the receiving station to check for corrupted data. Because the code is related to the original message bits through a generating polynomial, the code bits are considered redundant to the message bits used to generate them. Therefore, a process which uses polynomial division to generate redundant bits is referred to as cyclical redundancy code (CRC). Typically, messages are coded bitwise in hardware, the CRC generating polynomial function provided for by utilizing linear feedback shift registers. 
     CRC generation in software utilizes CRC generating lookup tables, instead of shift registers, to generate the applicable CRC code. Message bits are analyzed and compared to a CRC value contained in the CRC generating lookup table, the corresponding value representing the CRC checkbit value that is appended to the original message. However, CRC generation in software is inherently slower than the hardware implementation, even when performed over several message bits concurrently. Further, prior art methods for CRC generation in software are subject to the restriction that the degree of the generating polynomial cannot exceed the size of the message unit to which it is applied. 
     SUMMARY OF THE INVENTION 
     The present invention is a method and an apparatus for generating cyclical redundancy code (CRC) by analyzing segmented groups of bits from a message concurrently, producing a temporary remainder value as a result of a multiple bit lookup from a generating CRC lookup table, using the temporary remainder or a portion thereof along with the next sequential segmented group of message bits as exclusive-or inputs, taking the result of the exclusive-or output and applying the result, as a lookup value, to the generating CRC lookup table. The process is repeated until the message groups have been depleted, at which time the message is completely coded and the temporary remainder existing at the time represents the CRC checkbits for the message. The recursive method developed in association with the present invention is dubbed a Recursive Syndrome Expansion (RSE). 
     Although the present invention is particularly well suited for error detection and correction within cellular and PCS wireless networks, it is also equally applicable to other digital data and multimedia communication networks, including, but not limited to, optical fiber, coaxial cable, and hybrid fiber/coax networks, public switched telephone networks (PSTN), and wireless broadcast and satellite networks. 
     Advantageously, the present invention and its incorporation of RSE within its implementation provides for high speed CRC creation, at little or no additional expense for additional circuitry or components in an implementing configuration, with flexibility as to size of the generating polynomial, the size of each segmented group considered, and the relative size between the generating polynomial and the segmented groups, and with flexibility for implementation mode, especially when the invention is implemented in software. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     A more complete understanding of the present invention may be obtained from consideration of the following description in conjunction with the drawings in which: 
     FIG. 1 is a flow chart illustrating the functional steps relating to the application of cyclical redundancy code at a source and a destination as utilized in accordance with the present invention; 
     FIG. 2 is a flow chart illustrating the functional steps for generating cyclical redundancy code as performed in accordance with the present invention; 
     FIG. 3 is an illustration of an exemplary embodiment of the present invention utilizing a cyclical redundancy code length smaller than the length of the message group to which it is applied and implemented within a four table lookup scheme; 
     FIG. 4 is an illustration of an exemplary embodiment of the present invention utilizing a cyclical redundancy code length greater than the length of the message group to which it is applied and implemented within a two table lookup scheme; and 
     FIG. 5 is an illustration of an exemplary embodiment of the present invention utilizing bit multipliers to achieve degree alignment between a code remainder and the data bits being coded and checked. 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 is a flow chart illustrating the functional steps relating to the application of cyclical redundancy code at a source and a destination as utilized in accordance with the present invention. In step  110 , and after initially establishing a link and negotiating parameters, a transmitting source processes digital data in the form of messages. In step  115 , and prior to transmission, the source generates a CRC syndrome from a message of a predetermined unit size, in accordance with FIG. 2 (description to follow). In step  120 , the generated syndrome is then appended to the message data and transmitted to the destination. In step  125 , the message and syndrome are received at the destination and initial signal processing is commenced in accordance with step  130 . In step  135 , the destination then independently performs a CRC calculation in accordance with FIG. 2 (description to follow) using the same generating polynomial utilized to generate the CRC syndrome at the source. 
     The syndrome generated at the destination is then compared with the syndrome received at the destination, in accordance with step  140 . If the two syndromes match, then the received data message is accepted as non-corrupted and the data message is further processed at the destination for use, in accordance with step  145 . However, if the syndrome generated at the destination and the syndrome received at the destination are contradictory, then the decision process associated with step  150  is invoked. That is, utilization of a CRC scheme enables error detection and error correction at the destination. However, some schemes utilize only the error detection capabilities of CRC without invoking the corrective capabilities. Often this scheme is utilized when the accuracy of any particular data message is not of paramount importance, such as with the synchronous nature of data transmission for voice, audio, or video. When CRC is utilized for error detection without error correction, the size of the CRC syndrome needed to accurately detect an error is smaller than the size of the CRC syndrome needed to detect and correct an error. Additionally, even when a CRC scheme is utilized to detect and correct errors, if an error is detected which contains a number of bit errors beyond the capabilities for correction by a given CRC length, the data is not recoverable. Therefore, if data errors are detected, an error correction scheme is implemented, and the quantity of bit errors does not exceed the corrective capabilities for the length of the CRC syndrome utilized, then the corrupted data message is corrected and the data message is further processed at the destination for use, in accordance with step  155 . However, if the data is not correctable, either because an error correction scheme is not implemented or because the detected quantity of bit errors exceeds the corrective capabilities for the length of the CRC syndrome utilized, then the bifurcation of step  160  results. That is, if the accuracy of an uncorrectable data message is essential, a retransmit request is sent to the source, in accordance with step  165 . If, however, the accuracy of an uncorrectable data message is not essential, as is the case with data messages of a synchronous nature (such as voice, audio, or video), then the corrupted and uncorrectable data message is discarded and the next sequential data message is processed, in accordance with step  170 . 
     FIG. 2 is a flow chart illustrating the functional steps for generating CRC as performed in accordance with the present invention. However, a supporting mathematical basis and proof are presented prior to the detailed description supporting FIG.  2 . Computation of a CRC syndrome for a data message, in accordance with the present invention, is performed by mathematically representing the data message as a polynomial with bit position i indexing the coefficients of the x i−1  terms. The message polynomial (M(x)) is therefore described by:                M        (   x   )       =       ∑     i   =   0       N   -   1              x   i     ·     m   i                 [   1   ]                                
     where m i  is assigned the value of zero or one as a coefficient for each exponential term represented by the message polynomial. The value of N is determined by the length of each message polynomial over which a CRC syndrome is calculated. Therefore, each data message for which CRC checkbits are calculated, in accordance with the present invention, is represented as a message polynomial of degree N. 
     A predetermined generator polynomial (G(x)) is used to compute the CRC syndrome, and therefore, each of the CRC checkbits, with:                G        (   x   )       =       ∑     k   =   0     r            x   k     ·     g   i                 [   2   ]                                
     where g i  is assigned the value of zero or one as a coefficient for each exponential term represented by the generator polynomial and depending upon a selection of a specific generator polynomial to determine each appropriate g i  value. Therefore, the degree of generator polynomial G(x) is r. Rather than compute the CRC syndrome N bits at a time (that is, computation of the syndrome considering each bit of the message simultaneously), the present invention calculates p bits at a time, thus minimizing the required storage for a checkbit lookup table. Therefore, the message polynomial M(x) can be written as:                M        (   x   )       =       ∑     i   =   0       k   -   1                x   _     i     ·     x     i   *   p                   [   3   ]                                
     where the polynomial consists of (k−1) terms, each term being p bits in length, so that 
     
       
         N= k*p   [4] 
       
     
     and each group of p bits is represented by                  x   _     i     =       ∑     l   =   0       p   -   1              x   l     ·     m   j                 [   5   ]                                
     where 
     
       
           j =[( i*p )+ l]   [6] 
       
     
     Equation [1] can therefore be rewritten as: 
     
       
         M( x )=   x     0   +x   p (   x     1   + x     p ( x   2   +x   p ( . . . + x   p (   x     k−2   +x   p ( x   k−1 ) . . . )  [7] 
       
     
     The syndrome operator is represented by the symbol S[ ], where                S        [     f        (   x   )       ]       =     ⌊         x   r     ·     f        (   x   )           G        (   x   )         ⌋             [   8   ]                                
     Implementation of the present invention for generation of CRC checkbits (that is, the coefficients representing the syndrome polynomial) utilizes two properties applicable to binary polynomials; (i) the property of linearity and (ii) an asserted property. The linearity property is represented by the relationship 
     
       
         S[ƒ( x )+ g ( x )]=S[ƒ( x )]+S[ g ( x )]  [9] 
       
     
     meaning that the syndrome of the sum of two functions is equal to the sum of the syndrome of the first function with the syndrome of the second function. The property of linearity is an established property, as would be apparent to those skilled in the art. The asserted property, with developed proof subsequently provided, is represented by the claim that: 
     
       
         S[ƒ( x )· g ( x )]=S[ƒ( x )·S[ g ( x )]]  [10] 
       
     
     which is described by the expression “the syndrome of the product of two binary polynomials is equal to the syndrome of the product of the first polynomial and the syndrome of the second polynomial.” 
     Let 
     
       
         ƒ( x )=Q( x )·G( x )+S[ƒ( x )]  [11] 
       
     
     where Q(x) is a quotient polynomial. Multiplying both sides of equation [11] by g(x) results in 
     
       
           g ( x )·ƒ( x )= g ( x )·Q( x )·G( x )+ g ( x )·S[ƒ( x )]  [12] 
       
     
     Applying the syndrome operator to both sides of equation [12] gives 
     
       
         S[ g ( x )·ƒ( x )]=[0]+S[ g ( x )·S[ƒ( x )]]  [13] 
       
     
     since S[ ] is a linear operator and because the term [g(x)·Q(x)·G(x)] is divisible by G(x) without a remainder (since Q(x), the quotient function, is represented as a factor). Therefore, applying equations [9] and [10] to equation [7] 
     
       
         S[ x   r M( x )]=S[ x   r (   x     0   +x   p (   x     1   +x   p (   x     2   + x     p ( . . . + x   p (   x     k−2   +x   p (   x     k−1 ) . . .)]  [14] 
       
     
     
       
         =S[ x   r     x     0   +x   p ( x   r     x     1   +x   p ( . . . +( x   r     x     k−2   +x   p ( x   r     x     k−1 ) . . . )]  [15] 
       
     
     
       
         =S[ x   r     x     0   +x   p S[ x   r     x     1   +x   p S[ . . . +S[ x   p S[ x   r     x     k−2   +x   p S[ x   r     x     k−1 ]. . . ]  [16] 
       
     
     Advantageously, the terms of equation [16] represent the steps, as utilized in accordance with the present invention, for a systematic methodology of determining the syndrome (and thus generating the checkbits) from a data message of arbitrary length through computations performed on p bits of data concurrently and with an equivalent generator polynomial of degree r. The process of calculating CRC group checkbits concurrently and utilizing prior calculated group checkbits as a factor affecting sequential calculations within a common message in accordance with the present invention is called a Recursive Syndrome Expansion (RSE). 
     Since the mathematical basis and proofs supporting implementation of the present invention have been described, attention is now directed to FIG.  2  and the accompanying detailed description. The procedure for generating CRC checkbits is equivalent whether performed at a source or a destination. Therefore, although the following description refers to steps performed at a source prior to transmitting data messages with appended CRC checkbits, it is understood that the same procedure applies equally for CRC checkbit generation at the receiving destination. When a source attempts to transmit a data message and appended CRC checkbits to a destination, the destination must generate CRC checkbits utilizing the same generating polynomial (or equivalent checkbit lookup tables) as used by the source when generating the appended checkbits. Then, in accordance with step  210 , the values for data message length, the group bit size (p) for a data message which are concurrently considered, the generating polynomial degree (r), the quantity, length, and width of the generating checkbit lookup tables, and the generator implementing geometric structure must be understood and shared by the source and destination. Various alternative embodiments of the present invention are possible for sharing and understanding these key parameters, as would be apparent to those skilled in the art. In one embodiment of the present invention, each of the values and parameters described is fixed at both source and destination, so that negotiation between the source and destination is not required prior to commencing data message transmission. Another alternative embodiment of the present invention presupposes no initial shared understanding between source and destination regarding data message length, p, r, the quantity, length, or width of the generating checkbit lookup tables, or the implementing geometric structure of the generator. Also, while the values for r and the specific generator, G(x), need to be shared (at some point prior to production of CRC checkbits) between the transmitter and receiver, the specific value for p can be independently chosen by the transmitter and receiver. Therefore, negotiations fixing these parameters are conveyed between source and destination prior to data message transmission. Yet other alternative embodiments maintain one or more of these initializing parameters fixed, thus providing flexibility by allowing each of the other requisite parameters to be negotiated during preliminary transmissions between source and destination (and prior to data message transmission). 
     In step  215 , bits from a data message, N bits in length, are segmented into groups of size p bits, resulting in k groups, represented by  x   k−1  to  x   0 . The convention utilized in conjunction with an embodiment of the present invention assigns  x   0  as the group of least significant bits, whereas  x   k−1  is assigned as the group of most significant bits for a particular data message (M(x)). Equation [7] is an expression for the data message when segmented into groups. Indexing variable (q) is set equal to the value of (k−1), in accordance with step  220 . The product  x   q ·x r  is produced in accordance with step  225 . Since q is initially set equal to (k−1), the group represents the most significant bits group of least significant bits of M(x). The syndrome is then generated in accordance with step  230 . Syndrome generation, in accordance with the present invention, is accomplished utilizing checkbit lookup table(s). In the simplest embodiment of the present invention, table checkbit lookup values are provided in one table for each possible sequence represented by the coefficients of  x   q ·x r , and therefore the implementing lookup table contains 2 (q+r)  entries. The value assigned to r is not restricted in relation to the message size and therefore r may be equal to, greater than, or less than the parallelism (implementation group size) desired. Each of the 2 (q+r)  entries is of length r bits. However, other efficacious configurations utilizing a plurality of tables are also contemplated, as is subsequently described in conjunction with several alternative embodiments of the present invention. 
     A remainder value (data message checkbits), R, is then set equal to the coefficients of the syndrome generated from the  x   k−1  group, in accordance with step  235 . The value of q is then examined in accordance with step  240 . If q is equal to zero, then checkbit generation is complete, R is appended to the respective generating data message, and the next sequential data message is considered for CRC generation. The value of q is equal to zero while performing step  240  only when N≦p, that is, when the implementing group length is less than or equal to the data message length. If the value of q is not equal to zero, then in accordance with step  250 , the value of q is decremented. In step  255 , x r  is multiplied by  x   q , R is multiplied by x p , the resulting products are summed, and the syndrome of the sum is generated, as was previously performed, via checkbit lookup table(s). The remainder value, R, is then set equal to the coefficients of the syndrome generated from the  x   q  group, in accordance with step  260 . The value of q is then examined in accordance with step  265 . If q is equal to zero, then checkbit generation is complete, R is appended to the respective generating data message, and the next sequential data message is considered for CRC generation. If, however, the value of q is not equal to zero, then a recursive loop is entered, commencing with step  250  during which the value of q is again decremented. The recursive sequence, comprised of steps  250 ,  255 ,  260 , and  265 , is continued until the value of q equals zero, at which time the loop is exited, R is appended to the respective generating data message, and the next sequential data message is considered for CRC generation. This recursive sequence, in conjunction with the initial group syndrome calculation for  x   k−1 , represents the method steps which implement a RSE, in accordance with equation [16]. 
     FIGS. 3,  4 , and  5  represent three illustrative embodiments of the present invention utilizing table lookup based implementations and demonstrating the invention&#39;s flexibility in that CRC length (r) may be greater than, less than, or equal to the parallelism of the implementation (p), and that group sizes other than those which are integral multiples of an octet may be contemplated. They are illustrative embodiments only, and not exhaustive, since a recursive syndrome expansion, in accordance with equation [16], allows any arbitrary parallel implementation once a CRC size is established, as would be apparent to those skilled in the art. 
     FIG. 3 is a representation of an exemplary embodiment of the present invention utilizing a cyclical redundancy code length smaller than the length of the message group to which it is applied and implemented within a four table lookup scheme. CRC computations for message M(x)  310  are performed by considering a plurality of message data bits concurrently. The instant embodiment considers message data bits in groups sized 32 bits in length (that is, p=32). However, the instant embodiment also segments groups into four subgroups, each operated upon concurrently, with each subgroup comprised of eight bits. Subgroups are represented according to indexing variable I, with subgroup [I+3]  312 , subgroup [I+2]  314 , subgroup [I+1]  316 , and subgroup [I]  318  shown, subgroup [I] representing the least significant bits and subgroup [I+3] representing the most significant bits for those subgroups shown. Prior subgroups ([I+1],[I+2], . . . ), not shown, have been processed as message bits of lessor significance in a prior recursion. Subsequent subgroups ([I+4],[I+5], . . . ), also not shown, represent message bits of greater significance and are processed in a subsequent recursion. Message data bits are CRC generation seeds for a checkbit lookup unit  330 , which is comprised of four individual implementation tables; T 1   338 , T 2   336 , T 3   334 , and T 4   332 . Subgroup bits are read from the appropriate message subgroup and corresponding checkbit values are set, depending upon the incoming subgroup bit values. Therefore, bit values from subgroup [I]  318  provide the seed value for a lookup from table T 1   338 , bit values from subgroup [I+1]  316  provide the seed value for a lookup from table T 2   336 , bit values from subgroup [I+2]  314  provide the seed value (after an exclusive-or operation with a prior recursion remainder, R 1 , at an interveningly coupled [I+2] EXOR gate  324 ) for a lookup from table T 3   334 , and bit values from subgroup [I+3]  312  provide the seed value (after an exclusive-or operation with a prior recursion remainder, R 2 , at an interveningly coupled [I+3] EXOR gate  320 ) for a lookup from table T 4   332 . Each table stores entries for a total of 256 checkbit lookup values, since each table is implemented with an eight bit lookup seed. The instant embodiment of the present invention generates a sixteen bit CRC (sixteen checkbits) for each respective lookup seed, therefore r=16. As a programmed alternative to hardware CRC, table checkbit storage is accomplished within any of a number of alternative storage devices and components including, but not limited to, RAM, ROM, magnetic or optical storage devices, PROM or EPROM, fixed component memory, or any other memory devices deemed appropriate for a given application, as would be apparent to those skilled in the art. 
     The checkbit lookup unit  330  is coupled to an Exclusive-Or (EXOR) unit  340  and each group of sixteen checkbits generated are transmitted thereover. The instant embodiment of the EXOR unit  340  is comprised of three EXOR gates. A first EXOR gate  342  is coupled to the output from tables T 3  and T 4  and accepts thereover each sequential group of sixteen checkbits generated, performs an exclusive-or operation on a bit by bit basis between the T 4  and T 3  checkbits, and returns a sixteen bit value in response. A second EXOR gate  344  is coupled to the output from tables T 2  and T 1  and accepts thereover each sequential group of sixteen checkbits generated, performs an exclusive-or operation on a bit by bit basis between the T 2  and T 1  checkbits and returns a sixteen bit value in response. A third EXOR gate  348  is coupled to the output of the first and second EXOR gates, accepts each sequential group of sixteen checkbits generated from each, performs a bitwise exclusive-or comparison and yields a remainder, R, as a result. The value of R is recomputed during each recursion. The EXOR unit  340  output is coupled to a R storage and segmenting device  350 . The storage function of the R storage and segmenting device  350  is used to store the prior calculated recursion value of R for use in the next CRC recursion calculation. Therefore, a shift register or bubble memory device are typically used to implement the storage function, although RAM, ROM, magnetic or optical storage devices, PROM or EPROM, fixed component memory, or any other memory devices deemed appropriate for a given application are suitable alternatives, as would be apparent to those skilled in the art. The segmenting function of the R storage and segmenting device  350  bifurcates the current value of R into R 1  and R 2  for use in the next recursion. R 1  represents the most significant R bits, whereas R 2  represents the least significant R bits. R 1  is coupled as an input to an [I+2] EXOR gate  324  via an R 1  link  326 . R 2  is coupled as an input to an [I+3] EXOR gate  320  via an R 2  link  322 . 
     The embodiment as illustrated in FIG. 3 is a 32 bit parallel implementation utilizing a 16 bit CRC (p=32 and r=16). Each table is comprised of 256 entries (2 8 =256, since each subgroup is comprised of eight bits and each possible subgroup combination returns a checkbit value). The remainder R has a degree of 15 or less, since R is always at least one degree less than the degree of the generating polynomial. The term x p R has a degree of 47 or less, since x p  has a degree of 32 and R has a degree of 15 or less. The term  x   q x r  has a degree of 47 or less, since  x   q  has a degree of 31 or less and x r  has a degree of 16. Therefore terms x p R and  x   q x r  are in perfect alignment. 
     A functional description of the instant embodiment of the present invention is furnished by letting [I], [I+1], [I+2], and [I+3] represent the message bit values of a message group comprised of four intermediate message bytes within M(x), with [I] being the least significant byte and [I+3] being the most significant byte. The current remainder, R [I−1], is a value calculated and influenced by message bytes through [I−1]. The remainder is segmented into two bytes, R 1 [I−1] and R 2 [I−1], where R 1 [I−1] is the most significant R[I+4] byte and R 2 [I−1] is the least significant R[I+4] byte. The next sequential recursion then yields a remainder, R[I+3], whose value is calculated and influenced by message bytes through [I+3]. The sequential recursion through [I+3] is described by 
      R[I+3]=T1[I]⊕T2[I+1]⊕T3(R 1 [I−1]⊕[I+2]) ⊕T4(R 2 [I−1]⊕[I+3]) 
     with the process repeated for subsequent message bytes until the message is complete, at which time the existing remainder represents M(x) CRC checkbits, R is appended to M(x) and transmitted to the destination. 
     FIG. 4 is a representation of an exemplary embodiment of the present invention utilizing a cyclical redundancy code length greater than the length of the length of the message group to which it is applied and implemented within a two table lookup scheme. CRC computations for message M(x)  410  are performed by considering a plurality of message data bits concurrently. The instant embodiment of the present invention considers message data bits in groups sized eight bits in length (that is, p=8). An intermediate message group, [I]  415 , is shown. Prior groups ([I+1],[I+2], . . . ), not shown, have been processed as message bits of lessor significance in a prior recursion. Subsequent groups ([I−1],[I−2], . . . ), also not shown, represent message bits of greater significance and are processed in a subsequent recursion. Message data bits are CRC generation seeds provided to a checkbit lookup unit  432 , which is comprised of two individual implementation tables; T 1   435  and T 2   440 . Group bits are read from a message group and the corresponding checkbit values are set, the checkbit values depending upon the value of the incoming group bits. Therefore, bit values from group [I]  415  provide the seed value for a lookup from table T 1   435  (after an exclusive-or operation with prior recursion remainder R 1  at an interveningly coupled [I] EXOR gate  420 ). The output from the [I] EXOR gate  420  is coupled to lookup table T 1   435 , which provides a T 1  checkbit output. Each table stores entries for a total of 256 checkbit lookup values, since each table is implemented with an eight bit lookup seed. The instant embodiment of the present invention generates a sixteen bit CRC (sixteen checkbits) for each respective lookup seed, therefore r=16. As a programmed alternative to hardware CRC, table checkbit storage is accomplished within any of a number of alternative storage devices and components including, but not limited to, RAM, ROM, magnetic or optical storage devices, PROM or EPROM, fixed component memory, or any other memory devices deemed appropriate for a given application, as would be apparent to those skilled in the art. 
     Prior recursion remainder R 2  is coupled as an input to table T 2   440 , which provides a T 2  checkbit output. An EXOR gate  432  is coupled to the output from tables T 1  and T 2  and accepts thereover each sequential group of sixteen checkbits generated, performs an exclusive-or operation on a bit by bit basis between the T 1  and T 2  checkbits, and returns a sixteen bit remainder, R, as the EXOR gate  450  output. The value of R is recomputed during each recursion. The EXOR gate  450  output is coupled to a R storage and segmenting device  460 . The storage function of the R storage and segmenting device  460  is used to store the prior calculated recursion value of R for use in the next CRC recursion calculation. Therefore, a shift register or bubble memory device are typically used to implement the storage function, although RAM, ROM, magnetic or optical storage devices, PROM or EPROM, fixed component memory, or any other memory devices deemed appropriate for a given application are suitable alternatives, as would be apparent to those skilled in the art. The segmenting function of the R storage and segmenting device  460  bifurcates the current value of R into R 1  and R 2  for use in the next recursion. R 1  represents the most significant R bits, whereas R 2  represents the least significant R bits. R 1  is coupled as an input to the [I] EXOR gate  420  via an R 1  link  425 . R 2  is coupled as an direct eight bit lookup to table T 2   440  via an R 2  link  430 . 
     The embodiment as illustrated in FIG. 4 is a eight bit parallel implementation utilizing a 16 bit CRC (p=8 and r=16). Each table is comprised of 256 entries (2 8 =256, since each group is comprised of eight bits and each possible group combination returns a checkbit value). The remainder R has a degree of 15 or less, since R is always at least one degree less than the degree of the generating polynomial. The term x p R has a degree of 23 or less, since x p  has a degree of 8 and R has a degree of 15 or less. The term  x   q x r  has a degree of 23 or less, since  x   q  has a degree of 7 or less and x r  has a degree of 16. Therefore terms x p R and  x   q x r  are in perfect alignment. 
     A functional description of the instant embodiment of the present invention is firnished by letting [I] represent the message bit values of a message group comprised of eight bits (one byte) within M(x). The current remainder, R[I+1], is a value calculated and influenced by message bytes through [I+1]. The remainder is segmented into two bytes, R 1 [I+1] and R 2 [I+1], where R 1 [I+1] is the most significant R[I+1] byte and R 2 [I+1] is the least significant R[I+1] byte. The next sequential recursion then yields a remainder, R[I], whose value is calculated and influenced by message bytes through [I]. The sequential recursion through [I]is described by 
     
       
         R[I]=T1(R 1 [I+1]⊕[I])⊕T2(R 2 [I+1]) 
       
     
     with the process repeated for subsequent message bytes corresponding to subsequent I values ([I−1],[I−2], . . . ) until the message is complete, at which time the existing remainder represents M(x) CRC checkbits and R is appended to M(x) and transmitted to the destination. 
     FIG. 5 is an illustration of an exemplary embodiment of the present invention utilizing bit multipliers to achieve degree alignment between a code remainder and the data bits being coded and checked. CRC computations for message M(x)  510  are performed by considering a plurality of message data bits concurrently. The instant embodiment of the present invention considers message data bits in groups sized eight bits in length (that is, p=8). An intermediate message group, [I]  520 , is shown. Prior groups ([I+1],[I+2], . . . ), not shown, have been processed as message bits of lessor significance in a prior recursion. Subsequent groups ([I−1],[I−2], . . . ), also not shown, represent message bits of greater significance and are processed in a subsequent recursion. Message data bits are coupled and conveyed thereover to a x 5  multiplier  530 , effectively converting the eight bit message data input into the coefficients of a twelfth degree polynomial. The output of the x 5  multiplier  530  is then coupled as an input to an EXOR gate  540 . The second input coupled and conveyed thereover as an input to EXOR gate  540  are the coefficients of a function dependent upon prior recursion remainder R  560 . The output of EXOR gate  540  is coupled as an input to a checkbit lookup table, T  550 . The individual bit values of the output of EXOR gate  540  determines which corresponding checkbit values are set by comparing the individual bit values to a lookup table  550 . The table  550  stores entries for a total of 8,192 checkbit lookup values, since each table is implemented with a thirteen bit lookup seed. The instant embodiment of the present invention generates a five bit CRC (five checkbits) for each respective lookup seed, therefore r=5. As a programmed alternative to hardware CRC, table checkbit storage is accomplished within any of a number of alternative storage devices and components including, but not limited to, RAM, ROM, magnetic or optical storage devices, PROM or EPROM, fixed component memory, or any other memory devices deemed appropriate for a given application, as would be apparent to those skilled in the art. 
     The table  550  output is a recursive remainder, R, which is recomputed during each recursion. The table  550  output is coupled to a storage device  560  and the most recent calculated R value is conveyed thereover. The storage device  560  is utilized to store the prior calculated recursion value of R for use in the next CRC recursion calculation. Therefore, a shift register or bubble memory device is typically used to implement the storage function, although RAM, ROM, magnetic or optical storage devices, PROM or EPROM, fixed component memory, or any other memory devices deemed appropriate for a given application are suitable alternatives, as would be apparent to those skilled in the art. The storage device  560  output is coupled to a x 8  multiplier  570 . The x 8  multiplier  570  effectively converts the five bit value of R into the coefficients of a twelfth degree polynomial. The x 8  multiplier  570  output is coupled as an input to the EXOR gate  540 . 
     The embodiment as illustrated in FIG. 5 is a eight bit parallel implementation utilizing a five bit CRC (p=8 and r=5). The lookup table  550  is comprised of 8,192 entries (2 (8+5) =8,192, since each lookup seed is comprised of thirteen bits and each possible group combination returns a checkbit value). The remainder R has a degree of 4 or less, since R is always at least one degree less than the degree of the generating polynomial. The term x p R has a degree of 12 or less, since x p  has a degree of 8 and R has a degree of 4 or less. The term  x   q x r  has a degree of 12 or less, since  x   q  has a degree of 7 or less and x r  has a degree of 5. Therefore terms x p R and  x   q x r  are in perfect alignment. 
     A functional description of the instant embodiment of the present invention is furnished by letting [I] represent the message bit values of a message group comprised of eight bits (one byte) within M(x). The current remainder, R[I+1], is a value calculated and influenced by message bytes through [I+1]. The next sequential recursion then yields a remainder, R[I], whose value is calculated and influenced by message bytes through [I]. The sequential recursion through [I] is described by 
     
       
         R[I]=T{[ x   5 ·I]⊕[ x   8 ·R[I+1]]} 
       
     
     with the process repeated for subsequent message bytes corresponding to subsequent Ivalues ([I−1],[I−2], . . . ) until the message is complete, at which time the existing remainder represents M(x) CRC checkbits and R is appended to M(x) and transmitted to the destination. 
     In accordance with another embodiment of the present invention, storage requirements for a CRC lookup table are reduced by implementing a Reduced Table lookup algorithm. Creating and implementing a Reduced Table lookup algorithm is a task well known to those skilled in the art. A Reduced Table lookup algorithm looks to each bit in a message group individually. Looking first to the least significant bit in a data message group, if the value of the bit is set (m i =1), then the least significant bit lookup value is accepted as the initial checkbit value. The next least significant bit is then examined and if its bit is set, then the lookup table value corresponding to its bit position is EXOR&#39;ed with the prior checkbit value. The result represents the new checkbit value. The process is continued bitwise until the most significant bit associated with a data message group is processed. The resulting checkbit value represents the CRC value assigned to the data message group. 
     Numerous modifications and alternative embodiments of the present invention will be apparent to those skilled in the art in view of the foregoing description. Accordingly, this description is to be construed as illustrative only and is for the purpose of teaching those skilled in the art the best mode of carrying out the invention and is not intended to illustrate all possible forms thereof. It is also understood that the words used are words of description, rather than limitation, and that details of the structure may be varied substantially without departing from the spirit of the invention and the exclusive use of all modifications which come within the scope of the appended claims are reserved.