Reed-Solomon decoder

Claim 2

A decoder for decoding Reed-Solomon encoded data comprising input means for receiving said encoded data in a stream of code blocks, memory means coupled to said input means for storing said received encoded data, processing means coupled to said memory means for performing decoding functions on said stored encoded data and returning processed data to said memory, output means coupled to said memory means for transmitting decoded data from said decoder, said memory means including three identical memories, one for storing encoded data to be decoded, one for storing data being decoded, and one for storing decoded data being transmitted out of the decoder, each memory having its own addressing means and data output terminals, means for determining when each of said input means, processing means and output means have completed their respective functions on a different code block, and switching means responsive to said determining means for sequentially swapping memories between said input means, processing means and output means, whereby overall pipelining of code blocks is provided through said decoder without physically transferring code blocks through more than one memory.

Claim 3

A decoder as defined in claim 1 wherein said processing means is comprised of a plurality of sections, each for carrying out an algorithm step, and each pipelined such that data is pipelined through the decoding means for decoding while overall pipelining is affected by memory swapping.

Claim 4

A decoder as defined in claim 2 wherein said data is encoded in a Reed-Solomon code consisting of codewords made up of K data and N-K check symbols, where K is an arbitrary number and K is a number smaller than N, and each symbol is made up of J binary bits encoded with a generator polynomial g(X) and a field generating polynomial M(X) which defines the representation of the Galois field, and said processing means comprises the following sequentially pipelined processing means: pipelined means for generating a syndrome polynomial S(X) in response to each received codeword R(X), wherein said syndrome consists of m terms and has the form S(X)=S.sub.m X.sup.m-1 +S.sub.m-1 X.sup.m-2 . . . +S.sub.2 X+S.sub.1 and said received code word is defined as R(X)=R.sub.o +R.sub.1 X+R.sub.2 X.sup.2 . . . R.sub.n-1 X.sup.N-1 +R.sub.n X.sup.N pipelined means for computing Euclid's algorithm for determining an error locator polynomial σ(X)=σ j X j +σ j-1 X j-1 . . . +σ 1 X+σ o , where 1≦j≦m/2 and an error magnitude evaluator polymomial ω(X)=ω i X i +ω i-1 X i-1 . . . ω i X+ω o , where i=j-1, pipelined means for computing the roots β of the error locator polynomial ω(X) to determine the location of errors, means for computing the error magnitudes Eβ from the derivative σ'(X) of the error locator polynomial, the error magnitude evaluator polynomial ω(X) and the root β of the error locator polynomial, comprising means for computing σ'(β) and ω(β), and means for computing Eβ=σ(β)/ω(β), and pipelined means for correction of error by adding the error magnitudes at the proper locations found by taking the negative logrithm of the error locator root β.

Claim 5

A decoder as defined in claim 3 wherein each code block received includes a keyword which specifies for the decoder the generator polynomial g(X) to be used, whereby said decoder may decode a number of different Reed-Solomon codes generated with a different generator polynomial.

Claim 6

A decoder as defined in claim 4 wherein each keyword of a code block received specifies the depth of interleaving of symbols, and including means for deinterleaving a code block and arranging it into codewords for processing.

Claim 9

wherein each code block received includes a keyword which specifies for the decoder the generator polynomial g(X) to be used, whereby said decoder may decode a number of different Reed-Solomon codes generated with a different generator polynomial.

Claim 10

wherein each code block received includes a keyword which specifies for the decoder the generator polynomial g(X) to be used, whereby said decoder may decode a number of different Reed-Solomon codes generated with a different generator polynomial.

Claim 11

A method of decoding Reed-Solomon encoded data as defined in claim 6 wherein each keyword of a code block received specifies the depth of interleaving of symbols, and including means for deinterleaving a code block and arranging it into codewords for processing.

Claim 12

A method of decoding Reed-Solomon encoded data as defined in claim 7 wherein codewords are pipelined through the sequential algorithms, thereby eliminating delays by allowing processing to begin on a codeword before decoding is completed on a first codeword.

Claim 13

A method of decoding Reed-Solomon encoded data as defined in claim 8 wherein the number of errors in a codeword is totaled for transmsittal with the decoded data.