US 9,312,883 B1Granted

Hierarchical cyclic redundancy check circuitry

AssigneeAltera Corporation

InventorsDavid W. Mendel, Gregg William Baeckler

Life of this patent

Estimating the term…

Loading patent…

Abstract

Cyclic redundancy check (CRC) circuitry of a given input data path width is provided to perform CRC on data packets with fixed/variable word length where either the start of packet or the end of packet or both don't need to be aligned with the last and first word or bit of the CRC circuitry's input data path. The CRC circuitry is organized in a hierarchical configuration. A first level performs partial cyclic redundancy checks which are then combined in a second level to perform the cyclic redundancy check from all received data words or bits independent of the start of packet and end of packet positions. The hierarchical configuration enables the increase of the input data path width without incurring the significant increase in area observed for conventional CRC circuitry. This also decreases the number and length of interconnects compared to conventional CRC circuitry, and thus facilitates timing closure.

Claims22

Dependent claims

Circuitry operable to perform cyclic redundancy check on data received in a first cycle and a second cycle that is subsequent to the first cycle, wherein the data comprises a data packet, and wherein the data packet is bounded by a start of packet and an end of packet, comprising:

a first plurality of circuits that receives at least a portion of the data packet that is partitioned into a plurality of words, comprising:
a first circuit in the first plurality of circuits that receives a first subset of the data packet in the first cycle, and that produces first subset cyclic redundancy check bits based on the first subset of the data packet, wherein the first subset of the data packet comprises a first number of words;
and
a second circuit in the first plurality of circuits that receives a second subset of the data packet in the first cycle, and that produces second subset cyclic redundancy check bits based on the second subset of the data packet, wherein the second subset of the data packet comprises a second number of words that is smaller than the first number, wherein the first plurality of circuits produces first cyclic redundancy check bits that comprise at least one of:
the first subset cyclic redundancy check bits and the second subset cyclic redundancy check bits, and
a second plurality of circuits that receives the first cyclic redundancy check bits from the first plurality of circuits, wherein the second plurality of circuits produces second cyclic redundancy check bits based on the first cyclic redundancy check bits.

3 more elements

A method for operating cyclic redundancy check (CRC) computation circuitry that performs a cyclic redundancy check calculation on a data packet, wherein the data packet comprises a plurality of words and is bounded by a start of packet and an end of packet, the method comprising:

partitioning the data packet into a plurality of subsets comprising at least first, second, and third subsets that contain respective first, second, and third numbers of words, wherein the third number is greater than the second number, wherein the second number is at least as large as the first number, wherein the first, second, and third subsets share a common word in the data packet, and wherein the first subset of words is not a subset of the third subset of words;
performing a separate partial cyclic redundancy check calculation for each data packet subset in the plurality of subsets to generate results;
and
computing cyclic redundancy check bits for the data packet by performing cyclic redundancy check calculations using results from some of the separate partial cyclic redundancy check calculations.

1 more element

A method for performing a cyclic redundancy check (CRC) calculation on a data packet with multiple data words, wherein the data packet is bounded by a start of packet and an end of packet, the method comprising:

dividing the multiple data words into groups of data words wherein at least one group of data words in the groups of data words includes more words than another group of data words in the groups of data words, wherein the another group of data words comprises a first data word that is not contained in the at least one group of data words and a second data word that is contained in the at least one group of data words and that is from the data packet;
generating first CRC results by performing partial cyclic redundancy check calculations on the groups of data words;
and
generating second CRC results by using a plurality of multiplexers to select between the first CRC results based on the start of packet.

1 more element

Dependencies are inferred from the claim text.

Facts

Application: 13/742,192Filed 15 Jan 2013
Granted: 12 Apr 2016
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

H03M 13/091
Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit: parallel or block-wise CRC computation
H03M 13/093
Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit: cRC update after modification of the information word
G06F 11/1004
Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's: to protect a block of data words, e.g. CRC or…
H03M 13/09
Using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits: error detection only, e.g.…