Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-05-18
2001-08-07
Moise, Emmanuel L. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S763000, C714S769000, C714S781000
Reexamination Certificate
active
06272659
ABSTRACT:
FIELD OF INVENTION
The present invention relates to error correcting systems for computer storage devices, particularly to an enhanced method and apparatus for correcting a multi-dimensional code, such as a product code, by adjusting the correction power during the iterative passes to minimize miscorrections.
BACKGROUND OF THE INVENTION
In computer storage devices (such as magnetic and optical disc drives) the bandwidth of the recording channel is limited, as well is the signal power. To achieve performance gains, various coding techniques are employed to increase the effective signal-to-noise ratio (SNR) by increasing the system's immunity to noise. This allows an increase in storage capacity by increasing the recording density while maintaining an arbitrarily low bit error rate.
In error correction coding (ECC), the binary data to be recorded are processed mathematically to generate redundancy symbols that are appended to the data to form codewords which are written to the disc storage medium. Upon readback, the recorded codewords are estimated (detected) from the read signal, and the redundancy symbols are used to decode the estimated codewords back into the originally recorded user data. The redundancy symbols provide, in effect, a buffer which shields the codeword from noise as it passes through the recording channel. When enough noise “penetrates” this buffer, it mutates a written codeword into a different received codeword, thereby resulting in an error when decoded into the user data.
The more redundancy symbols employed in an error correction code, the larger the buffer around the codeword and the more noise that can be tolerated before a decoding error occurs. However, there is an upper bound on the performance of any given recording channel known as the “channel capacity” which refers to the maximum user data transmission rate (or recording density) achievable for a given channel while maintaining an arbitrarily low bit error rate. Ultimately, the channel capacity is a function of the channel bandwidth and the signal to noise ratio (SNR). As mentioned above, error correction codes are a means for improving performance by increasing the effective SNR.
There are many approaches to encoding/decoding the user data in order to maximize the reliability and efficiency of a recording 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 commonly employed in disc storage systems, particularly the Reed-Solomon block code due to its excellent error correction properties and low implementation cost and complexity.
Block codes encode a k-symbol input block of the source data stream into an n-symbol output block or codeword where n-k is the number of redundancy symbols and k
is referred to as the code rate. The codewords are then transmitted through (stored to) the communication medium and decoded by the receiver. The encoding process performs a mathematical operation over the input block such that the output codewords are different from one another by a parameter referred to as the minimum distance of the code d
min
. The minimum distance d
min
between codewords determines the amount of noise that the system can tolerate before a received codeword is decoded erroneously.
With Reed-Solomon codes, the data stream is processed as a sequence of symbols, where the symbols are typically selected from a finite field GF(2
w
). 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
)
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 codeword polynomial C(x):
C
(
x
)=(
x
m
·D
(
x
))+
W
(
x
).
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 codeword C(x) is transmitted through the noisy communication channel, wherein the received codeword C′(x) equals the transmitted codeword C(x) plus an error polynomial E(x). The received codeword C′(x) is corrected according to the following steps: (1) compute error syndromes S
i
; (2) compute the coefficients of an error locator polynomial using the error syndromes S
i
; (3) compute the roots of the error locator polynomial, the logs of the roots are the error locations l
i
; and (4) compute 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 codeword polynomial C′(x) divided by the factors of the generator polynomial G(x):
S
i
=C
′(
x
)MOD(
x+&agr;
i
)
when
G
(
x
)
=
∏
i
=
0
m
-
1
(
x
+
α
i
)
where &agr; is a primitive element of the finite field GF(2
w
). Techniques for performing the other steps of the decoding process, 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, the above referenced U.S. Pat. No. 5,446,743 entitled “COEFFICIENT UPDATING METHOD AND APPARATUS FOR REED-SOLOMON DECODER.”
The use of erasure pointers is a well known technique for increasing the power of an error correction code. An erasure pointer is an address pointing to a symbol location of a codeword where an error is likely to have occurred. For example, an erasure pointer may be generated by detecting timing phase errors or marginal amplitude in the read signal during read back. An address Ls generated to point to the codeword symbol where the timing error or amplitude attenuation was excessive. The erasure pointers are then used to augment the error correction procedure by providing information in addition to the error syndromes S
i
. An erasure polynomial is generated using the erasure pointers, where each root of the erasure polynomial replaces a root in 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 need be computed for each erasure pointer, which accounts for the increase in the correction capability of the code. Without erasure pointers the code is capable of correcting only INT(m/2) codeword symbols where m is the degree of the generator polynomial (and the number of error syndromes), whereas with erasure pointers the code is capable of correcting n+INT((m−n)/2) codeword symbols where n is the number of erasure His pointers (in effect doubling the correction capability when the number of erasure pointers equals the number of error syndromes, i.e., when n equals m).
Another technique known in the prior art to further increase the power of an error correction code is to arrange the codewords into what is known as a multi-dimensional code, such as a two-dimensional product code. Digital Video Disc (DVD) storage systems, for example, commonly employ a two-dimensional product code shown in FIG.
2
. The codewords are arranged into intersecting horizontal (row or Q) and vertical (column or P) codewords and the decoding process is carried out in iterative passes. First a pass over the horizontal codewords is performed to correct as many errors as possible; any uncorrectable horizontal codewords are left unmodified. Then a pass is made over the vertical codewords to correct as many errors as possible, where a symbol corrected in a vertical codeword also corrects the corresponding symb
Cirrus Logic Inc.
Moise Emmanuel L.
Sheerin Howard H.
Shifrin Dan
LandOfFree
Error correction code processor employing adjustable... 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 code processor employing adjustable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correction code processor employing adjustable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2493040