# US 8,788,916 B2 · Architecture and control of reed-solomon error-correction decoding

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,788,916 B2
- Document ID: US8788916B2
- Status: Granted
- Kind: B2
- Application number: 13/554,830
- Filed: 2012-07-20
- Published: 2012-11-08
- Granted: 2014-07-22
- Earliest claimed: 2004-10-27
- Assignees: Marvell International Ltd.
- Applicants: Siu-Hung Fred Au; Gregory Burd; Zining Wu; Jun Xu; Ichiro Kikuchi; Tony Yoon
- Inventors: Siu-Hung Fred Au; Gregory Burd; Zining Wu; Jun Xu; Ichiro Kikuchi; Tony Yoon
- Web page: https://patentgrep.com/patent/US8788916B2

## CPC

- H03M 13/458: {by updating bit probabilities or hard decisions in an iterative fashion for convergence to a final decoding result}
- H03M 13/1515: {Reed-Solomon codes}
- H03M 13/1555: {Pipelined decoder implementations}
- H03M 13/2906: {using block codes (H03M13/2957 takes precedence)}
- H03M 13/3707: {Adaptive decoding and hybrid decoding, e.g. decoding methods or techniques providing more than one decoding algorithm for one code}
- H03M 13/45: Soft decoding, i.e. using symbol reliability information (H03M13/41 takes precedence)
- H03M 13/451: {using a set of candidate code words, e.g. ordered statistics decoding [OSD]}
- H03M 13/63: {Joint error correction and other techniques (H03M13/31 and H03M13/33 take precedence)}
- H03M 13/6511: {Support of multiple decoding rules, e.g. combined MAP and Viterbi decoding}
- H03M 13/098: {using single parity bit}
- H03M 13/1102: {Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes}
- H03M 13/153: {using the Berlekamp-Massey algorithm}
- 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}
- 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}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

Systems and methods are provided for implementing various aspects of 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. If the decision-codeword corresponds to an inner code and an RS code is the outer code, a soft-information map can process the soft-information for the decision-codeword to produce soft-information for a RS decision-codeword. A RS decoder can employ the Berlekamp-Massey algorithm (BMA), list decoding, and a Chien search, and can include a pipelined architecture. A threshold-based control circuit can be used to predict whether list decoding will be needed and can suspend the list decoding operation if it predicts that list decoding is not needed.

## Claims

### Claim 1

A method for decoding a dataword based on a decision-codeword using a Reed-Solomon decoder, comprising:
receiving a decision-codeword;
producing a modified decision-codeword based on the received decision-codeword;
producing a first error indicator based on the received decision-codeword;
producing a second error indicator based on the modified decision-codeword; and
using circuitry, determining a validity of at least one of the first error indicator and the second error indicator, wherein the validity indicates whether errors in the received decision-codeword are capable of being corrected.

### Claim 2 (depends on 1)

The method of claim 1, further comprising
producing a soft-information component based on the modified decision-codeword.

### Claim 3 (depends on 2)

The method of claim 2, wherein producing the soft-information component further comprises:
determining a most-likely error event;
determining an incidence vector; and
determining a next most-likely value that corresponds to the most-likely error event.

### Claim 4 (depends on 1)

The method of claim 1, wherein:
producing the first error indicator comprises running a Berlekamp-Massey algorithm in a first stage of the circuitry, the method further comprising producing a second error indicator based on a modified decision-codeword by running a list decoding algorithm in a second stage of the circuitry.

### Claim 5 (depends on 4)

The method of claim 4, wherein the list decoding algorithm uses iterative decoding.

### Claim 6 (depends on 1)

The method of claim 1, wherein:
the first error indicator comprises a plurality of error locator polynomials; and
determining the validity of the first error indicator comprises performing a Chien search on the plurality of error locator polynomials.

### Claim 7 (depends on 6)

The method of claim 6, wherein performing the Chien search comprises computing error values in the received decision-codeword using a Forney algorithm in response to the Chien search identifying a valid error locator polynomial.

### Claim 8 (depends on 4)

The method of claim 4, wherein the first error indicator is produced using a first stage of the circuitry, the second error indicator is produced using a second stage of the circuitry, and a validity of at least one of the first error indicator and the second error indicator is determined using a third stage of the circuitry, further comprising receiving a clock signal that is indicative of a computing interval for the first stage, the second stage, and the third stage.

### Claim 9 (depends on 4)

The method of claim 4, wherein the first error indicator is produced using a first stage of the circuitry, the second error indicator is produced using a second stage of the circuitry, and a validity of at least one of the first error indicator and the second error indicator is determined using a third stage of the circuitry, and wherein the second stage is used earlier than the third stage.

### Claim 10 (depends on 4)

The method of claim 4, wherein the first error indicator is produced using a first stage of the circuitry, the second error indicator is produced using a second stage of the circuitry, and a validity of at least one of the first error indicator and the second error indicator is determined using a third stage of the circuitry, and wherein the third stage is used later than the first stage and is used earlier than the second stage.

### Claim 11 (depends on 10)

The method of claim 10, further comprising suspending the use of the second stage if the third stage determines that the first error indicator is valid.

### Claim 12 (depends on 4)

The method of claim 4, wherein the first error indicator is produced using a first stage of the circuitry, the second error indicator is produced using a second stage of the circuitry, and a validity of at least one of the first error indicator and the second error indicator is determined using a third stage of the circuitry, wherein the Reed-Solomon decoder comprises a syndrome computation stage, and the method further comprises: computing a plurality of syndromes based on the received decision-codeword using the syndrome computation stage; and receiving the plurality of syndromes at the first stage.

### Claim 13 (depends on 1)

The method of claim 1, further comprising producing a decoded dataword based on determining the validity of the first error indicator.

### Claim 14 (depends on 1)

The method of claim 1, wherein producing the first error indicator comprises running a Berlekamp-Massey algorithm.

### Claim 15

A method for decoding a dataword based on a decision-codeword using a Reed-Solomon decoder, comprising:
receiving a decision-codeword;
using circuitry, producing a partially decoded decision-codeword based on the received decision-codeword;
producing a first error indicator based on the received decision-codeword in a first pipeline stage;
producing a second error indicator based on the partially decoded decision-codeword in a second pipeline stage; and
using the circuitry, determining a validity of at least one of the first error indicator and the second error indicator in a third pipeline stage, wherein the validity indicates whether errors in the received decision-codeword are capable of being corrected.

### Claim 16 (depends on 15)

The method of claim 15, wherein producing the partially decoded decision-codeword comprises performing list decoding on the received decision-codeword.

### Claim 17 (depends on 15)

The method of claim 15, wherein the modified decision-codeword is produced when the validity indicates that the received decision-codeword is incapable of being decoded.

### Claim 18 (depends on 15)

The method of claim 15, wherein a validity of the second error indicator indicates whether errors in the modified decision-codeword are capable of being corrected.