Single cycle cyclic redundancy checker/generator

• US 6,810,501 B1
• Filed: 01/03/2001
• Issued: 10/26/2004
• Est. Priority Date: 01/03/2001
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Padmanabhan, Ramesh, Ferguson, Dennis C., Skibo, Thomas Michael, Wu, Chang-Hong, Chen, Devereaux C.
• Primary Examiner(s): Lamarre, Guy J.
• Application Number:
  US09/752,829
• Time in Patent Office: 1,392 Days
• Field of Search: 714/781, 714/757, 714/758, 714/52, 714/759, 714/761, 714/804, 714/801, 714/762, 714/787, 714/788, 708/521, 708/530-531, 708/534, 370/392, 370/394, 370/395.31, 370/399, 370/395.51
• US Class Current: 714/781
• CPC Class Codes: H03M 13/091 Parallel or block-wise CRC computation

Abstract

A system updates a cyclic redundancy check (CRC) value. The system receives data containing an arbitrary number of valid and invalid portions. The valid portions are positioned adjacent to one another. The system also receives a signal representing a quantity of valid portions in the data and a current CRC value. The system updates the current CRC value using the data and signal in a single clock cycle.

Claims

1. A method for updating a cyclic redundancy check (CRC) value, comprising:

receiving data containing valid and invalid portions, the valid portions being adjacent to one another;

receiving first information representing the number of valid portions in the data;

receiving second information representing a current CRC value; and

determining the updated CRC value based on the data, first information, and second information.

2. The method of claim 1 wherein the receiving data, the receiving first information, the receiving second information, and the determining occurs in a single clock cycle.

3. A system for updating a cyclic redundancy check (CRC) value, comprising:

means for receiving data containing valid and invalid portions, the valid portions being adjacent to one another;

means for receiving first information representing the number of valid portions in the data;

means for receiving second information representing a current CRC value; and

means for determining the updated CRC value based on the data, first information, and second information.

4. In a network device, a cyclic redundancy checker (CRC) comprising:

a plurality of CRC units configured to receive data, containing valid and invalid bits, the valid bits being adjacent to one another, and a current CRC value, and generate CRC outputs based on the received data and current CRC value; and

at least one multiplexer configured to receive the CRC outputs and information representing a number of valid bits in the received data, and output one of the received CRC outputs based on the information.

5. The CRC of claim 4 wherein the plurality of CRC units is organized in a multiple level tree structure.

6. The CRC of claim 4 wherein the plurality of CRC units is organized in a single level tree structure.

7. In a network device, a cyclic redundancy checker (CRC) comprising:

a first input port configured to receive first data to be added to a current CRC value, the first data containing valid and invalid portions, the valid portions being adjacent to one another;

a second input port configured to receive second data representing a number of valid portions in the first data;

a third input port configured to receive the current CRC value;

CRC logic coupled to the first, second and third ports and configured to generate an updated CRC value based on the first data, second data, and current CRC value; and

an output port coupled to the CRC logic and configured to output the updated CRC value.

8. The CRC of claim 7 wherein the third port comprises:

a first sub-port configured to receive a current 32 bit CRC value; and

a second sub-port configured to receive a current 16 bit CRC value.

9. The CRC of claim 7 wherein, when generating, the CRC logic is configured to:

generate the updated CRC value in a single clock cycle.

10. The CRC of claim 9 wherein the first data includes 128 bits.

11. A network device comprising:

a routing engine configured to maintain one or more routing tables and a forwarding table; and

a packet forwarding engine including;

a cyclic redundancy checker (CRC) configured to receive a packet having valid portions and invalid portions, the valid portions being adjacent, receive a signal representing a number of valid portions in the packet, receive a current CRC value, and determine an updated CRC value based on the received packet, signal, and current CRC value, and

a transmitter configured to append the updated CRC value to the packet and transmit the packet.

12. The router of claim 11 wherein, when determining, the CRC is configured to:

generate the updated CRC value in a single clock cycle.

13. A method for updating a cyclic redundancy check (CRC) value, comprising:

receiving data containing an arbitrary number of valid and invalid portions, the valid portions being positioned adjacent to one another;

receiving a signal representing a quantity of valid portions in the data;

receiving a current CRC value; and

updating the current CRC value using the received data and the received signal in a single clock cycle.

14. The method of claim 13 wherein the data includes 128 bits.