Dedicated ALU architecture for 10-bit Reed-Solomon error correction module

• US 5,778,009 A
• Filed: 06/14/1995
• Issued: 07/07/1998
• Est. Priority Date: 06/14/1995
• Status: Expired due to Term

• Current Assignee: Maxtor Corporation (Seagate Technology Holdings Plc)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Ou, Michael, Fredrickson, Lisa
• Primary Examiner(s): Elmore, Reba I.
• Assistant Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US08/490,345
• Time in Patent Office: 1,119 Days
• Field of Search: 371/37.1, 371/37.2, 371/37.5, 371/38.1, 371/39.1, 371/40.1, 360/40
• US Class Current: 714/752
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence

Abstract

A system architecture for implementing a 10-bit Reed-Solomon code for detecting and correcting data errors in a single code word to protect a data block containing up to 1023 10-bit data symbols, i.e., the equivalent of up to 1278 8-bit symbols, including error check redundancy, maximizes the use of all allocated error correction overhead for an entire block of data, regardless of the particular error pattern characteristics encountered in a given system application. The architecture is particularly well suited for digital data processing and/or storage systems encountering non-bursty, (i.e., substantially random), error patterns, such is characteristic of data storage and retrieval systems employing semiconductor based memory stores. 5-bit extension field operations, (i.e., over a Galois field GF(2⁵)), generated by using the irreducible polynomial, P₃₂ (X)=X⁵ +X² +1, over GF(2), are utilized to perform certain, requisite arithmetic functions over the Galois field GF(2¹⁰) with a hardware-minimized error correction architecture.

Claims

1. An adjunct data block storage and retrieval system for connection to a host computer via an interface, the system for receiving, storing and retrieving, respectively, digital data packetized in a plurality of blocks of k m-bit data symbols, comprising:

a data path connected to the interface,

first reformatting means connected to the data path for reformatting the blocks of m-bit data symbols into blocks of 10-bit data symbols;

an encoder connected to the first reformatting means and having means for generating r 10-bit error check symbols from each reformatted block of 10-bit data symbols;

second reformatting means connected to said encoder and for reformatting said r 10-bit error check symbols generated by said encoder into (10/m)*r m-bit error check symbols;

check symbol appending means connected to the second reformatting means for appending said (10/m)*r m-bit error check symbols to the respective m-bit data block from which they were generated;

a solid state data storage memory array means connected to the data path and to the check symbol appending means for receiving and storing, said plurality of m-bit data blocks including the respective appended (10/m)*r m-bit error check symbols for each block; and

retrieval means connected to the solid state data storage memory array means for retrieving said stored m-bit data blocks from said data storage means and reformatting them into respective 10-bit code words, each retrieved 10-bit code word comprising k 10-bit data symbols and r 10-bit error check symbols.

2. The adjunct data block storage and retrieval system of claim 1 wherein the retrieval means includes:

a syndrome generator for generating r 10-bit error syndromes from each retrieved 10-bit code word;

means for detecting the existence of at least one non-zero error syndrome in a given set of generated error syndromes; and

hardware-embodied error correction circuitry comprising;

means for receiving said r 10-bit error syndromes from said syndrome generator when at least one non-zero syndrome is detected,

a dedicated Galois field arithmetic logic unit having means for executing arithmetic operations on 10-bit symbols by performing extension field operations over a Galois field of 2⁵, and

a programmed controller for providing state instructions to said arithmetic logic unit which cause the arithmetic logic unit to carry out a programmed error correction routine for determining the location of, and correction value for, respectively, up to 2 erroneous 10-bit data symbols in a given retrieved 10-bit code word.

3. The adjunct data block storage and retrieval system of claim 2, said dedicated Galois field arithmetic logic unit operating upon a Galois field GF(2⁵) generated from an irreducible polynomial g(x)=x⁵ +x² +1, over GF(2).

4. The adjunct data block storage and retrieval system of claim 3, said dedicated Galois field arithmetic logic unit further operating upon the Galois field GF(2¹⁰) generated from an irreducible polynomial P₁₀₂₄ (y)=y² +y+1, over GF(2⁵).

5. The adjunct data block storage and retrieval system of claim 4, said Galois field GF(2¹⁰) having as its primitive element (101)h.

6. The adjunct data block storage and retrieval system of claim 2, said data storage means characterized in that data errors occurring in a block of data stored therein occur in substantially random bit locations.

7. The data storage and retrieval system of claim 2, said encoder combined with said syndrome generator in a single circuit.

8. The adjunct data block storage and retrieval system of claim 1 wherein said solid state data storage memory array comprises a FLASH random access memory.

9. A data storage and retrieval system for receiving, storing and retrieving, respectively, data packetized in blocks of m-bit data symbols, comprising:

an interface circuit for receiving the blocks of m-bit data symbols from an external data processing system;

a block buffer connected to the interface circuit for temporarily storing at least one of the blocks of m-bit data symbols from said interface circuit;

first reformatting means connected to the interface circuit for reformatting said blocks of m-bit data symbols received from said interface circuit into blocks of k 10-bit data symbols;

an encoder circuit connected to the first reformatting means and having means for generating r 10-bit error check symbols from each block of k 10-bit data symbols;

second reformatting means connected to the encoder circuit for reformatting said r 10-bit error check symbols generated by said encoder circuit into (10/m)*r m-bit error check symbols, wherein said (10/m)*r m-bit error check symbols are appended in said block buffer to the respective m-bit data block from which they were generated;

a semiconductor data storage array connected to said interface circuit and to said block buffer for receiving and storing, respectively, said m-bit data blocks, including the respective appended m-bit error check symbols from said block buffer;

data block retrieval means connected to the semiconductor data storage array for retrieving said stored m-bit data blocks from said data storage means and reformatting them into respective 10-bit code words, each retrieved 10-bit code word comprising k 10-bit data symbols and r 10-bit error check symbols;

a syndrome generator for generating r 10-bit error syndromes from each retrieved 10-bit code word;

means for detecting the existence of at least one non-zero error syndrome; and

error correction circuitry comprising;

means for receiving said r 10-bit error syndromes from said syndrome generator when at least one non-zero syndrome is detected,

a dedicated Galois field arithmetic logic unit having means for executing arithmetic operations on 10-bit symbols by performing extension field operations over a Galois field of 2⁵,

a programmed controller for providing state instructions to said arithmetic logic unit for carrying out a programmed error correction routine for determining the location of, and correction value for, respectively, up to 2 erroneous 10-bit data symbols in a given retrieved 10-bit code word.

10. The data storage and retrieval system of claim 9, said dedicated Galois field arithmetic logic unit operating upon a Galois field GF(2⁵) generated from an irreducible polynomial g(x)=x⁵ +x² +1, over GF(2).

11. The data storage and retrieval system of claim 10, said dedicated Galois field arithmetic logic unit further operating upon a Galois field GF(2¹⁰) generated from an irreducible polynomial P₁₀₂₄ (y)=y² +y+1, over GF(2⁵), and having as its primitive element (101)h.

12. The data storage and retrieval system of claim 9, further comprising a second buffer for receiving and temporarily storing, respectively, said m-bit data blocks retrieved from said semiconductor data storage array.

13. The data storage and retrieval system of claim 9, wherein r=8.

14. The data storage and retrieval system of claim 9, wherein (10/m)*k=256, m=16, and r=8, respectively.

15. The data storage and retrieval system of claim 9, wherein (10/m)*k=512, m=8, and r=8, respectively.

16. An adjunct data block storage and retrieval system for connection to a host computer, the system for receiving, storing and retrieving, respectively, digital data packetized in a plurality of blocks of k m-bit data symbols, comprising:

a data path from the host computer connected to an interface,

first reformatting means connected to the data path for reformatting the blocks of m-bit data symbols into blocks of 10-bit data symbols;

an encoder connected to the first reformatting means and having means for generating r 10-bit error check symbols from each reformatted block of 10-bit data symbols;

second reformatting means connected to said encoder and for reformatting said r 10-bit error check symbols generated by said encoder into (10/m)*r m-bit error check symbols;

check symbol appending means connected to the second reformatting means for appending said (10/m)*r m-bit error check symbols to the respective m-bit data block from which they were generated;

a mass-storage block memory means connected to the data path and to the check symbol appending means for receiving and storing said plurality of m-bit data blocks including the respective appended (10/m)*r m-bit error check symbols for each block;

retrieval means connected to the mass-storage block memory means for retrieving said stored m-bit data blocks and reformatting them into respective 10-bit code words, each retrieved 10-bit code word comprising k 10-bit data symbols and r 10-bit error check symbols, the retrieval means further including;

a dedicated Galois field arithmetic logic unit having means for executing an error correction algorithm by performing arithmetic operations on at least some of the r 10-bit error check symbols for locating and correcting up to two error bursts within the data block;

a programmed controller for providing state instructions to said arithmetic logic unit which carry out said error correction algorithm; and

,

a programmed digital microprocessor means for selectively receiving and processing the said at least some of the r 10-bit error check symbols for executing program-based error correction routines whenever error bursts in excess of two are determined by the dedicated Galois field arithmetic logic unit to be present within the data block.

17. The adjunct data block storage and retrieval system set forth in claim 16 wherein said dedicated Galois field arithmetic logic unit generates a Galois field GF(2¹⁰) using an irreducible polynomial P₁₀₂₄ (y)=y² +y+1, over a Galois field 2⁵, said Galois field 2⁵ being generated using the irreducible polynomial g(x)=x⁵ +x² +1, over GF(2).

18. The adjunct data block storage and retrieval system set forth in claim 17 wherein said dedicated Galois field arithmetic logic unit includes at least one Galois field 2⁵ multiplier within a Galois field 2¹⁰ multiplier functional sub-unit;

and, at least one Galois field 2⁵ inverter within a Galois field 2¹⁰ inverter functional sub-unit.