Reed-solomon decoder

• US 9,166,623 B1
• Filed: 03/14/2013
• Issued: 10/20/2015
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Microsemi Solutions (U.S.), Inc. (Microchip Technology Incorporated)
• Original Assignee: PMC Sierra US Inc (Microchip Technology Incorporated)
• Inventors: Bates, Stephen, Graumann, Peter, Northcott, Phil
• Primary Examiner(s): MCMAHON, DANIEL F
• Application Number:
  US13/803,919
• Time in Patent Office: 950 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/153 using the Berlekamp-Massey algorithm
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/1555 Pipelined decoder implementations
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/45 Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence

Abstract

A system and method of decoding a Reed-Solomon code using a Reed-Solomon decoder comprising an erasure location selector, multiple syndrome formers and multiple Berlekamp-Massey decoders that share a single error correction unit, and means for selecting a Berlekamp-Massey decoder output as the input to the error correction unit. The method improves the bit error rate performance of the Reed-Solomon decoder compared to known hard-decision and soft-decision Reed-Solomon decoders. The Reed-Solomon decoder also provides hardware area and power savings over more complex Reed-Solomon decoders.

Claims

1. A method of decoding a Reed-Solomon code comprising:

generating a plurality of syndromes based on received input symbols and based on a plurality of estimated erasure locations at a plurality of syndrome formers;

decoding the plurality of syndromes at a plurality of Berlekamp-Massey (BM) decoders;

selecting an output of one of the plurality of BM decoders to generate a selected decoder output;

correcting the received input symbols based on the selected decoder output, at a single error correction unit; and

ordering the plurality of BM decoders by an increasing number of processed erasures,

wherein the selected decoder output corresponds to the output of a lowest order BM decoder, from the ordered plurality of BM decoders, that generates a correctable codeword.

2. The method of claim 1, further comprising generating the estimated erasure locations based on received symbol metrics at an erasure location selector.

3. The method of claim 1, further comprising generating the plurality of estimated erasure locations based on received symbol metrics at an erasure location selector.

4. The method of claim 2, wherein the symbol metrics are a measure of Euclidean distance between a symbol and its nearest correct symbol.

5. The method of claim 1, wherein correcting comprises correcting according to a Forney algorithm.

6. A Reed-Solomon decoder, comprising:

a plurality of syndrome formers configured to produce a plurality of syndromes based on received input symbols and based on a plurality of estimated erasure locations;

a plurality of Berlekamp-Massey (BM) decoders configured to receive the plurality of syndromes, the plurality of BM decoders being ordered by an increasing number of processed erasures, each of the plurality of syndrome formers being uniquely associated with one of the plurality of BM decoders;

a single error correction unit associated with the plurality of BM decoders; and

a decoder output selector configured to select either an output of the first BM decoder or an output of the second BM decoder and to provide a selected decoder output to the single error correction unit for correcting the received input symbols,

wherein the decoder output selector comprises;

logic for identifying the first BM decoder, the second BM decoder, or one the plurality of additional BM decoders, the logic being configured to select a lowest order BM decoder wherein the output of the lowest order BM decoder generates a correctable codeword; and

a multiplexer for providing the output of the first BM decoder, the second BM decoder, or one the plurality of additional BM decoders, as the selected decoder output to the single error correction unit.

7. The decoder of claim 6, further comprising an erasure location selector associated with the second syndrome former and configured to provide the estimated erasure locations based on received symbol metrics.

8. The decoder of claim 6, wherein the decoder output selector comprises:

logic for identifying either the first BM decoder or the second BM decoder; and

a multiplexer for providing either the output of the first BM decoder or the output of the second BM decoder as the selected decoder output to the single error correction unit.

9. The decoder of claim 6, further comprising an erasure location selector associated with the plurality of additional syndrome formers and configured to provide a plurality of estimated erasure locations based on received symbol metrics.

10. The decoder of claim 7, wherein the symbol metrics received at the erasure location selector are a measure of Euclidean distance between a symbol and its nearest correct symbol.

11. The decoder of claim 6, wherein the single error correction unit comprises logic for correcting the received input symbols according to a Forney algorithm.