Method and a system for multiple error detection and correction

• US 4,782,490 A
• Filed: 03/16/1987
• Issued: 11/01/1988
• Est. Priority Date: 03/16/1987
• Status: Expired due to Fees

• Current Assignee: GT Technologies
• Original Assignee: Cythera Corporation
• Inventors: Tenengolts, Grigory
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): BEAUSOLIEL JR, ROBERT W
• Application Number:
  US07/025,978
• Time in Patent Office: 596 Days
• Field of Search: 371/37, 371/38, 371/39, 371/40, 371/3
• US Class Current: 714/756
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials

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(2⁸), 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(2⁸).

The Reed-Solomon code has a form

g.sub.0 (x)=x.sup.4 +α.sup.54 x.sup.3 +α.sup.9 x.sup.2

+α⁵⁴ x+1,

where α is a primitive element of the field GF(2⁸), 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 x₁ of an error location polynomial

σ(x)=x.sup.2 +σ.sub.1 x+σ.sub.2

to calculate the second root x₂ 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).

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 g₀ (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(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.

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 g₀ (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(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.

3. A system as recited in claim 2 in which m=8 and α

is a root of a primative polynomial x⁸ +x⁶ +x⁵ +x⁴ +1 over GF(2).

4. A system as recited in claim 2 wherein said correction verification generator meas including means for generating said first check symbols with a code with a generator polynomial

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

9. A system as recited in claim 7 wherein said fourth shift register means has h serially connected stages respectively designated x⁰, x¹, . . . , and x^h-1, wherein said third shift register means has h serially connected stages respectively designated x^h, x^h+1, . . . , and x^2h-1, wherein said second shift register means has h serially connected stages respectively designated x^2h, x^2h+1, . . . , and x^3h-1, and wherein said first shift register means has h serially connected stages respectively designated x^3h, x^3h+1, . . . , x^4h-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(2^m).

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(2^m).

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

View Dependent Claims (13, 14)

13. A system as recited in claim 12 wherein said error location calculator means calculates another root x₂ of said error location polynomial by means of an equation

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 x⁰ through x^2h-1 stages, when the value in at least one of said x⁰ 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⁰ through x^2h-1 stages is zero for receiving as a pattern of a single burst the contents of said x^4h-1 through x^2h 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

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 x₁ 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

View Dependent Claims (19, 21)

19. A method as recited in claim 17 wherein

m=8

and

a=α

⁹,

where α

is a root of a primitive polynomial

space="preserve" listing-type="equation">x.sup.8 +x.sup.6 +x.sup.5 +x.sup.4 +1

over GF(2).

21. A system as recited in claim 19 wherein said combinatorial circuit employs means for performing multiplication by a in the Galois field GF(2^m).

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(2^m) 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(2^m), 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