Parallel crc computation with data enables

Abstract

Methods and devices generate cyclic redundancy check (CRC) values for a sequence of parallel words of data. The data words may have only some of the bits enabled. The input words are preconditioned, and then a common block generates a CRC remainder value. A specific preconditioning is selected based on the number of enabled bits. Additional post-processing may be performed to the CRC remainder.

1 . A device for generating a cyclic redundancy check (CRC) on parallel input data having data enables, the parallel input data having N bits, the cyclic redundancy check using a CRC polynomial having p bits, the device comprising:
 a plurality of conditioning blocks coupled to at least a portion of an input word and an intermediate CRC value, each conditioning block configured to generate bitwise exclusive OR values of values from the input word and values from the intermediate CRC value;   a selector coupled to the conditioning blocks and configured to select the bitwise exclusive OR values from one of the conditioning blocks;   a CRC modulo block coupled to the selector and configured to generate a remainder for the selected bitwise exclusive OR values divided by the CRC polynomial.   
     
     
         2 . The device of  claim 1 , further comprising:
 a register coupled to the CRC modulo block and configured to save the generated CRC remainder; and   a second selector coupled to the registered value and an initial value, the second selector configured to supply the registered value or the initial value as the intermediate CRC value.   
     
     
         3 . The device of  claim 1 , wherein the bitwise exclusive OR values generated in each conditioning block comprise an exclusive OR of the most-significant bit of the at least a portion of the input word coupled to the conditioning block and the most-significant bit of the intermediate CRC value. 
     
     
         4 . The device of  claim 1 , wherein the plurality of conditioning blocks comprises one conditioning block for each of a plurality of potential numbers of enabled bits in the input word and the at least a portion of the input word coupled to each conditioning block matches one of the potential numbers of enabled bits in the input word. 
     
     
         5 . The device of  claim 4 , wherein the conditioning blocks coupled to only a portion of the input word are further configured to append N−n zeros to the most-significant bit position, n being the number of bits in the portion of the input word; and
 wherein each conditioning block is further configured to zero pad the generated bitwise exclusive OR values by appending zeros to the least-significant bit position to supply zero padded exclusive OR values having N+p bits. 
 
     
     
         6 . The device of  claim 4 , wherein the selector is configured to select the bitwise exclusive OR values from the conditioning blocks coupled to the at least a portion of the input word corresponding to the number of enabled bits of the input word. 
     
     
         7 . A device for generating a cyclic redundancy check (CRC) on parallel input data having data enables, the parallel input data having N bits, the cyclic redundancy check using a CRC polynomial having p bits, the device comprising:
 a plurality of preconditioning blocks coupled to at least a portion of an input word and at least a portion of an intermediate CRC value, each preconditioning block configured to generate bitwise exclusive OR values of values from the input word and values from the intermediate CRC value;   a first selector coupled to the preconditioning blocks and configured to select the bitwise exclusive OR values from one of the preconditioning blocks;   a CRC modulo block coupled to the first selector and configured to generate a CRC value for the selected bitwise exclusive OR values;   a second selector coupled to a portion of the intermediate CRC value and selecting zero values and values from the portion of the intermediate CRC value;   an exclusive OR block coupled to the CRC modulo block and the second selector and configured to generate bitwise exclusive OR values of the CRC value from the CRC modulo block and the selected values from the second selector.   
     
     
         8 . The device of  claim 7 , further comprising:
 a register coupled to the exclusive OR block and configured to save the generated generate bitwise exclusive OR values; and   a third selector coupled to the registered value and an initial value, the second selector configured to supply the registered value or the initial value as the intermediate CRC value.   
     
     
         9 . The device of  claim 7 , wherein the CRC modulo block is further configured to generate the CRC value by appending p zeros to selected bitwise exclusive OR values to produce a dividend and finding the remainder of the dividend divided by the CRC polynomial. 
     
     
         10 . The device of  claim 7 , wherein the bitwise exclusive OR values generated in each preconditioning block comprise an exclusive OR of the most-significant bit of the at least a portion of the input word coupled to the preconditioning block and the most-significant bit of the at least a portion of the intermediate CRC value coupled to the preconditioning block. 
     
     
         11 . The device of  claim 7 , wherein the plurality of preconditioning blocks comprises one preconditioning block for each of a plurality of potential numbers of enabled bits in the input word and the at least a portion of the input word coupled to each conditioning block matches one of the potential numbers of enabled bits in the input word, and when the number of bits in the at least a portion of the input word coupled to the conditioning block is less than p, the number of bits in the at least a portion of an intermediate CRC value coupled to the preconditioning block matches the number of bits in the at least a portion of the input word coupled to the conditioning block. 
     
     
         12 . The device of  claim 11 , wherein the preconditioning blocks coupled to at least a portion of the input word having more than p bits are further configured to append n−p zeros to the most-significant bit position of the bitwise exclusive OR values, n being the number of bits of the input word coupled to the preconditioning block. 
     
     
         13 . The device of  claim 12 , wherein the preconditioning blocks coupled to only a portion of the input word are further configured to append N−n zeros to the least-significant bit position of the bitwise exclusive OR values. 
     
     
         14 . The device of  claim 11 , wherein the first selector is configured to select the bitwise exclusive OR values from the preconditioning blocks coupled to the at least a portion of the input word corresponding to the number of enabled bits of the input word. 
     
     
         15 . The device of  claim 11 , wherein the second selector selects p-bit values selected from all zeros and the least-significant bits of the intermediate CRC value corresponding to each of the potential numbers of enabled bits in the input word padded with zeros in the least-significant positions. 
     
     
         16 . The device of  claim 15 , wherein the second selector is configured to, select all zeros when p or more bits are enabled in the input word and select the zero padded intermediate CRC value corresponding to the number of enabled bits in the input word when fewer than p bits are enabled in the input word. 
     
     
         17 . A method for use in generating a cyclic redundancy check (CRC) on parallel input data in a communication system having data enables, the parallel input data having N bits, the cyclic redundancy check using a CRC polynomial having p bits, the method comprising:
 receiving an input word of the input data having n enabled bits;   when n is less than N, aligning an intermediate CRC value with the enabled bits of the input word and generating bitwise exclusive OR values of the aligned intermediate CRC value and the enabled bits of the input word;   when n equals N, generating bitwise exclusive OR values of the intermediate CRC value and the bits of the input word;   padding the exclusive OR values with zeros;   generating a remainder of the zero padded exclusive OR values divided by the CRC polynomial;   supplying the remainder as an updated intermediate CRC value.   
     
     
         18 . The method of  claim 17 , wherein generating bitwise exclusive OR values comprises generating an exclusive OR of the most-significant enabled bit of the input word and the most-significant bit of the intermediate CRC value. 
     
     
         19 . The method of  claim 17 , wherein when n is less than N, generating bitwise exclusive OR values of the aligned intermediate CRC value and the enabled bits of the input word comprises, when p is less than n, appending n−p zeros to the least-significant bit position of the aligned intermediate CRC value, and when n is less than p, appending p−n zeros to the least-significant bit position of the input word; and
 when n equals N, generating bitwise exclusive OR values of the intermediate CRC value and the bits of the input word comprises, when p is less than N, appending N−p zeros to the least-significant bit position of the intermediate CRC value, and when N is less than p, appending p−N zeros to the least-significant bit position of the input word. 
 
     
     
         20 . The method of  claim 17 , wherein padding the exclusive OR values with zeros comprises:
 when n is less than N, appending N−n zeros to the most-significant bit position;   when p is greater than n, appending n zeros to the least-significant bit position; and   when n is less than p, appending p zeros to the least-significant bit position.   
     
     
         21 . The method of  claim 17 , wherein the intermediate CRC value is a string of p zeros when the input word is the first input word of a data block. 
     
     
         22 . A method of generating a cyclic redundancy check (CRC) value for a data block, the data block supplied as parallel input data having N bits and having data enables, the cyclic redundancy check using a CRC polynomial having p bits, the method comprising:
 receiving a first input word including the first N bits from the data block;   generating first bitwise exclusive OR values of an initial value and the bits of the first input word;   padding the first exclusive OR values with zeros;   generating an intermediate CRC value by finding the remainder of the zero padded first exclusive OR values divided by the CRC polynomial;   receiving additional input words having N subsequent bits from block and for each additional input word:
 generating bitwise exclusive OR values of the intermediate CRC value and the bits of the additional input word; 
 padding the exclusive OR values with zeros; and 
 generating an updated intermediate CRC value for use with a next input word by finding the remainder of the zero padded exclusive OR values divided by the CRC polynomial; 
   receiving a final input word having n enabled bits from the data block, n less than or equal to N;   when n is less than N, aligning the intermediate CRC value with the enabled bits of the final input word and generating final bitwise exclusive OR values of the aligned intermediate CRC value and the enabled bits of the final input word;   when n equals N, generating final bitwise exclusive OR values of the intermediate CRC value and the bits of the final input word;   padding the final exclusive OR values with zeros; and   generating the CRC value by finding the remainder of the zero padded final exclusive OR values divided by the CRC polynomial.   
     
     
         23 . The method of  claim 22 , wherein generating first bitwise exclusive OR values of an initial value and the bits of the first input word comprises generating an exclusive OR of the most-significant bit of the initial value and the most-significant bit of the first input word;
 wherein generating bitwise exclusive OR values of the intermediate CRC value and the bits of the additional input word comprises generating an exclusive OR of the most-significant bit of the intermediate CRC value and the most-significant bit of the input word;   wherein generating final bitwise exclusive OR values of the aligned intermediate CRC value and the enabled bits of the final input word comprises generating an exclusive OR of the most-significant bit of the intermediate CRC value and the most-significant enabled bit of the final input word; and   wherein generating bitwise final exclusive OR values of the intermediate CRC value and the bits of the final input word comprises generating an exclusive OR of the most-significant bit of the intermediate CRC value and the most-significant bit of the final input word.   
     
     
         24 . The method of  claim 22 , wherein generating first bitwise exclusive OR values of an initial value and the bits of the first input word comprises, when p is less than N, appending N−p zeros to the least-significant bit position of the initial value, and, when N is less than p, appending p−N zeros to the least-significant bit position of the first input word;
 wherein generating bitwise exclusive OR values of the intermediate CRC value and the bits of the additional input word comprises, when p is less than N, appending N−p zeros to the least-significant bit position of the aligned intermediate CRC value, and, when N is less than p, appending p−N zeros to the least-significant bit position of the additional input word; 
 wherein when n is less than N, generating final bitwise exclusive OR values of the aligned intermediate CRC value and the enabled bits of the final input word comprises, when p is less than n, appending n−p zeros to the least-significant bit position of the aligned intermediate CRC value, and, when n is less than p, appending p−n zeros to the least-significant bit position of the final input word; 
 wherein when n equals N, generating final bitwise exclusive OR values of the intermediate CRC value and the bits of the final input word comprises, when p is less than N, appending N−p zeros to the least-significant bit position of the intermediate CRC value, and, when N is less than p, appending p−N zeros to the least-significant bit position of the input word. 
 
     
     
         25 . The method of  claim 22 , wherein padding the first exclusive OR values with zeros comprises, when p is less than N, appending N zeros to the least-significant bit position and, when N is less than p, appending p zeros to the least-significant bit position;
 wherein padding the exclusive OR values with zeros comprises, when p is less than N, appending N zeros to the least-significant bit position and, when N is less than p, appending p zeros to the least-significant bit position; and   wherein padding the final exclusive OR values with zeros comprises, when n is less than N, appending N−n zeros to the most-significant bit position, when p is less than n, appending n zeros to the least-significant bit position, and, when n is less than p, appending p zeros to the least-significant bit position.   
     
     
         26 . The method of  claim 22 , wherein the initial value is a string of p zeros. 
     
     
         27 . A method for generating a cyclic redundancy check (CRC) on parallel input data in a communication system having data enables, the parallel input data having N bits, the cyclic redundancy check using a CRC polynomial having p bits, the method comprising:
 receiving an input word of the input data having n enabled bits;   when n is less than p, selecting a first portion of an intermediate CRC value and generating bitwise exclusive OR values of the first portion of the intermediate CRC value and the enabled bits of the input word;   when n is not less than p, generating bitwise exclusive OR values of the intermediate CRC value and the enabled bits of the input word;   when p equal N, selecting the exclusive OR values as a CRC operand and, when p not equal N, padding the exclusive OR values with zeros to produce the CRC operand;   generating a CRC value for the CRC operand;   when n is less than p, selecting a second portion of the intermediate CRC value, generating bitwise exclusive OR values of the second portion of the intermediate CRC value and the generated CRC value, and supplying the exclusive OR values as an updated intermediate CRC value; and   when n is not less than p, supplying the generated CRC value as the updated intermediate CRC value.   
     
     
         28 . The method of  claim 27 , wherein generating the CRC value comprises appending p zeros to the CRC operand to produce a dividend and finding the remainder of the dividend divided by the CRC polynomial. 
     
     
         29 . The method of  claim 27 , wherein the first portion of the intermediate CRC value is the n most-significant bits of the intermediate CRC value and the second portion of the intermediate CRC value is the p−n least-significant bits of the intermediate CRC value. 
     
     
         30 . The method of  claim 29 , wherein generating bitwise exclusive OR values of the first portion of the intermediate CRC value and the enabled bits of the input word comprises generating a exclusive OR of the most-significant enabled bit of the input word and the most-significant bit of the intermediate CRC value, and
 wherein generating bitwise exclusive OR values of the intermediate CRC value and the enabled bits of the input word comprises generating a exclusive OR of the most-significant enabled bit of the input word and the most-significant bit of the first portion of the intermediate CRC value.   
     
     
         31 . The method of  claim 27 , wherein padding the exclusive OR values with zeros comprises:
 when n is less than N, appending N−n zeros to the most-significant bit position; and   when n is less than p, appending p−n zeros to the least-significant bit position.   
     
     
         32 . The method of  claim 27 , wherein the intermediate CRC value is a string of p zeros when the input word is the first input word of a data block. 
     
     
         33 . A method for use in generating a cyclic redundancy check (CRC) on parallel input data in a communication system having data enables, the parallel input data having N bits, the cyclic redundancy check using a CRC polynomial having p bits, p less than N, the method comprising:
 receiving an input word of the input data having n enabled bits;   when n is less than p, generating bitwise exclusive OR values of the n most-significant bits of the intermediate CRC value and the enabled bits of the input word and appending p−n zeros to the most-significant bit position to produce a CRC operand;   when n equals p, generating bitwise exclusive OR values of the intermediate CRC value and the enabled bits of the input word and appending N−n zeros to the most-significant bit position to produce a CRC operand;   when n is greater than p, generating bitwise exclusive OR values of the enabled bits of the input word and the intermediate CRC value with n−p zeros appended to the least-significant bit position and, when n is less than N, appending N−n zeros to the most-significant bit position to produce a CRC operand;   generating a CRC value for the CRC operand by appending p zeros to the CRC operand to produce a dividend and finding the remainder of the dividend divided by the CRC polynomial;   when n is less than p, selecting p−n least-significant bits of the intermediate CRC value, appending n zeros to the least-significant bit position of the selected bits of the intermediate CRC value, generating bitwise exclusive OR values of selected bits of the intermediate CRC value with appended zeros and the generated CRC value, and supplying the exclusive OR values as an updated intermediate CRC value; and   when n is not less than p, supplying the generated CRC value as the updated intermediate CRC value.   
     
     
         34 . A method for use in generating a cyclic redundancy check (CRC) on parallel input data in a communication system having data enables, the parallel input data having N bits, the cyclic redundancy check using a CRC polynomial having p bits, p equal N, the method comprising:
 receiving an input word of the input data having n enabled bits;   when n is less than p, generating bitwise exclusive OR values of the n most-significant bits of the intermediate CRC value and the enabled bits of the input word and appending p−n zeros to the most-significant bit position to produce a CRC operand;   when n equals p, generating bitwise exclusive OR values of the intermediate CRC value and the bits of the input word to produce a CRC operand;   generating a CRC value for the CRC operand by appending p zeros to the CRC operand to produce a dividend and finding the remainder of the dividend divided by the CRC polynomial;   when n is less than p, selecting p−n least-significant bits of the intermediate CRC value, appending n zeros to the least-significant bit position of the selected bits of the intermediate CRC value, generating bitwise exclusive OR values of selected bits of the intermediate CRC value with appended zeros and the generated CRC value, and supplying the exclusive OR values as an updated intermediate CRC value; and   when n equals p, supplying the generated CRC value as the updated intermediate CRC value.   
     
     
         35 . A method for use in generating a cyclic redundancy check (CRC) on parallel input data in a communication system having data enables, the parallel input data having N bits, the cyclic redundancy check using a CRC polynomial having p bits, p greater than N, the method comprising:
 receiving an input word of the input data having n enabled bits;   generating bitwise exclusive OR values of the n most-significant bits of the intermediate CRC value and the enabled bits of the input word and, when n is less than N, appending N−n zeros to the most-significant bit position of the exclusive OR values to produce a CRC operand;   generating a CRC value for the CRC operand by appending p zeros to the CRC operand to produce a dividend and finding the remainder of the dividend divided by the CRC polynomial;   selecting p−n least-significant bits of the intermediate CRC value and appending n zeros to the least-significant bit position of the selected bits of the intermediate CRC value;   generating bitwise exclusive OR values of selected bits of the intermediate CRC value with appended zeros and the generated CRC value; and   supplying the exclusive OR values as an updated intermediate CRC value.