Scalable cyclic redundancy check circuit

FIELD OF THE INVENTION

0001The present invention relates to the field of cyclic redundancy check circuits; more specifically, it relates to a scalable cyclic redundancy check circuit.

BACKGROUND OF THE INVENTION

0002Error checking of data transmissions between sending and receiving devices use a cyclic redundancy check circuit (CRC) implementing various CRC codes in both the sending and receiving devices. The CRC code is calculated by an exclusive OR (XOR) subtree. As high speed serial interconnect technologies evolve, many of the standards governing these technologies allow bandwidths well beyond the traditional 96 and 128 bits per cycle bandwidths, yet maintain the same transmission frequency as for the older smaller 96 and 128 bits per cycle bandwidths. As bandwidth increases, the complexity and depth of the XOR subtree must increase as the need to process more bits per clock cycle grows. Traditional CRC designs when applied to large bandwidth data transmissions very quickly develop the interrelated problems of timing closure and physical silicon area required to implement the XOR subtree. Therefore, there is a need for a CRC circuit that can handle large bandwidths without timing closure problems.

SUMMARY OF THE INVENTION

0003A first aspect of the present invention is a cyclic redundancy check circuit, comprising: a W-bit packet data slice latch having outputs; a multiple level XOR subtree having inputs and outputs, each level comprising one or more XOR subtrees, each output of the packet data slice latch coupled to an input of the multiple level XOR subtree, each lower level XOR subtree of the multiple level XOR subtree coupled to a higher level XOR subtree of the multiple level XOR subtree through an intervening latch level; a remainder XOR subtree having inputs and outputs; a combinational XOR subtree having inputs and outputs, the outputs of the remainder XOR subtree and the outputs of the multiple level XOR subtree coupled to the inputs of the combinational XOR subtree; and an M-bit current CRC result latch having inputs and outputs, the output of the combinational XOR subtree coupled to the inputs of the current CRC result latch and the outputs of the M-bit current CRC result latch coupled to the inputs of the remainder XOR subtree.

0004A second aspect of the present invention is a method for cyclic redundancy check calculation, comprising: providing a W-bit packet data slice latch having outputs; providing a multiple level XOR subtree having inputs and outputs, each level comprising one or more XOR subtrees, each output of the packet data slice latch coupled to an input of the multiple level XOR subtree, each lower level XOR subtree of the multiple level XOR subtree coupled to a higher level XOR subtree of the multiple level XOR subtree through an intervening latch level; providing a remainder XOR subtree having inputs and outputs; providing a combinational XOR subtree having inputs and outputs, the outputs of the remainder XOR subtree and the outputs of the multiple level XOR subtree coupled to the inputs of the combinational XOR subtree; and providing an M-bit current CRC result latch having inputs and outputs, the output of the combinational XOR subtree coupled to the inputs of the current CRC result latch and the outputs of the M-bit current CRC result lath coupled to the inputs of the remainder XOR subtree.

0005A third aspect of the present invention is a method of designing an M-bit cyclic redundancy check circuit, the method comprising: partitioning an XOR function of the cyclic redundancy check circuit into a remainder XOR partition and a multiple level packet data slice XOR partition; determining I, the largest number of bits I of a subset of the M-bits of a CRC result required to generate output bits of a remainder partition XOR subtree of the cyclic redundancy check circuit; determining Z, the largest number of inputs to an XOR gate in a design library to be used in the cyclic redundancy check circuit; calculating K, the maximum number of XOR stages comprised of Z-input XOR gates in the remainder XOR subtree; calculating N, the maximum number of inputs to any XOR subtree in any level of a multiple level XOR subtree partition of the cyclic redundancy check circuit; partitioning the multiple level XOR subtree partition into XOR subtrees having no number of inputs that is larger than a number of inputs to the remainder XOR subtree; and inserting a latch between each XOR subtree of a lower level partition of the packet data slice XOR partition and a immediately higher level partition of the packet data slice XOR partition.

BRIEF DESCRIPTION OF DRAWINGS

0006The features of the invention are set forth in the appended claims. The invention itself, however, will be best understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

0007<figref idref="DRAWINGS">FIG. 1</figref> is an exemplary related art 32-bit CRC circuit.

0008<figref idref="DRAWINGS">FIG. 2</figref> is an exemplary 32-bit CRC circuit according to the present invention;

0009<figref idref="DRAWINGS">FIG. 3</figref> is a generic scalable M-bit CRC circuit according to the present invention; and

0010<figref idref="DRAWINGS">FIG. 4</figref> is a flowchart of the method of designing a scalable CRC circuit according to the present invention.

DETAILED DESCRIPTION OF THE INVENTION

0011The terminology Q by P-way XOR subtree defines an XOR subtree having Q outputs and (P×Q) inputs. The notation Q^P should be read as Q^P.

0012<figref idref="DRAWINGS">FIG. 1</figref> is an exemplary related art 32-bit CRC circuit. In <figref idref="DRAWINGS">FIG. 1</figref>, a CRC circuit <b>100</b> includes a 128-bit packet data slice latch <b>105</b>, a single, 160-bit input/32-bit output XOR tree <b>110</b> and a 32-bit current CRC remainder latch <b>115</b>. The bit width of the remainder latch defines the CRC type, in the present example a 32-bit CRC or CRC32. The output of packet slice latch <b>105</b> is connected to the input of XOR tree <b>110</b> by a 128-bit bus; each bit being connected to a different input. The output of XOR subtree <b>110</b> is connected to the input of current CRC remainder latch <b>115</b>. The output of current CRC remainder latch <b>115</b> is a 32-bit CRC output bus <b>120</b>, which is also connected to the input of XOR tree <b>110</b> to provide the cyclic portion of the CRC result. Each output bit of current CRC remainder latch <b>115</b> is connected to a different input of XOR tree <b>110</b>, and to inputs not used by packet data slice latch <b>105</b>.

0013Data bits are moved from packet data slice latch <b>105</b> through XOR tree <b>110</b> and current CRC remainder latch <b>115</b> by a clock signal CLK. The same CLK signal moves data bits out of current CRC remainder latch <b>115</b> onto CRC output bus and into XOR tree <b>110</b>. The arrangement of XOR gates in XOR tree <b>110</b> implements the CRC code and performs the actual CRC calculation.

0014As the number of input bits to an XOR tree increases, the depth of XOR gates (the number of XOR gates connected in series from the input to the output of the XOR tree) as well as the number of inputs in each individual XOR gate in the XOR tree increases. At some point, it will take more than a single clock cycle for data bits to travel through the XOR tree and the CRC circuit will generate an erroneous CRC result. The present invention avoids XOR tree data bit propagation time problems by partitioning the XOR tree into XOR-subtrees, which are each small enough not to have a data bit propagation time problem. It should be noted that data bit propagation time is dependent on the integrated circuit technology that the CRC circuit is physically fabricated in.

0015The present invention partitions the XOR tree into two main partitions. The first partition is a single XOR subtree for processing the remainder of the CRC. The second partition is a multi-level partition, each level comprised of multiple XOR subtrees. Each of these multiple XOR subtrees is no larger than the remainder XOR subtree. Each level of XOR subtrees perform a portion of the CRC calculation and each XOR subtree belonging to a particular level performs a portion of the portion of the CRC calculation performed by the level. The size of the remainder subtree is chosen so that all the XOR calculation it performs can be completed in one clock cycle. Since all the XOR subtrees of the multi-level partition are the size (or smaller) each levels portion of the CRC is likewise performed in one clock cycle or less.

0016<figref idref="DRAWINGS">FIG. 2</figref> is an exemplary CRC circuit according to the present invention. In <figref idref="DRAWINGS">FIG. 2</figref>, a CRC circuit <b>200</b> includes a 2048-bit packet data slice latch <b>205</b>, 27 sets (in subsets of 8) of 32 by (0 to 5)-way leaf XOR subtrees <b>210</b> and corresponding 32-bit latches <b>215</b>, 27 sets of 32 by 8-way XOR subtrees <b>220</b> and corresponding 32-bit latches <b>225</b>, a 32 by 27-way XOR subtree <b>230</b>, a 32 by 2-way XOR subtree <b>235</b>, a remainder XOR subtree <b>240</b> and a 32-bit current CRC remainder latch <b>245</b>. Packet data slice latch <b>205</b> is a partition level 0 latch. Latches <b>215</b> are partition level 1 latches, and latches <b>225</b> are partition level 2 latches, so there are three latch levels in CRC circuit <b>200</b>. Leaf XOR subtrees <b>210</b>, XOR subtrees <b>220</b> and <b>230</b> may be considered to be in a data slice XOR subtree.

0017Each leaf XOR subtree <b>210</b> is connected to packet data slice latch <b>205</b> by 0 to 5 32-bit inputs (i. e. 160 inputs to each leaf XOR subtree). Each of the 32 outputs of each leaf XOR subtree <b>210</b> is connected to a different input of a corresponding latch <b>215</b>. There need not be any particular relationship between a particular input of a particular leaf XOR subtree <b>210</b> and a particular bit from packet data slice latch <b>205</b>. Each of the 32 outputs of each latch <b>215</b> of each set of 8 latches <b>215</b> is connected to a different input of a corresponding XOR subtree <b>220</b>. Each of the 32 outputs of each latch <b>225</b> is connected to a different input of XOR subtree <b>230</b>. Each of the 32 outputs of XOR subtree <b>230</b> is connected to a different input of a 32 member first subset of the 64 inputs of XOR subtree <b>235</b>. Each of the 32 outputs of XOR subtree <b>235</b> is connected to a different input of current CRC remainder latch <b>245</b>. The 32 outputs of current CRC remainder latch <b>245</b> are connected to a 32-bit output bus <b>250</b> and to a different input of remainder XOR subtree <b>240</b>. Each of the 32 outputs of remainder XOR subtree <b>245</b> is connected to a different input of a second 32 member of the 64 inputs of XOR subtree <b>235</b>. The two subsets do not have common inputs.

0018Data bits are moved from packet data slice latch <b>205</b> through leaf XOR subtrees <b>210</b> into latches <b>215</b> by clock signal CLK. Data bits are moved from latches <b>215</b> through XOR subtrees <b>220</b> and into latches <b>225</b> by clock signal CLK. Data bits are moved from latches <b>225</b>, through XOR subtrees <b>230</b> and <b>235</b> into current CRC remainder latch <b>245</b> by clock signal CLK Data bits are moved from current remainder latch <b>245</b> onto output bus <b>250</b> and through remainder XOR subtree <b>240</b> and XOR subtree <b>235</b> back into current CRC remainder latch <b>245</b> by clock signal CLK. The specific arrangement of XOR gates in leaf XOR subtree <b>210</b> and XOR subtrees <b>220</b>, <b>230</b>, <b>235</b> and <b>240</b> implements the CRC code and performs the actual CRC calculation.

0019The structure of CRC circuit <b>200</b> is determined by maximum delay through the XOR subtree <b>240</b>. For example, if XOR subtree <b>240</b> is implemented using only 3-input and 2-input XOR gates and the largest CRC remainder expected is 1059-bits then the maximum size of a subset of the 32-bit CRC remainder is 20-bits. The value 1059 is specific to the particular CRC calculation and number of bits processed per CLK cycle. The value 20 is also determined by the particular CRC calculation as are the particular the bits of the 32-bit input to remainder XOR subtree <b>240</b> in the subset. The XOR gate structure containing the shortest delay path is realized in a 3 (the smallest whole positive number greater than log₃20) XOR gate level XOR subtree. The maximum number of inputs of a 3 XOR gate level XOR subtree using 3 input XOR gates is 3³or 27. Thus when partitioning the XOR subtree comprised of leaf XOR subtrees <b>210</b> and XOR subtrees <b>220</b>, <b>230</b> and <b>235</b>, each partition must not be larger than a 27 input XOR operation. The minimum number of latch stages in the XOR subtree comprised of leaf XOR subtrees <b>210</b> and XOR subtrees <b>220</b>, <b>230</b> and <b>235</b> is 3 (the smallest whole positive number greater than log₂₇1059). To process 2048-bits of data in one clock cycle, the worst-case single XOR operation must operate on 1059 bits.

0020A data packet's 32-bit CRC remainder is calculated by initializing CRC <b>200</b> to a value of 0×FFFF_FFFF, and then processing the packet through the CRC circuit. Given the current CRC remainder value and a 2048-bit slice of the data packet, the next CRC remainder is calculated and then latched. The next CRC remainder value is calculated by performing a bit wise XOR operation on the two 32-bit outputs of XOR subtree <b>235</b> and remainder XOR subtree <b>240</b>. Each bit of the output of remainder XOR subtree <b>240</b> is calculated by performing an XOR operation over a subset of bits of the current CRC remainder value. Each bit of the output of XOR subtree <b>230</b> is calculated by performing an XOR operation over a subset of bits of the portion of packet data currently being processed.

0021While the output of remainder XOR subtree <b>240</b> is the result a single XOR operation, the output XOR subtree <b>230</b> is the result of several levels or partitions of XOR operations performed respectively by XOR subtree <b>230</b>, XOR subtrees <b>220</b> and leaf XOR subtrees <b>210</b>. The topmost XOR operation partition (that performed by XOR subtree <b>230</b>) is picked such that each output is fed by an XOR operation on 27 inputs. The remaining, lower XOR operation partition sizes (those performed by XOR subtrees <b>220</b> and by leaf XOR subtrees <b>210</b>) are picked arbitrarily to balance partition sizes across the bottom two partitions. There are 244 partitions total. (8×27=216 level 0 partitions, 27 level 1 partitions and 1 level 2 partition.) The output of each partition, except for the last partition, is latched. When the last 2048-bits of a data packet are processed, the next CRC remainder is the CRC value for the packet.

0022<figref idref="DRAWINGS">FIG. 3</figref> is a generic scalable M-bit CRC circuit according to the present invention. In <figref idref="DRAWINGS">FIG. 3</figref>, a CRC circuit <b>300</b> includes a W-bit packet data slice latch <b>305</b>, N^YM by N-way leaf XOR subtrees <b>310</b> and corresponding M-bit latches <b>315</b> (N, Y and M are defined infra), intermediate levels of M by N-way XOR subtrees and corresponding latches (not shown), N²of M by N-way XOR subtrees <b>320</b> and corresponding M-bit latches <b>325</b>, N M by N-way XOR subtrees <b>330</b> and corresponding M-bit latches <b>335</b>, a M by N way XOR subtree <b>340</b>, an M by 2 way XOR subtree <b>345</b>, a remainder XOR subtree <b>350</b> and an M-bit current CRC remainder latch <b>360</b>. Packet data slice latch <b>305</b> is a partition level 0 latch. Latches <b>315</b> are partition level 1 latches, latches <b>315</b> are partition level (Y−1) latches and latches <b>335</b> are partition level Y latches, so there are Y+1 partition levels in CRC circuit <b>300</b>. Leaf XOR subtrees <b>310</b>, intermediate XOR subtrees (not shown), XOR subtrees <b>320</b>, <b>325</b> and <b>340</b> may be considered to be in a data slice XOR subtree.

0023Each leaf XOR subtree <b>310</b> is connected to packet data slice latch <b>305</b> by variable numbers of M-bit input. Each of the M outputs of each leaf XOR subtree <b>310</b> is connected to a different input of a corresponding latch <b>315</b>. There need not be any particular relationship between a particular input of a particular leaf XOR subtree <b>310</b> and a particular bit from packet data slice latch <b>305</b>. After progressing through intermediate partition levels, each of the M outputs of each of XOR subtrees <b>320</b> is connected to a different input of corresponding latches <b>325</b>. Each of the M outputs of each latch <b>325</b> is connected to a different input of corresponding XOR subtrees <b>330</b>. Each of the M outputs of XOR subtrees <b>330</b> are connected a different input of corresponding latches <b>335</b>. Each of the M inputs of latches <b>335</b> is connected to different inputs of XOR subtree <b>340</b>. Each of the M outputs of XOR subtree <b>340</b> is connected to a different input of a first M member subset of the 2M inputs of XOR subtree <b>345</b>. Each of the M outputs of XOR subtree <b>345</b> is connected to a different input of current CRC remainder latch <b>355</b>. The M outputs of current CRC remainder latch <b>355</b> are connected to an M-bit output bus <b>360</b> and to different inputs of remainder XOR subtree <b>350</b>. Each of the M outputs of remainder XOR subtree <b>350</b> is connected to a different input of a second M member subset of the 2M inputs of XOR subtree <b>345</b>. The two subsets do not have common inputs.

0024Data bits are moved from packet data slice latch <b>305</b> through the (Y−1) partition levels by a clock signal CLK applied to the latches within each partition level. The specific arrangement of XOR gates in the XOR subtrees of the various partition levels of CRC circuit <b>300</b> and XOR subtrees <b>340</b> and <b>345</b> and remainder XOR subtree <b>350</b> implements the CRC code and performs the actual CRC calculation.

0025The structure of CRC circuit <b>300</b> is determined by maximum delay through the XOR subtree <b>350</b>. For example, if XOR subtree <b>350</b> is implemented using only Z-input or smaller XOR gates and the largest CRC remainder expected is J-bits then the maximum size of a subset of the M-bit CRC remainder is I-bits. The value I is specific to the particular CRC calculation and number of bits processed per CLK cycle. The value J is determined by the particular CRC calculation as are the particular bits of the M-bit input to remainder XOR subtree <b>350</b> in the subset. The XOR gate structure containing the shortest delay path is realized in a K (the smallest whole positive number greater than log_ZI) XOR gate level XOR subtree. The maximum number of inputs of a K level XOR subtree using Z input XOR gates is K^Z=N. Thus when partitioning the XOR subtree comprised of leaf XOR subtrees <b>310</b> through XOR subtree <b>345</b>, each partition must not be larger than a J input XOR operation (which is the size of XOR operation performed by remainder XOR subtree <b>340</b>). The minimum number of latch stages in the XOR subtree comprised of leaf XOR subtrees <b>310</b> through XOR subtree <b>345</b> is Y+1 (the smallest whole positive number greater than log_NJ).

0026A data packet's M-bit CRC remainder is calculated by initializing CRC <b>300</b> to a value of −1, and then processing the packet through the CRC circuit. Given the current CRC remainder value and a W-bit slice of the data packet, the next CRC remainder is calculated and then latched. The next CRC remainder value is calculated by performing a bit wise XOR operation on the two M-bit outputs of XOR subtree <b>345</b> and remainder XOR subtree <b>350</b>. Each bit of the output of remainder XOR subtree <b>350</b> is calculated by performing an XOR operation over a subset of bits of the current CRC remainder value. Each bit of the output of XOR subtree <b>340</b> is calculated by performing an XOR operation over a subset of bits of the portion of packet data currently being processed.

0027Another way to understand the structure of CRC circuit <b>300</b> is that the number of levels of said XOR subtrees in the XOR subtree from leaf XOR subtrees <b>310</b> to XOR subtree <b>340</b> is a function of A, the maximum number of input bits to all leaf XOR subtrees <b>310</b> to give a single output bit of XOR subtree <b>340</b> and of B, the maximum number of input bits to remainder XOR subtree <b>350</b> to give a single output bit of the remainder XOR subtree. The number of levels of said XOR subtrees in the XOR subtree from leaf XOR subtrees <b>310</b> to XOR subtree <b>340</b> being log_BA.

0028While the output of remainder XOR subtree <b>350</b> is the result of a single XOR operation, the output XOR subtree <b>340</b> is the result of several levels or partitions of XOR operations performed as illustrated in <figref idref="DRAWINGS">FIG. 3</figref>. The topmost XOR operation partition (that performed by XOR subtree <b>340</b>) is picked such that each output is fed by an XOR operation on N inputs. The output of each partition, except for the last partition, is latched. When the last W-bits of a data packet are processed, the next CRC remainder is the CRC value for the packet.

0029<figref idref="DRAWINGS">FIG. 4</figref> is a flowchart of the method of designing a scalable CRC circuit according to the present invention. In step <b>400</b> it the largest number of bits in a subset of bits of a CRC remainder to be processed by an XOR operation on that subset of bits by the remainder XOR subtree is determined. This number designated I, and the particular bits of the CRC remainder making up the subset is a function of the CRC function being implemented.

0030In step <b>405</b>, from a design library <b>410</b> of circuit elements, the XOR gate having the largest number of inputs is determined. Generally this XOR gate is determined by the length of the data path through the XOR gate, its attendant delay, and the amount of integrated circuit real estate it requires. This number of inputs is designated Z.

0031In step <b>415</b>, the largest number of XOR gate levels K, in the remainder XOR subtree is calculated using the formula K=smallest whole positive number greater than (log_ZI).

0032In step <b>420</b>, the largest number of XOR operations N, that are no slower than the XOR operations performed by the remainder XOR subtree is calculated using the formula N=K^Z.

0033In step <b>425</b>, the data slice XOR subtree operating on data packet slices is partitioned into XOR subtrees such that no XOR subtree of the data slice XOR subtree has more inputs then the remainder XOR subtree.

0034In step <b>430</b>, the XOR output of every XOR subtree in the data slice XOR subtree are latched except the topmost XOR subtree.

0035Thus, the present invention provides a scalable CRC circuit that can handle large bandwidths without timing closure problems.

0036The description of the embodiments of the present invention is given above for the understanding of the present invention. It will be understood that the invention is not limited to the particular embodiments described herein, but is capable of various modifications, rearrangements and substitutions as will now become apparent to those skilled in the art without departing from the scope of the invention. Therefore it is intended that the following claims cover all such modifications and changes as fall within the true spirit and scope of the invention.