Architecture and control of Reed-Solomon list decoding

• US 8,635,513 B1
• Filed: 02/01/2012
• Issued: 01/21/2014
• Est. Priority Date: 10/27/2004
• Status: Expired due to Fees

• Current Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Au, Siu-Hung Fred, Burd, Gregory, Wu, Zining, Xu, Jun, Kikuchi, Ichiro, Yoon, Tony
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US13/363,898
• Time in Patent Office: 720 Days
• Field of Search: 714/780, 714/784
• US Class Current: 714/784
• CPC Class Codes: H03M 13/098 using single parity bit
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• 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/1545 Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial
• CPC Class Codes: H03M 13/1555 Pipelined decoder implementations
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/3707 Adaptive decoding and hybrid decoding, e.g. decoding methods or techniques providing more than one decoding algorithm for one code
• CPC Class Codes: H03M 13/4146 soft-output Viterbi decoding according to Battail and Hagenauer in which the soft-output is determined using path metric differences along the maximum-likelihood path, i.e. "SOVA" decoding
• CPC Class Codes: H03M 13/45 Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence
• CPC Class Codes: H03M 13/451 using a set of candidate code words, e.g. ordered statistics decoding [OSD]
• CPC Class Codes: H03M 13/458 by updating bit probabilities or hard decisions in an iterative fashion for convergence to a final decoding result
• CPC Class Codes: H03M 13/63 Joint error correction and other techniques H03M13/31 and H03M13/33 take precedence
• CPC Class Codes: H03M 13/6511 Support of multiple decoding rules, e.g. combined MAP and Viterbi decoding

Abstract

Systems and methods are provided for implementing list decoding in a Reed-Solomon (RS) error-correction system. A detector can provide a decision-codeword from a channel and can also provide soft-information for the decision-codeword. The soft-information can be organized into an order of combinations of error events for list decoding. An RS decoder can employ a list decoder that uses a pipelined list decoder architecture. The list decoder can include one or more syndrome modification circuits that can compute syndromes in parallel. A long division circuit can include multiple units that operate to compute multiple quotient polynomial coefficients in parallel. The list decoder can employ iterative decoding and a validity test to generate error indicators. The iterative decoding and validity test can use the lower syndromes.

Claims

1. A method for decoding an n-symbol decision-codeword to produce a k-symbol dataword using a Reed-Solomon decoder, the Reed Solomon decoder comprising a list decoder having a pipeline architecture comprising a plurality of pipeline stages, and where a number of symbol errors in the decision-codeword is greater than t=(n−

k)/2, the method comprising;

receiving soft-information corresponding to a modified decision-codeword; and

producing an error indicator that corresponds to the modified decision-codeword using a pipeline stage of the list decoder.

2. The method of claim 1, further comprising:

producing a decision-codeword associated with the modified decision-codeword, the decision-codeword containing a potentially erroneous symbol,

wherein the soft-information corresponding to the modified decision-codeword comprises at least one of;

a position of the potentially erroneous symbol in the decision-codeword,

a next-most-likely value for the potentially erroneous symbol, and

an error value that corresponds to a difference between a value of the potentially erroneous symbol and the next-most-likely value.

3. The method of claim 1, further comprising producing the error indicator using iterative decoding.

4. The method of claim 1, wherein the pipeline stage is a first pipeline stage further comprising predicting a validity of the error indicator using a second pipeline stage of the list decoder.

5. The method of claim 1, wherein the pipeline stage is a first pipeline stage further comprising producing modified syndromes based on the soft-information using a second pipeline stage of the list decoder.

6. The method of claim 5, further comprising performing long division operations using the second stage.

7. The method of claim 5, wherein the second stage is earlier in the pipeline architecture than the first stage.

8. The method of claim 5, further comprising:

utilizing a computing resource using the first stage during a first period of time; and

utilizing the computing resource using the second stage during a second period of time, wherein the first period of time is different from the second period of time.

9. The method of claim 1, further comprising operating the pipelined architecture based on a computing interval that has a duration of more than one interval of a clock signal.

10. The method of claim 1, further comprising storing error indicators in a memory, wherein the memory is in communication with the pipelined architecture.

11. The method claim 10, further comprising utilizing at least one delay memory connected between the memory and the pipelined architecture.

12. A method for decoding an n-symbol decision-codeword to produce a k-symbol dataword using a Reed-Solomon decoder comprising a list decoder, where a number of symbol errors in the decision-codeword is greater than t=(n−

k)/2, comprising;

listing most-likely error events;

producing error indicators; and

producing order information indicating an order in which combinations of the most-likely error events are processed by the list decoder.

13. The method of claim 12, wherein the Reed Solomon decoder comprises a soft-information controller, further comprising directing the list decoder to process combinations of the most-likely error events in accordance with the order information using the soft-information controller.

14. The method of claim 12, further comprising:

producing an indicator associated with a combination in the combinations of the error events; and

storing an error indicator corresponding to the combination in a memory.

15. The method 14, wherein the combination is a first combination, and wherein the error indicator is a first error indicator, and further comprising:

producing a second indicator associated with a second combination in the combinations of the error events, wherein the second indicator indicates that an error indicator corresponding to the second combination is not to be stored in the memory.