Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-11-08
2004-05-04
Dildine, R. Stephan (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S793000
Reexamination Certificate
active
06732325
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to methods and apparatus for detecting and correcting errors in transmitted or stored data, and more particularly, to methods and apparatus for detecting and correcting errors using limited working storage.
Error-correction codes (ECC) are commonly used in many of today's computer and telecommunication systems. For example, error detection and correction codes are used to minimize the number of errors and/or erasures (missing or known to be corrupted data) caused by unreliable communication channels, such as digital wireless transmission systems. In another example, error detection and correction codes are used to minimize the number of errors and/or erasures that are produced by high speed and high density magnetic or optical storage devices.
For many error correction codes (ECC), the data to be transmitted are processed mathematically to generate redundancy symbols, which are appended to the data to form code words, which are then transmitted. When the code words are received, the redundancy symbols are used to decode the received code words back into the original data.
Generally, more protection is provided by using more redundancy symbols. There is, however, an upper bound or “channel capacity” on the performance of any given channel. The “channel capacity” refers to the maximum data transmission rate (or recording density) that can be achievable for a given channel while maintaining an arbitrarily low error rate. Ultimately, the channel capacity is a function of the channel bandwidth and the signal to noise ratio (SNR) of the channel. Error correction codes can be thought of as helping to improve the channel performance by increasing the effective SNR.
There are many approaches for encoding/decoding the user data to maximize the reliability and efficiency of a channel. Ultimately, the goal is to design a system that approaches the channel capacity while minimizing the implementation complexity and cost. Block error-correcting codes are often used because of their good error correction properties and low implementation complexity and cost. The Reed-Solomon (RS) code is a particular type of block error-correction code.
Block codes typically encode a K-symbol input block of source data into an N-symbol output block or code word, where N-K is the number of redundancy symbols.
The code words are transmitted through the communication medium and decoded by a receiver. The encoding process includes a mathematical operation over the input block such that the output code words are different from one another by a parameter referred to as the minimum distance of the code d
min
. The minimum distance d
min
determines the amount of noise that the system can tolerate before a received code word is decoded erroneously.
With Reed-Solomon (RS) codes, the data stream is processed as a sequence of symbols, where the symbols are typically selected from a finite field GF(2
w
), where the parameter “w” denotes the number of binary data bits per symbol. Each symbol of the K-symbol input block represents the coefficients of a data polynomial D(x). The redundancy symbols (which are also represented as a polynomial W(x)) are then computed as the modulo division of the input data polynomial D(x) divided by a generator polynomial G(x):
W
(
x
)=(
x
m
·D
(
x
))
MOD G
(
x
) Equation (1)
where m is the degree of the generator polynomial, which equals the number of redundancy symbols. The redundancy polynomial W(x) is then added to the data polynomial D(x) to generate a code word polynomial C(x):
C
(
x
)=(
x
m
·D
(
x
))+
W
(
x
) Equation (2)
Those skilled in the art understand that the encoder circuitry for performing the above operations can be implemented with minimum cost using a linear feedback shift register (LFSR).
After encoding, the code word C(x) is transmitted through the noisy communication channel, wherein the received code word R(x) equals the transmitted code word C(x) plus an error polynomial E(x). The received code word R(x) is often corrected by: (1) computing the values of the error syndromes s
i
; (2) computing the coefficients of an error locator polynomial using the error syndromes s
i
; (3) computing the roots of the error locator polynomial, the logs of the roots being the error locations; and (4) computing the error values using the error syndromes s
i
and the roots of the error locator polynomial.
The error syndromes s
i
are computed as the modulo division of the received code word polynomial R(x) divided by the factors of the generator polynomial G(x):
S
i
=R
(
x
)
MOD
(
x+&agr;
i
) Equation (3)
when
G
(
x
)
=
∏
i
=
0
m
-
1
(
x
+
α
i
)
Equation
(
4
)
where &agr; is a primitive element of the finite field GF(
2
w
). In practice, the error syndromes s
i
are often calculated using a relation similar to:
[
s
1
s
2
s
3
⋮
s
n
-
k
]
=
[
r
1
r
2
r
3
⋮
r
n
]
[
H
1
,
1
H
2
,
1
H
3
,
1
⋯
H
n
,
1
H
1
,
2
H
2
,
2
⋯
⋯
H
n
,
2
⋮
⋮
⋰
⋯
⋮
⋮
⋮
⋮
⋰
⋮
H
1
,
n
-
k
H
2
,
n
-
k
H
3
,
n
-
k
⋯
H
n
,
n
-
k
]
Equation
(
5
)
where vector “s” is the syndrome vector, vector “r” is the received code word, and matrix “H” is the decoding matrix calculated from the MOD(x+&agr;
i
) term of Equation (3).
Techniques for performing the remaining steps of the decoding process, including computing the error locator polynomial, computing the roots of the error locator polynomial, and computing the error values, are well known by those skilled in the art. See, for example, U.S. Pat. No. 5,446,743 to Zook, U.S. Pat. No. 5,715,262 to Gupta, U.S. Pat. No. 6,031,875 to Im, U.S. Pat. No. 6,041,431 to Goldstein, and U.S. Pat. No. 6,047,395 to Zook.
The use of erasure pointers is a technique that is commonly used to increase the power of an error correction code (ECC). An erasure pointer is typically an address pointing to a symbol location of a code word where an error is likely to have occurred. For example, an erasure pointer may be generated by a transport layer that detects timing phase errors, marginal amplitude signals, etc. Alternatively, or in addition, the erasure pointers may be generated by another layer of ECC coding. Regardless of how the erasure pointers are generated, the erasure pointers can be used to augment the error correction code by providing information in addition to the error syndromes s
i
.
An erasure polynomial is commonly generated using the erasure pointers, where each root of the erasure polynomial replaces a root of the error locator polynomial. If the number of erasure pointers equals the number of error syndromes, then the erasure polynomial replaces the error locator polynomial.
Since the erasure pointer corresponds to the error location, only an error value needs to be computed for each erasure pointer, thereby accounting for the increase in the correction capability of the code. Without erasure pointers, the code is capable of correcting INT(m/2) code word symbols, where “m” is the degree of the generator polynomial (and the number of error syndromes). With erasure pointers, the code is capable of correcting n+INT((m−n)/2) code word symbols, where “n” is the number of erasure pointers. Thus, the error correction capability of the code in effect doubles when the number of erasure pointers equals the number of error syndromes, i.e., when “n” equals “m”.
In most applications, the receiver includes working storage (e.g., Random If Access Memory) for providing short-term storage during the decoding process. For relatively high-speed applications, working storage is preferred over slower secondary storage (e.g., magnetic or optical disks) because the read and write times of most secondary storage devices are inadequate.
While working storage is fast, it is relatively expensive. Accordingly, reducing the amount of working storage would be beneficial. In most implement
Furman Scott F.
Tash Jonathan K.
Blakely , Sokoloff, Taylor & Zafman LLP
Digeo, Inc.
Dildine R. Stephan
LandOfFree
Error-correction with limited working storage does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Error-correction with limited working storage, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error-correction with limited working storage will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3187309