Global parity symbol for interleaved reed-solomon coded data

• US 5,642,366 A
• Filed: 07/05/1994
• Issued: 06/24/1997
• Est. Priority Date: 07/05/1994
• Status: Expired due to Term

• Current Assignee: PMC-Sierra Incorporated (Microchip Technology Incorporated)
• Original Assignee: Adaptec Incorporated (Steel Partners Holdings LP)
• Inventors: Miller, David H., Lee, Frank S., Koralek, Richard W.
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): OAKES, BRIAN
• Application Number:
  US08/270,858
• Time in Patent Office: 1,085 Days
• Field of Search: 371/37.1, 371/38.1, 371/39.1, 371/37.4, 371/37.5, 371/37.7, 371/40.1
• US Class Current: 714/762
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials
• CPC Class Codes: H03M 13/2735 Interleaver using powers of a primitive element, e.g. Galois field [GF] interleaver
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27

Abstract

A circuit and method includes a global parity symbol in a multi-way interleaved Reed-Solomon code implementation to enhance error-detection capability of the Reed-Solomon code. In one embodiment, the global parity symbol is computed over both the data symbols and the check symbols of the Reed-Solomon code, thereby providing data detection capability for errors occurring in the check symbols.

Claims

1. A method for providing a w-way interleaved Reed-Solomon error correcting code word in a data storage or data communication application, comprising the steps of:

receiving a plurality of data symbols;

computing, in each interleave a code word including said data symbols and a plurality of check symbols, said check symbols being generated by a generator polynomial given by;

space="preserve" listing-type="equation">G(X)=(X+α

.sup.j)(X+α

.sup.j+1)(X+α

.sup.j+2) . . . (X+α

.sup.j+i-1)(X+α

.sup.j+i)

where α

is a primitive element of GF(2^m) and, i and j are integers;

providing a global parity symbol GP associated with a syndrome S_GP given by one of;

##EQU18## where γ

₀, γ

₁, . . . γ

_w-1 are non-zero elements of a galois field GF(2^m), and S.sub.(i+j+1)w.sbsb.0 and S.sub.(j-1)w.sbsb.0 are, respectively, the partial syndromes corresponding to (X+α

^i+j+1) and (X+α

^j-1) for interleave w₀ ; and

for each interleave, transmitting to a storage device or a transmission medium, in accordance with said data storage or data communication application, said code word and said associated global parity symbol GP;

wherein said check symbols are generated by a single generator polynomial;

space="preserve" listing-type="equation">G.sub.w (X)=(X.sup.w +α

.sup.j)(X.sup.w +α

.sup.j+1) . . . (X.sup.w +α

.sup.j+i-1)(X.sup.w +α

.sup.j+i).

2. A method as in claim 1, wherein said the number w of interleaves divides (j+i+1), and said global parity symbol GP being computed over all interleaves using a single second generator function ##EQU19##

3. A method as in claim 1, wherein said number w of interleaves divides (j-1), and said global parity symbol GP being computed over all interleaves using a single second generator function ##EQU20##

4. A method as in claim 1, wherein said global parity symbol GP is computed as part of said Reed-Solomon error correcting code word, such that an error in said global parity symbol is detected by a non-zero syndrome computed from said check symbols and said global parity symbol.

5. A method as in claim 1, wherein said global parity symbols and said check symbols are generated simultaneously by the generator polynomial:

##EQU21##

6. A method as in claim 1, wherein said global parity symbols and said check symbols are generated simultaneously by the generator polynomial:

##EQU22##

7. A method as in claim 1, further comprising:

receiving from said storage device or transmission medium said Reed-Solomon error correcting code word; and

decoding said error correction and detecting code by computing partial syndromes S_j, S_j+i, S_j+2, . . . , S_j+i, of said generator function and said syndrome S_GP ;

wherein said Reed-Solomon error correcting code is 3-way interleaved, said method further comprises the step of estimating said syndrome S_GP using the relation;

space="preserve" listing-type="equation">S.sub.GP =S.sub.3 (α

)=S.sub.32 α

.sup.2 +S.sub.31 α

+S.sub.30.

8. A method as in claim 7, wherein said Reed-Solomon error correcting code is 3-way interleaved and said global parity symbol GP is generated by a polynomial (X+α

^v), where v is an integer, said method further comprising the step of estimating said syndrome S_GP using the relation;

space="preserve" listing-type="equation">S.sub.GP =S.sub.32 α

.sup.2v +S.sub.31 α

.sup.v +S.sub.30.

9. A method as in claim 7, wherein said Reed-Solomon error correction code is 3-way interleaved, further comprising the step of estimating said syndrome S_GP using the relation:

space="preserve" listing-type="equation">S.sub.GP =S.sub.32 α

.sub.2 +S.sub.31 α

.sub.1 +S.sub.30 α

.sub.0

where α

₀, α

₁ and α

₂ are non-zero elements of said Galois field.