Error correction code encoder

• US 4,856,003 A
• Filed: 05/07/1987
• Issued: 08/08/1989
• Est. Priority Date: 05/07/1987
• Status: Expired due to Term

• Current Assignee: Maxtor Corporation (Seagate Technology Holdings Plc)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Weng, Lih-Jyh
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): BEAUSOLIEL JR, ROBERT W
• Application Number:
  US07/047,627
• Time in Patent Office: 824 Days
• Field of Search: 371/37, 371/38, 371/39, 371/40, 371/2
• US Class Current: 714/784
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence

Abstract

An encoder encodes a sector of data to produce ECC symbols using a GF(2¹⁰) code by first appending one or more pseudo data bytes to the sector data bytes. The data string of sector data bytes and pseudo data bytes are then encoded to produce a desired number of 10-bit ECC symbols. Two selected bits from each ECC symbol are compared to a known bit pattern. If the selected bits match the pattern, the bits are truncated and the remaining 8-bit symbols are concatenated with the data string to form a codeword. The codeword bytes can later be decoded, and any error correction performed, by appending the bit pattern as necessary. If the selected bits do not match the pattern, the pseudo data bytes are modified such that encoding the data bytes and the modified pseudo data bytes produce 10-bit ECC symbols with the selected bits matching the bit pattern. The selected bits are then truncated and the remaining 8-bit symbols are concatenated with the data string to form the code-word.

Claims

1. A method for encoding data symbols into code words using a modified Reed-Solomon error correction code ("ECC") over Galois Field (p^q) and a generator polynomial g(x) which has q-bit coefficients which are elements of the Galois Field such that a maximum of d errors can be corrected, said method comprising the steps of:

1. encoding K data symbols plus L predetermined pseudo data symbols to produce d q-bit ECC symbols;

2. ascertaining whether n selected bits in each of said q-bit ECC symbols match a predetermined truncation pattern, and if any of said selected bits do not match the corresponding bits in said truncation pattern, ascertaining the location of the non-matching bits; and

3. (a) in response to a determination that said selected n bits in each of said q-bit ECC symbols match said pattern, forming a code word containing said K data symbols, said L psuedo data symbols and d ECC symbols, each of which is formed from the q-n bits of a q-bit ECC symbol which are not said selected bits,

(b) in response to a determination that said selected n bits in at least one of said q-bit ECC symbols do not match said pattern,

3. The encoding method as recited in claim 1 wherein said modifying step further comprises:

1. selecting one or more rows of entries in a modifier table for each q-bit ECC symbol in response to the location of each of said selected n bits of said d q-bit ECC symbols which does not match the corresponding bit in said predetermined n-bit pattern;

2. forming L pseudo data symbol modifiers and d q-bit ECC symbol modifiers by adding, modulo p, said selected table rows, such that the column entries in each of said selected table rows are added to the corresponding entries in each of the other selected table rows; and

3. modifying said L pseudo data symbols and said q-bit ECC symbols by adding, modulo p, said pseudo data symbol modifiers and said ECC symbol modifiers to corresponding ones of said pseudo data symbols and said ECC symbols.

5. The method of claim 1 wherein the Galois Field GP (p^q) is selected such that a block of data consisting of 512 or 576 data symbols can be encoded.

6. The method of claim 1 wherein the Galois Field is GF(2¹⁰) and the predetermined truncation pattern is two bits long such that the data symbols and the code word ECC symbols are eight bits long.

7. The method of claim 5 wherein the predetermined pattern consists of two ZEROS in the leading two symbol bit positions.

10. The encoding apparatus as recited in claim 7 wherein said modifying means further comprises:

A. means for selecting one or more rows of entries in a modifier table for each q-bit ECC symbol in response to the location of each of said selected n bits of said q-bit ECC symbols which does not match the corresponding bit in said predetermined n-bit pattern;

B. means for forming L pseudo data symbol modifiers and d q-bit ECC symbol modifiers by adding, modulo p, said selected table rows, such that the column entries in each of said selected table rows are added to the corresponding entries in each of the other selected table rows; and

C. means for modifying said L pseudo data symbols and said q-bit ECC symbols by adding, modulo p, said pseudo data symbol modifiers and said ECC symbol modifiers to corresponding ones of said pseudo data symbols and said ECC symbols.

11. The apparatus of claim 7 wherein the Galois Field GF (p^q) is selected such that a block of data consisting of 512 or 576 data symbols can be encoded.

12. The apparatus of claim 7 wherein the Galois Field is GF(2¹⁰) and the predetermined pattern is two bits long such that the data symbols and the ECC symbols are eight bits long.

13. The apparatus of claim 10 wherein the predetermined pattern consists of two ZEROS in the leading two symbol bit positions.

15. The method recited in claim 12 wherein said modifier table consists of nd rows and d+L columns, with the first L columns being associated with respective ones of said L pseudo data symbols and one column being associated with each of said d ECC symbols, said table being generated by:

A. selecting potential d+1 column entries, where the d+1 column is associated with the first pseudo data symbol, for said modifier table from the elements of GF(p^q) such that the selected n bits of each potential d+1 column entry match said truncation pattern;

B. separately encoding said potential d+1 column entries by steps 1-3 of claim 12, thereby to produce d code symbols corresponding to each of said potential d+1 column entries such that each potential d+1 column entry together with all ZERO entries for the remaining L-1 pseudo data symbols and the d code symbols form potential table rows; and

C. selecting table rows from said potential table rows such that

i. each ECC symbol has n rows associated with it,

ii. in each of said n rows, the code symbol in the column associated with the ECC symbol has one of said n selected bits which does not match said truncation pattern, and

iii. each of said n rows has a different one of said selected n bits which does not match said truncation pattern.

2. modifying said predetermined pseudo data symbols to provide L modified pseudo data symbols such that encoding a string consisting of the data symbols and the modified pseudo data symbols will produce q-bit replacement ECC symbols in which said selected n bits of each of said replacement ECC symbols match said pattern, andforming a code word containing said K data symbols, said L modified psuedo data symbols and d ECC symbols, each of which is formed from the q-n bits of a q-bit replacement ECC symbol which are not the selected bits.

4. The method recited in claim 2 wherein said modifier table consists of nd rows and d+L columns, with the first L columns being associated with respect ones of said L pseudo data symbols and one column being associated with each of said d ECC symbols, said table being generated by:

i. selecting, from each of the q-bit coefficients of g(x), n element bits which have the same bit positions as said n selected bits of said q-bit ECC symbols, using the element bits as nd elements of the bottom row of an "(L)(q-n) by q-n" matrix, and using all ZEROS for the remaining bottom row elements,

ii. multiplying (modulo p(x)) each of said coefficient symbols by α

, the primitive element of Galois Field (p^q), to provide modified coefficients,

iii. using the element bits of said modified coefficients as the nd elements of the next row of said matrix and using all-ZEROS for the remaining row elements,

iv. repeating steps ii and iii until said matrix contains q-n rows.

8. An apparatus for encoding data symbols into code words using a modified Reed-Solomon error correction code ("ECC" over Galois Field (p^q) and a generator polynomial g(x) which has q-bit coefficients which are elements of the Galois Field, such that a maximum of d errors can be corrected, said apparatus comprising:

A. means for encoding K data symbols plus L predetermined pseudo data symbols to produce d q-bit ECC symbols;

B. means for ascertaining whether n selected bits in each of said q-bit ECC symbols match a truncation pattern, and if any of said selected bits do not match the corresponding bits in said truncation pattern, ascertaining the location of the non-matching bits; and

C. (1) in response to a determination that said selected n bits in each of said q-bit ECC symbols match said pattern, means for forming a code word containing said K data symbols, said L psuedo data symbols and d EEC symbols, each of which is formed from the q-n bits of a q-bit ECC symbol which are not said selected bits,

(2) in response to a determination that said selected n bits in at least one of said q-bit ECC symbols do not match said pattern,

9. modifying means for modifying said predetermined pseudo data symbols to provide L modified pseudo data symbols such that encoding a string consisting of the data symbols and the modified pseudo data symbols will produce q-bit replacement ECC symbols in which said selected n bits of each of said replacement ECC symbols match said pattern, andmeans for forming a code word containing said K data symbols, said L modified psuedo data symbols and d ECC symbols, each of which is formed from the q-n bits of a q-bit replacement ECC symbol which are not the selected bits.

14. A method for encoding data symbols into code words using a modified Reed-Soloman error correction code ("ECC") over Galois Field (p^q) and a generator polynomial g(x) which has q-bit coefficients which are elements of the Galois Field such that a maximum of d errors can be corrected, said method comprising the steps of:

1. encoding K data symbols plus L predetermined pseudo data symbols to produce d q-bit ECC symbols;

2. ascertaining whether n selected bits in each of said q-bit ECC symbols match a predetermined truncation pattern, and if any of said selected bits do not match the corresponding bits in said truncation pattern, ascertaining the location of the non-matching bits; and

3. (a) in response to a determination that said selected n bits in each of said q-bit ECC symbols match said pattern, forming a code word containing said K data symbols, said L pseudo data symbols and d ECC symbols, each of which is formed from the q-n bits of a q-bit ECC symbol which are not said selected bits,

(b) in response to a determination that said selected n bits in at least one of said q-bit ECC symbols do not match said pattern;

1. modifying said predetermined pseudo data symbols to provide L modified pseudo data symbols such that encoding a string consisting of the data symbols and the modified pseudo data symbols will produce q-bit replacement ECC symbols in which said selected n bits of each of said replacement ECC symbols match said pattern by;

i. selecting one or more rows of entries in a modifier table for each q-bit ECC symbol in response to the location of each of said selected n bits of said d q-bit ECC symbols which does not match the corresponding bit in said predetermined n-bit pattern,

ii. forming L pseudo data symbol modifiers and d q-bit ECC symbol modifiers by adding, modulo p, said selected table rows, such that the column entries in each of said selected table row are added to the corresponding entries in each of the other selected table rows,

iii. modifying said L pseudo data symbols and said q-bit ECC symbols by adding, modulo p, said pseudo data symbol modifiers and said ECC symbol modifiers to corresponding ones of said pseudo data symbols and said ECC symbols, and

2. forming a code word containing said K data symbols, said L modified pseudo data symbols and d ECC symbols, each of which is formed from the q-n bits of a q-bit replacement ECC symbol which are not the selected bits.

17. The apparatus recited in claim 14 wherein said modifier table consists of nd rows and d+L columns, with the first L columns being associated with respective ones of said L pseudo data symbols and one column associated with each of said d ECC symbols, said table being generated by:

A. selecting potential d+1 column entries, where the d+1 column is associated with the first pseudo data symbol, for said modifier table from the elements of GF(p^q) such that the selected n bits of each potential d+1 column entry match said truncation pattern;

B. separately encoding said potential d+1 column entries by the same apparatus used to encode in claim 14, thereby to produce d code symbols corresponding to each of said potential d+1 column entries such that each potential d+1 column entry together with all-ZERO entries for the remaining L-1 pseudo data symbols and the d code symbols form potential table rows;

C. selecting table rows from said potential table rows such that

i. each ECC symbol has n rows associated with it,

ii. in each of said n rows, the code symbol in the column associated with the ECC symbol has one of said n selected bits which does not match said truncation pattern;

,

iii. each of said n rows has a different one of said selected n bits which does not match said truncation pattern;

D. if L is greater than one, encoding by the same apparatus used to encode in claim 14 a symbol string S of two q-bit symbols with a first q-bit symbol consisting of q-1 ZEROS followed by a ONE and a second q-bit symbol consisting of all ZEROS, to produce a polynomial f(x);

E. selecting potential d+2 column entries for said modifier table, where the d+2 column is associated with the second pseudo data symbol, as in step A;

F. separately encoding said potential d+2 column entries by multiplying said potential entries by said polynomial f(x) to produce d+1 code symbols corresponding to each of said potential d+2 column entries such that each potential d+2 column entry together with all zero entries for the remaining L-2 pseudo data symbols and the d+1 code word symbols form potential table rows;

G. selecting table rows from said potential table rows as in step C;

H. if L is greater than two, encoding by the same apparatus used to encode claim 14 a symbol string S'"'"' of three q-bit symbols with the first two symbols the same as the symbols in said symbol string S and the third symbol consisting of all ZEROS to produce a polynomial f'"'"'(x);

I. selecting potential d+3 column entries for said modifier table, where the d+3 column is associated with the third pseudo data symbol, as in step A;

J. repeating step F, substituting f'"'"'(x) for f(x), to produce potential table rows for each of said d+3 potential column entries as in step F;

K. selecting table rows from said potential table rows as in step C;

L. repeating steps H through K, with said symbol string S'"'"' being lengthened by one all-ZERO symbol with each repetition, until nd table rows have been selected.

18. The apparatus recited in claim 14 wherein said modifier table consists of nd rows and d+L columns, with the first L columns being associated with respective ones of said L pseudo data symbols and one column being associated with each of said d ECC symbols, said table being generated by:

A. selecting from each of the q-bit coefficients of g(x), n element bits which have the same bit positions as said n selected bits of said q-bit ECC symbols, using the element bits as nd elements of the bottom row of a matrix, and using all-ZEROS for the remaining bottom row elements;

B. multiplying (modulo p(x)) each of said coefficient symbols by α

, the primitive element of Galois Field (p^q) to provide modified coefficients;

C. using the element bits of said modified coefficients as the nd elements of the next row of said matrix, and using all-ZEROS for the remaining row elements;

D. repeating steps B and C until said matrix contains q-n rows;

E. if L is greater than one, encoding said symbol string S as in claim 14 to produce a polynomial f(x);

F. repeating steps A through D substituting f(x) for the generator polynomial until the matrix contains (2)(q-n) rows;

G. if L is greater than two, encoding said symbol string S'"'"' as in claim 14 to produce a polynomial f'"'"'(x) and repeating steps A through D, substituting f'"'"'(x) for f(x), until the matrix contains (3)(q-n) rows;

H. repeating step G with said symbol string S'"'"' being lengthened by one all-ZERO symbol with each repetition until the matrix contains (L)(g-n) rows;

I. forming the pseudo inverse of said matrix by using row reduction to manipulate said matrix into a form as close as possible to the identity matrix;

J. forming the d+1 column of said modifier table by using each of the first nd rows of said pseudo inverted matrix as the q-n bits of a resulting entry in the d+1 column of the table, said q-n bits corresponding to the symbol bits which are not the n selected bits;

K. producing q-bit d+1 column table entries by combining the q-n bits of said resulting entries and said selected n-bit truncation pattern;

L. encoding each said d+1 column entry by the same apparatus used to encode in claim 17 to produce d entries for the rows of said table where each row consists of said d+1 column entry, said d column entries, and all ZERO entries for the remaining L-1 columns;

M. forming the d+2 column of said modifier table by using each of the second nd rows of said pseudo inverted matrix and repeating steps J-L;

N. repeating step M to form the remaining L-3 columns and associated rows of said modifier table.

16. An apparatus for encoding data symbols into code words using a modified Reed-Soloman error correction code ("ECC") over Galois Field (p^q) and a generator polynomial g(x) which has q-bit coefficients which are elements of the Galois Field, such that a maximum of d error can be corrected, said apparatus comprising:

A. means for encoding K data symbols plus L predetermined pseudo data symbols to produce d q-bit ECC symbols;

B. means for ascertaining whether n selected bits in each of said q-bit ECC symbols match a truncation pattern, and if any of said selected bits do not match the corresponding bits in said truncation pattern, ascertaining the location of the non-matching bits; and

C. (1) in response to a determination that said selected n bits in each of said q-bit ECC symbols match said pattern, means for forming a code word containing said K data symbols, said L pseudo data symbols and d ECC symbols, each of which is formed from the q-n bits of a q-bit ECC symbol which are not said selected bits,

(2) in response to a determination that said selected n bits in at least one of said q-bit ECC symbols do not match said pattern, means for modifying said q-bit ECC symbols including;

1. modifying means for modifying said predetermined pseudo data symbols to provide L modified pseudo data symbols such that encoding a string consisting of the data symbols and the modified pseudo data symbols will produce q-bit replacement ECC symbols in which said selected n bits of each of said replacement ECC symbols match said pattern, said modifying means including;

i. means for selecting one or more rows of entries in a modifier table for each q-bit ECC symbol in response to the location of each of said selected n bits of said d q-bit ECC symbols which does not match the corresponding bit in said predetermined n-bit pattern,

ii. means for forming L pseudo data symbol modifiers and d q-bit ECC symbol modifier by adding, modulo p, said selected table rows, such that the column entries in each of said selected table rows are added to the corresponding entries in each of the other selected table rows,

iii. means for modifying said L pseudo data symbols and said q-bit ECC symbols by adding, modulo p, said pseudo data symbol modifiers and said ECC symbol modifiers to corresponding ones of said pseudo data symbols and said ECC symbols; and

2. means for forming a code word containing said K data symbols, said L modified pseudo data symbols and d ECC symbols, each of which is formed from the q-n bits of a q-bit replacement ECC symbols which are not the selected bits.