Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-12-21
2003-08-19
Dildine, R. Stephen (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06609225
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to error detection in communication between components and systems; more particular, the invention relates to generating and checking cyclic redundancy code (CRC) values using a multi-byte CRC generator on a variable number of bytes.
BACKGROUND OF THE INVENTION
Devices such as computers, routers, networking equipment, and components thereof communicate information internally and/or with other devices. For example, computers might communicate across a local area network (LAN) using Ethernet protocol, or application-specific integrated circuits (ASICs) may communicate with each other over a single or parallel bit bus. It is important for these devices to reliably communicate and to detect errors in their communication.
One common technique for detecting transmission errors is a technique known as the cyclic redundancy check (CRC). A CRC allows the detection of errors using only a small number of redundant bits typically sent along with the communicated information. For example, a 32-bit CRC gives strong protection against common bit errors in messages that are thousands of bits long. Ethernet, a common link-level protocol, uses a frame format that includes CRC-32, a specific 32-bit CRC having the polynomial of:
CRC
-32
:P
(
x
)=
x
26
+x
23
+x
22
+x
16
+x
16
+x
12
+x
11
+x
10
+x
8
+x
7
+x
5
+x
4
+x
2
+x
+1
One common method for computation of a CRC operates serially on each bit of a message using a shift register and XOR gates, where the number of bits in the shift register equals the degree of the CRC generating polynomial. The value of the CRC is determined by calculating the CRC from the first byte of the frame and stops calculating the CRC at the last byte. During transmission, this CRC is usually appended to the end of the frame. The receiver of the frame then calculates the CRC on the frame it receives, and compares the calculated CRC to the data source generated CRC that was appended to the end of the frame. If they match, the frame has a good CRC; otherwise, the frame is corrupted and is typically discarded. This serial approach for determining a CRC may be sufficient for certain applications. However, especially at higher operating rates, the serial determination of a CRC may be too slow or may limit the effective communication rate between devices or components.
One approach to increase the rate for determining a CRC is to process several bytes in parallel, such as using a balanced XOR tree. However, a balanced XOR tree suffers from the inability to adjust to a variable number of bytes on which to determine a CRC. For example, Ethernet frames are of variable length from sixty-four bytes to 1518 bytes. Thus, a high-speed device, such as a switch, transmitting Ethernet frames needs to accommodate the calculation of a CRC on frames of varying lengths. For example, if sixty-four bytes are operated on in parallel, then there are sixty-four possibilities where the last byte can be located.
One costly approach to accommodate variable length data frames is to implement multiple, independent balanced XOR trees for each possible data length and then to select between the results. For example, determining a CRC in parallel on blocks of sixty-four bytes would require sixty-four balanced XOR trees and then selecting between the results based on the data length (e.g., the position of the last byte of data in the block of sixty-four bytes). Some deficiencies in this approach include a timing delay due to multiplexing the results, particularly as the number of bytes operated on in parallel becomes large. Additionally, implementing such a large number of XOR trees is costly (e.g., if would require a lot of gates and silicon area in an ASIC).
The number of gates and space requirements can be reduced by using ripple XOR trees of various byte widths with multiplexing to send the output of one to the input of the next appropriate XOR tree. One approach is to implement binary multiples (e.g., 1, 2, 4, 8, etc.) of input data width. However, this approach still entails significant time delays and a limited performance.
Needed is a new way of generating CRC values using a multi-byte CRC generator on a variable number of bytes.
SUMMARY OF THE INVENTION
A device determines a cyclic redundancy check (CRC) on a block of information. A preliminary CRC on the block of information plus at least one additional byte of information is first determined. Then, the CRC is determined through a reverse CRC operation on the preliminary CRC.
REFERENCES:
patent: 4162480 (1979-07-01), Berlekamp
patent: 4833678 (1989-05-01), Cohen
patent: 4856003 (1989-08-01), Weng
patent: 5282214 (1994-01-01), Dravida
patent: 5398284 (1995-03-01), Koopman et al.
patent: 2000269826 (2000-09-01), None
Winn Schwartu, Wipe Out Web Graffiti By Going Back To Basics, Feb. 14, 2000, Network World, p. 59.
Cisco Technology Inc.
Dildine R. Stephen
The Law Office of Kirk D. Williams
LandOfFree
Method and apparatus for generating and checking 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 Method and apparatus for generating and checking cyclic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating and checking cyclic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3091299