Hardware-efficient CRC generator for high speed communication networks
View Patent ↗A cyclic redundancy check (CRC) generator, in accordance with a specific embodiment of the present invention, generates a 32-bit CRC for each packet whose data bytes are carried over a 128-bit bus by first dividing the data bytes by a 123 nd degree generator polynomial and subsequently dividing the remainder of the first division by a 32 nd degree generator polynomial. Data bytes of a new packet are divided by a different dividing logic than those of a current packet. The remainder of division performed on the bytes of a new packet are supplied to the dividing logic adapted to divide the bytes of a current packet. The division by the 123 nd degree generator polynomial is performed on a per byte basis, with the remainder of the division of the (i+1) th byte being used in the division of the i th byte.
1. A method comprising:
dividing data bytes of a first N-bit word in a first generator polynomial operation to generate a first remainder; and
dividing the first remainder in a second generator polynomial operation to generate a M-bit cyclic redundancy check.
2. The method of claim 1 , further comprising determining if the data bytes of the N-bit word are part of a current data packet or a new data packet.
3. The method of claim 1 , wherein dividing the data bytes of the first N-bit word comprises dividing data bytes that belong to a new data packet using the first generator polynomial operation to generate a third remainder.
4. The method of claim 3 , wherein dividing data bytes that belong to the new data packet comprises dividing data bytes that belong to a current data packet using the first generator polynomial operation to generate a fourth remainder.
5. The method of claim 4 , further comprising dividing the third remainder or the fourth remainder using the second generator polynomial operation to generate the M-bit cyclic redundancy check.
6. A method comprising:
dividing data bytes of a N-bit word in a two-stage division operation, the two stage division operation includes a first-stage division operation that employs a first generator polynomial for dividing the data bytes to generate a first remainder, and a second-stage division operation that employs a second generator polynomial to generate a cyclic redundancy check from the first remainder.
7. The method of claim 6 , further comprising decoding the N-bit word to determine which data bytes belong to a current data packet or a new data packet.
8. The method of claim 7 , wherein determining which data bytes belong to a current data packet or a current data packet comprises determining the end position of a current data packet or a beginning position of a new data packet.
9. The method of claim 6 , wherein the first-stage division operation comprises dividing data bytes of the N-bit word associated with a new data packet with the first generator polynomial to generate a second remainder.
10. The method of claim 9 , wherein the first-stage division operation comprises dividing data bytes of the N-bit word associated with a current data packet with the first generator polynomial to generate a third remainder.
11. The method of claim 10 , wherein the first remainder comprises the second remainder or the third remainder.
12. An integrated circuit, the circuit comprising:
a first logic circuit employing a first generator polynomial to derive a first remainder from data bytes of an N-bit word; and
a second logic circuit employing a second generator polynomial to derive a cyclic redundancy check from the first remainder.
13. The integrated circuit of claim 12 , wherein the first logic circuit comprises a first dividing logic circuit capable of generating the first generator polynomial for dividing data bytes that belong to new data packets to generate a second remainder.
14. The integrated circuit of claim 12 , wherein the first logic circuit comprises a second dividing logic circuit capable of generating the first generator polynomial for dividing data bytes that belong to current data packets to generate a third remainder.
15. The integrated circuit of claim 12 , wherein the second logic circuit comprises a third dividing logic circuit capable of generating the second generator polynomial for dividing the first remainder to derive the cyclic redundancy check.
16. An integrated circuit for generating a cyclic redundancy check, the circuit comprising:
a data selection circuit for determining which data bytes of N-bit data belong to a new data packet or to a current data packet;
a first logic circuit coupled to the data selection circuit, wherein the first logic circuit is capable generating a first remainder from data bytes of the new data packet;
a second logic circuit coupled to the data selection circuit, wherein the second logic circuit is capable of generating a second remainder from data bytes of the current data packet; and
a third logic circuit capable of generating the cyclic redundancy check from either the first remainder or the second remainder.
17. The integrated circuit of claim 16 , wherein the data selection circuit comprises a decoder circuit capable of generating a select signal indicative of a new data packet or a current data packet.
18. The integrated circuit of claim 17 , wherein the data selection circuit comprises a multiplexer circuit that in response to the select signal directs data bytes of the N-bit data to the first logic circuit or the second logic circuit.
19. The integrated circuit of claim 16 , wherein the first logic circuit comprises a dividing circuit capable of dividing data bytes of the N-bit data from the new data packet by a first generator polynomial.
20. The integrated circuit of claim 16 , wherein the second logic circuit comprises a dividing circuit capable of dividing data bytes of the N-bit data from the current data packet by a first generator polynomial.
21. The integrated circuit of claim 16 , wherein the third logic circuit comprises a dividing circuit capable of dividing either the first remainder or the second remainder by a second generator polynomial to generate the cyclic redundancy check.