Method and a system for multiple error detection and correction
First 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
space="preserve" listing-type="equation">g(x)=g.sub.0 (x.sup.h), where x is a variable, h is the degree of interleaving, and g0 (x) is a generator polynomial of the form ##EQU3## where
space="preserve" listing-type="equation">v=2.sup.m-1 -2,α
is a primitive element of the Galois field GF(2m), a is a positive integer, b is a positive integer, and m is a positive integer; and
appending said check symbols to said data.
2 Assignments
0 Petitions
Accused Products
Abstract
Disclosed is a method and a system for error detection and correction in which codewords are made up of data and two groups of check symbols. The first group of check symbols is generated by a correction verification code, which verifies error correction; and, the second group of check symbols is generated by an interleaved Reed-Solomon code with symbols from the Galois field GF(28), which serves for error correction.
The correction verification code is cyclic with a generator polynomial
g.sub.v (x)=x.sup.2 +1
over the field GF(28).
The Reed-Solomon code has a form
g.sub.0 (x)=x.sup.4 +α.sup.54 x.sup.3 +α.sup.9 x.sup.2
+α54 x+1,
where α is a primitive element of the field GF(28), generated by a polynomial
p(x)=x.sup.8 +x.sup.6 +x.sup.5 +.sup.4 +1.
The error correction system decoder uses the first root x1 of an error location polynomial
σ(x)=x.sup.2 +σ.sub.1 x+σ.sub.2
to calculate the second root x2 of the polynominal.
The detection system, which employs a portion of the error correction system circuitry, uses a generalized Hamming cyclic code with a generator polynomial
g.sub.d (x)=x.sup.2 +α.sup.9 x+1
where α is a root of a primitive polynomial
p(x)=x.sup.8 +x.sup.6 +x.sup.5 +x.sup.4 +1
over the field GF(2).
-
Citations
21 Claims
-
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
space="preserve" listing-type="equation">g(x)=g.sub.0 (x.sup.h),where x is a variable, h is the degree of interleaving, and g0 (x) is a generator polynomial of the form ##EQU3## where
space="preserve" listing-type="equation">v=2.sup.m-1 -2,α
is a primitive element of the Galois field GF(2m), a is a positive integer, b is a positive integer, and m is a positive integer; andappending said check symbols to said data.
-
-
2. 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
space="preserve" listing-type="equation">g(x)=g.sub.0 (x.sup.h),where x is a variable, h is the degree of interleaving, and g0 (x) is a generator polynomial of the form ##EQU4## where
space="preserve" listing-type="equation">v=2.sup.m-1 -2.α
is a primitive element of the Galois field GF(2m), 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. - View Dependent Claims (3, 4, 5, 6, 7, 8, 9, 10, 11)
-
5. A system as recited in claim 4 in which p=2 and m=8.
-
6. A system as recited in claim 4 wherein said correction verification generator means includes
a plurality of input gates having a set of inputs and a set of outputs, said input gates for selectively coupling said data 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 half adder having a first set of inputs, a second set of inputs connected to said set of outputs of said input gates, 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; and shift register means 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 half adder.
-
-
7. A system as recited in claim 2 wherein said encoder/residue generator means includes
a plurality of input gates having a set of inputs and a set of outputs, said input gates for selectively coupling said data and first check symbol 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 added 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 output gates and to said set of inputs of said feedback gates; a second half adder having a first set of inputs, a second set of inputs, and a set of outputs; a third half adder having a first set of inputs, a second set of inputs, and a set of outputs; a fourth half adder having a first set of inputs, a second set of inputs, and a set of outputs; a first combinatorial circuit having a set of inputs connected to said set of outputs of said feedback gates and a set of outputs connected both to said first set of inputs of said fourth half adder and to said first set of inputs of said second half adder; a second 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 third 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; second shift register means having a set of inputs connected to said set of outputs of said third half adder and a set of outputs connected to said second set of inputs of said second half adder; third shift register means having a set of inputs connected to said set of outputs of said fourth half adder and a set of outputs connected to said second set of inputs of said third half adder; and fourth 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 fourth half adder.
-
- 8. A system as recited in claim 7 wherein said encoder/residue generator means further receives signals representing a codeword, including data, first check symbols, and second check symbols, said first check symbols having been generated from said data with a code with a generator polynomial
- space="preserve" listing-type="equation">g.sub.v (x)=x.sup.p +1
over the Galois field GF(2m), where p is a positive integer, said second check symbols having been generated from said data and said first check symbols as "data" with an interleaved Reed-Solomon code with a generator polynomial
space="preserve" listing-type="equation">g(x)=g.sub.0 (x.sup.h),where x is a variable, h is the degree of interleaving, and ##EQU5## where
space="preserve" listing-type="equation">v=2.sup.m-1 -2,α
is a primitive element of the Galois field (GF(2m), and m is a positive integer and wherein said encoder/residue generator means further includes an error detector having a set of inputs connected to said set of inputs of said output gates and an output, said error detector for developing at said error detector output a signal which indicates the presence of an error in said codeword.
-
-
9. A system as recited in claim 7 wherein said fourth shift register means has h serially connected stages respectively designated x0, x1, . . . , and xh-1, wherein said third shift register means has h serially connected stages respectively designated xh, xh+1, . . . , and x2h-1, wherein said second shift register means has h serially connected stages respectively designated x2h, x2h+1, . . . , and x3h-1, and wherein said first shift register means has h serially connected stages respectively designated x3h, x3h+1, . . . , x4h-1, and wherein h is greater than one.
-
10. A system as recited in claim 7 wherein said first combinatorial circuit employs means for performing multiplication by α
- a in the Galois field GF(2m).
-
11. A system as recited in claim 7 wherein said second combinatorial circuit employs means for performing multiplication by α
- b in the Galois field GF(2m).
- 12. 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
- space="preserve" listing-type="equation">g(x)=g.sub.0 (x.sup.h),
where x is a variable, h is the degree of interleaving, and ##EQU6## where
space="preserve" listing-type="equation">v=2.sup.m-1 -2,α
is a primitive element of the Galois field GF(2m), 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 x0, x1, . . . , and x4h-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 xi-1 th, said xi-1+h th, said xi-1+2H th, and xi-1+3h th stages of said shift register means of said encoder/residue generator means, said syndrome calculator means for calculating four syndromes
space="preserve" listing-type="equation">S.sub.j =S(α
.sup.v+j)/α
.sup.4(v+j),where j=1, 2, 3, and 4, from the polynomial
space="preserve" listing-type="equation">S(x)=S.sub.3 x.sup.3 +S.sub.2 x.sup.2 +S.sub.1 x+S.sub.0,where S0, S1, S2, and S3 are equal to the contents of said xi-1, said xi-1+h, said xi-1+2h, and said xi-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
space="preserve" listing-type="equation">σ
(x)=x.sup.2 +σ
.sub.1 x+σ
.sub.2,where
space="preserve" listing-type="equation">σ
.sub. = (S.sub.1 S.sub.2 +S.sub.0 S.sub.3)/Δ
,
space="preserve" listing-type="equation">σ
.sub.2 =(S.sub.1 S.sub.3 +S.sub.2)/Δ
, and
space="preserve" listing-type="equation">Δ
=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 x1 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. - View Dependent Claims (13, 14)
- 14. A system as recited in claim 12 wherein encoder/residue generator means in responsive to a signal and operative to shift said residue in said shift register stages and wherein said system further comprises:
-
residue buffer means connected to said encoder/residue generator means and to said syndrome calculator means, said residue buffer means for receiving and storing said residue for a predetermined period of time; and error trapping correction unit means connected to said encoder/residue generator means and to said half adder means, said error trapping correction unit means for detecting a non-zero value in at least one of said x0 through x2h-1 stages, when the value in at least one of said x0 through x2h-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 x0 through x2h-1 stages is zero for receiving as a pattern of a single burst the contents of said x4h-1 through x2h stages, for developing a count 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.
- 15. 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
- space="preserve" listing-type="equation">g.sub.v (x)=x.sup.p +1,
over the Galois field GF(2m), 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
space="preserve" listing-type="equation">g(x)=g.sub.0 (x.sup.h),where x is a variable, h is the degree of interleaving, and ##EQU7## where
space="preserve" listing-type="equation">v=2.sup.m-1 -2,α
is a primitive element of the Galois field GF(2m), 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 gv (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 x0, x1, . . . , and x4h-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 xi-1 th, said xi-1 th, said xi-1+2h th, and xi-1+3 th stages of said shift register means of said encoder/residue generator means, said syndrome calculator means for calculating four syndromes
space="preserve" listing-type="equation">S.sub.i =S(α
.sup.v+j)/α
.sup.4(v+j),where j=1, 2, 3, and 4, from the polynomial
space="preserve" listing-type="equation">S(x)=S.sub.3 x.sup.3 +S.sub.2 x.sup.2 +S.sub.1 x+S.sub.0,where S0, S1, S2, and S3 are equal to the contents of said xi-1, said xi-1+h, said xi-1+2h, and said xi-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
space="preserve" listing-type="equation">σ
(x)=x.sup.2 +σ
.sub.1 x+σ
.sub.2,where
space="preserve" listing-type="equation">σ
.sub. = (S.sub.1 S.sub.2 +S.sub.0 S.sub.3)/Δ
,
space="preserve" listing-type="equation">σ
.sub.2 =(S.sub.1 S.sub.3 +S.sub.2)/Δ
, and
space="preserve" listing-type="equation">Δ
=S.sub.1.sup.2 +S.sub.0 S.sub.2 ;
-
16. error location calculator means connected to said error location polynomial calculator means to receive said error location polynomial, said error location modulator means for calculating at least one root x1 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; 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; and correction verification unit means connected to said error value calculator means to receive said error value when said error value was calculated from that portion of said codeword which includes said data and said first check symbols and connected to said correction verification generator means to receive said first residue byte, said correction verification unit means for storing a binary sequence, for XORing said stored binary sequence with said error value, for replacing said stored binary sequence with the results of said XORing, for comparing said stored XORing result with said first residue byte, and for developing a signal which indicates when said stored XORing result differs from said first residue byte.
-
- 17. 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
- space="preserve" listing-type="equation">g(x)=g.sub.0 (x.sup.h),
where x is a variable, h is the degree of interleaving, and ##EQU8## where
space="preserve" listing-type="equation">v=2.sup.m-1 -2,α
is a primitive element of the Galois field GF(2m), 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 x0, x1, . . . , and x4h-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 xi-1 th, said xi-1+h th, said xi-1+2h th, and xi-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
space="preserve" listing-type="equation">S.sub.j =S(α
.sup.v+j)/α
.sup.4(v+j),where j=1, 2, 3, and 4, from the polynomial
space="preserve" listing-type="equation">S(x)=S.sub.3 x.sup.3 +S.sub.2 x.sup.2 +S.sub.1 x+S.sub.0,where S0, S1, S2, and S3 are equal to the contents of said xi-1, said xi-1+h, said xi-1+2h, and said xi-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
space="preserve" listing-type="equation">σ
(x)=x.sup.2 +σ
.sub.1 x+σ
.sub.2,where
space="preserve" listing-type="equation">σ
.sub. = (S.sub.1 S.sub.2 +S.sub.0 S.sub.3)/Δ
,
space="preserve" listing-type="equation">σ
.sub.2 =(S.sub.1 S.sub.3 +S.sub.2)/Δ
, and
space="preserve" listing-type="equation">Δ
=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 x1 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 x0 through x2h-1 stages, when the value in at least one of said x0 through x2h-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 x0 through x2h-1 stages is zero for receiving as a patter of a single burst the contents of said x4h-1 through x2h 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. - View Dependent Claims (19, 21)
-
18. 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
space="preserve" listing-type="equation">g.sub.d (x)=x.sup.2 +ax+1,which is irreducible over the Galois field GF(2m) and which has a period equal to
space="preserve" listing-type="equation">(2.sup.2m -1)/(2.sup.m -1),with symbols from the Galois field GF(2m), where x is a variable and m is a positive integer; and appending said check symbols to said data.
-
- 20. 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
- space="preserve" listing-type="equation">g.sub.d (x)=x.sup.2 +ax+1,
which is irreducible over the Galois field GF(2m) and which has a period equal to
space="preserve" listing-type="equation">(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.
Specification