Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
1998-10-20
2001-09-25
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S757000
Reexamination Certificate
active
06295626
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field circuit design and, more specifically to design of circuits for calculating cyclic redundancy check (CRC) codes.
2. Description of the Related Art
Cyclic redundancy check (CRC) codes have many uses. In computer networking, for example, a CRC code is a very powerful tool and easily implemented technique to obtain data reliability in networking. The CRC technique is used to verify the integrity of blocks of data called Frames. Using this technique, the transmitter appends an extra n bit sequence to every frame called Frame Check Sequence (FCS). FCS holds redundant information about the frame that helps the receiver detect errors in the frame. CRC is one of the most commonly used techniques for error detection in data communications.
One known hardware implementation of a bit-wide CRC generator is a simple linear feedback shift register (see FIG.
1
.). For example,
FIG. 1
illustrates a bit wide CRC generator for the polynominal G(x)=1+X+X
3
+X
5
. While such a circuit is simple and can run at very high clock speeds, it suffers from the limitation that the stream must be bit-serial. This means that n clock cycles will be required to calculate the CRC values for an n-bit data stream. In many high speed data networking applications where data frames need to be processed at high speeds this latency is intolerable and hence, implementation of CRC generation and checking on a parallel stream of data becomes desirable.
A byte-wide CRC generator can be implemented to generate CRC for an 8-bit wide data stream in one clock cycle as opposed to 8 clock cycles with a conventional CRC generator (and, other width CRC generators can be implemented for other width data streams). In addition, several software implementations have been proposed to compute the CRC for a multi-bit data stream. See, e.g., Perez et al.,
Byte wise CRC calculations,
IEEE Micro. 3(3):40-50 June, 1983 and Pandeya et al.,
Parallel CRC lets many lines use one circuit,
Computer Design, 14(9):87-91, September, 1975.
SUMMARY OF THE INVENTION
A symbolic simulation based algorithm to derive boolean equations for a parameterizable data width CRC generator/checker is described. The equations generated are used to implement a data flow representation of the CRC circuit in VHDL. The VHDL description is then synthesized into gates.
REFERENCES:
patent: 5132975 (1992-07-01), Avaneas
patent: 5282215 (1994-01-01), Hyodo et al.
patent: 5774480 (1998-06-01), Willy
patent: 5905664 (1999-05-01), Ko et al.
Helness, “Implementation of a parallel Cyclic Redundancy Check Generator”, Computer Design, Mar. 1974, pp. 91-96, Mar. 1974.*
Pei et al., “High-Speed Parallel CRC Circuits in VLSI”, IEEE Trans. on Communications, vol. 40, No. 4, Apr. 1992, pp. 653-657, Apr. 1992.
Farzaneh Farivar
Nair Rajesh G.
Ryan Gerry
Baker Stephen M.
Blakely , Sokoloff, Taylor & Zafman LLP
Nortel Networks Limited
LandOfFree
Symbol based algorithm for hardware implementation of cyclic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Symbol based algorithm for hardware implementation of cyclic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symbol based algorithm for hardware implementation of cyclic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2484359