Soft decision Reed-Solomon decoder
AssigneeCyclotomics, Inc.
InventorElwyn R. Berlekamp
Life of this patent
Estimating the term…
Abstract
In a Reed-Solomon Decoder, each byte of a received codeword is matched to the closest resembling one of a set of allowed symbols and assigned a certain reliability, reflecting the degree of resemblance. The symbols thus matched are arranged in descending order to reliability to form a virtual codeword, the first K symbols being virtual message bytes and the remaining r symbols being virtual check bytes. The virtual codeword is then decoded using an algorithm which produces a series of iterative approximations to the transmitted codeword. The approximation most closely resembling the received codeword is selected as the corrected codeword.
Claims14
A Reed-Solomon soft decision decoder, comprising:
- remainder generator means for generating a set of remainder coefficients from a received codeword;
- remainder processor means for processing said remainder coefficients by executing one or more iterations of a recursive algorithm, whereby to generate one set of error descriptive coefficients upon each execution of one of said iterations;
- and
- means for computing a candidate corrected codeword from each set of said error descriptive coefficients whereby to produce a plurality of candidate codewords
- wherein said remainder generator means comprises:
- means for receiving an analog N-byte m-bit-per-byte codeword in the form of a plurality of analog voltages representing a corresponding plurality of bits comprised within each byte of said analog codeword, said analog voltages not necessarily being restricted to a binary set of voltages;
- means for determining the resemblance of each of the N-bytes of said analog codeword to each of a set of binary m-bit bytes, and, for each of said N-bytes of said analog codeword, selecting said one of the set of binary bytes having the greatest resemblance thereto;
- means for forming a virtual codeword from the set of said binary bytes selected by said determining means, by rearranging said selected binary bytes in descending order of their resemblances;
- and
- means for computing said set of remainder coefficients from said virtual codeword.
In a Reed-Solomon decoder which generates plural sets of error correction coefficients during corresponding plural iterations of a recursive algorithm so as to process in each iteration a successive one of a set of remainder coefficients and the set of error descriptive coefficients generated during the previous iteration, a remainder generator which generates said set of remainder coefficients, said remainder generator comprising:
- means for receiving a plurality of analog voltages representing a corresponding plurality of individual bits of a received N-byte m-bit-per-byte codeword;
- means for generating or storing all binary m-bit bytes;
- means for computing the inner product between each of said bytes of said received codeword in each of said binary bytes, and for selecting therefrom N correct bytes having the greatest inner products with corresponding ones of said bytes of said received codeword;
- means for rearranging said bytes selected by said computing means in descending order of their inner products to form a virtual codeword;
- virtual encoder means for computing a set of r virtual check bytes from the first k bytes of said virtual codeword having the k highest inner products;
- and
- means for subtracting said virtual check bytes from the last r bytes of said virtual codeword having the r smallest inner products, whereby the difference computed by the subtraction comprises said remainder coefficients.
A method for performing soft decision decoding, comprising:
- choosing N binary m-bit bytes from a set of m-bit binary bytes, each of the N binary bytes being that one of said set of all m-bit binary bytes which has the greatest resemblance to a corresponding byte in a received codeword;
- reordering said N binary bytes in descending order of their individual resemblances to the corresponding received codeword bytes, so as to form a virtual codeword;
- computing a set of virtual remainder coefficients from said virtual codeword;
- executing at least one iteration of a recursive algorithm so as to process a successive one of said virtual remainder coefficients and any error descriptive coefficients computed during any previous iteration thereof, whereby to generate a corresponding new set of error descriptive coefficients, wherein a plurality of such iterations of said recursive algorithm generates a corresponding plurality of sets of said error descriptive coefficients;
- computing a candidate corrected codeword for each of said set of error descriptive coefficients;
- and
- choosing that candidate codeword most closely resembling said received codeword.
Dependencies are inferred from the claim text.