Abstract:
A method for encoding information bits to derive a cyclically encoded group of code bits from the information bits that were encoded, using a computer processor. A sequence of data states are generated that are the result of a series of exclusive OR operations of each of the code bits with each of the bits of a first generator word and bitwise ANDing each of the resultant bits with the results of the next previous such exclusive OR operations shifted in the direction of the least significant bit (&#34;LSB&#34;) so as to generate a data state. The invention involves the following steps. First, an initial data state of zero is provided. Next, the LSB of the code bits is bitwise exclusive ORed with the current data state. Next, the result of the previous step is bitwise ANDed with the value n, where n is a selected binary value 2 x  -1, where x is any positive integer. Next, the current data state is changed to the next sequential data state by changing the data state to one of 2 x  predetermined data states, depending on the x LSBs of the result of the previous step. Then, both the code bits and the now current data state are shifted by x bits in the direction of the LSB; and, finally, the second through fifth of the foregoing steps are repeated until all code bits have been operated on.

Description:
TECHNICAL FIELD OF THE INVENTION 
     This invention relates to Digital Signal Processors, and in particular relates to improved methods for the implementation of cyclical redundancy check (&#34;CRC&#34;) algorithms. 
     BACKGROUND OF THE INVENTION 
     The use of cyclic codes to add redundancy for error detection and correction is a well known and much used technique in digital processing. One of the reasons for the favor of the cyclic redundancy check is that the encoding and decoding process is efficient because little, if any, storage is required. This is because the code words are generated by shifting and exclusive ORing (&#34;XORing&#34;). 
     Nonetheless, the speed of computation of prior art techniques for cyclic encoding in digital processors is limited by the need for three processor operations for each bit processed, that is, a shift, an XOR and a compare. As digital data transmission rates increase, with improvements in technology, cyclic encoding in real time is becoming a problem. Without real time cyclic encoding, such encoding must be deferred, requiring, potentially, large amounts of memory. Furthermore, in some applications real time encoding may be a necessity. 
     Thus, there is a need for an approach to cyclic encoding that improves the speed of such computations. The present invention provides such an approach. 
     SUMMARY OF THE INVENTION 
     The present invention provides a method for encoding information bits to derive a cyclically encoded group of code bits from the information bits, using a computer processor. A sequence of data states are generated that are the result of a series of exclusive OR operations of each of the code bits with each of the bits of a first generator word and bitwise ANDing each of the resultant bits with the results of the next previous such exclusive OR operations shifted in the direction of the least significant bit (&#34;LSB&#34;) so as to generate a data state. The invention involves the following steps. First, the LSB of the code bits is bitwise exclusive ORed with the current data state. Next, the result of the previous step is bitwise ANDed with the value n, where n is a selected binary value 2 x  -1, where x is any positive integer. Next, the current data state is changed to the next sequential data state by changing the data state to one of 2 x  predetermined data states, depending on the x LSBs of the result of the previous step. Then, both the code bits and the now current data state are shifted by x bits in the direction of the LSB; and, finally, steps 1) through 4) are repeated until all code bits have been operated on. 
     Thus, the present invention, through novel paralellization techniques, enables the use of parallel processing of more than one bit, thus improving the speed of computation in cyclic encoding. The techniques involved in the present invention are suitable for implementation in software code operating on a processor, such as a digital signal processor, and are also suitable for implementation in dedicated hardware for even faster computation. 
    
    
     These and other features of the invention that will be apparent to those skilled in the art from the following detailed description of the invention, taken together with the accompanying drawings. 
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a computer subsystem including a digital signal processor; 
     FIG. 2 is a diagram illustrating the data flow involved in the CRC process implemented by the preferred embodiment of the present invention; and 
     FIG. 3 is a diagram similar to that of FIG. 1, but showing where certain portions of the method of the preferred embodiment of the present invention are performed. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The preferred embodiment of the present invention is implemented in a computer having a general purpose digital signal processor (&#34;DSP&#34;). FIG. 1 is a block diagram of a subsystem 2 of such a computer. The subsystem 2 generally includes a DSP 4 and a memory 6, which can include cache memory, as well as RAM memory and mass storage. The DSP 4 communicates with memory 6 by way of a data bus 8. The structure and operation of DSP subsystems such as subsystem 2 are well known in the art, and discussion of same is not included herein, in the interest of brevity and clarity. The preferred embodiment is a novel method of operating such a subsystem 2, wherein instructions stored in memory 6 are executed in DSP 4, and the discussion hereinbelow focuses on that method. 
     FIG. 2 is a block diagram depicting the data flow for an encoding process in a digital computer for an (n, k) cyclic code with the generator polynomial of the following Formula (1): 
     
         g(X)=1+g.sub.1 X+g.sub.2 X.sup.2 + . . . +g.sub.n-k-1 X.sup.n-k-1 +X.sup.n-k. 
    
     where: 
     k=the number of information bits. 
     n=the number of code bits in the code word, 
     X n-k  =a place holder for bit n-k, and 
     g=the set of code words, g 0 , g 1 , g 2 , . . . g n-k-1  (the polynomial generator). 
     The process of FIG. 2 encodes an (n, k) cyclic code in systematic form, in three steps. First, the message polynomial u(X), comprising the k information bits u 0 , u 1 , u 2 , . . . u k-1 , is multiplied by X n-k . Then, X n-k  u(X) is divided by g(X) to obtain the remainder b(X). Finally, the code word b(X)+X n-k  u(X) is formed. All these three steps are accomplished with the process of FIG. 2 which may be implemented as a linear (n-k)-stage shift register with feedback connections based on the generator polynomial in Formula (1), above, or, as is preferred, as a process running on a DSP. 
     As can be seen, the message u(X) is applied to the input 10 of the process serially, one bit at a time, and as it is so applied it is also provided as one input to a binary addition step 12. Data are generally clocked through the process of FIG. 2 one bit at a time. For example, the function of gate 14 is to hold one bit of data for one cycle for appropriate sequencing of the data flow in the process. The other input to the binary addition step 12 is the output b b-k-1  of a final addition step, described below, that represents the most significant bit of the remainder b(X). The output of binary addition step 12 is provided to the input of gate 14. The output of gate 14 is, in turn, provided to the inputs of a series of multiplier steps g 1 , g 2 , . . . g n-k-1 , in which the input thereto is multiplied by the code word for the position of the multiplier indicated by the subscript to the &#34;g&#34; term identifying the multiplier, and to the input of a first storage position b 0 , as shown. Thus, for example, multiplier step g 2  multiplies its input by the code word g 2 . Again, while the process is preferably implemented as a process running in a microprocessor, multiplier steps g 1 , g 2 , . . . g n-k-1 , could be implemented in hardware, for example as AND gates, and storage positions b 0 , b 1 , . . . b b-k-1  could be implemented in hardware, for example as stages of a shift register. Also, the addition step 12 (as well as addition steps 16, 18 and 20, described below) could be implemented in hardware, for example as a binary adder, such as an exclusive OR gate. Actually, the provision of the output of gate 14 directly to the first storage position b 0  is equivalent to providing that output to multiplier step g 0 , which is the value &#34;1&#34;, which it will be in all generator polynomials useful for CRC encoding as described herein, and then providing that output to the first storage position b 0 . The bit value in first storage position b 0 , when the complete encoding operation is finished, is the first of the series, b 0 , b 1 , b 2 , . . . b n-k-1 , of parity check bits that are the result of the encoding process, and are the complete code vector for the block of information bits u(X). 
     The output of the first storage position b 0  is provided to one input of a second binary addition step 16. The other input of binary addition step 16 is the output of multiplier step g 1 . The output of the second binary adder 16 is provided to a second storage position b 1 , the output of which is provided to one input of a third binary addition step 18, the other input of which is the output of multiplier step g 2 , and the output of which is provided to a third storage position b 2 , and so forth, as shown, until the output of storage position b n-k-2  (not shown) is provided to one input of a binary addition step 20, the other input of which is the output of multiplier step g n-k-1 , and the output of which is provided to a final storage position b n-k-1 . As mentioned above, the output of the final storage position b n-k-1  is provided to one input of the first binary addition step 12. It is also provided to output path 22 when data path selector 24 is in the appropriate position 26. The alternative position 28 for data path selector 24 passes data on the input path 10 straight through to the output path 22. This is simply reading out the parity bits. FIG. 2 shows data path selector 24 in the latter, alternative position 28. Note that data path selector 24 simply indicates data path where the process described above is implemented in a process on a microprocessor, but it could be implemented in hardware, for example, as a switch. 
     The three steps mentioned above will now be explained in more detail. 
     Step 1. With gate 14 turned on, the k information bits u 0 , u 1 , u 2 , . . . u k-1  (or u(X)=u 0  +u 1  X+. . . u k-1  X k-1  in polynomial form) are shifted into the process and simultaneously into the communication channel. Shifting the message u(X) into the process from the front end is equivalent to premultiplying u(X) by X n-k . As soon as the complete message has entered the process, the n-k digits in the storage locations form the remainder. 
     Step 2. The feedback connection is broken, by turning off gate 14. 
     Step 3. The digits b 0 , b 1 , b 2 , . . . b n-k-1 , together with the k information digits, form a complete code vector, or state, and can be shifted out through output path 22. 
     The CRC algorithm discussed above in connection with FIG. 2 can be described with the following code, referred to herein as the &#34;CRC&#34; code. Note that in this CRC code, as in the other sets of code set forth herein, individual line numbers appear immediately to the left of each line. Also, note that b 0 , b 1 , b 2 , . . . b n-k-1  are reversed from the usual ordering, such that b 0  is the most significant bit (&#34;MSB&#34;) and b n-k-1  is the least significant bit (&#34;LSB&#34;). 
     
         ______________________________________1   FOR i = 1 TO n2     IF (((state   input) &amp; 1 == 1) THEN3       state = state   generator4     ELSE5       state = state6     ENDIF7     state = state &gt;&gt; 18     input = input &gt;&gt; 19   NEXT iwhere:&#34;i&#34; =         the ith bit of the input which is         being processed&#34;input&#34; =     an N-bit input word&#34;state&#34; =     the running state of the CRC, initialized         to the known value, zero&#34;generator&#34; = an R-bit generator word&#34; &#34; =         the bitwise exclusive-OR operation&#34;&amp;&#34; =         the bitwise AND operation&#34;==&#34; =        the equality comparison&#34;&gt;&gt;&#34; =        a logical right-shift&#34;A = B&#34; =     store B into A.______________________________________ 
    
     In the foregoing code listing, the statement in line 3 thereof designates the instruction to multiply the state b 0 , b 1 , b 2 , . . . b n-k-1  by the polynomial generator g 0 , g 1 , g 2 , . . . g n-k-1 . The input data is provided in sequence LSB to MSB. Thus the &#34;newest&#34; bit is the MSB, and the &#34;oldest&#34; bit is the LSB. Notationally, the generator coefficient g n-k-1  is at the MSB position, while g 0  is at the LSB position. 
     The preferred embodiment of the present invention is implemented by the execution of a set of code instructions on a computer including a DSP, such as a Texas Instruments® TMS320C5x DSP, that are set forth and described in detail hereinbelow. In order to better understand the code of the preferred embodiment of the present invention, a series of sets of code are discussed that show a process of change from conventional, prior art code to the code of the preferred embodiment. These sets of code are presented in sequence and identified as &#34;prior art,&#34; and then following the prior art code, &#34;Example 1,&#34; &#34;Example 2,&#34; and so forth. The final set of code is the code of the preferred embodiment, and is identified as such. Note that text following a semicolon, such as appears in lines 1 and 11 of the code of Example 1, is comment text that is not executed or otherwise operated on. 
     Thus, the first set of code, that of the prior art, is now presented: 
     
         ______________________________________ 1  FOR i = 1 to N    ; for each bit in the input 2    temp1 = state   input3     temp2 = temp1 &amp; 14     IF (temp2 == 1) THEN 5        temp3 = state   generator 6    ELSE 7        temp3 = state 8    ENDIF 9        state = temp3 &gt;&gt; 110        input = input &gt;&gt; 111  NEXT i            ; the next input bit    where:  temp1-temp3 are temporary values, andother variables are as in the CRC code.______________________________________ 
    
     Notice that in the prior art code above, six steps are necessary to implement the algorithm, set forth in lines 2, 3, 4, 5 (and 7), 9 and 10. Also notice that steps 2 through 10 constitute a loop recurrence. In other words, the next iteration of the loop has that sequence of steps as a constraint. FIG. 3 shows the &#34;location&#34; of the steps in the prior art code listing in the process of FIG. 2. Thus, lines 2 and 3 are implemented in the addition step 12, lines 5 and 7 are implemented in the multiplier steps g 1 , g 2 , . . . g n-k-1 , and line 9 is implemented in the shifts into the storage positions b 0 , b 1 , . . . b b-k-1 , all as shown in FIG. 3. 
     Note that a particular iteration&#39;s steps 5 and 7 must complete before the next iteration&#39;s step 2 may begin, because step 2 relies on the state calculated by the previous iteration. Therefore, at best any processor capable of performing the steps of the prior art code must take at least four steps per bit. 
     Now, the next set of code, that of Example 1, is presented and described. 
     
         ______________________________________ 1  FOR i = 1 TO N STEP 2 2      IF (((state   input) &amp; 1) == 1) THEN 3        state = state   generator 4      ELSE 5        state = state 6      ENDIF 7      state = state &gt;&gt; 1 8      input = input &gt;&gt; 1 9      IF (((state   input) &amp; 1) == 1) THEN10        state = state   generator11      ELSE12        state = state13      ENDIF14      state = state &gt;&gt; 115      input = input &gt;&gt; 116  NEXT i______________________________________ 
    
     Note that the code of Example 1 performs two iterations at a time. However, the recurrence is now in the steps of lines 2-3, 5, 7 and 8, and in the steps of lines 9-10, 12, 14 and 15, respectively. This requires eight steps per two bits. 
     Now, the next set of code, that of Example 2, is presented and described. 
     
         ______________________________________ 1  FOR i = 1 TO N STEP 2 2    IF (((state   input) &amp; 1) ==1) THEN 3      state = state   generator 4      state = state &gt;&gt; 1 5      input = input &gt;&gt; 1 6      IF ((state   input) &amp; 1) == 1) THEN 7        state = state   generator 8      ELSE 9        state = state10      ENDIF11      state = state &gt;&gt; 112      input = input &gt;&gt; 113    ELSE14      state = state15      state = state &gt;&gt; 116      input = input &gt;&gt; 117      IF (((state   input) &amp; 1) == 1) THEN18        state = state   generator19      ELSE20        state = state21      ENDIF22      state = state &gt;&gt; 123      input = input &gt;&gt; 124    ENDIF25  NEXT______________________________________ 
    
     Note that the IF/ELSE pair in lines 2 and 13 represent the IF/ELSE pair of lines 2 and 4 of Example 1. The steps set forth in lines 7 through 15 of Example 1 are split out into two sets of subroutines in Example 2, the first being set forth in lines 4 through 12, and the second being set forth in lines 15 through 23, that is, placed in both the IF path starting at line 2 and the ELSE path starting at line 13. 
     Now, the next set of code, that of Example 3, is presented and described. 
     
         ______________________________________ 1  FOR i = 1 TO N STEP 2 2    IF (((state   input) &amp; 1) ==1) THEN 3      state = state   generator 4      IF ((((state &gt;&gt;1)   (input &gt;&gt; 1)) &amp; 1) == 5          1) THEN 6        state = (state &gt;&gt;1)   generator 7      ELSE 8        state = (state &gt;&gt; 1) 9      ENDIF10    ELSE11      state = state12      IF ((((state &gt;&gt; 1)   (input &gt;&gt; 1)) &amp; 1)13          == 1) THEN14        state = (state &gt;&gt; 1)   generator15      ELSE16        state = (state &gt;&gt; 1)17      ENDIF18    ENDIF19    state = state &gt;&gt; 120    input = input &gt;&gt; 221  NEXT______________________________________ 
    
     Note that the first shift term, state &gt;&gt;1, of Example 2 is distributed by being substituted into lines 4, 6, 8, 12, 14 and 16 of Example 3. The second shift term, input &gt;&gt;1, is distributed by being substituted into lines 4, 12 and 20. Note that the substitution into 20 results in a shifting by 2, instead of by 1. 
     Now, the next set of code, that of Example 4, is presented and described. 
     
         ______________________________________ 1  FOR i = 1 TO N STEP 2 2    IF (((state   input) &amp; 1) ==1) THEN 3      IF ((((state   generator) &gt;&gt;1) 4          (input &gt;&gt;1) &amp; 1) ==1 THEN 5        state = ((state   generator) &gt;&gt;1) 6          generator 7      ELSE 8        state = ((state   generator) &gt;&gt;1) 9      ENDIF10    ELSE11      IF ((((state &gt;&gt; 1)   (input &gt;&gt; 1)) &amp; 1)12            == 1) THEN13        state = (state &gt;&gt; 1)   generator14      ELSE15        state = (state &gt;&gt; 1)16      ENDIF17    ENDIF18    state = state &gt;&gt; 119    input = input &gt;&gt; 220  NEXT______________________________________ 
    
     Note that in Example 4, the state   generator term has been distributed, as compared with Example 3. 
     Now, the next set of code, that of Example 5, is presented and described. 
     
         ______________________________________ 1  FOR i = 1 TO N STEP 2 2    IF (((state   input) &amp; 1) ==1) THEN 3      IF ((((state   generator   input) &gt;&gt;1) &amp; 4        1) == 1) THEN 5          state = ((state   generator 6            (generator &lt;&lt;1)) &gt;&gt;1 7      ELSE 8          state = ((state   generator) &gt;&gt;1) 9      ENDIF10    ELSE11      IF ((((state   input) &gt;&gt; 1) &amp; 1) == 1)12        THEN13          state = (state   (generator &gt;&gt;14            1)) &gt;&gt; 115      ELSE16          state = state &gt;&gt; 117      ENDIF18    ENDIF19    state = state &gt;&gt; 120    input = input &gt;&gt; 221  NEXT______________________________________ 
    
     Note that in Example 5 a kind of &#34;reverse distribution&#34; is done, compared with Example 4. That is, terms are consolidated. For example, lines 3-4 of Example 4, 
     
         IF ((((state   generator)&gt;&gt;1) (input&gt;&gt;1) &amp; 1)==1 THEN 
    
     becomes lines 3-4 of Example 5: 
     
         IF ((((state   generator   input)&gt;&gt;1) &amp; 1)==1) THEN. 
    
     Other terms are similarly consolidated in Example 5. 
     Now, the next set of code, that of Example 6, is presented and described. 
     
         ______________________________________ 1  FOR i = 1 TO N STEP 2 2    IF (((state   input) &amp; 1) == 1) THEN 3      IF ((((state   generator   input) &gt;&gt; 1) &amp; 4        1) == 1) THEN 5          state = state   generator 6            (generator &gt;&gt; 1) 7      ELSE 8          state = state   generator 9      ENDIF10    ELSE11      IF ((((state   input) &gt;&gt; 1) &amp; 1) == 1)12        THEN13          state = state   (generator &gt;&gt;14            1)15      ELSE16          state = state17      ENDIF18    ENDIF19    state = state &gt;&gt; 220    input = input &gt;&gt; 221  NEXT______________________________________ 
    
     Note that in Example 6 the term state &gt;&gt;1 is factored out and performed in line 19, where the combination of terms results in a shift by 2. 
     Now, the next set of code, that of Example 7, is presented and described. 
     
         ______________________________________ 1  FOR i = 1 TO N STEP 2 2    IF (((state   input) &amp; 1) == 1) THEN 3      IF ((((state   input) &gt;&gt; 1) &amp; 1) == 0) 4        THEN 5          state = state   generator 6            (generator &gt;&gt; 1) 7      ELSE 8          state = state   generator 9      ENDIF10    ELSE11      IF ((((state   input) &gt;&gt; 1) &amp; 1) == 1)12        THEN13          state = state   (generator &gt;&gt;14          1)15      ELSE16          state = state17      ENDIF18    ENDIF19    state = state &gt;&gt; 220    input = input &gt;&gt; 221  NEXT______________________________________ 
    
     Note that in Example 7, with regard to the change to line 3, a transformation is made, compared to the same statement in lines 3-4 of Example 6, based on certain knowledge of the generator. The transformation is made operating on the assumption that the generator inverts the result of the test, because the LSB of the generator is 1. Thus, the generator is removed, and the test value for comparison inverted to &#34;0&#34;. Compare line 11 of Example 7, where the test is not inverted, because the term state input was not  ed with the generator. 
     Now, the next set of code, that of Example 8, is presented and described. 
     
         ______________________________________ 1  FOR i = 1 TO N STEP 2 2    IF (((state   input) &amp; 3) == 1) THEN 3      state = state   generator   (generator &lt;&lt; 4        1) 5    ENDIF 6    IF (((state   input) &amp; 3) == 3) THEN 7            state = state   generator 8    ENDIF 9    IF ((((state   input ) &amp; 3) == 2) THEN10      state = state   (generator &gt;&gt; 1)11    ENDIF12    IF (((state   input) &amp; 3) == 0) THEN13      state = state14    ENDIF15    state = state &gt;&gt; 216    input = input &gt;&gt; 217  NEXT______________________________________ 
    
     Note that in Example 8 the tests are combined in nested IF/THEN statements, dealing with the now resulting four different possibilities, that is, 0, 1, 2 or 3 (binary 00, 01, 10, 11, respectively), for the MSBs, as the shifting is now done by two bits, instead of one bit, as in Example 1. This reduces the number of lines. 
     Now, the next set of code, that of Preferred Embodiment, is presented and described. 
     
         ______________________________________ 1  FOR i = 1 TO N STEP 2 2     temp1 = (state   input)  ; step 1 3     temp2 = temp1 &amp; 3        ; step 2 4     IF (temp2 == 1) THEN     ; step 3a 5      state = state   generator 3                           ; step 4a 6     ENDIF 7     IF (temp2 == 3) THEN     ; step 3b 8      state = state   generator                           ; step 4b 9     ENDIF10     IF (temp2 == 2) THEN     ; step 3c11      state = state   generator2                           ; step 4c12     ENDIF13     IF (temp2 == 0) THEN     ; step 3d14      state = state           ; step 4d15     ENDIF16     state = state &gt;&gt; 2       ; step 5a17     input = input &gt;&gt;2        ; step 5b18  NEXT                        i______________________________________ 
    
     The code in the preferred embodiment expresses the code of Example 8 in 2-operand steps, so that a processor can perform them. Certain temporary variables are introduced here. Thus, 
     
         generator 3=generator   generator&lt;&lt;1 
    
     and 
     
         generator 2=generator&lt;&lt;1. 
    
     In both Example 8 and in the preferred embodiment, m bits of the CRC are operated on in parallel. Also, tests on m bits of the input   state are tested simultaneously. In addition, there are 2 m  possible results of the tests, and there are 2 m  new generators, generator 3, generator 2, generator and 0, to compute the next state b. The generators are constants and can be built from the 1-bit-at-a-time generator. Since the term, generator, is a constant, one can predict how the results of the 2 m  tests map to the new generator. 
     Thus, the present invention, through novel paralellization techniques, enables the use of parallel processing of more than one bit, thus improving the speed of computation in cyclic encoding. The techniques involved in the present invention are suitable for implementation in software code operating on a processor, such as a digital signal processor, and are also suitable for implementation in dedicated hardware for even faster computation. 
     Although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the invention as defined by the appended claims.