METHOD OF COMPUTING PARTIAL CRCS

• US 20080091759A1
• Filed: 11/08/2007
• Published: 04/17/2008
• Est. Priority Date: 09/30/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: ANDERSON, Richard, Sandon, Peter, Georgiou, Christos
• Granted Patent: US 7,971,122 B2
• Time in Patent Office: Days
• US Class Current: 708/504
• 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; and

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

2. The method of claim 1, further comprising calculating a CRC for an in order data block using any previously computed in order CRC.

3. The method of claim 2, further comprising computing a final CRC by combining the results of the combining step and the calculating a CRC step.

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

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

6. 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.

7. The method of claim 1, wherein the message arrives out of order.

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

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

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

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

12. 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; and

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

13. The apparatus of claim 12, further comprising a component to calculate a CRC for an in order data block using an immediately previously calculated in order CRC, if available.

14. The apparatus of claim 13, 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.

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

16. The apparatus of claim 12, 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.

17. The apparatus of claim 12, wherein the message arrives out of order.

18. The apparatus of claim 12, wherein the data blocks are of different lengths.

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

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

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

22. A computer program product comprising a computer usable medium having readable program code embodied in the 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; and

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

23. 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; 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 a CRC for an in order data block using an immediately previously calculated in order CRC, if available.

24. 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; 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 Sk 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.