Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-09-22
2003-09-02
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S784000, C714S758000
Reexamination Certificate
active
06615387
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to an error correction apparatus and method. In particular, the invention relates to an apparatus and method for detecting miscorrections of data read from a storage medium using Linear Block Code encoding and decoding as an error detection code (EDC).
BACKGROUND
A storage medium is subject to various types of noise, distortion, and interference; various errors can occur at the output of the storage medium. This is particularly true for rotating magnetic media based storage systems and media, such as hard magnetic disc drives. The current trend is to store greater amounts of digital data in smaller areas on the storage medium. This trend increases the probability of errors. To detect errors and correct the detected errors, error correction coding (ECC) is used. To verify that the corrections made by the ECC are valid, an EDC is used.
Error correction coding typically consists of at least an “encoding algorithm” and a “decoding algorithm”. For example, if systematic encoding is used, the encoding algorithm takes a block of k data symbols and computes r parity symbols which are appended to the data symbols to form a block of data. For any given code, the number r is fixed and the number k must be less than a fixed bound.
The block of data consisting of data symbols and parity symbols is referred to as a “codeword”. However, a codeword written to the storage medium can be corrupted during read-back from the storage medium. Consequently, the decoding algorithm takes the codeword, which may or may not be corrupted, as input and then determines if errors have occurred and, if so, attempts to correct those errors. The decoding algorithm can correct up to T errors, where T is a fixed constant depending on the code and related to the number of parity symbols used to construct the codeword. Typically, the decoding algorithm computes symbols called “syndromes”, which are determined from the (possibly corrupted) data and parity symbols read from the storage medium. As a result of the codeword design, if all bits in all the syndromes are 0, the data read constitutes a valid codeword. Otherwise, errors are detected and the syndromes are used as the inputs to the error correction algorithm.
Linear Block Codes (LBC) are a very broad class of codes that are useful for error correction. Details concerning LBCs are apparent to those skilled in the art of error control systems and are therefore set forth briefly for a proper understanding of the invention. Generally, source data is segmented into blocks of k m-bit data or message symbols; each block can represent one of 2
mk
distinct messages. An encoder then transforms the blocks of k data/message symbols into larger blocks of n symbols. The encoder essentially adds. r=(n−k) parity symbols to the k data/message symbols. The collection of all such blocks of length n is a linear (n, k) block code because its 2
mk
codewords form a k-dimensional subspace of the vector space of all the n-tuples over a Galois Field (GF) of order 2
m
(GF(2
m
)). Consequently, it is possible to define a generator matrix as well as a parity check matrix. Encoding of the source data to generate a codeword, using non-systematic encoding, is accomplished by multiplying the k data/message symbols by the generator matrix. Decoding occurs by multiplying a received codeword by the parity check matrix to generate syndromes. If the syndromes equal zero, the received codeword is valid and the k data/message symbols are, with high probability, uncorrupted (i.e., the received codeword is the original codeword).
One typical and frequently employed class of LBC error correcting codes (ECC) are Reed-Solomon (RS) codes. For a T
ECC
-error correcting RS code, 2T
ECC
ECC parity symbols
102
, such that r=2T
ECC
, are appended to each block of k m-bit user data symbols
102
to create a codeword
103
, as depicted in FIG.
1
. There are k+2T
ECC
symbols in a RS codeword. The RS code views each m-bit user data symbol as an element of GF(2
m
). A GF is a finite field, the elements of which may be represented as polynomials in alpha (&agr;), where &agr; is a root of an irreducible polynomial of degree m. Table 1 depicts a subset of irreducible polynomials of degree m. The RS codeword consists of a block of m-bit symbols. Constructing the GF(2
m
) requires defining an irreducible polynomial P(x) of degree m. In addition, a primitive element beta &bgr; is chosen so that every nonzero element of GF(2
m
) is a power of &bgr;. The element &bgr; is not necessarily a root of P(x).
TABLE I
Exemplary Subset of Irreducible Primitive Polynomials of Degree m
m
m
3
1 + X + X
3
14
1 + X + X
6
+ X
10
+ X
14
4
1 + X + X
4
15
1 + X + X
15
5
1 + X
2
+ X
5
16
1 + X + X
3
+ X
12
+ X
16
6
1 + X + X
6
17
1 + X
3
+ X
17
7
1 + X
3
+ X
7
18
1 + X
7
+ X
18
8
1 + X
2
+ X
3
+ X
4
+ X
8
19
1 + X + X
2
+ X
5
+ X
19
9
1 + X
4
+ X
9
20
1 + X
3
+ X
20
10
1 + X
3
+ X
10
21
1 + X
2
+ X
21
11
1 + X
2
+ X
11
22
1 + X + X
22
12
1 + X + X
4
+ X
6
+ X
12
23
1 + X
5
+ X
23
13
1 + X + X
3
+ X
4
+ X
13
24
1 + X + X
2
+ X
7
+ X
24
A RS codeword is viewed as a codeword polynomial (C(x)) and the redundancy symbols are chosen so that the roots of C(x) include the roots of a generator polynomial G(x) whose roots are 2T consecutive powers of &bgr; beginning with &bgr;
m0
, such that G(x)=(x−&bgr;
m0+1
) . . . (x−&bgr;
m0+2T−1
) and mO is an arbitrary integer. The k user data symbols are viewed as the high order coefficients of a degree k+2T−1 polynomial (U(x)), and the redundancy symbols are the coefficients of the remainder (B(x)) when the polynomial U(x) is divided by G(x) such that B(x)=U(x) modulo G(x), and C(x)=U(x)−B(x).
Once the codeword C(x) is formed, C(x) is generally written to a data storage medium. The process of corrupting the original codeword C(x) generally occurs during read back from the storage medium where a received polynomial R(x) is returned. However, if the received polynomial R(x) is not corrupted, R(x) is equal to C(x), the codeword polynomial before being written to the storage media.
However, errors often occur in bursts rather than in random patterns, so that several consecutive bytes or symbols are in error. Since the correction code's capacity is limited to 2T errors, error bursts will often exceed the code's capacity. For example, errors in such a burst are confined to a single codeword, the error correction coding technique cannot correct these errors.
Interleaving the user data is often used to overcome this deficiency respective of burst errors. Interleaving involves partitioning a block of data into smaller sub-blocks called interleaves and independently computing parity for each of the interleaves. Interleaving provides two principal advantages: (a) error bursts are distributed over several codewords; and (b) larger blocks of data can be encoded.
The ability to encode larger blocks of data with interleaving is vital when dealing with binary data. Binary data is partitioned into sub-blocks referred to as symbols. Typically, the symbols consist of 8 bits and are called bytes. Yet, the codeword size for RS codes of binary data is limited to 2
m
−1 symbols, where m is the number of bits per symbol. If a RS code uses byte symbols, the number k of data symbols is bounded by 255−2T
ECC
. However, a typical block size for user data in a byte based system is often a 512-byte sector of data read from a storage medium. Unfortunately, 512-bytes cannot be encoded with a GF(2
8
) RS code unless interleaving is used.
However, the use of interleaving does not eliminate the possibility of undetected corruption of user data. One possi
Gosula Venkata Raja
Lee Schweiray Joseph
Williamson Clifton James
Berger Derek J.
Lamarre Guy
Lucente David K.
Seagate Technology LLC
LandOfFree
Method and apparatus for error detection 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 error detection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for error detection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3068823