High Speed Decoding of Reed-Solomon Codes

The present invention relates to Reed-Solomon codes and more particularly to decoding of such codes.

Reed-Solomon codes are the most powerful random error correcting codes now known. Since these codes form a class of Bose-Chaudhuri-Hocquenghem (BCH) codes, general BCH decoding techniques can be applied to them. A typical BCH decoding procedure is to first calculate the error syndromes, then find the error location polynomial, thereafter search for the roots of the error correction polynomial and finally calculate the errors and make the actual correction or corrections. This specification deals with the finding of the error location polynomial. General solutions to this problem are known such as those described in Chapter 9 of Error-Correcting Codes, Second Edition, by Peterson and Weldon, published in 1972 by The MIT Press, Cambridge, Massachusetts. It is also generally known that it is possible to obtain particular solutions for specific applications and it has been suggested in Bossen et al, U.S. Pat. No. 3,893,071 that where a code is capable of correcting one or more errors to first check to see if a single error has occurred and if it has, correct for it. This is done on the basis that most errors are single errors and checking for multiple errors would be time consuming. However with Reed-Solomon codes the number of calculations needed to be made to find the error location polynomial in this manner is significant.

Therefore in accordance with the present invention a decoding scheme is generated for Reed-Solomon code which is based on the idea of checking for single errors first and correcting for them prior to checking for higher value errors. In Reed-Solomon codewords made up of k data and n-k check symbols where each symbol is made up of m binary bits, the error location polynomial .sigma.(x) = x.sup.e + .sigma..sub.1 x.sup.e-1 . . . . +.sigma..sub.e where e equals the number of errors and the coefficients of .sigma.(x) are related to the error syndromes S.sub.i for the codeword by the equation

A decoder incorporating the present invention first tests to see if S.sub.0 = 0. If S.sub.0 .noteq. 0, the assumption is made that a single symbol error has occurred. The decoder quickly verifies this by determining if S.sub.2 + .sigma.S.sub.1 = 0 and S.sub.3 + .sigma.S.sub.2 = 0 when .sigma. = S.sub.1 /S.sub.0. If the error is not a single symbol error the decoder goes on to determine if a double symbol error has occurred and then goes on to determine if there are triple symbol errors if it turns out that a double symbol error has not occurred.

Therefore it is an object of the present invention to provide a simplified decoding scheme for BCH codes.

Another object is to increase the speed of decoding for Reed-Solomon codes.

Further objects are to simplify decoding for Reed-Solomon codes used to correct three symbol errors.

These and other objects, features and advantages of the invention will be apparent from the following detailed description of a preferred embodiment of the invention as illustrated in the accompanying drawings of which:

FIG. 1 is a schematic of a tape containing data.

FIG. 2 is the format in which data is stored on the tape of FIG. 1.

FIG. 3 is a flow diagram illustrating the decoding procedure.

FIG. 4 is a decoder for Reed-Solomon codes capable of correcting three symbol errors.

FIG. 5 is a hardware implementation for the error location polynomial calculator of the decoder in FIG. 4.

As shown in FIG. 1 data is arranged serially and recorded diagonally on tape 10 in the direction shown by the arrows on the dotted lines. Each data stripe across the tape contains a segment of data 14. As shown in FIG. 2 each segment of data 14 is made up of 32 codewords each made up of 65 data bytes or symbols and 6 check bytes or symbols. Each of the bytes or symbols contains eight binary data bits.

The codewords are arranged on the tape in the manner described in Patel, U.S. Pat. No. 3,913,068. That is the first byte of word 1 is recorded. Then the first byte of word 2 and so on until the first byte of all 32 words is recorded. After that the second bytes of all words are recorded. Then the third bytes of all words are recorded. This continues until all 72 bytes in each of the 32 words is recorded. By recording data in this manner, burst errors up to 96 bytes or 768 bits long can be corrected using the check bytes for correcting three bytes in each word.

The check bytes or symbols are generated using a triple-error-correcting Reed-Solomon codes where the 6 check symbols are binary m-tuples. In standard coding terms set forth in Chapter 7 of the previously mentioned Peterson and Weldon reference, the code symbols are elements of GF(2.sup.m), the finite field of 2.sup.m elements where m = 8, the number of bits in the symbols.

The generator polynomial g(x) of the code is

where .alpha. is a primitive element of GF(2.sup.m). The code length is assumed to be less than or equal to 2.sup.m -1.

Let C(x) and R(x) be the transmitted codeword and the received codeword, respectively. The difference between R(x) and C(x) is the error polynomial E(x), i.e.,

where the coefficients of the polynomials are in GF(2.sup.m). The error polynomial contains only the terms corresponding to the locations and the values of the errors. Thus, if Y.sub.j is the value of the error at position x.sup.j, then

where the summation is over all positions of the errors.

The codeword C(x) is always divisible by g(x), i.e., C(.alpha..sup.i) = 0 for 0 .ltoreq.i.ltoreq.5. From (2), we have

Let us define

S.sub.i is called an error syndrome and is obtained by evaluating R(x) at x =.alpha..sup.i. From this definition and (3), we have

Let X.sub.j = .alpha..sup.j. X.sub.j represents the error location at .alpha..sup.j. Then

The error-location polynomial .sigma.(x) is defined by

where e is the number of errors. The coefficients of .sigma.(X) are related to the error syndromes S.sub.i by the following equations:

Our problem here is to solve for .sigma..sub.i based on the set of equations in (7).

Let us write out the equations of (7) explicitly for the cases e = 1, e = 2, and e = 3.

Case e = 1

case e = 2

case e = 3

suppose that the decoder starts with the assumption e = 1. The decoder would have to find a solution .sigma..sub.1 to the five equations in (8). If there is no solution to (8), then the decoder assumes e = 2 and tries to solve for .sigma..sub.1 and .sigma..sub.2 in (9).

If there is no solution again, then the decoder assumes e = 3 and tries to solve for the equations in (10). If there is no solution, the decoder assumes e>3. If this is the case, there are more than 3 errors.

The procedure described above involves the solving of all the equations (8), (9) and (10). In accordance with the present invention, a new decoder is provided to reduce the number of calculations in the decoding procedure. The following properties of the error syndromes are keys to the new procedure.

Property 1 -- If S.sub.i .noteq. 0 for some i, 0 .ltoreq. i .ltoreq. 5, then e .gtoreq. 1.

Proof: If e = 0, then S.sub.i = 0 for 0 .ltoreq. i .ltoreq. 5. Thus, S.sub.i .noteq. 0 implies e .noteq. 0.

Property 2 -- If S.sub.i = 0 and S.sub.j .noteq. 0 for some i and j such that i .noteq. j, and 0 .ltoreq. i, j .ltoreq. 5, then e .gtoreq. 2.

Proof: From Property 1, e .noteq. 0. If e = 1, then S.sub.i = Y.sub.j X.sub.j.sup.i .noteq. 0 for 0 .ltoreq. i .ltoreq. 5. Since some S.sub.i = 0, e .noteq. 1.

Property 3 -- If S.sub.0 .noteq. 0, and S.sub.2 S.sub.0 + S.sub.1.sup.2 = 0, then e = 1, or e .gtoreq. 3.

Proof: We have to show e .noteq. 2. From page 284 of the above-mentioned Peterson and Weldon reference, it is sufficient to show that the determinant ##EQU1## Since .DELTA. = S.sub.1.sup.2 + S.sub.0 S.sub.2 = 0 by assumptions, Property 3 is true.

Property 4 -- If S.sub.0 .noteq. 0, S.sub.2 S.sub.0 + S.sub.1.sup.2 = 0, and S.sub.3 S.sub.0 + S.sub.1 S.sub.2 = 0, then e = 1, or e > 3.

Proof: From Property 3, we only have to show e .noteq. 3. It is sufficient to show that ##EQU2## Now, .DELTA..sub.3 = S.sub.2 (S.sub.2.sup.2 + S.sub.1 S.sub.3) + S.sub.3 (S.sub.1 S.sub.2 + S.sub.0 S.sub.3) + S.sub.4 (S.sub.1.sup.2 + S.sub.0 S.sub.2) = S.sub.2 (S.sub.2.sup.2 + S.sub.1 S.sub.3) by assumptions. Also, from the assumptions S.sub.1 S.sub.2 + S.sub.0 S.sub.3 = 0 and S.sub.1.sup.2 + S.sub.2 S.sub.0 = 0, we have either S.sub.1 = S.sub.2 = S.sub.3 = 0, or S.sub.2.sup.2 + S.sub.1 S.sub.3 = 0. Thus, .DELTA..sub.3 = 0.

Property 5 -- Let .DELTA. = S.sub.1.sup.2 + S.sub.0 S.sub.2 .noteq. 0, .sigma..sub.1 = (S.sub.1 S.sub.2 + S.sub.0 S.sub.3)/.DELTA., .sigma..sub.2 = (S.sub.1 S.sub.3 + S.sub.2.sup.2)/.DELTA.. If D = S.sub.4 + .sigma..sub.1 S.sub.3 + .sigma..sub.2 S.sub.2 = 0, then e = 2, or e > 3.

Proof: Since .DELTA. .noteq. 0, e .noteq. 0 and e .noteq. 1 [Peterson and Weldon, p. 284]. It is sufficient to show e .noteq. 3. Since ##EQU3## Property 6 -- If S.sub.0 = S.sub.1 = 0, S.sub.2 .noteq. 0, then e .gtoreq. 3.

Proof: Property 6 follows from Property 3 and Property 2.

Property 7 -- If S.sub.0 = S.sub.1 = S.sub.2 = 0, and S.sub.i = 0 for some i, 3 .ltoreq. i .ltoreq. 5, then e .gtoreq. 3.

Proof: From Property 6, e .ltoreq. 3. Since S.sub.0 = S.sub.1 = S.sub.2 = 0, the determinant .DELTA..sub.3 in the proof of Property 5 is zero. Thus, e .noteq. 3.

Based on the properties presented at the end of the last section, a procedure shown in FIG. 3 can be used for the calculation of the coefficients of the error-location polynomial.

(0) If S.sub.0 .noteq. 0, e .gtoreq. 1 is assumed. Next step is (1). If S.sub.0 = 0, and S.sub.1 .noteq. 0, e .gtoreq. 2 is assumed. Next step is (2). If S.sub.0 = S.sub.1 = 0, and S.sub.2 .noteq. 0, e = 3 is assumed. Next step is (5). If S.sub.0 = S.sub.1 = S.sub.2 = 0, and S.sub.i .noteq. 0 for some i, 3 .ltoreq. i .ltoreq. 5, e .gtoreq. 3 is detected. If S.sub.i = 0 for 0 .ltoreq. i .ltoreq. 5, no error is assumed.

(1) S.sub.0 .noteq. 0. Set .sigma. = S.sub.1 /S.sub.0. If S.sub.2 + .sigma.S.sub.1 .noteq. 0, e .gtoreq. 2 is assumed. Next step is (2). If S.sub.2 + .sigma.S.sub.1 = 0, and S.sub.3 + .sigma.S.sub.2 .noteq. 0, e .gtoreq. 3 is assumed. Next step is (4). If S.sub.2 + .sigma.S.sub.1 = S.sub.3 + .sigma.S.sub.2 = 0, e = 1 is assumed. Let X.sub.i = .sigma., Y.sub.i = S.sub.0. (2)

.DELTA. = s.sub.1.sup.2 + s.sub.0 s.sub.2 .noteq. 0. set .sigma..sub.1 = (S.sub.1 S.sub.2 + S.sub.0 S.sub.3)/.DELTA., .sigma..sub.2 =

(s.sub.1 s.sub.3 + s.sub.2.sup.2)/.DELTA., d = s.sub.4 + .sigma..sub.1 s.sub.3 + .sigma..sub.2 s.sub.2.

if D = 0, e = 2 is assumed.

If D .noteq. 0, e = 3 is assumed. Next step is (3).

(3) Set

.sigma..sub.1.sup.1 = (S.sub.3 .sigma..sub.2 + S.sub.4 .sigma..sub.1 + S.sub.5)/D

.sigma..sub.2.sup.1 = 1/.DELTA. (s.sub.1 s.sub.3 + s.sub.0 s.sub.4) + .sigma..sub.1.sup.1 .sigma..sub.1

.sigma..sub.3.sup.1 = 1/.DELTA. (s.sub.1 s.sub.4 + s.sub.2 s.sub.3) +.sigma..sub.1.sup.1 .sigma..sub.2

(4) s.sub.0 s.sub.2 + s.sub.1.sup.2 = 0. set D = S.sub.0 S.sub.3 + S.sub.1 S.sub.2, and

.sigma..sub.1 = 1/D (S.sub.1 S.sub.3 + S.sub.0 S.sub.4)

.sigma..sub.2 = 1/d [s.sub.2 (s.sub.3 + .sigma..sub.1 s.sub.2) + (s.sub.5 + .sigma..sub.1 s.sub.4) s.sub.0 ]

.sigma..sub.3 = 1/s.sub.0 (s.sub.3 + .sigma..sub.1 s.sub.2 + .sigma..sub.2 s.sub.1)

(5) s.sub.0 = s.sub.1 = 0, s.sub.2 .noteq. 0. set

.sigma..sub.1 = S.sub.3 /S.sub.2

.sigma..sub.2 = 1/s.sub.2 (s.sub.4 + .sigma..sub.1 s.sub.3)

.sigma..sub.3 = 1/s.sub.2 (s.sub.5 + .sigma..sub.1 s.sub.4 + .sigma..sub.2 s.sub.3)

the procedure is designed for the correction of 3 or fewer number of errors. The validity of the procedure follows from Property 1 to Property 7.

Let .alpha. be a root of the polynomial X.sup.8 + X.sup.6 + X.sup.5 + X.sup.4 + 1 in GF(2.sup.8). The generator of the three-symbol (or three-byte) error correcting code is

Consider the following three cases of errors:

Case I. e = 1, x = .alpha..sup.30, y = .alpha..sup.19

S.sub.0 = .alpha..sup.19

s.sub.1 = .alpha..sup.49

s.sub.2 = .alpha..sup.79

s.sub.3 = .alpha..sup.109

s.sub.4 = .alpha..sup.139

s.sub.5 = .alpha..sup.169

case II. e = 2, x.sub.1 = .alpha..sup.10, y.sub.1 = .alpha..sup.54 x.sub.2 = .alpha..sup.48, y.sub.1 = .alpha.

S.sub.0 = .alpha..sup.162

s.sub.1 = .alpha..sup.31

s.sub.2 = .alpha..sup.156

s.sub.3 = .alpha..sup.214

s.sub.4 = .alpha..sup.180

s.sub.5 = .alpha..sup.195

case III. e = 3, x.sub.1 = 1, y.sub.1 = .alpha..sup.41 x.sub.2 = .alpha..sup.21, y.sub.2 = .alpha. x.sub.3 = .alpha..sup.62, y.sub.3 = .alpha..sup.128

S.sub.0 = .alpha..sup.172

s.sub.1 = .alpha..sup.235

s.sub.2 = .alpha..sup.152

s.sub.3 = .alpha..sup.53

s.sub.4 = .alpha..sup.25

s.sub.5 = .alpha..sup.54

in each case let us go through the procedure for the calculation of the coefficients of the error-location polynomial.

Case I.

(1) set .sigma. = S.sub.1 /S.sub.0 = .alpha..sup.49 /.alpha..sup.19 = .alpha..sup.30

(2) test for S.sub.2 + .sigma.S.sub.1 = 0 S.sub.2 + .sigma.S.sub.1 = .alpha..sup.79 + .alpha..sup.30 + 49 = 0

(3) test for S.sub.3 + .sigma.S.sub.2 = 0

s.sub.3 + .sigma.s.sub.2 = .alpha..sup.109 + .alpha..sup.30 + 79 = 0

x = .sigma. = .alpha..sup.30

y = S.sub.0 = .alpha..sup.19

Case II.

(1) set .sigma. = S.sub.1 /S.sub.0 = .alpha..sup.-- 162 = .alpha..sup.124

set .DELTA..sub.1 = S.sub.2 + .sigma.S.sub.1 = .alpha..sup.156 + .alpha..sup.124 + 31 = .alpha..sup.131 .DELTA..sub.1 .noteq. 0

(3) set .DELTA. = S.sub.0 .DELTA..sub.1 = .alpha..sup.38

.sigma..sub.1 = (s.sub.1 1s.sub.2 + s.sub.o S.sub.3)/.DELTA. = (.alpha..sup.187 + .alpha..sup.121)/.alpha..sup.38 = .alpha..sup.119

.sigma..sub.2 =0 (s.sub.1 s.sub.3 + s.sub.2.sup.2)/.DELTA. = (.alpha..sup.245 + .sigma..sup.57)/.alpha..sup.38 = .alpha..sup.58

(4) test for D = S.sub.4 + .sigma..sub.1 S.sub.3 + .sigma..sub.2 S.sub.2 =

D = .alpha..sup.180 + .alpha..sup.119 + 214 + .alpha..sup.58 + 156 = 0 thus .sigma.(x) = x.sup.2 + .alpha..sup.119 x + .alpha..sup.58

Case III.

(1) set .sigma. = S.sub.1 /S.sub.0 = .alpha..sup.63

(2) test .DELTA..sub.1 = S.sub.2 + .sigma.S.sub.1

.DELTA..sub.1 = .alpha..sup.152 + .alpha..sup.63 + 235 = .alpha..sup.81 .noteq. 0

(3) set .DELTA. = S.sub.0 .DELTA..sub.1 = .alpha..sup.253

.sigma..sub.1 = (s.sub.1 s.sub.2 + s.sub.o S.sub.3)/.DELTA. = .alpha..sup.69

.sigma..sub.2 = (s.sub.1 s.sub.3 + s.sub.2.sup.2)/.DELTA. = .alpha..sup.161

(4) test D = S.sub.4 + .sigma..sub.1 S.sub.3 + .sigma..sub.2 S.sub.2

d = .alpha..sup.25 + .alpha..sup.122 + .alpha..sup.58 = .alpha..sup.203 .noteq. 0

(5) .sigma..sub.1.sup.1 = (s.sub.3 .sigma..sub.2 + s.sub.4 .sigma..sub.1 + s.sub.5)/d = .alpha..sup.79

.sigma..sub.2.sup.1 = 1/.DELTA. (s.sub.1 s.sub.3 + s.sub.0 s.sub.4) + .sigma..sub.1.sup.1 .sigma..sub.1 = .alpha..sup.187

.sigma..sub.3.sup.1 = 1/.DELTA. (s.sub.1 s.sub.4 + s.sub.2 s.sub.3) + .sigma..sub.1.sup.1 .sigma..sub.2 = .alpha..sup.83

thus .sigma.(x) = x.sup.3 + .alpha..sup.79 x.sup.2 + .alpha..sup.187 x + .alpha..sup.83.

An overall diagram for the decoding of Reed-Solomon codes for three-symbol error correction is shown in FIG. 4. The data read out from storage media 16 such as magnetic tape are stored in data buffer 18 while the data are being decoded. In the first step of decoding, the data are fed into syndrome generator 20 to generate syndromes S.sub.0, S.sub.1, S.sub.2, S.sub.3, S.sub.4, S.sub.5. The syndromes are stored in syndrome buffer 22. The OR gates 24 of the syndromes determine if errors exist. If the errors exist, the decoder starts the error correction procedure. The error-location polynomial calculator 26 calculates the error-location polynomial using the procedure shown in FIG. 3. The error-location calculator 28 finds the roots of the error-location polynomial using known prior art schemes such as the one described in the book entitled, Algebraic Coding Theory written by E. R. Berlekamp and published in 1968 by McGraw-Hill or described in Flagg U.S. application serial number 613,592, filed Sept. 15, 1975 and assigned to the same assignee as the present invention. Finally the error values calculator 30 determines the value of error at each error location. The error locations and the error values are used to modify the data from the output of the data buffer.

The implementation of error-location polynomial calculator 26 of the decoder is shown in FIG. 5. Syndrome buffer 32 is a read/write memory that stores the syndromes S.sub.0, S.sub.1, S.sub.2, S.sub.3, S.sub.4, S.sub.5. Each syndrome is an element of GF(2.sup.m) and is stored in m-bit binary form. For example, .alpha..sup.17 in GF(2.sup.8) is stored as 11101001. Work buffer 34 is a read/write buffer which stores intermediate as well as final results of the algebraic operations in the calculation of the coefficients of the error-location polynomial. Partial results that will be used in succeeding operations are stored in this buffer. The sequencer 36 directs the sequence of algebraic operations. It provides addresses to the syndrome buffer and work buffer. It turns on the read/write lines to these buffers and gates the proper registers for algebraic operations. It examines an output of algebraic operation and branches to next appropriate operation. An example of a sequencer could be a microprocessor programmed to perform the sequence of events set forth in FIG. 3.

The log buffer 38 and anti-log buffer 40 are read only memory buffers that stores tables for the logorithm and antilogorithm of the field elements of GF(2.sup.m). An address of log buffer is the binary representation of a field element, say .alpha..sup.i. The entry in the address is the logorithm of .alpha..sup.i with .alpha. as a base; i.e., i. On the other hand, the entry in the address i of anti-log buffer is the binary representation of .alpha..sup.i. The log and anti-log tables for the field elements described in this specification are:

The algebraic operations required in the described decoding procedure are addition, multiplication, division, and test for zero. The following are examples of how each of the operations can be performed by the apparatus of FIG. 5.

To add .alpha..sup.i with .alpha..sup.j, these two field elements are fed to A and B registers 41 and 42. The component-wise Exclusive OR of the contents of A and B registers 40 and 42 in Exclusive OR circuit 44 is the sum of the two field elements. For example, .alpha..sup.13 + .alpha..sup.17 = 00110110 + 11101001 = 11011111. The output of the Exclusive OR circuit 44 is placed in register 46 and from there fed to the work buffer 34.

To test if .alpha..sup.i is a zero element, .alpha..sup.i is loaded to H register 47. A component-wise logic OR of the contents of H register 47 are performed by OR circuit 48 and the result placed into M register 50. The contents of the M register 50 is zero if and only if .alpha..sup.i is a zero field element.

Suppose we want to multiply .alpha..sup.i by .alpha..sup.j. These two field elements are first tested for zero. If either one of the elements is zero, the result of the multiplication is zero. If both elements are nonzero, they are sequentially fed into the memory address register (MAR) 52 of log buffer 38. The outputs i and j from the log buffer are stored in D and E registers 54 and 56. Then 1's complement addition of the contents of the D and E registers is performed to yield i + j = t mod (2.sup.m -1). The output of anti-log buffer with t as the input is .alpha..sup.t. For example, consider the multiplication of .alpha..sup.10 and .alpha..sup.9. The contents in register D and E are 00001010 and 00001001. The 1's complement addition of these two numbers is 00010011. The output from anti-log buffer is then .alpha..sup.4 = 01111101.

The division of .alpha..sup.i by .alpha..sup.j is done essentially in the same way as the multiplication of .alpha..sup.i and .alpha..sup.j. The only difference is that subtraction instead of addition of register D by register E is performed. This is done by loading the logorithm of .alpha..sup.j into E and loading the complement of E into register F. Then, 1's complement addition of D and F is performed. For example, to divide .alpha..sup.10 by .alpha..sup.9, register D is loaded with 00001010 and register E is loaded with 00001001. Thus register F is 11110110. The 1's complement addition of D and F is 00000001 and register G is .alpha. = 01000000.

From the description of the preferred embodiment of the invention one skilled in the art will recognize a variety of applications for the invention and appropriate modifications within the scope of the claims.