Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-10-23
2004-05-04
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S758000, C714S781000, C714S782000, C714S783000, C714S784000
Reexamination Certificate
active
06732317
ABSTRACT:
FIELD
The field includes routers, switches, modems, and generally hardware that sends and/or receives data. More particularly, this pertains to cyclic redundancy code (CRC) calculation to detect errors in data communication.
BACKGROUND
When data communication occurs, some data may be corrupted en route from the sender to the receiver. A reliable implementation of error detection may inform the receiver of the garbled state of a message, and allow the receiver to request a retransmission of the garbled data. Robust error detection thus improves the versatility of data transfers between units on a network, such as routers and switches, and units in a computer.
One error-detecting code is the CRC. In CRC, data in the message may be considered as a message poylnomial M(x), with the bits of the data being the coefficients of M(x). The CRC bits of the message are generated by dividing M(x) by a cyclic redundancy code equation, or a generator polynomial G(x). The quotient polynomial Q(x) is discarded and the coefficients of the remainder polynomial R(x) are appended to M(x) before transmission by the sender of M(x) +R(x). After reception, the receiver divides M(x)+R(x) by G(x). If the data transmission is error free, the new remainder is zero. A non-zero new remainder indicates that an error occurred in the transmission. The above CRC implementation is illustrative; other CRC implementations can be applied.
As data transmission speeds increase, the CRC hardware may need to generate the CRC faster. For example, upcoming standards such as 10 Gigabit Ethernet standard, being formalized as part of the IEEE 802.3ae standard, and the InfiniBand Architecture Specification, currently embodied in the Mar. 31, 2000 Release 0.9, present a need for high performance CRC hardware. One approach to generate CRC data faster is to start from the ground up, such as a new transistor layout, extensive testing associated with a next-generation design, etc. This approach can be time-consuming and expensive. Thus, it would be desirable to combine CRC hardware to handle faster data transmission. In the event a ground up approach was taken, it would be desirable to combine new CRC hardware to handle even faster data transmission.
SUMMARY
To overcome the limitations described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses an apparatus using multiple cyclic redundancy code circuits to generate a cyclic redundancy code for a message. The generated cyclic redundancy code may be combined with the message and transmitted, or compared with an incoming message to detect errors.
A wide data stream representing a message can be divided into multiple narrower data streams, for example by interleaving. Each of the cyclic redundancy code circuits can have a message data input receiving one of the narrower data streams, and a cyclic redundancy code input. Each cyclic redundancy code circuit may generate an intermediate cyclic redundancy code after processing a previously generated cyclic redundancy code received from the cyclic redundancy code input and/or a part of the message data received from the message data input.
The cyclic redundancy code generator can be incorporated into any data device, such as a computer, a router, a network interface card, etc. The incorporated cyclic redundancy code generator may process data traffic internal to the data device, and/or communicated with another data device.
Some method embodiments generate the cyclic redundancy code for a message through generating intermediate cyclic redundancy codes, and/or dividing a message into multiple message streams. Another method embodiment assembles a cyclic redundancy code generator by coupling multiple cyclic redundancy code circuits.
Embodiments may combine cyclic redundancy code hardware based on a presently existing polynomial, thus preserving compatibility with legacy systems. For example, hardware may be developed that processes incoming data more than one byte at a time using the present generating polynomial. Embodiments may also combine cyclic redundancy code hardware based on a different polynomial, such as a newer polynomial.
REFERENCES:
patent: 3678469 (1972-07-01), Freeman et al.
patent: 3982226 (1976-09-01), Bunker et al.
patent: 4593393 (1986-06-01), Mead et al.
patent: 4720830 (1988-01-01), Joshi et al.
patent: 5375127 (1994-12-01), Leak et al.
patent: 5757826 (1998-05-01), Fredrickson
Document No.: NN78102058, Parallel Programmable Array Structured CRC Generator, IBM Technical Disclosure Bulletin, vol. No.: 21, Issue No.: 5, p. No.: 2058-2059, Oct. 1, 1978.*
International Search Report, Application No. PCT/US 01/51347, mailed Mar. 6, 2003.
Joshi, S.M. et al. “A New Parallel Algorithm for CRC Generation”, 2000 IEEE International Conference on Communications, Jun. 18-22, 2000, pp. 1764-1768.
Hobson, R. F. et al. “A High-Performance CMOS 32-Bit Parallel CRC Engine”, IEEE Journal of Solid-State Circuits, vol. 34, No. 2, Feb. 1999, pp. 233-235.
Tong-BI Pei et al., “High-Speed Parallel CRC Circuits in VLSI”, IEEE Transactions on Communications, vol. 40, No. 4, Apr. 1, 1992, pp. 653-657.
Albertengo, G. et al. “Parallel CRC Generation”, IEEE Micro, vol. 10, No. 5, Oct. 1, 1990, pp. 63-71.
William Sinnema, Digital, Analog and Data Communication, Second Edition, pp. 424-437, A Reston Book, Prentice—Hall, Inc. Englewood Cliffs, New Jersey 07632.
Aram Perez, Byte—wise CRC Calculations, pp. 40-50, IEEE Micro, 1983.
R.J. Glaise, A two-step computation of cyclic redundancy code CRC-32 for ATM Networks, pp. 705-709, vol. 41, No. 6, Nov. 1997, IBM J. Res. Develop.
R.J. Glaise and X. Jacquart, Fast CRC Calculation, pp. 602-605, IEEE 1993.
De'cady Albert
Kivlin B. Noäl
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Sun Microsystems Inc.
Torres Joseph D.
LandOfFree
Apparatus and method for applying multiple CRC generators to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for applying multiple CRC generators to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for applying multiple CRC generators to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3204530