Error correction code encoder

Claim 3

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, and 2. 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.

Claim 4

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, and 2. 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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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

Claim 9

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

Claim 12

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, and 2. means 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.

Claim 13

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, and 2. means 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.

Claim 14

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.

Claim 15

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.

Claim 16

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

Claim 17

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

Claim 20

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.

Claim 23

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.

Claim 24

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.