Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-12-30
2004-10-05
Lamarre, Guy J. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06802038
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to a method for efficiently calculating a cyclic redundancy check (CRC).
BACKGROUND OF THE INVENTION
The use of a Cyclic Redundancy Check (CRC) to verify the integrity of data is well known in the art. Essentially, a transmitter, or source, of data, or perhaps a device associated therewith, computes a CRC value on data that is to be transmitted. The data is then transmitted along with the computed CRC value to a receiver or destination. The receiver of the data, or an associated device, upon receiving the data and the transmitted CRC value, computes a new CRC value on the received data using the same CRC algorithm as used by the source. The new CRC value computed on the received data is compared to the transmitted CRC value computed and transmitted by the source along with the data. If the two CRC values match, the data was transmitted and received without corruption.
If the data received by the destination differs in any regard from the data that was to be transmitted by the source, the CRC transmitted with the data does not match the new CRC calculated by the receiver, and the destination and or source react accordingly. The most common approach is to use feedback and retransmission. For example, the destination may discard the data, and/or notify the source that an error likely occurred at least in receiving the data, and the source may then retransmit the data, according to a protocol by which the source and destination communicate with each other. Another more efficient approach is to utilize received data, both information data and CRC values, to intelligently detect and correct errors incurred during transmission, such as the Maximum-likelihood detector and the Chase decoder. These methods, however, are inherently more computation intensive, and may require a large amount of CRC recomputation as in the case of the Chase decoder.
It should be noted here that the term data is meant to encompass any type, format, or length of data, and likely is received as a string of binary digits. It may be that the data is actually transmitted as a string of binary digits in a digital signal, or transmitted as an analog signal and converted to a string of bits in a digital signal for processing by logic within an integrated circuit. Moreover, the transmitter and receiver may represent any two devices that communicate with either other, such as peer devices communicating via an internetwork, client and server devices communicating via the Internet, or user terminals communicating with a base station in a cellular radio network communication system, etc. Moreover, CRCs values may be utilized to check the integrity of data in virtually every situation where data is transmitted, regardless of the type of transmission link or distance between the source and destination. For example, the process of checking for data integrity is as applicable to data packets transmitted over a data bus coupling logic circuits of a chipset as between cells of data transmitted via a radio frequency spectrum between a base station and user terminal in a wireless network.
In the prior art, Chase decoders operate in conjunction with a receiver to recover from an integrity error in the received data stream. A Chase decoder essentially intelligently rearranges a number of the symbols, such as binary digits, in a string of symbols (e.g., binary digits) comprising the data if the new CRC calculated by the receiver does not match the CRC transmitted with the data. Chase decoders intelligently guess which binary digits in the data stream are incorrect, and “flip” such binary digits, or bits. Chase decoders are well known in the art, and therefore, the details of their operation are left to the reader.
After flipping one or more binary digits in a string of binary digits comprising the received data, the CRC for the string of bits comprising the data is then recalculated and compared to the CRC transmitted with the data. This process is iterative the decoder continues to flip bits, the CRC is recalculated, and the recalculated CRC is then compared to the transmitted CRC until the CRCs match, thus obviating the need to retransmit the data. However, recalculating the CRC, especially if the string of binary digits over which the CRC is calculated is large, can be computationally intensive. For an embedded controller, or a device with limited computing capabilities or battery power, such as a user terminal in a wireless communications network, such computationally intensive calculations are not desirable.
SUMMARY
An embodiment of the present invention contemplates receiving a stream of information and appended thereto a cyclic redundancy check (CRC) value for the information stream. A new CRC value is computed for the received information stream and compared to the CRC value transmitted with the information stream. If the transmitted CRC value and the new CRC value are different, then a portion of the information stream is altered, and a pointer based on the altered information stream is obtained which points to a table. An entry pointed to in the table provides a predefined value to be used in revising the new CRC value. The new CRC value is revised by taking into account the predefined value and the new CRC value. The transmitted CRC value is again compared to the new CRC value as revised, and if the CRCs. still do not match, the information stream may be altered again, the new CRC value revised yet again, and the transmitted CRC value again compared to the new CRC as revised.
REFERENCES:
patent: 6195780 (2001-02-01), Dravida et al.
patent: 6640301 (2003-10-01), Ng
patent: 2002/0172198 (2002-11-01), Kovacevic
Jain, R. “A comparison of hashing schemes for address lookup in computer networks;”Communications, IEEE Transactions on;Oct. 1992; On page(s): 1570-1573; vol.: 40, Issue: 10.*
Proakis, John G., “Digital Communications”, McGraw-Hill Series in Electrical and Computer Engineering, 3rd Edition, Mar. 1995, pp. 413-465.
Chase, David, “A Class of Algorithms for Decoding Block Codes with Channel Measurement Information”, IEEE Transactions on Information Theory, vol. IT-18, No. 1, Jan. 1972, pp. 170-182.
ArrayComm, Inc.
Blakey Sokoloff Taylor & Zafman LLP
Lamarre Guy J.
LandOfFree
Cyclic redundancy check computation algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cyclic redundancy check computation algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cyclic redundancy check computation algorithm will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3269253