Dedicated ALU architecture for 10-bit Reed-Solomon error correction module
First Claim
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.
6 Assignments
0 Petitions
Accused Products
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(25)), generated by using the irreducible polynomial, P32 (X)=X5 +X2 +1, over GF(2), are utilized to perform certain, requisite arithmetic functions over the Galois field GF(210) with a hardware-minimized error correction architecture.
-
Citations
18 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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 25, 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. - View Dependent Claims (10, 11, 12, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18)
-
Specification