Abstract:
In accordance with the teachings described herein, systems and methods are provided for calculating a Cyclic Redundancy Check (CRC) code for a message. A system includes a first CRC calculator and a second CRC calculator. The first CRC calculator is configured to receive a first data block of the message, and to calculate a first CRC value based at least in part on the first data block, the message including the first data block and a second data block. The second CRC calculator is configured to receive the first CRC value and the second data block of the message, and to calculate a second CRC value based on the first CRC value and the second data block, the second CRC calculator being different from the first CRC calculator.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims priority to and benefit from U.S. Provisional Patent Application No. 61/392,746, filed on Oct. 13, 2010, and entitled “Efficient Method for Pipelined CRC Implementation.” The content of this provisional application is incorporated herein by reference in its entirety. 
    
    
     FIELD 
     The technology described in this patent document relates generally to generation of error codes suitable for use in computer processing systems. More particularly, systems and methods are disclosed for cyclic redundancy check implementations in data transmission systems. 
     BACKGROUND 
     Cyclic redundancy check (CRC) is a widely used technique for detecting errors in digital data, and is suitably used in data transmission, data storage and algorithms for the selection of processing cores in multi-core processor devices, for example. A CRC code typically is computed through binary polynomial division using a computational device that performs a calculation on a first part of the message and then provides the result from the initial calculation as feedback to itself for a subsequent calculation on a second part of the message. 
     SUMMARY 
     In accordance with the teachings described herein, systems and methods are provided for calculating a Cyclic Redundancy Check (CRC) code for a message in a data stream. An example system includes a first CRC calculator and a second CRC calculator. The first CRC calculator is configured to receive a first data block of the message and to calculate a first CRC value based at least in part on the first data block, the message including the first data block and a second data block. The second CRC calculator is configured to receive the first CRC value and the second data block of the message and to calculate a second CRC value based on the first CRC value and the second data block, the second CRC calculator being different from the first CRC calculator. 
     As further examples, the system includes one or more additional CRC calculators, where the first CRC calculator, the second CRC calculator, and the one or more CRC calculators are cascaded in series. Each of the one or more additional CRC calculators is configured to receive an intermediate CRC value from a previous CRC calculator in the cascaded series and a data block of the message, and to calculate a new CRC value based on the received intermediate CRC value and the received data block, the previous CRC calculator being different from any other CRC calculators in the cascaded series. The intermediate CRC value received from the previous CRC calculator is determined based in part on CRC values calculated at all previous CRC calculators in the cascaded series. A last CRC calculator in the cascaded series is configured to output the CRC code of the message. Each of the cascaded CRC calculators is configured to receive a data block of the message based on a location of the data block in the message. 
     As additional examples, each of the cascaded CRC calculators includes one or more polynomial calculators and a register. The one or more polynomial calculators are configured to receive a data block of the message, and to calculate a CRC value based at least in part on the received data block. The register is configured to store the calculated CRC value, and to output the calculated CRC value to a next CRC calculator after a predetermined period of time, the next CRC calculator being different from any other CRC calculators in the cascaded series. The second CRC calculator is configured to output the second CRC value as the CRC code for the message when the second data block is the last data block of the message. 
     As further examples, the system includes a third CRC calculator and a fourth CRC calculator. The third CRC calculator is configured to receive the second CRC value and a third data block of the message, and to calculate a third CRC value based on the second CRC value and the third data block. The fourth CRC calculator is configured to receive the third CRC value and a fourth data block of the message, and to output the CRC code of the message based on the third CRC value and the fourth data block. The first CRC calculator is configured to receive an additional input, and to calculate the first CRC value based on the first data block and the additional input, the additional input having a predetermined value. The first CRC calculator is configured to receive a zero as the additional input for calculating the first CRC value. The first CRC calculator is further configured to receive a third data block of a second message, and to calculate a third CRC value based at least in part on the third data block, the second message including the third data block and a fourth data block. The second CRC calculator is further configured to receive the third CRC value and the fourth data block of the second message, and to calculate a fourth CRC value based on the third CRC value and the fourth data block. 
     As another example, a method is provided for calculating a Cyclic Redundancy Check (CRC) code for a message in a data stream. A message including a first data block and a second data block is received. The first data block of the message is received at a first CRC calculator. A first CRC value is calculated based at least in part on the first data block, and provided to a second CRC calculator for calculating a second CRC value based on the second data block of the message and the first CRC value, the second CRC calculator being different from the first CRC calculator. 
     As further examples, the second data block of the message is received at the second CRC calculator. The second CRC value is calculated based on the first CRC value and the second data block of the message, and output as the CRC code of the message. For each of the remaining data blocks of the message other than the first data block, the data block is received at a CRC calculator associated with the data block. A CRC value is calculated for the data block based on the data block and a previous CRC value for a previous data block of the message. When the data block is not the last data block of the message, the CRC value is provided to a next CRC calculator for calculating a next CRC value based on the CRC value and a next data block of the message, the CRC calculator being different from all previous CRC calculators. A final CRC value calculated for the last data block of the message is output as the CRC code of the message. 
     As additional examples, an additional input is received at the first CRC calculator. The first CRC value is calculated based on the first data block and the additional input, the additional input having a predetermined value. The first CRC value is calculated based on the first data block and the additional input having a value of zero. A second message including a third data block and a fourth data block is received. The third data block of the second message is received at the first CRC calculator. A third CRC value is calculated based at least in part on the third data block, and provided to the second CRC calculator for calculating a fourth CRC value based on the fourth data block of the message and the third CRC value. One of a plurality of data processors is selected to process the message based on the CRC code of the message. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a diagram of an example system for calculating a CRC code for a message using multiple CRC calculators. 
         FIG. 2  shows a diagram of an example CRC calculator. 
         FIG. 3  shows a timing diagram of an example for calculating a CRC code for an 128-bit message using four CRC calculators. 
         FIG. 4  shows an example flow diagram for calculating a CRC code for a message using two CRC calculators. 
         FIG. 5  shows an example flow diagram for calculating a CRC code for a message using multiple CRC calculators. 
         FIG. 6  shows a diagram of an example system for selecting a processing core to process a message based on a CRC code calculated for the message. 
     
    
    
     DETAILED DESCRIPTION 
     To calculate a CRC code of a message, the message is divided into multiple blocks of equal size, in an embodiment, and these blocks of the message are then processed, one by one, by a single CRC calculator. Specifically, the CRC calculator generates an intermediate CRC value for a particular block of the message (except the last block of the message), and then provides the intermediate CRC value as a feedback to be used for calculating another CRC value for the next block of the message. When the CRC calculator finishes processing the last block of the message, the calculated CRC value of the last block of the message is output as the CRC code for the message. This single-CRC-calculator approach usually requires a plurality of multiplexers in front of the CRC calculator, or a single multiplexer selecting from among many inputs, and thus requires a lot of real estate and routing resources. Instead, in accordance with an embodiment, multiple CRC calculators are used to calculate a CRC code of a message. 
       FIG. 1  shows a diagram of an example system  100  for calculating a CRC code for a message  104  using multiple CRC calculators. The example system  100  includes a plurality of CRC calculators  102   1 ,  102   2 , . . . ,  102   n . Each of the CRC calculators  102   1 ,  102   2 , . . . ,  102   n  receives a data block which is a portion of the message  104 , and provides a calculated CRC value to a next CRC calculator. The next CRC calculator is configured to calculate a new CRC value based on the CRC value calculated in a previous CRC calculator and a next data block of the message  104  until the last CRC calculator  102   n  outputs the CRC code of the complete message  104 . 
     Specifically, in an embodiment, the message  104  is transmitted in a data stream that is received at the system  100 . In an example, the data stream is received from a network. Message  104  includes a plurality of data blocks  106   1 ,  106   2 , . . . ,  106   n . The CRC calculators  102   1 ,  102   2 , . . . ,  102   n  each receive one of the data blocks and an additional input, and calculate a CRC value based on the received data block and the additional input. The additional input for the first CRC calculator  102   1  has a predetermined value  110  (e.g., 0), while the additional input for each of the CRC calculators  102   2 , . . . ,  102   n  is a CRC value (e.g.,  108   1 , . . . ,  108   n-1 ) calculated by a previous CRC calculator. The CRC value  108   n  calculated by the final CRC calculator  102   n  is output as the CRC code of the message  104 . 
     The CRC calculators  102   1 ,  102   2 , . . . ,  102   n  in the embodiment of  FIG. 1  are cascaded in series, and each of the CRC calculators receives a data block (e.g.,  106   1 ,  106   2 , . . . ,  106   n ) of the message  104  based on a location of the data block in the message  104 . Further, in an embodiment, the CRC code of the message  104  is suitably used in an algorithm for selecting, e.g. randomly or pseudo-randomly selecting, a processing core in a multi-processor system to process the message. 
       FIG. 2  shows a diagram of an example CRC calculator  200 . The CRC calculator  200  receives a data block  202  and an additional input  204 , and generates a CRC value  206  as an output. In particular, the CRC calculator  200  includes two or more polynomial calculators  208  and a register  210 . For example, the polynomial calculators  208  are arranged in cascade. The polynomial calculators  208  receive the data block  202 , and the additional input  204  which has a predetermined value (e.g., 0) or another CRC value generated by a previous CRC calculator. Then, the polynomial calculators  208  generate an intermediate output  212  (e.g., the CRC value  206 ) based on the data block  202  and the additional input  204 . The register  210  stores the intermediate output  212 , and outputs the CRC value  206  at a particular time determined by a clock signal  214 . 
       FIG. 3  shows at  300  a timing diagram of an example embodiment for calculating a CRC code for a 128-bit message  302  using four CRC calculators  304 ,  306 ,  308 , and  310  arranged in cascade. During different time periods, the CRC calculators each receive a data block of the message  302 , and provide a previously calculated CRC value to a next CRC calculator for calculating a new CRC value, until the final CRC calculator  310  outputs the CRC code  312  for the message  302 . 
     Specifically, in the example seen, the 128-bit message  302  is divided into four data blocks,  314 ,  316 ,  318 , and  320 , each having 32 bits of data. Each of the CRC calculators  304 ,  306 ,  308 , and  310  receives a data block based on the location of the data block in the message  302 . During a first time period  322 , the CRC calculator  304  receives the data block  314  and a predetermined additional input (not shown), and generates a CRC value  330  which is provided to the CRC calculator  306 . Then, in a time period  324 , the CRC calculator  306  receives the data block  316  and the CRC value  330 , and generates another CRC value  332  which is provided to the CRC calculator  308 . Further, the CRC calculator  308  receives the data block  318  and the CRC value  332  in a time period  326 , and outputs a CRC value  334  to the CRC calculator  310 . Lastly, during a time period  328 , the CRC calculator  310  outputs the CRC code result  312  for the message  302  based on the received data block  320  and the CRC value  334 . 
     Similarly, the four CRC calculators  304 ,  306 ,  308 , and  310  are used to process subsequent messages. For example, when another data block  336  of a new message arrives at the CRC calculator  304  during the time period  324 , the CRC calculator  304  has already processed the data block  314 , and thus is free to begin processing the data block  336  to initiate a new cycle for the new message. 
     A CRC-32 polynomial is used for calculating the CRC code of the message in this example. Other CRC polynomials, such as CRC-8, CRC-16, and CRC-64, can be implemented to similarly carry out the CRC code calculation. 
       FIG. 4  shows at  400  an example flow diagram for calculating a CRC code for a message using two CRC calculators. The message, including at least a first data block and a second data block, is received at  402 . The first data block is received at a first CRC calculator at  404 . The first CRC value is calculated based at least in part on the first data block at  406 . In an embodiment, at  406  the first CRC value is calculated based on the first data block and an additional input. Then the first CRC value is provided to a second CRC calculator for calculating a second CRC value based on the second data block of the message and the first CRC value at  408 . The second CRC value is output as the CRC code for the entire message. 
       FIG. 5  shows at  500  an example flow diagram for calculating a CRC code for a message using multiple CRC calculators. The message, including multiple data blocks, is received at  502 . At  504 , a data block of the message is received at a CRC calculator. A CRC value is calculated at the CRC calculator at  506 . In an embodiment, at  506  the CRC value is calculated based on the data block and an additional input. It is noted that the additional value is zero or some other suitable value. Then, at  508 , the calculated CRC value is provided to a next CRC calculator. A new data block of the message is also received at the next CRC calculator at  510 . A next CRC value is calculated at the next CRC calculator at  512 . 
     A determination of whether a last data block of the message is being processed is performed at  514 . If the new data block processed at the next CRC calculator is the last data block of the message, then the next CRC value is output as the CRC code of the message at  516 . If the last data block of the message has not been processed yet, then the process continues in cascade to a following CRC calculator until the last data block of the message has been processed. 
       FIG. 6  shows a diagram of an example system  600  for selecting a processing core to process a message based on a CRC code calculated for the message. The example system  600  includes an integrated circuit  602  which receives an incoming data packet  604  from a network  606 . A message generator  608  in the integrated circuit  602  generates one or more messages  610  from the data packet  604 , and a cascaded CRC calculator  612  calculates a CRC code  614  for the message  610 . A core selector  616  routes the message  610 , based on the calculated CRC code  614 , to one of multiple processing cores  618   1 ,  618   2 , . . . ,  618   m , . . . ,  618   n  that are contained in the integrated circuit  602  for processing. For instance, in the illustrated example, the core selector  616  routes the message  610  to the processing core  618   m  for processing, as shown in  FIG. 6 . 
     This written description uses examples to disclose the invention, include the best mode, and also to enable a person skilled in the art to make and use the invention. The patentable scope of the invention includes other examples that occur to those skilled in the art.