Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1997-12-10
2001-02-27
De Cady, Albert (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S759000
Reexamination Certificate
active
06195780
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of data transmission error control coding, and more particularly to methods for generating cyclical redundancy code (CRC) in message groups rather than bitwise.
BACKGROUND OF THE INVENTION
Digital information transmitted from a sending station to a receiving station may be protected from errors by developing code related to the individual bits comprising a message, appending the code to the original message and transmitting the message and the code to the receiving station, and then generating code at the receiving station to check for corrupted data. Because the code is related to the original message bits through a generating polynomial, the code bits are considered redundant to the message bits used to generate them. Therefore, a process which uses polynomial division to generate redundant bits is referred to as cyclical redundancy code (CRC). Typically, messages are coded bitwise in hardware, the CRC generating polynomial function provided for by utilizing linear feedback shift registers.
CRC generation in software utilizes CRC generating lookup tables, instead of shift registers, to generate the applicable CRC code. Message bits are analyzed and compared to a CRC value contained in the CRC generating lookup table, the corresponding value representing the CRC checkbit value that is appended to the original message. However, CRC generation in software is inherently slower than the hardware implementation, even when performed over several message bits concurrently. Further, prior art methods for CRC generation in software are subject to the restriction that the degree of the generating polynomial cannot exceed the size of the message unit to which it is applied.
SUMMARY OF THE INVENTION
The present invention is a method and an apparatus for generating cyclical redundancy code (CRC) by analyzing segmented groups of bits from a message concurrently, producing a temporary remainder value as a result of a multiple bit lookup from a generating CRC lookup table, using the temporary remainder or a portion thereof along with the next sequential segmented group of message bits as exclusive-or inputs, taking the result of the exclusive-or output and applying the result, as a lookup value, to the generating CRC lookup table. The process is repeated until the message groups have been depleted, at which time the message is completely coded and the temporary remainder existing at the time represents the CRC checkbits for the message. The recursive method developed in association with the present invention is dubbed a Recursive Syndrome Expansion (RSE).
Although the present invention is particularly well suited for error detection and correction within cellular and PCS wireless networks, it is also equally applicable to other digital data and multimedia communication networks, including, but not limited to, optical fiber, coaxial cable, and hybrid fiber/coax networks, public switched telephone networks (PSTN), and wireless broadcast and satellite networks.
Advantageously, the present invention and its incorporation of RSE within its implementation provides for high speed CRC creation, at little or no additional expense for additional circuitry or components in an implementing configuration, with flexibility as to size of the generating polynomial, the size of each segmented group considered, and the relative size between the generating polynomial and the segmented groups, and with flexibility for implementation mode, especially when the invention is implemented in software.
REFERENCES:
patent: 5132975 (1992-07-01), Avaneas
patent: 5325372 (1994-06-01), Ish-Shalom
patent: 5428629 (1995-06-01), Gutman et al.
patent: 5619516 (1997-04-01), Li et al.
patent: 5691997 (1997-11-01), Lackey, Jr.
patent: 5878057 (1999-03-01), Maa
Dravida Subrahmanyam
Ravikumar Srinivasan S.
Cady Albert De
Gibbons Del Deo Dolan Griffinger & Vecchione
Lucent Technologies - Inc.
Ton David
LandOfFree
Method and apparatus for generating cyclical redundancy code 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 cyclical redundancy code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating cyclical redundancy code will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2605250