Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-03-20
2001-08-14
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S785000
Reexamination Certificate
active
06275964
ABSTRACT:
TECHNICAL FIELD
The invention relates to the detection and correction of errors occurring in data codewords which are transmitted over a communication channel and in particular a mechanism of software enhanced error correction in a data communication system.
BACKGROUND
In a data communication system, reliability in transmission of sequences is achieved at the cost of redundancy, which decreases that rate of information transmission, and complexity, which is added to both sides—transmitter and receiver. In block codes, the sequence of information bytes is first broken up to k-byte long segments, and then each is augmented by n−k redundancy bytes, which depend on the k information bytes. The redundant bytes ensure minimum Hamming distance between the n-byte long codewords, a distance which allows error detection and correction.
Hardware components for error detection/correction (aka CRC—cyclic redundant code) are inexpensive and widely used. Different components offer different error detection and correction capabilities. Some of these components work on bits, and they can detect/correct up to a fixed number of bit errors that occur to the codeword while on transmission, and some work on bytes, and they are more suitable for channels which tend to corrupt the transmission in bursts. On the transmitter side, the component computes, very fast, the redundancy bytes of the codeword, and on the receiver side it checks, very fast, whether the word received is a codeword. If so, the component truncates the redundancy bytes and forwards the information bytes on the application. If not, either it just asks for a retransmission (in case that detection only is employed) or it tries to correct the errors, and then forwards the (corrected) information bytes on to the application. In any case, the application sees the channel and the hardware as one fast and reliable (to some extent) unit which transmits k-byte long segments of information.
When the application wishes to further protect itself against channel errors, the commonly used practice is to make that protection within the k-byte long segment: view them as blocks crossing the channel, use k′<k bytes for information, and compute, in software, the k−k′ redundancy bytes. In this practice, the total number of redundancy bytes used (by the hardware and by the software) usually exceeds what can be achieved by a code designed to work with blocks of length n, out of which only k′ are information bytes.
A commonly used hardware that detects up to 2t byte-errors and corrects up to t byte-errors is using Reed Solomon codes. These codes are over an alphabet size of 2
m
and use codewords of length n=2
m
−1 or a divisor of that number. For instance, in case of byte characters, the codewords are of length 255 bytes. For detecting up to t byte-errors, t redundant bytes must be used allowing 255-t information bytes. For correcting up to t corrupted bytes, 2t redundant bytes must be used, allowing 255−2t information bytes in each codeword. These numbers of redundant bytes are the minimum possible in any code.
Assuming that t does not suffice for the level of noise of the channel and it becomes necessary to enhance the perceived data reliability of the system by increasing the reliability of the channel such that it introduces fewer errors or by increasing the error correction capability of its detection/correction code. One solution would be to replace the whole hardware. Although hardware is not too expensive, it is rather cumbersome to stick it when the level of noise changes rather often. For instance, replacing a wireless connection in a mountainous region or even in a city with a coax cable would be very expensive. An alternative would be to upgrade the error detection and correction capabilities of the encoders and decoders. But, when the hardware encoders and decoders are used, this solution also may be too expensive, since hardware development costs are directly related to the complexity introduced by error detection and correction capability of the encoders and decoders. In addition, replacing existing hardware with enhanced hardware is also expensive and not always practical. For instance, replacing the network receiver card, e.g. modem, in thousands of home PCs with a new enhanced card is a very expensive proposal.
SUMMARY OF THE INVENTION
It is why the main object of the invention is to provide an error detecting and encoding mechanism which increases the system perceived data reliability without raising hardware costs.
Another object of the invention is to provide an error detecting and correcting mechanism wherein the correcting capability is extended by software means only.
Accordingly, the invention relates to a data communication system for transmitting data codewords of n bytes length over a communication channel from a transmitter to a receiver, the transmitter comprising a hardware encoder capable of receiving as input an information sequence of n−2t bytes and emitting in output a codeword of n bytes including n−2t information bytes and 2t redundant bytes, and the receiver comprising a hardware decoder capable of detecting up to 2t byte-errors and correcting up to t byte errors. The transmitter further comprises a software encoder transforming, in combination with the hardware encoder, an information sequence of n−2s bytes with t<s≦2t into a modified sequence, the transmitter emitting encoded codewords including n−2s information bytes and 2s redundant bytes, and the receiver further comprises a software decoder for correcting, in combination with the hardware decoder, up to s byte-errors when the hardware decoder has detected errors in the encoded codeword received from the communication channel.
An important feature of the invention is that the hardware decoder included in the receiver comprises a switch enabling an encoded codeword to be transferred to the software decoder for being corrected if there are less than s errors after the hardware decoder has detected errors in the encoded codeword.
The new mechanism according to the invention allows easy adaptation to the level of noise in the channel. The total number of redundancy bytes used, by the hardware and by the software extension, is the minimal possible by any error correcting code having the extended capabilities. The suggested mechanism benefits from the speed of hardware, and calls for software decoding only in cases that the hardware decoder detects errors.
REFERENCES:
patent: 5659557 (1997-08-01), Glover et al.
patent: 5742599 (1998-04-01), Lin et al.
patent: 5875200 (1999-02-01), Glover et al.
Nagin Kenneth
Rochberger Benny
Satran Julien
Sheinwald Dafna
Zeidner Efri
Cameron Douglas W.
Chung Phung M.
Dougherty Anne Vachon
International Business Machines - Corporation
LandOfFree
Software enhanced error correction mechanism in a data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Software enhanced error correction mechanism in a data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Software enhanced error correction mechanism in a data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2453454