Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-05-26
2001-11-20
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06321357
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to error prediction and correction in data communications. More particularly, the present invention provides a method and apparatus for burst error prediction and correction.
BACKGROUND
When information is transmitted and received over a communications channel, errors sometimes occur. In order to guarantee the reliability of the message being transmitted or received, it is necessary to be able to detect these errors. Error detection is the process of determining whether information that was received is the same as the information that was sent. Once the error is detected, it may be corrected.
An example of an error that may occur in communications systems is a burst error. A burst error occurs when a number of bits in a sequence are erroneously set to the same value.
FIG. 1
a
shows an example of a burst error in a block code
100
that contains
18
symbols
102
. The burst error starts at location
6
and has a length b=3. Burst errors may be caused by erasures or random errors. Symbols that are correct are shown as empty circles, for example symbol
102
. Symbols representing an error are shown as filled-in circles
104
. Block code
100
has errors
104
at locations
6
,
7
and
8
. The remaining symbols
102
, shown at locations
1
-
6
and
9
-
18
, do not contain errors.
Erasure errors are the result of gaps in an information stream. For example, if information is being read from a tape and a section of the tape has been erased, an erasure error has occurred. Another example of an erasure error is when information is transmitted over a communications line that is hit by lightning during a thunderstorm. The disruption in the communications cable caused by the lightning is where the erasure error has occurred. Random errors are the result of incorrect information being transmitted. Random errors are unpredictable and need to be detected because they cause data corruption.
Existing methods for detecting errors include sending additional information along with the desired message to be transmitted. This additional information, or redundancy, is used to determine whether the message contains errors. Examples of existing error correction schemes using redundancy include cyclic redundancy checks (CRC), checksum, and Reed-Solomon codes. A Reed-Solomon code is a block code that contains a total of n symbols, and a block of k (where k<n) information symbols within the block code. The k information symbols contain the message to be transmitted or received.
Assuming that k symbols make up the desired message, the remaining n-k symbols are check symbols that may be used for error correction processing. These codes are commonly indicated by the notation (n, k).
FIG. 1
b
shows an example of a (
18
,
6
) Reed-Solomon code
140
. Each symbol
102
is represented by a circle. Code
140
contains n=18 total symbols. The message contains k=6 symbols. The error correction portion contains n−k=12 symbols. “On TMS320 Microprocessor Base Programmable Real Time Reed-Solomon Coding-Decoding System”, International Journal of Satellite Communication, Vol. 8, April 1990, written by Jing-Zheng Ouyang, discusses Reed-Solomon codes in more detail, and is hereby incorporated by reference. Also incorporated by reference is R.E. Blahut, “Theory and Practice of error Control Codes,” Addison Wesley Publishing Company, Inc. 1983.
Each block code has an error correction capability, t, associated with it. T is expressed in terms of burst error length (number of symbols). This error correction capability, t, is a function of the type of error and a minimum distance, d*, corresponding to a maximum likelihood that an error may be detected. The random error correction capability of an (n, k) block code satisfies the following equation (1):
d*>=2t+1 (1)
This equation may be expressed in terms of random errors, v, and erasure errors, r, resulting in the following equation (2):
d*>=2v+r+1 (2)
Equation (2) reflects that random errors require a greater minimum distance for correction. In other words, the erasure correction capability is larger than the random error capability. If it can be assumed that only erasure errors, r, occurred, then equation (2) may be simplified to equation (3):
d*>r+1 (3)
FIG. 1
c
shows an example of an (n, k) block code
170
having random error correction capability t=3. If more errors than t appear in a sequence, then the error for that block code cannot be corrected. For example, block code
170
contains errors
104
in positions
4
,
8
,
12
, and
16
. The burst error length is b=1 because each error
104
is not adjacent to any other error. In this case, however, even though b<t, the errors may not be corrected. From a random errors point of view, the number of errors,
4
, is still greater than t (t=3) and therefore no correction can be had. Also, from the point of view of burst errors, a total of 12 errors beginning from
104
at location
4
is greater than t=3 and, likewise cannot be corrected. Hence, if in the block code there were no more than t errors
104
, for example as shown in
FIG. 1
a,
where the burst error length b=3, then the error can be corrected because b=t. Similarly, block codes containing burst error length b>t also could not be corrected.
Burst error length occurring in applications such as communications and data storage/retrieval presents a problem because it is unpredictable. An error correction capability t may be chosen to accommodate the longest burst error possible, i.e., the largest b value. The tradeoff is that a system that has a very high error correction capability requires more time and resources to process messages. Therefore, a need exists for maximizing the error correction capability of block codes. The present invention addresses this and related problems.
SUMMARY OF THE INVENTION
The present invention provides burst error prediction to maximize the error correction capability of block codes. A method an apparatus in accordance with the present invention for improving burst error correction involve transmitting block codes with interleaving, and predicting a burst error in the received block codes. Burst error prediction includes decoding received block codes and determining if the decoding is successful as will be further explained below. The received block codes have an error correction capability, an erasure detection capability and a burst error. Hence, a decoding step is performed to find the burst error in the block code. The burst error has a length associated therewith. The decoding is successful if the burst error length found is less than twice the error correction capability. If an initial decode attempt is not successful, then an initial burst error length is associated with the block code and another decode is performed. The burst error length has an initial value that is less than the error correction capability. After each unsuccessful decode, the burst error length is incremented by a predetermined amount until the burst error length exceeds twice the error correction capability, at which point the decode is assumed to have failed.
REFERENCES:
patent: 4633486 (1986-12-01), Berlekamp et al.
patent: 4835772 (1989-05-01), Peile et al.
patent: 4916702 (1990-04-01), Berlekamp
patent: 5299208 (1994-03-01), Blaum
patent: 5629949 (1997-05-01), Zook
patent: 5631909 (1997-05-01), Weng et al.
patent: 5684810 (1997-11-01), Nakamura et al.
patent: 5943348 (1999-08-01), Ly
patent: 0136 604 A (1985-04-01), None
Baker Stephen M.
InnoMedia Pte Ltd
McCutchen, Doyle, Brown & Energen, LLP
LandOfFree
Method and apparatus for burst error correction 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 burst error correction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for burst error correction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2601570