Method of computing partial CRCs
AssigneeInternational Business Machines Corporation
InventorsRichard E. Anderson, Christos John Georgiou, Peter A. Sandon
Life of this patent
Estimating the term…
Abstract
A method of calculating partial CRCs on-the-fly is provided without the need for pre-computed tables and without size restrictions on data blocks or packets. The method works for both fixed and variable length data blocks by computing the remainders of the powers of two as data blocks are received, without the need for pre-computing them and storing them in a table. The method may be employed on data streams wherein the data blocks are received out-of-order.
Claims20
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 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.
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 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
- initializing a CRC engine with a CRC remainder for the in order block, the CRC remainder being a result of a prior CRC computation.
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 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;
- and
- initializing 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.
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 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 of the calculated partial CRC and the generated remainder multiplier;
- and
- a component to calculate a CRC for an in order data block using an immediately previously calculated in order CRC, if available,
- 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.
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 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 of the calculated partial CRC and the generated remainder multiplier;
- a component to calculate a CRC for an in order data block using an immediately previously calculated in order CRC, if available;
- and
- 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.
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 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 of the calculated partial CRC and the generated remainder multiplier;
- a component to calculate a CRC for an in order data block using an immediately previously calculated in order CRC, if available;
- 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.
Dependencies are inferred from the claim text.