Method and apparatus for efficient programmable cyclic redundancy check (CRC)

摘要

A method and apparatus to optimize each of the plurality of reduction stages in a Cyclic Redundancy Check (CRC) circuit to produce a residue for a block of data decreases area used to perform the reduction while maintaining the same delay through the plurality of stages of the reduction logic. A hybrid mix of Karatsuba algorithm, classical multiplications and serial division in various stages in the CRC reduction circuit results in about a twenty percent reduction in area on the average with no decrease in critical path delay.

主权项

1. An apparatus comprising:
a plurality of reduction stages, each one of the plurality of the reduction stages to compute a product of a first operand with a first size and a second operand with a second size, wherein the first size and the second size are different sizes; wherein the first size of the first operand corresponds to one of the plurality of reduction stages; wherein each reduction state uses a multiplication algorithm in view of the size of the first operand; wherein when the first size of the first operand is less than or equal to a first threshold size, then the multiplication algorithm used to compute the product of the first operand and the second operand is a classical multiplication technique; wherein when the first size of the first operand is greater than the first threshold size, then the multiplication algorithm used to compute the product of the first operand and the second operand is a one level application of a Karatsuba (KA) multiplication technique or a two level application of the KA multiplication technique; and wherein the first threshold value is four bits.