Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-05-15
2004-03-02
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06701479
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of data processing. More specifically, the present invention relates to high speed cyclic redundancy check (CRC) generation, having special application to high speed network traffic routing, such as Gigabit Ethernet packet switching.
2. Background Information
Cyclic Redundancy Check (CRC) has long been employed as a metric to facilitate detection of data transmission error. The technique is employed in a wide variety of data processing related disciplines, including in particular, networking. The underlying mathematics including the polynomial divisions involved in the generation of a CRC value for a data block is well understood among those ordinarily skilled in the art. Various hardware as well as software implementations are known. Examples of known hardware implementations include but are not limited to the implementations available from e.g. Actel of Sunnyvale, Calif.
With advances in integrated circuit, microprocessor, networking and communication technologies, increasing number of devices, in particular, digital computing devices, are being networked together. Devices are often first coupled to a local area network, such as an Ethernet based office/home network. In turn, the local area networks are interconnected together through wide area networks, such as ATM networks, Frame Relays, and the like. Of particular notoriety is the TCP/IP based global inter-networks, Internet.
As a result of this trend of increased connectivity, increasing number of applications that are network dependent are being deployed. Examples of these network dependent applications include but are not limited to, email, net based telephony, world wide web and various types of e-commerce. Successes of many of these content/service providers as well as commerce sites depend on high speed delivery of a large volume of data. As a result, high speed networking, which in turn translates into high speed CRC generation is needed.
Unfortunately, the current generation of CRC generators known in the art are generally unable to meet the speed requirement of the next generation IC based high speed network traffic routing devices. For these IC based devices, it is not only necessary for the CRC generation resource to be sufficiently fast to keep pace with the processing of a single network traffic flow, it is further desirable that the CRC generation resource to be sufficiently efficient and fast, such that it can be shared among the various flow processing units, thereby eliminating the need to have dedicated CRC generation resource for each of the flow processing units.
Thus, a highly efficient approach to CRC generation is needed.
SUMMARY OF THE INVENTION
A CRC generation unit is equipped with multiple polynomial division circuits (PDC) to perform multiple different bit lengths polynomial divisions in parallel, including outputting of multiple remainder values, for an iteration of an iterative CRC generation for a data block. In one embodiment, the CRC generation unit also includes a selector to select one of the remainder values, and a register to store the selected remainder value, return the stored remainder value to the PDCs for formation of different bit length dividends, and output the stored remainder value of the last iteration as the generated CRC value.
In one embodiment, the CRC generation unit further includes alignment circuitry to align the data block. In one embodiment, multiple CRC generation units are provided to generate the CRC values of successive variable length data blocks.
In one embodiment, the CRC generation units form a shared resource to multiple network traffic flow processing units of a network traffic routing device.
In one embodiment, the network traffic routing device is disposed on a single integrated circuit.
REFERENCES:
patent: 5130991 (1992-07-01), Takano
patent: 5323403 (1994-06-01), Elliott
patent: 5619516 (1997-04-01), Li et al.
patent: 5734826 (1998-03-01), Olnowich et al.
patent: 5844923 (1998-12-01), Condon
patent: 6029186 (2000-02-01), DesJardins et al.
patent: 6119263 (2000-09-01), Mowbray et al.
patent: 6128766 (2000-10-01), Fahmi et al.
Monteiro et al., “Fast Configurable Polynomial Division for Error Control Coding Applications,” IEEE, Jul. 2001, pp. 158-161.
Monteiro et al., “A Polynomial Division Pipelined Architecture for CRC Error Detection Codes,” 13thInternational Conference on Microelectronics, Oct. 29-31, 2001, pp. 133-166.
Chase Shelly A
De'cady Albert
Network Elements, Inc.
Schwabe Williamson & Wyatt P.C.
LandOfFree
Fast cyclic redundancy check (CRC) generation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast cyclic redundancy check (CRC) generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast cyclic redundancy check (CRC) generation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3236912