Multiple error detecting and correcting system employing Reed-Solomon codes
First Claim
1. A circuit for detecting and correcting errors occurring in a Reed-Solomon code word w(x) constituted by a data word d(x) having k data symbols and a checksum word E(x) having n-k data symbols, the symbols of said checksum word E(x) being elements in the Galois Field GF(2m), for any integer m greater than 0, said checksum word being derived by encoding said data word d(x) by a predetermined generator polynomial g(x) having roots α
-
i wherein α
is a primitive element in the Galois Field GF(2m), said circuit comprising;
A. receiving means for receiving a word y(x) that was transmitted as the code word w(x), said word y(x) being comprised of a data word c(x) having k symbols and a checksum word E1(x) having n-k symbols,B. Reed-Solomon encoding means for encoding said data word c(x) by said generator polynomial g(x) for producing another checksum word E2(x), said encoding means comprising successively connected shift register stages and feedback means that enable encoding of the data word c(x) by said generator polynomial g(x) during shifting of the symbols thereof through said shift register,C. residue generating means connected to said receiving means and to said encoding means for receiving E1(x) and E2(x) for producing a residue R(x) therefrom by modulo-two summing respective symbols thereof,D. monitoring means connected to said residue generating means for indicating whether errors have occurred in the received word y(x),E. logic processing means responsive to said monitoring means for computing error syndromes Si from said residue R(x) thereby to enable the computation of error location signals and error value signals corresponding to the respective locations and values of errors occurring in data word c(x), andF. correcting means responsive to said error location and error value signals for correcting errors occurring in data word c(x) located in said receiving means.
5 Assignments
0 Petitions
Accused Products
Abstract
An error detecting and correcting system implementing the Reed-Solomon (1023, 1006) code having code words whose symbols are elements in the Galois field GF(210) generated by either the primitive polynomial x10 +x3 +1 or x10 +x7 +1. An original data word is encoded to produce a code word w(x) including a first set of checksum symbols appended thereto. Upon retrieval, the data symbols of the receive code word y(x) are encoded by the same encoder that encodes the original data word to produce a second set of checksum symbols. Both sets of checksum symbols are modulo-two summed to produce a residue R(x) from which error syndromes Si can be computed and thus enable rapid correction of errors in the received code word y(x). The system also monitors the number of non-zero symbols in the residue R(x) in order to avoid unnecessary computation of error syndromes Si and other decoding routines, such as when the received code word y(x) is otherwise uncorrectable or when the error exists only in the received checksum symbols, rather than in the data symbols. The distance between code words being (2T+ 2), the error correction routine is bypassed when the number of non-zero symbols in R(x) is less than or equal to T, which indicates that errors only reside in the checksum symbols. When the number of non-zero symbols equals (T+1), the error is uncorrectable. For determining whether a single error exists so that correction can quickly be made, the system also tests whether Si+1 /Si is constant for all error syndromes Si.
304 Citations
19 Claims
-
1. A circuit for detecting and correcting errors occurring in a Reed-Solomon code word w(x) constituted by a data word d(x) having k data symbols and a checksum word E(x) having n-k data symbols, the symbols of said checksum word E(x) being elements in the Galois Field GF(2m), for any integer m greater than 0, said checksum word being derived by encoding said data word d(x) by a predetermined generator polynomial g(x) having roots α
-
i wherein α
is a primitive element in the Galois Field GF(2m), said circuit comprising;A. receiving means for receiving a word y(x) that was transmitted as the code word w(x), said word y(x) being comprised of a data word c(x) having k symbols and a checksum word E1(x) having n-k symbols, B. Reed-Solomon encoding means for encoding said data word c(x) by said generator polynomial g(x) for producing another checksum word E2(x), said encoding means comprising successively connected shift register stages and feedback means that enable encoding of the data word c(x) by said generator polynomial g(x) during shifting of the symbols thereof through said shift register, C. residue generating means connected to said receiving means and to said encoding means for receiving E1(x) and E2(x) for producing a residue R(x) therefrom by modulo-two summing respective symbols thereof, D. monitoring means connected to said residue generating means for indicating whether errors have occurred in the received word y(x), E. logic processing means responsive to said monitoring means for computing error syndromes Si from said residue R(x) thereby to enable the computation of error location signals and error value signals corresponding to the respective locations and values of errors occurring in data word c(x), and F. correcting means responsive to said error location and error value signals for correcting errors occurring in data word c(x) located in said receiving means. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
i wherein α
-
8. In a digital data processing system including data storage means, a circuit for detecting and correcting errors occurring in digital data that is transferred between the data processing system and said data storage means, which circuit comprises:
-
A. Reed-Solomon encoding means for encoding a data word d(x) having k symbols upon transfer thereof from the data processing system to said data storage means thereby to produce an n-symbol code word w(x) constituted by said k-symbol data word d(x) and a checksum word E(x) having n-k symbols, said encoding means comprising plural successively connected shift register stages and feedback means that enable encoding of the data word d(x) by a generator polynomial g(x) during shifting of the data word through said shift register stages, B. means for storing said code word w(x) in said data storage means, C. retrieval means for retrieving from said data storage means a word y(x) that was previously stored as the code word w(x), said word y(x) being constituted by a data word c(x) having k symbols and a checksum word E1(x) having n-k symbols, said retrieval means including; i. receiving means connected to said data storage means for receiving the data word c(x) and the checksum word E1(x), ii. means connected to said Reed-Solomon encoding means and the data storage means for producing a second checksum word E2(x) having n-k symbols by encoding the data word c(x) with the same Reed-Solomon encoding means that produced the checksum word E1(x), iii. residue generating means that receives the symbols of the checksum words E1(x) and E2(x) for producing a residue R(x) therefrom by modulo-two summing respective symbols thereof, iv. monitoring means that receives said residue R(x) for indicating whether errors have occurred in the word y(x), v. logic processing means responsive to said monitoring means for computing error syndromes Si from said residue R(x) thereby to enable the computation of error location signals and error value signals corresponding to the respective locations and values of errors occurring in data word c(x), and vi. correcting means responsive to said error location and error value signals for correcting errors occurring in said data word c(x) which are located in said receiving means prior to being transferred to said data processing system. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
-
Specification