Method of computing partial CRCS

• US 7,971,122 B2
• Filed: 11/08/2007
• Issued: 06/28/2011
• Est. Priority Date: 09/30/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Anderson, Richard E., Georgiou, Christos John, Sandon, Peter A.
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US11/937,204
• Publication Number:
  US 20080091759A1
• Time in Patent Office: 1,328 Days
• Field of Search: 714/758, 714/776
• US Class Current: 714/758
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/091 Parallel or block-wise CRC computation
• CPC Class Codes: H03M 13/093 CRC update after modification of the information word
• CPC Class Codes: H03M 13/6516 Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0061 Error detection codes

Abstract

Apparatus and method of generating cyclic redundancy checks (CRCs) for a message with N data blocks. The method includes calculating a partial CRC for an out of order data block and storing the result, generating, using a division operation, a CRC remainder multiplier associated with the out of order data block and storing the result, repeating the calculating and generating steps until all N data blocks for the message are received; and combining the results of the calculating step and the generating step.

Claims

1. A method of generating cyclic redundancy checks (CRCs) for a message with N data blocks, comprising:

calculating a partial CRC for an out of order data block and storing the result;

generating, using a division operation, a CRC remainder multiplier associated with the out of order data block and storing the result;

repeating the calculating and generating steps until all N data blocks for the message are received;

combining the results of the calculating step and the generating step;

calculating a CRC for an in order data block using any previously computed in order CRC; and

computing a final CRC by combining the results of the combining step and the calculating a CRC step.

2. The method of claim 1, wherein the computing step includes a divide by a generating polynomial.

3. The method of claim 1, wherein the method computes remainders of the powers of two as data blocks are received.

4. The method of claim 1, wherein the method computes remainders of the powers of two as data blocks are received instead of pre-computing them and storing them in a table.

5. The method of claim 1, wherein the data blocks are of different lengths.

6. The method of claim 1, wherein the division operation treats bit strings as binary polynomial coefficients.

7. The method of claim 1, wherein the division operation treats bit strings as binary polynomial coefficients and uses modulo-2 arithmetic.

8. The method of claim 1, wherein all operations on remainders are themselves remainders except for a divisor.

9. An apparatus for generating cyclic redundancy checks (CRCs) for a message with N data blocks, comprising:

a component to calculate a partial CRC for an out of order data block and to store the result;

a component to generate, using a division operation, a CRC remainder multiplier associated with the out of order data block and to store the result;

a component to combine the results of the calculated partial CRC and the generated remainder multiplier;

a component to calculate a CRC for an in order data block using any previously computed in order CRC; and

a component to compute a final CRC by combining the results of combining the calculated partial CRC and the generated remainder multiplier and the calculated CRC for the in order data block.

10. The apparatus of claim 9, wherein the component to calculate the CRC for an in order data block uses an immediately previously calculated in order CRC, if available.

11. The apparatus of claim 10, wherein the component to calculate the CRC provides for initializing a CRC engine with a CRC remainder, the CRC remainder being the result of a prior CRC computation.

12. The apparatus of claim 9, wherein remainders of the powers of two are computed as data blocks are received.

13. The apparatus of claim 9, wherein remainders of the powers of two are computer as data blocks are received instead of pre-computing them and storing them in a table.

14. The apparatus of claim 9, wherein the data blocks are of different lengths.

15. The apparatus of claim 9, wherein the division operation treats bit strings as binary polynomial coefficients.

16. The apparatus of claim 9, wherein the division operation treats bit strings as binary polynomial coefficients and uses modulo-2 arithmetic.

17. The apparatus of claim 9, wherein all operations on remainders are themselves remainders except for a divisor.

18. A computer program product comprising a computer usable storage medium having readable program code embodied in the storage medium, the computer program product includes:

a first component to calculate a partial CRC for an out of order data block and storing the result;

a second component to generate, using a division operation, a CRC remainder multiplier associated with the out of order data block and storing the result;

a third component to combine the results of the first component and the second component;

a fourth component to calculate a CRC for an in order data block using any previously computed in order CRC; and

a fifth component to compute a final CRC by combining the results of the third component and the fourth component.

19. An apparatus for generating cyclic redundancy checks (CRCs) for a message with N data blocks, comprising:

a component to calculate a partial CRC for an out of order data block and to store the result;

a component to generate, using a division operation, a CRC remainder multiplier associated with the out of order data block and to store the result;

a component to combine the results of the calculated partial CRC and the generated remainder multiplier;

a component to calculate a CRC for an in order data block using any previously computed in order CRC; and

one of;

a component to initialize a first CRC engine with a partial CRC remainder and a second CRC engine with the CRC remainder multiplier, the partial CRC remainder and the CRC remainder multiplier being a result of a prior partial CRC computation; and

a component to produce a final CRC by combining the output from the component to combine results of the calculated partial CRC and the generator multiplier with the output from the component to calculate the CRC for an in order data block using any previously computed in order CRC.

20. An apparatus for generating cyclic redundancy checks (CRCs) for a message with N data blocks, comprising:

a component to calculate a partial CRC for an out of order data block and to store the result;

a component to generate, using a division operation, a CRC remainder multiplier associated with the out of order data block and to store the result;

a component to combine the results of the calculated partial CRC and the generated remainder multiplier;

a component to calculate a CRC for an in order data block using any previously computed in order CRC; and

one of;

wherein the component to calculate a partial CRC provides for calculating the partial CRC according to crc_b[k]=CRC (B_k), where crc_b[k] being the partial CRC for data block k and B_k being the data block bit pattern of data block k,

wherein the component to generate a remainder multiplier provides for generating the remainder multiplier according to crc_—

2[k]=CRC(2^sk), where crc_—

2[k] is the remainder multiplier for data block k, and S_k is the bit length of data block k, and

wherein the N data blocks contain at least one data block of the N data blocks that is one of a different length and a same length.