Method of computing partial CRCs

• US 8,108,753 B2
• Filed: 03/03/2008
• Issued: 01/31/2012
• 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:
  US12/041,060
• Publication Number:
  US 20080222488A1
• Time in Patent Office: 1,429 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

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. 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 repeat the calculation of the partial CRC and the generation of the CRC remainder multiplier until all N data blocks for the message are received;

a component to combine the results of the calculated partial CRC and the generated CRC 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 initialize a first CRC engine to calculate the CRC for the in order data block, and to initialize the first CRC engine with a partial CRC remainder and a second CRC engine with the CRC remainder multiplier for calculating the partial CRC for the out of order data block, the partial CRC remainder and the CRC remainder multiplier being a result of a prior partial CRC computation.

2. The apparatus of claim 1, wherein the component to initialize permits data blocks from different messages to be received correctly when intermixed by the network.

3. 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 CRC remainder multiplier;

a component to calculate a CRC for an in order data block using an immediately previously calculated in order CRC, if available;

a component to initialize a first CRC engine to calculate the CRC for the in order data block, and to initialize the first CRC engine and a second CRC engine for calculating the partial CRC for the out of order data block; 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.

4. The apparatus of claim 3, wherein the component to produce a final CRC includes a means to divide by a generating polynomial.

5. 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 repeat the calculation of the partial CRC and the generation of the CRC remainder multiplier until all N data blocks for the message are received;

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

a component to calculate a CRC for an in order data block using an immediately previously calculated in order CRC; and

a component to initialize a first CRC engine to calculate the CRC for the in order data block, and to initialize the first CRC engine and a second CRC engine for calculating the partial CRC for the out of order data block,

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.

6. 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 repeat the calculation of the partial CRC and the generation of the CRC remainder multiplier until all N data blocks for the message are received;

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

a component to calculate a CRC for an in order data block using an immediately previously calculated in order CRC; and

a component to initialize a first CRC engine to calculate the CRC for the in order data block, and to initialize the first CRC engine and a second CRC engine for calculating the partial CRC for the out of order data block,

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.

7. The apparatus of claim 6, wherein the component to generate the remainder multiplier includes a means to supply a bit pattern of length S_k plus one bit to a CRC engine.

8. 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 repeat the calculation of the partial CRC and the generation of the CRC remainder multiplier until all N data blocks for the message are received;

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

a component to calculate a CRC for an in order data block using an immediately previously calculated in order CRC; and

a component to initialize a first CRC engine to calculate the CRC for the in order data block, and to initialize the first CRC engine and a second CRC engine for calculating the partial CRC for the out of order data block,

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.