Modified reed solomon code selection and encoding system

• US 5,822,336 A
• Filed: 11/14/1996
• Issued: 10/13/1998
• Est. Priority Date: 11/14/1996
• Status: Expired due to Term

• Current Assignee: Maxtor Corporation (Seagate Technology Holdings Plc)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Shen, Ba-Zhong, Weng, Lih-Jyh
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US08/749,235
• Time in Patent Office: 698 Days
• Field of Search: 371/37.11, 371/40.14
• US Class Current: 714/784
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes

Abstract

An error correction system includes an encoder that uses a modified Reed-Solomon code to encode m-bit data symbols over GF(2^m+i) and form a preliminary code with d-1 (m+i)-bit ECC symbols. The encoder then modifies the ECC symbols by combining the preliminary code word with a combination of one or more modifying code words to produce modified ECC symbols that have i bits set in a pre-selected pattern. This combination also results in "R" pseudo redundancy symbols that include the i-bit pattern being appended to the modified ECC symbols. The encoder truncates the i-bit pattern from each of the ECC symbols and the pseudo-redundancy symbols, to produce a data code word that has symbols that are elements of GF(2^m). To decode the data code word, the decoder fills in the i-bit pattern in each of the data code word symbols and decodes the code word, treating the first R of the modified ECC symbols as code word data, or information, symbols, and the remaining modified ECC symbols and the pseudo redundancy symbols as code word ECC symbols. The system determines for the encoder the generator polynomial, g(x), and the modifying code words by determining a g(x)=(x+α^L)*(x+α^L+1) . . . *(x+α^L+d-2) with L=1, 2, . . . that produces i*(d-1) modifying code words that have only one selected bit of the i-bit pattern set to a one.

Claims

1. A method for encoding data symbols into code words using a distance d modified Reed-Solomon error correction code ("ECC") over Galois Field (p^m+i) to produce a code word in GF(p^m), the method including the steps of:

A. encoding k-R data symbols to produce d-1 (m+i)-bit ECC symbols and forming a preliminary code word;

B. ascertaining which, if any, of the i selected bits in each of the ECC symbols match a predetermined i-bit truncation pattern, and

C.(i) in response to a determination that the selected i bits in each of the ECC symbols match the pattern, forming a data code word by combining the preliminary code word with an additional modifying code word, s, that has R symbols with the I bits set in the i-bit pattern and d-1 symbols with the i bits set to all zeros, to append to the preliminary code word R pseudo redundancy symbols that each have the i-bit predetermined pattern and m all zero bits,

(ii) in response to a determination that the selected i bits in at least one of the ECC symbols do not match the pattern, modifying the ECC symbols by combining the symbols with an ECC modifier code word that includes d-1 ECC modifying symbols and R pseudo redundancy symbols, the combination producing a data code word with k-R data symbols, d-1 modified ECC symbols and R pseudo redundancy symbols, all of which have the selected i bits set in the predetermined pattern, and

(iii) truncating the i bits from the data code word symbols.

2. The encoding method as recited in claim 1 wherein the modifying step further includes:

a. selecting one or more modifying code words for each ECC symbol in response to the location of each one of the selected i bits in the symbol that does not match the corresponding bit in the predetermined i-bit pattern;

b. combining the modifying code words and an additional modifying code word to produce the ECC modifier code word.

3. The method recited in claim 1 wherein the modifying step further includes:

a. selecting R leading coefficients of one or more modifying code words for each ECC symbol, in response to the location of each one of the selected i bits of the symbol that does not match the corresponding bit in the predetermined i-bit pattern;

b. combining R leading coefficients of the modifying code words with R leading coefficients of the additional modifying code word to produce R code word information symbols; and

c. encoding the R information symbols to produce an ECC modifier code word that includes d-1 ECC symbol modifiers and R pseudo redundancy symbols.

4. A method for selecting a code for use in a modified Reed Solomon encoder that encodes using an error correction code over GF(p^m+i) to produce a code word with symbols in GF(p^m), the method including the steps of:

A. selecting a distance d and setting L, the lowest root, equal to zero;

B. using a generator polynomial

space="preserve" listing-type="equation">g(x)=(x+α

.sup.L)*(x+α

.sup.L+1)* . . . (x+α

.sup.L+n-k-1)=x.sup.n-k +g.sub.n-k-1 x.sup.n-k-1 + . . . +g.sub.1 x.sup.1 +g.sub.0 x.sup.0

produce a code word c₁ '"'"'(x)=g'"'"'_n-k x^n-k +g'"'"'_n-k-1 x^n-k-1 + . . . +g'"'"'x+1x⁰

where ##EQU26## C. cyclically shifting the code word c₁ '"'"'(x) to produce a code word c₁ (x) that has as a 1 as the coefficient of x^-1 ;

D. multiplying c₁ (x) by α

⁰, α

¹ . . . α

^m-1 to produce base code words b₀, b₁, . . . b_m-1 ;

E. cyclically shifting c₁ (x);

F. multiplying c₁ (x) by the coefficient of x⁰ of c₁ (x);

G. adding the results of steps D and E to produce a code word c₂ (x);

H. multiplying c₂ (x) by α

⁰, α

¹ . . . α

_m-1 to produce base code words b_m, b_m+1 . . . b_2m-1

I. cyclically shifting c₂ (x);

J. multiplying c₁ (x) by the coefficient of x⁰ of c₂ (x);

K. adding the results of steps H and I to produce a code word C₃ (x);

L. multiplying c₃ (x) by α

⁰, α

¹ . . . α

^m-1 to produce base code words b_2m, b_2m+1 . . . b_3m-1 ;

M. repeating steps H-K for all c_w (x), 3≦

w≦

i*m;

N. determining if i*(d-1) modifying code words can be produced from linear combinations of the base words b₀, b₁, . . . b.sub.(m*w)-1

O. if so, selecting g(x) as the generator polynomial;

P. if not setting L=L+1 and if L≦

p^m+i -1 repeating steps B-N.

5. A method for determining modifying code words for use in a modified Reed Solomon encoder that uses an error correction code over GF(2^t)^h+j to produce a code word with symbols in GF(2^t)^h, the method including the steps of:

A. determining an irreducible polynomial of degree h over GF(2^t);

B. selecting an α

^v from GF(2^t)^h that when multiplied by g(x) produces a code word with one coefficient having an element of one in a predetermined position and the other of the coefficients having 0 as the corresponding element;

C. selecting another α

^v to produce another code word with a different coefficient having an element of one in a predetermined position and other coefficients having 0 as the corresponding element;

D. repeating step C to produce a total of j*(d-1) code words;

E. multiplying the code words produced in steps B-D by selected elements of GF(2^t)^h to produce additional code words that have a selected element of GF(2^t)^h in the predetermined position.

6. A system for sending data from one encoder to a selected one of many decoders, each of which uses a modified Reed Solomon code that is associated with a preselected i-bit pattern, the system including:

A. an encoder that encodes data over GF(p^m+i) and produces data code words in GF(p^m) using a modified Reed Solomon Code and one of many preselected i-bit truncation patterns, the encoder encoding data intended for a particular one of the decoders using the i-bit pattern associated with the particular decoder; and

B. a plurality of decoders, each of the decoders decoding the data code word using the i-bit pattern that is associated with the decoder, the decoders using patterns that differ from the pattern used to encode the data decoding the data code word to uncorrectable data and the decoder using the same pattern that is used to encode the data decoding the data code word to error-free or correctable data.

7. A system of claim 6, wherein each decoder includes:

a. means for encoding up to k-R data symbols to produce d-1 (m+i)-bit ECC symbols and forming a preliminary code word;

b. means for ascertaining which, if any, of the i selected bits in each of the ECC symbols match a predetermined i-bit truncation pattern, and

c. means for (i) in response to a determination that the selected i bits in each of the ECC symbols match the pattern, forming a data code word by combining the preliminary code word with an additional modifying code word S, that has R symbols with the i bits set in the i-bit pattern used by the decoder and d-1 symbols with the i bits set to all zeros, to append to the preliminary code word R pseudo redundancy symbols that each have the i-bit predetermined pattern,

(ii) in response to a determination that the selected i bits in at least one of the ECC symbols do not match the pattern, modifying the ECC symbols by combining the symbols with an ECC modifier code word that includes d-1 ECC modifying symbols and R pseudo redundancy symbols, the combination producing a data code word with k-R data symbols, d-1 modified ECC symbols and R pseudo redundancy symbols, all of which have the selected i bits set in the predetermined pattern.

8. The encoding system of claim 7 wherein each of the decoders further includes:

a. means for selecting one or more modifying code words for each ECC symbol in response to the location of each one of the selected i bits in the symbol that does not match the corresponding bit in the predetermined i-bit pattern;

b. means for combining the modifying code words and the additional modifying code word to produce the ECC modifier code word.

9. The system of claim 7 wherein the encoder further includes:

a. means for selecting the R leading coefficients of one or more modifying code words for each ECC symbol, in response to the location of each one of the selected i bits of the symbol that does not match the corresponding bit in the predetermined i-bit pattern;

c. means for combining the R leading coefficients of the modifying code words and R leading coefficients of the additional modifying code word to produce R information symbols

d. means for encoding the R information symbols to produce the ECC modifier code word.

10. A system for storing data to and retrieving data from a disk, the system including:

A. an encoder for encoding data over GF(2^m+i) and producing data code words over GF(2^m), the encoder using one of many preselected i-bit truncation patterns and encoding data to be stored in a particular track on the disk using the i-bit pattern associated with the particular track; and

B. means for retrieving data from a track on the disk; and

C. a decoder for decoding the retrieved data code word using the i-bit pattern associated with the track from which the data code word was intended to be retrieved, the decoder decoding the data code word to uncorrectable data if the means for retrieving the data retrieves the data from the incorrect track and decoding the data code word to error-free or correctable data if the data code word was retrieved from the correct track.

11. A system of claim 10, wherein the encoder includes:

a. means for encoding up to k-R data symbols to produce d-1 (m+i)-bit ECC symbols and forming a preliminary code word;

b. means for ascertaining whether i selected bits in each of the ECC symbols match a predetermined i-bit truncation pattern, and

c. means for (i) in response to a determination that the selected i bits in each of the ECC symbols match the pattern, forming a data code word by combining the preliminary code word with an additional modifying code word that has R symbols with the bits set in the i-bit pattern associated with the track and d-1 symbols with the i bits set to all zeros, to append to the preliminary code word R pseudo redundancy symbols that each have the i-bit predetermined pattern;

(ii) in response to a determination that the selected i bits in at least one of the ECC symbols do not match the pattern, modifying the ECC symbols by combining the symbols with an ECC modifier code word that includes d-1 ECC modifying symbols and R pseudo redundancy symbols, the combination producing a data code word with k-R data symbols, d-1 modified ECC symbols and R pseudo redundancy symbols, all of which have the selected i bits set in the predetermined pattern.

12. The encoding system of claim 11 wherein the encoder further includes:

a. means for selecting one or more modifying code words for each ECC symbol in response to the location of each one of the selected i bits in the symbol that does not match the corresponding bit in the selected i-bit pattern;

b. means for selecting an additional modifying code word that has particular symbols with the i bits set in the selected pattern;

c. means for combining the modifying code words and the additional modifying code word to produce an ECC modifier code word that includes d-1 ECC symbol modifiers and the R pseudo redundancy symbols; and

d. means for modifying the ECC symbols in the preliminary code word by combining the preliminary code word and the ECC modifier code word.

13. The system of claim 11 wherein the encoder further includes:

a. means for selecting the R leading coefficients of one or more modifying code words for each ECC symbol, in response to the location of each one of the i bits of the symbol that does not match the corresponding bit in the selected i-bit pattern;

b. means for selecting the R leading coefficient of an additional modifying code word that has particular symbols with the i bits set in the selected pattern;

c. means for combining the R leading coefficients of the modifying code words and the additional modifying code word to R information symbols;

d. means for encoding the R information symbols to produce the ECC modifier code word.

14. A method of reducing the modifying code word storage requirements of a system that encodes data over GF(2^m+i) to produce code words in GF(2^m) using a modified Reed Solomon code, the method including the steps of:

A. determining a ground field GF(2^t) where GF(2^m)=GF(2^t)^h and GF(2^m+i)=GF(2^t)^h+j and a generator polynomial g(x) of degree t;

B. determining an irreducible polynomial of degree h over GF(2^t);

C. determining t-i+1 modifying code words in GF(2^t)^h that each have, respectively, an element 1 of GF(2^t) 1 in a selected position;

D. storing the first coefficient of each of the modifying code words in locations associated, respectively, with the position of a non-zero element in the symbols of GF(2^t)^h.