Single cycle cyclic redundancy checker/generator

Details Single cycle cyclic redundancy checker/generator Single cycle cyclic redundancy checker/generator

2001-01-03

2004-10-26

Lamarre, Guy J. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S757000, C714S758000, C714S781000

Reexamination Certificate

active

06810501

ABSTRACT:

BACKGROUND OF THE INVENTION
A. Field of the Invention
The present invention relates generally to routing systems and, more particularly, to systems and methods for performing cyclic redundancy checks on data transmitted in a communication system.
B. Description of Related Art
Cyclic Redundancy Checking (CRC) ensures the accuracy of frames transmitted between devices in a frame relay network. In practice, an originating device generates a CRC value based on the content of the frame to be transmitted and transmits the CRC value with the frame. A destination device compares the received CRC value to a recomputed CRC value to determine whether the frame was received correctly.
Several approaches exist for generating and checking CRCs. One such approach is described in Section C of RFC1662, “PPP in HDLC-like Framing,” July 1994, pp. 18-24. As described therein, the fast Frame Check Sequence (FCS) implementation requires successive iterations (16 for a 16 bit FCS, 32 for a 32 bit FCS) over the following loops:
F
cs=(fcs>>8){circumflex over ( )}fcstab_
16
[(fcs{circumflex over ( )}(*cp++)& 0xff) . . . for FCS
16
F
cs=(fcs>>8){circumflex over ( )}fcstab_
32
[(fcs{circumflex over ( )}(*cp++)& 0xff) . . . for FCS
32
where a memory access to an FCS lookup table (fcstab_
16
and fcstab_
32
, respectively) is required for each loop. It will be appreciated that such an approach is inappropriate for extremely high performance applications (e.g., OC
192
) due to its iterative nature and concomitant memory accesses.
In high performance applications, conventional CRC generating and checking approaches face several problems. A first problem is speed. Typically, high performance routers require line rate performance (i.e., bits are processed as they arrive off the wire). The ability to calculate a CRC checksum in a single clock cycle is highly desirable to meeting this design goal.
A second problem is data width. For a given clock rate, the wider the checksum that can be calculated, the higher the line rate that can be supported. As such, high performance routers need the ability to handle wide input data (e.g., 128 bits for OC
192
applications). Moreover, since the CRC check can occur over all, some, or none of the bits in an incoming bit stream, high performance routers need the ability to perform the CRC on a bit stream having an arbitrary number of invalid bits.
Therefore, there exists a need for systems and methods that improve CRC operations in a high performance environment.
SUMMARY OF THE INVENTION
Systems and methods, consistent with the present invention, address this and other needs by providing a cyclic redundancy checker/generator capable of performing a CRC operation in single cycle on data having wide width and an arbitrary number of invalid bits.
In accordance with the purpose of the invention as embodied and broadly described herein, a method for updating a cyclic redundancy check (CRC) value includes receiving data containing valid and invalid portions. The valid portions are positioned adjacent to one another. The method also receives first information representing the number of valid portions in the data and second information representing a current CRC value. The method determines the updated CRC value based on the data, first information, and second information.
In another implementation consistent with the present invention, a CRC includes a plurality of CRC units and at least one multiplexer. The CRC units receive data, containing valid and invalid portions, the valid portions being adjacent to one another, and a current CRC value, and generate CRC outputs based on the received data and current CRC value. The multiplexer receives the CRC outputs and information representing a number of valid portions in the received data, and outputs one of the received CRC outputs based on the information.
In yet another implementation consistent with the present invention, a CRC includes a first input port, a second input port, a third input port, CRC logic, and an output port. The first input port receives first data to be added to a current CRC value. The first data contains valid and invalid portions, where the valid portions are adjacent to one another. The second input port receives second data representing a number of valid portions in the first data. The third input port receives the current CRC value. The CRC logic is 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. The output port is coupled to the CRC logic and configured to output the updated CRC value.
In still another implementation consistent with the present invention, a network device includes a routing engine and a packet forwarding engine. The routing engine maintains one or more routing tables and a forwarding table. The packet forwarding engine includes a CRC and a transmitter. The CRC receives a packet having valid portions and invalid portions, the valid portions being adjacent, receives a signal representing a number of valid portions in the packet, receives a current CRC value, and determines an updated CRC value based on the received packet, signal, and current CRC value. The transmitter appends the updated CRC value to the packet and transmits the packet.
In still another implementation consistent with the present invention, a method for updating a CRC value is disclosed. The method includes 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 data and signal in a single clock cycle.


REFERENCES:
patent: 5084891 (1992-01-01), Ariyavisitakul et al.
patent: 5323403 (1994-06-01), Elliott
patent: 5499224 (1996-03-01), Sanada
patent: 5878057 (1999-03-01), Maa
patent: 6009547 (1999-12-01), Jaquette et al.
patent: 6195780 (2001-02-01), Dravida et al.
Sait, et al. ‘Hardware design and VLSI implementation of a byte-wise CRC generator chip,’ IEEE Transactions on Consumer Electronics, Feb. 1995, pp: 195-200, vol. 41, Issue: 1.*
Simpson, W., Editor, “PPP in HDLC-like Framing”, STD 51, RFC 1662, Daydreamer, Jul. 1994, http://www.faqs.org/rfcs/rfc1662.html, pp. 1-18.
Ganssle, Jack, Software by Design: “Computing CRCs in Parallel,” Circuit Cellar Ink, Jun./Jul. 1989, pp. 55, 56, 58, and 59.

Affiliated with

Also associated with

Rating

Single cycle cyclic redundancy checker/generator does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Single cycle cyclic redundancy checker/generator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single cycle cyclic redundancy checker/generator will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3329664