Method and a system for multiple error detection and correction

Claim 1

A method of encoding a block of data comprising in combination the steps of: generating a plurality of check symbols from said data with an interleaved Reed-Solomon code with a generator polynomial g(x)=g.sub.0 (x.sup.h), where x is a variable, h is the degree of interleaving, and g 0 (x) is a generator polynomial of the form ##EQU3## where v=2.sup.m-1 -2, α is a primitive element of the Galois field GF(2 m ), a is a positive integer, b is a positive integer, and m is a positive integer; and appending said check symbols to said data.

Claim 2

A method of encoding a block of data comprising in combination the steps of: generating a plurality of check symbols from said data with an interleaved Reed-Solomon code with a generator polynomial g(x)=g.sub.0 (x.sup.h), where x is a variable, h is the degree of interleaving, and g 0 (x) is a generator polynomial of the form ##EQU3## where v=2.sup.m-1 -2, α is a primitive element of the Galois field GF(2 m ), a is a positive integer, b is a positive integer, and m is a positive integer; and appending said check symbols to said data.

Claim 3

A system for receiving signals representing data and for developing signals representing a codeword, the system comprising in combination: correction verification generator means including a set of inputs for connection to receive the data signals and a set of outputs at which said correction verification generator means develops signals representing at least one first check symbol; and encoder/residue generator means including a set of inputs connected to receive said data signals followed by said first check symbol signals, and a set of outputs at which said encoder/residue generator means develops the codeword signals, said encoder/residue generator means including means for generating from said data and said first check symbols as "data" a plurality of second check symbols with an interleaved Reed-Solomon code with a generator polynomial g(x)=g.sub.0 (x.sup.h), where x is a variable, h is the degree of interleaving, and g 0 (x) is a generator polynomial of the form ##EQU4## where v=2.sup.m-1 -2. α is a primitive element of the Galois field GF(2 m ), a is a positive integer, b is a positive integer, and m is a positive integer and for appending said first and said second check symbols to said data to develop said codeword.

Claim 4

A system for receiving signals representing data and for developing signals representing a codeword, the system comprising in combination: correction verification generator means including a set of inputs for connection to receive the data signals and a set of outputs at which said correction verification generator means develops signals representing at least one first check symbol; and encoder/residue generator means including a set of inputs connected to receive said data signals followed by said first check symbol signals, and a set of outputs at which said encoder/residue generator means develops the codeword signals, said encoder/residue generator means including means for generating from said data and said first check symbols as "data" a plurality of second check symbols with an interleaved Reed-Solomon code with a generator polynomial g(x)=g.sub.0 (x.sup.h), where x is a variable, h is the degree of interleaving, and g 0 (x) is a generator polynomial of the form ##EQU4## where v=2.sup.m-1 -2. α is a primitive element of the Galois field GF(2 m ), a is a positive integer, b is a positive integer, and m is a positive integer and for appending said first and said second check symbols to said data to develop said codeword.

Claim 14

A system for correcting errors in a codeword that includes data and check symbols at least a portion of which (2) have been generated at least said data with an interleaved Reed-Solomon code with a generator polynomial g(x)=g.sub.0 (x.sup.h), where x is a variable, h is the degree of interleaving, and ##EQU6## where v=2.sup.m-1 -2, α is a primitive element of the Galois field GF(2 m ), and m is a positive integer, the system comprising in combination: data buffer means for connection to receive the data portion of the codeword, said data buffer means for storing for a predetermined period said data; encoder/residue generator means for connection to receive said codeword, said encoder/residue generator means including shift register means having a plurality of shift register stages respectively designated x 0 , x 1 , . . . , and x 4h-1 for generating a residue with said generator polynomial, correction iteration counter means connected to said encoder/residue generator means, said correction iteration counter means for counting h interations of a correction procedure including an ith iteration wherein i=1, 2, . . . , and h and for developing a signal for terminating said correction procedure; syndrome calculator means connected to said encoder/residue generator means to receive at said ith iteration the contents of said x i-1 th, said x i-1+h th, said x i-1+2H th, and x i-1+3h th stages of said shift register means of said encoder/residue generator means, said syndrome calculator means for calculating four syndromes S.sub.j =S(α.sup.v+j)/α.sup.4(v+j), where j=1, 2, 3, and 4, from the polynomial S(x)=S.sub.3 x.sup.3 +S.sub.2 x.sup.2 +S.sub.1 x+S.sub.0, where S 0 , S 1 , S 2 , and S 3 are equal to the contents of said x i-1 , said x i-1+h , said x i-1+2h , and said x i-1+3h stage, respectively, of said shift register means of said encoder/residue generator means at said ith iteration of said correction procedure; error location polynomial calculator means connected to said syndrome calculator means to receive said syndromes, said error location polynomial calculator means for calculating an error location polynomial σ(x)=x.sup.2 +σ.sub.1 x+σ.sub.2, where σ.sub. = (S.sub.1 S.sub.2 +S.sub.0 S.sub.3)/Δ, σ.sub.2 =(S.sub.1 S.sub.3 +S.sub.2)/Δ, and Δ=S.sub.1.sup.2 +S.sub.0 S.sub.2 ; error location calculator means connected to said error location polynomial calculator means to receive said error location polynomial, said error location calculator means for calculating at least one root x 1 of said error location polynomial to find an associated error location; error value calculator means connected to said syndrome calculator means and to said error location calculator means, said error value calculator means for calculating an error value associated with said error location; and half adder means connected to said data buffer means and to said error value calculator means, said half adder means for correcting said error value at said error location in said data.

Claim 15

A system for correcting errors in a codeword that includes data and check symbols at least a portion of which (2) have been generated at least said data with an interleaved Reed-Solomon code with a generator polynomial g(x)=g.sub.0 (x.sup.h), where x is a variable, h is the degree of interleaving, and ##EQU6## where v=2.sup.m-1 -2, α is a primitive element of the Galois field GF(2 m ), and m is a positive integer, the system comprising in combination: data buffer means for connection to receive the data portion of the codeword, said data buffer means for storing for a predetermined period said data; encoder/residue generator means for connection to receive said codeword, said encoder/residue generator means including shift register means having a plurality of shift register stages respectively designated x 0 , x 1 , . . . , and x 4h-1 for generating a residue with said generator polynomial, correction iteration counter means connected to said encoder/residue generator means, said correction iteration counter means for counting h interations of a correction procedure including an ith iteration wherein i=1, 2, . . . , and h and for developing a signal for terminating said correction procedure; syndrome calculator means connected to said encoder/residue generator means to receive at said ith iteration the contents of said x i-1 th, said x i-1+h th, said x i-1+2H th, and x i-1+3h th stages of said shift register means of said encoder/residue generator means, said syndrome calculator means for calculating four syndromes S.sub.j =S(α.sup.v+j)/α.sup.4(v+j), where j=1, 2, 3, and 4, from the polynomial S(x)=S.sub.3 x.sup.3 +S.sub.2 x.sup.2 +S.sub.1 x+S.sub.0, where S 0 , S 1 , S 2 , and S 3 are equal to the contents of said x i-1 , said x i-1+h , said x i-1+2h , and said x i-1+3h stage, respectively, of said shift register means of said encoder/residue generator means at said ith iteration of said correction procedure; error location polynomial calculator means connected to said syndrome calculator means to receive said syndromes, said error location polynomial calculator means for calculating an error location polynomial σ(x)=x.sup.2 +σ.sub.1 x+σ.sub.2, where σ.sub. = (S.sub.1 S.sub.2 +S.sub.0 S.sub.3)/Δ, σ.sub.2 =(S.sub.1 S.sub.3 +S.sub.2)/Δ, and Δ=S.sub.1.sup.2 +S.sub.0 S.sub.2 ; error location calculator means connected to said error location polynomial calculator means to receive said error location polynomial, said error location calculator means for calculating at least one root x 1 of said error location polynomial to find an associated error location; error value calculator means connected to said syndrome calculator means and to said error location calculator means, said error value calculator means for calculating an error value associated with said error location; and half adder means connected to said data buffer means and to said error value calculator means, said half adder means for correcting said error value at said error location in said data.

Claim 18

A system for correcting errors in a codeword that includes data, a first group of check symbols and a second group of check symbols, at least a portion of the first group of check symbols having been generated by a code with a generator polynomial g.sub.v (x)=x.sup.p +1, over the Galois field GF(2 m ), where p is a positive integer, the second group of check symbols having been generated from the data and the first group of check symbols as "data" by an interleaved Reed-Solomon code with a generator polynomial g(x)=g.sub.0 (x.sup.h), where x is a variable, h is the degree of interleaving, and ##EQU7## where v=2.sup.m-1 -2, α is a primitive element of the Galois field GF(2 m ), and m is a positive integer, the system comprising in combination: correction verification generator means for connection to receive the data and the first group of check symbols of the codeword, said correction verification generator means for generating from said codeword with the generator polynomial g v (x) a first residue including at least one byte; encoder/residue generator means for connection to receive said codeword, said encoder/residue generator means including shift register means having a plurality of shift register stages respectively designated x 0 , x 1 , . . . , and x 4h-1 for generating a second residue with the generator polynomial g(x); data buffer means for connection to receive said data of said codeword, said data buffer means for storing for a predetermined period said data; correction iteration counter means connected to said encoder/residue generator means, said correction iteration counter means for counting h iterations of a correction procedure including an ith iteration wherein i=1, 2, . . . , and h, and for developing a signal for terminating said correction procedure; syndrome calculator means connected to said encoder/residue generator means to receive at each of said iterations the contents of said x i-1 th, said x i-1 th, said x i-1+2h th, and x i-1+3 th stages of said shift register means of said encoder/residue generator means, said syndrome calculator means for calculating four syndromes S.sub.i =S(α.sup.v+j)/α.sup.4(v+j), where j=1, 2, 3, and 4, from the polynomial S(x)=S.sub.3 x.sup.3 +S.sub.2 x.sup.2 +S.sub.1 x+S.sub.0, where S 0 , S 1 , S 2 , and S 3 are equal to the contents of said x i-1 , said x i-1+h , said x i-1+2h , and said x i-1+3h stage, respectively, of said shift register means of said encoder/residue generator means at said ith iteration of said correction procedure; error location polynomial calculator means connected to said syndrome calculator means to receive said syndromes, said error location polynomial calculator means for calculating an error location polynomial σ(x)=x.sup.2 +σ.sub.1 x+σ.sub.2, where σ.sub. = (S.sub.1 S.sub.2 +S.sub.0 S.sub.3)/Δ, σ.sub.2 =(S.sub.1 S.sub.3 +S.sub.2)/Δ, and Δ=S.sub.1.sup.2 +S.sub.0 S.sub.2 ;

Claim 19

A system for correcting errors in a codeword that includes data, a first group of check symbols and a second group of check symbols, at least a portion of the first group of check symbols having been generated by a code with a generator polynomial g.sub.v (x)=x.sup.p +1, over the Galois field GF(2 m ), where p is a positive integer, the second group of check symbols having been generated from the data and the first group of check symbols as "data" by an interleaved Reed-Solomon code with a generator polynomial g(x)=g.sub.0 (x.sup.h), where x is a variable, h is the degree of interleaving, and ##EQU7## where v=2.sup.m-1 -2, α is a primitive element of the Galois field GF(2 m ), and m is a positive integer, the system comprising in combination: correction verification generator means for connection to receive the data and the first group of check symbols of the codeword, said correction verification generator means for generating from said codeword with the generator polynomial g v (x) a first residue including at least one byte; encoder/residue generator means for connection to receive said codeword, said encoder/residue generator means including shift register means having a plurality of shift register stages respectively designated x 0 , x 1 , . . . , and x 4h-1 for generating a second residue with the generator polynomial g(x); data buffer means for connection to receive said data of said codeword, said data buffer means for storing for a predetermined period said data; correction iteration counter means connected to said encoder/residue generator means, said correction iteration counter means for counting h iterations of a correction procedure including an ith iteration wherein i=1, 2, . . . , and h, and for developing a signal for terminating said correction procedure; syndrome calculator means connected to said encoder/residue generator means to receive at each of said iterations the contents of said x i-1 th, said x i-1 th, said x i-1+2h th, and x i-1+3 th stages of said shift register means of said encoder/residue generator means, said syndrome calculator means for calculating four syndromes S.sub.i =S(α.sup.v+j)/α.sup.4(v+j), where j=1, 2, 3, and 4, from the polynomial S(x)=S.sub.3 x.sup.3 +S.sub.2 x.sup.2 +S.sub.1 x+S.sub.0, where S 0 , S 1 , S 2 , and S 3 are equal to the contents of said x i-1 , said x i-1+h , said x i-1+2h , and said x i-1+3h stage, respectively, of said shift register means of said encoder/residue generator means at said ith iteration of said correction procedure; error location polynomial calculator means connected to said syndrome calculator means to receive said syndromes, said error location polynomial calculator means for calculating an error location polynomial σ(x)=x.sup.2 +σ.sub.1 x+σ.sub.2, where σ.sub. = (S.sub.1 S.sub.2 +S.sub.0 S.sub.3)/Δ, σ.sub.2 =(S.sub.1 S.sub.3 +S.sub.2)/Δ, and Δ=S.sub.1.sup.2 +S.sub.0 S.sub.2 ;

Claim 22

A system for correcting errors in a codeword that includes data and check symbols at least a portion of which (2) have been generated from at least the data with an interleaved Reed-Solomon code with a generator polynomial g(x)=g.sub.0 (x.sup.h), where x is a variable, h is the degree of interleaving, and ##EQU8## where v=2.sup.m-1 -2, α is a primitive element of the Galois field GF(2 m ), and m is a positive integer, the system comprising in combination: data buffer means for connection to receive the data portion of the codeword, said data buffer means for storing for a predetermined period said data; encoder/residue generator means for connection to receive said codeword, said encoder/residue generator means including shift register means having a plurality of shift register stages respectively designated x 0 , x 1 , . . . , and x 4h-1 for generating a residue with said generator polynomial, said encoder/residue generator means being responsive to a signal and operative to shift said residue in said shift register stages; residue buffer means connected to said encoder/residue generator means, said residue buffer means for receiving and storing said residue; firmware correction unit means including, correction iteration counter means connected to said encoder/residue generator means, said correction iteration counter means for counting h iterations of a correction procedure including an ith iteration wherein i=1, 2, . . . , and h and for developing a signal for terminating said correction procedure, syndrome calculator means connected to said residue buffer means to receive at each of said iterations the contents of said x i-1 th, said x i-1+h th, said x i-1+2h th, and x i-1+3h th stages of said shift register means of said encoder/residue generator means stored in said residue buffer means, said syndrome calculator means for calculating four syndromes S.sub.j =S(α.sup.v+j)/α.sup.4(v+j), where j=1, 2, 3, and 4, from the polynomial S(x)=S.sub.3 x.sup.3 +S.sub.2 x.sup.2 +S.sub.1 x+S.sub.0, where S 0 , S 1 , S 2 , and S 3 are equal to the contents of said x i-1 , said x i-1+h , said x i-1+2h , and said x i-1+3h stage, respectively, of said shift register means of said encoder/residue generator means at said ith iteration of said correction procedure; error location polynomial calculator means connected to said syndrome calculator means to receive said syndromes, said error location polynomial calculator means for calculating an error location polynomial σ(x)=x.sup.2 +σ.sub.1 x+σ.sub.2, where σ.sub. = (S.sub.1 S.sub.2 +S.sub.0 S.sub.3)/Δ, σ.sub.2 =(S.sub.1 S.sub.3 +S.sub.2)/Δ, and Δ=S.sub.1.sup.2 +S.sub.0 S.sub.2, error location calculator means connected to said error location polynomial calculator means to receive said error location polynomial, said error location calculator means for calculating at least one root x 1 of said error location polynomial to find an associated error location, error value calculator means connected to said syndrome calculator means and to said error location calculator means, said error value calculator means for calculating an error value associated with said error location, and error trapping correction unit means connected to said encoder/residue generator means, said error trapping correction unit means for detecting a non-zero value in at least one of said x 0 through x 2h-1 stages, when the value in at least one of said x 0 through x 2h-1 stages is non-zero for developing said encoder/residue generator means shifting signal so as to cause said encoder/residue generator means to shift said residue, when the value in all of said x 0 through x 2h-1 stages is zero for receiving as a patter of a single burst the contents of said x 4h-1 through x 2h stages, for developing a ccount of the number of times said residue is shifted in said shift register stages, for developing from said count a burst location, and for developing a signal which indicates when said residue has been shifted a predetermined number of times; and half adder means connected to said data buffer means, to said error trapping correction unit means, and to said error value calculator means, said half adder means for correcting said error value at said error location in said data.

Claim 23

A system for correcting errors in a codeword that includes data and check symbols at least a portion of which (2) have been generated from at least the data with an interleaved Reed-Solomon code with a generator polynomial g(x)=g.sub.0 (x.sup.h), where x is a variable, h is the degree of interleaving, and ##EQU8## where v=2.sup.m-1 -2, α is a primitive element of the Galois field GF(2 m ), and m is a positive integer, the system comprising in combination: data buffer means for connection to receive the data portion of the codeword, said data buffer means for storing for a predetermined period said data; encoder/residue generator means for connection to receive said codeword, said encoder/residue generator means including shift register means having a plurality of shift register stages respectively designated x 0 , x 1 , . . . , and x 4h-1 for generating a residue with said generator polynomial, said encoder/residue generator means being responsive to a signal and operative to shift said residue in said shift register stages; residue buffer means connected to said encoder/residue generator means, said residue buffer means for receiving and storing said residue; firmware correction unit means including, correction iteration counter means connected to said encoder/residue generator means, said correction iteration counter means for counting h iterations of a correction procedure including an ith iteration wherein i=1, 2, . . . , and h and for developing a signal for terminating said correction procedure, syndrome calculator means connected to said residue buffer means to receive at each of said iterations the contents of said x i-1 th, said x i-1+h th, said x i-1+2h th, and x i-1+3h th stages of said shift register means of said encoder/residue generator means stored in said residue buffer means, said syndrome calculator means for calculating four syndromes S.sub.j =S(α.sup.v+j)/α.sup.4(v+j), where j=1, 2, 3, and 4, from the polynomial S(x)=S.sub.3 x.sup.3 +S.sub.2 x.sup.2 +S.sub.1 x+S.sub.0, where S 0 , S 1 , S 2 , and S 3 are equal to the contents of said x i-1 , said x i-1+h , said x i-1+2h , and said x i-1+3h stage, respectively, of said shift register means of said encoder/residue generator means at said ith iteration of said correction procedure; error location polynomial calculator means connected to said syndrome calculator means to receive said syndromes, said error location polynomial calculator means for calculating an error location polynomial σ(x)=x.sup.2 +σ.sub.1 x+σ.sub.2, where σ.sub. = (S.sub.1 S.sub.2 +S.sub.0 S.sub.3)/Δ, σ.sub.2 =(S.sub.1 S.sub.3 +S.sub.2)/Δ, and Δ=S.sub.1.sup.2 +S.sub.0 S.sub.2, error location calculator means connected to said error location polynomial calculator means to receive said error location polynomial, said error location calculator means for calculating at least one root x 1 of said error location polynomial to find an associated error location, error value calculator means connected to said syndrome calculator means and to said error location calculator means, said error value calculator means for calculating an error value associated with said error location, and error trapping correction unit means connected to said encoder/residue generator means, said error trapping correction unit means for detecting a non-zero value in at least one of said x 0 through x 2h-1 stages, when the value in at least one of said x 0 through x 2h-1 stages is non-zero for developing said encoder/residue generator means shifting signal so as to cause said encoder/residue generator means to shift said residue, when the value in all of said x 0 through x 2h-1 stages is zero for receiving as a patter of a single burst the contents of said x 4h-1 through x 2h stages, for developing a ccount of the number of times said residue is shifted in said shift register stages, for developing from said count a burst location, and for developing a signal which indicates when said residue has been shifted a predetermined number of times; and half adder means connected to said data buffer means, to said error trapping correction unit means, and to said error value calculator means, said half adder means for correcting said error value at said error location in said data.

Claim 24

A method of encoding a block of data comprising in combination the steps of: generating a plurality of check symbols from said data with a Hamming code with a generator polynomial g.sub.d (x)=x.sup.2 +ax+1, which is irreducible over the Galois field GF(2 m ) and which has a period equal to (2.sup.2m -1)/(2.sup.m -1), with symbols from the Galois field GF(2 m ), where x is a variable and m is a positive integer; and appending said check symbols to said data.

Claim 25

A method of encoding a block of data comprising in combination the steps of: generating a plurality of check symbols from said data with a Hamming code with a generator polynomial g.sub.d (x)=x.sup.2 +ax+1, which is irreducible over the Galois field GF(2 m ) and which has a period equal to (2.sup.2m -1)/(2.sup.m -1), with symbols from the Galois field GF(2 m ), where x is a variable and m is a positive integer; and appending said check symbols to said data.

Claim 27

A system for detecting errors in a codeword that includes data and check symbols which have been generated from the data with a generator polynomial g.sub.d (x)=x.sup.2 +ax+1, which is irreducible over the Galois field GF(2 m ) and which has a period equal to (2.sup.2m -1)/(2.sup.m -1), where x is a variable and m is a positive integer, the system comprising in combination: an encoder/residue generator including, a plurality of input gates having a set of inputs and a set of outputs, said input gates for selectively coupling externally developed signals each to a corresponding one of said set of outputs of said input gates, a plurality of feedback gates having a set of inputs and a set of outputs, said feedback gates for selectively coupling signals developed at said set of inputs of said feedback gates each to a corresponding one of said set of outputs of said feedback gates, a plurality of output gates having a set of inputs and a set of outputs, said output gates for selectively coupling signals developed at said set of inputs of said output gates each to a corresponding one of said set of outputs of said output gates, `a first half adder having a first set of inputs connected to said set of outputs of said input gates, a second set of inputs, and a set of outputs connected both to said set of inputs of said feedback gates and to said set of inputs of said output gates, a second half adder having a first set of inputs, a second set of inputs, and a set of outputs, a combinatorial circuit having a set of inputs connected to said set of outputs of said feedback gates and a set of outputs connected to said first set of inputs of said second half adder, first shift register means having a set of inputs connected to said set of outputs of said second half adder and a set of outputs connected to said second set of inputs of said first half adder, and second shift register means having a set of inputs connected to said set of outputs of said first half adder and a set of outputs connected to said second set of inputs of said second half adder and an error detector connected to said set of inputs of said output gates.

Claim 28

A system for detecting errors in a codeword that includes data and check symbols which have been generated from the data with a generator polynomial g.sub.d (x)=x.sup.2 +ax+1, which is irreducible over the Galois field GF(2 m ) and which has a period equal to (2.sup.2m -1)/(2.sup.m -1), where x is a variable and m is a positive integer, the system comprising in combination: an encoder/residue generator including, a plurality of input gates having a set of inputs and a set of outputs, said input gates for selectively coupling externally developed signals each to a corresponding one of said set of outputs of said input gates, a plurality of feedback gates having a set of inputs and a set of outputs, said feedback gates for selectively coupling signals developed at said set of inputs of said feedback gates each to a corresponding one of said set of outputs of said feedback gates, a plurality of output gates having a set of inputs and a set of outputs, said output gates for selectively coupling signals developed at said set of inputs of said output gates each to a corresponding one of said set of outputs of said output gates, `a first half adder having a first set of inputs connected to said set of outputs of said input gates, a second set of inputs, and a set of outputs connected both to said set of inputs of said feedback gates and to said set of inputs of said output gates, a second half adder having a first set of inputs, a second set of inputs, and a set of outputs, a combinatorial circuit having a set of inputs connected to said set of outputs of said feedback gates and a set of outputs connected to said first set of inputs of said second half adder, first shift register means having a set of inputs connected to said set of outputs of said second half adder and a set of outputs connected to said second set of inputs of said first half adder, and second shift register means having a set of inputs connected to said set of outputs of said first half adder and a set of outputs connected to said second set of inputs of said second half adder and an error detector connected to said set of inputs of said output gates.