Efficient and scalable cyclic redundancy check circuit using Galois-field arithmetic

1. A method comprising:

receiving a plurality of constants and a slice of input data;

generating a dot product array based on the plurality of constants and the slice;

generating a partial-sum array based on a Galois-field reduction of the dot product array; and

generating individual bits of a product result based on performing an exclusive OR operation on the individual bit in the partial-sum array and a selected number of non-sequential higher-order bits in the partial-sum array.

2. The method of claim 1 , further comprising:

receiving a plurality of bit slices of input data;

generating a plurality of product results that respectively correspond to the plurality of bit slices; and

generating a cyclic redundancy check for the input data based on the plurality of product results.

3. The method of claim 2 , wherein said generating the cyclic redundancy check comprises:

XOR'ing the plurality of product results.

4. The method of claim 1 , wherein both the slice and the product result are n-bit values, where n is an integer.

5. The method of claim 1 , wherein the plurality of constants are based on an irreducible generator polynomial.

6. The method of claim 1 , wherein each of the plurality of constants are based on a 16-bit CRC polynomial that is 0x18BB7.

7. The method of claim 1 , wherein the product result is a 16-bit partial cyclic redundancy check (CRC) result and the partial-sum array is a 31-bit partial sum array and said generating the individual bits comprises:

computing the 16-bit partial CRC result by performing an exclusive OR on each of the 16 lower-order bits of the 31-bit partial sum array with a selected non-sequential number of the higher-order bits of the 31-bit partial sum array,

wherein the selected number of higher-order bits is 7, 8, 9, or 10.

8. The circuit of claim 1 , wherein the product result is S′ [15:0], the partial sum array is S[30:0], and the Boolean equations are:

S′[0]=S[0]^S[16]^S[17]^S[18]^S[19]^S[20]^S[22]^S[23]^S[26]^S[28]^S[29];

S′[1]=S[1]^S[16]^S[21]^S[22]^S[24]^S[26]^S[27]^S[28]^S[30];

S′[2]=S[2]^S[16]^S[18]^S[19]^S[20]^S[25]^S[26]^S[27];

S′[3]=S[3]^S[17]^S[19]^S[20]^S[21]^S[26]^S[27]^S[28];

S′[4]=S[4]^S[16]^S[17]^S[19]^S[21]^S[23]^S[26]^S[27];

S′[5]=S[5]^S[16]^S[19]^S[23]^S[24]^S[26]^S[27]^S[29];

S′[6]=S[6]^S[17]^S[20]^S[24]^S[25]^S[27]^S[28]^S[30];

S′[7]=S[7]^S[16]^S[17]^S[19]^S[20]^S[21]^S[22]^S[23]^S[25];

S′[8]=S[8]^S[16]^S[19]^S[21]^S[24]^S[28]^S[29];

S′[9]=S[9]^S[16]^S[18]^S[19]^S[23]^S[25]^S[26]^S[28]^S[30];

S′[10]=S[10]^S[17]^S[19]^S[20]^S[24]^S[26]^S[27]^S[29];

S′[11]=S[11]^S[16]^S[17]^S[19]^S[21]^S[22]^S[23]^S[25]^S[26]^S[27]^S[29]^S[30];

S′[12]=S[12]^S[17]^S[18]^S[20]^S[22]^S[23]^S[24]^S[26]^S[27]^S[28]^S[30];

S′[13]=S[13]^S[18]^S[19]^S[21]^S[23]^S[24]^S[25]^S[27]^S[28]^S[29];

S′[14]=S[14]^S[19]^S[20]^S[22]^S[24]^S[25]^S[26]^S[28]^S[29]^S[30]; and

S′[15]=S[15]^S[16]^S[17]^S[18]^S[19]^S[21]^S[22]^S[25]^S[27]^S[28]^S[30].

9. A system comprising:

an interface controller configured to receive input data; and

a cyclic-redundancy check (CRC) component coupled with the interface controller and including:

a plurality of multiplier circuits configured to receive constants and a respective plurality of slices of the input data, individual multiplier circuits configured to generate partial-sum arrays based on the constants and respective slices; a combiner coupled with each of the plurality of multiplier circuits and configured to generate a combined partial-sum array based on the plurality of partial-sum arrays; and

a modulo block coupled with the combiner and configured to generate a cyclic redundancy check (CRC) value based on the combined partial-sum array.

10. The system of claim 9 , wherein individual bits of the CRC value are generated based on respective subsets of bits of the combined partial-sum array as determined by Boolean equations that represent influence of higher-order bits of the combined partial-sum array on the individual bits.

11. The system of claim 9 , wherein individual multiplier circuits of the plurality of multipliers include:

a logic array configured to:

receive the constants and a slice of the input data; and

generate a dot product array based on the constants and the slice; and

a reduction block configured to generate a partial-sum array based on a Galois-field reduction of the dot product array.

12. The system of claim 9 , wherein the constants are based on a 16-bit CRC polynomial.

13. The system of claim 9 , wherein the combiner is configured to XOR the plurality of partial-sum arrays to generate the combined partial-sum array.