# US 2009/0292976 A1 · Architecture and control of reed-solomon error identification and evaluation

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

- Number: US 2009/0292976 A1
- Document ID: US20090292976A1
- Status: Published application
- Kind: A1
- Application number: 12/512,710
- Filed: 2009-07-30
- Published: 2009-11-26
- Earliest claimed: 2004-10-27
- Assignees: Marvell International Ltd.
- Inventors: Ichiro Kikuchi; Siu-Hung Fred Au; Gregory Burd; Zining Wu; Jun Xu; Tony Yoon
- Web page: https://patentgrep.com/patent/US20090292976A1

## 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 error identification and evaluation for a Reed-Solomon (RS) error-correction code (ECC) system. The BMA algorithm and/or list decoding may produce one or more error locator polynomials that are related to a decision-codeword. An accelerated Chien search can be used to more quickly evaluate the one or more error locator polynomial. If the accelerated Chien search identifies a valid error locator polynomial, a normal Chien search can be used to identify error locations, and Forney's algorithm or an equivalent technique can be used to evaluate the error values. A RS ECC decoder can include a computation circuit that evaluates an error locator polynomial or an error evaluator polynomial. The computation circuit can include computation components that receive the coefficients of the polynomials.

## Claims

### Claim 1

A Reed-Solomon decoder for producing a dataword based on a decision-codeword, the decoder comprising:
a decision-codeword; and
an error correction circuit for identifying error locations and computing error values for the decision-codeword, the error correction circuit being configurable to operate in a first mode and a second mode, where an amount of time required to identify error locations when operating in the first mode is greater than an amount of time required to identify error locations when operating in the second mode.

### Claim 2 (depends on 1)

The Reed-Solomon decoder of claim 1, further comprising:
an error locator polynomial corresponding to the decision-codeword; and
an error evaluator polynomial corresponding to the error locator polynomial.

### Claim 3 (depends on 2)

The Reed-Solomon decoder of claim 2, wherein:
when the error correction circuit operates in the first mode, the error correction circuit evaluates both the error locator polynomial and the error evaluator polynomial; and
when the error correction circuit operates in the second mode, the error correction circuit evaluates only the error locator polynomial.

### Claim 4 (depends on 1)

The Reed-Solomon decoder of claim 1, wherein the error correction circuit comprises circuitry for identifying error locations.

### Claim 5 (depends on 4)

The Reed-Solomon decoder of claim 4, wherein the circuitry for identifying error locations comprises Chien search circuitry.

### Claim 6 (depends on 4)

The Reed-Solomon decoder of claim 4, wherein the circuitry for identifying error locations comprises circuitry for evaluating an error locator polynomial having a plurality of terms.

### Claim 7 (depends on 6)

The Reed-Solomon decoder of claim 6, wherein the circuitry for evaluating an error locator polynomial comprises:
a first summation circuit for computing a sum of even-positioned terms in the plurality of terms; and
a second summation circuit for computing a sum of odd-positioned terms in the plurality of terms.

### Claim 8 (depends on 1)

The Reed-Solomon decoder of claim 1, wherein the error correction circuit comprises circuitry for computing error values.

### Claim 9 (depends on 8)

The Reed-Solomon decoder of claim 8, wherein the circuitry for computing error values uses Forney's algorithm to compute an error value ei based on:
e
i
=
X
i
2
-
b

Ω

(
X
i
-
1
)
Λ
′

(
X
i
-
1
)
,
where,
i is an integer in a range [0, n−1],
b is a constant integer,
Xi=αi, where α is a primitive element,
Λ′(x) is a formal derivative of an error locator polynomial, and
Ω(x) is an error evaluator polynomial.

### Claim 10 (depends on 8)

The Reed-Solomon decoder of claim 8, wherein the circuitry for computing error values computes an error value ei based on:
e
i
=
X
-
(
2

t
-
2
+
b
)
B

(
X
i
-
1
)

Λ
′

(
X
i
-
1
)
,
where,
i is an integer in the range [0, n−1],
Xi=αi, where α is a primitive element,
2t=(n−k), where n is a length of the decision-codeword and k is a length of a dataword,
Λ′(x) is a formal derivative of an error locator polynomial, and
B(x) is an scratch polynomial.

### Claim 11 (depends on 8)

The Reed-Solomon decoder of claim 8, wherein the circuitry for computing error values is configurable to identify error locations.

### Claim 12 (depends on 1)

A read path comprising the Reed-Solomon decoder of claim 1.

### Claim 13 (depends on 12)

A disk drive comprising the read path of claim 12.

### Claim 14 (depends on 3)

The Reed-Solomon decoder of claim 3, wherein:
if the error locator polynomial is determined to be a final error locator polynomial, the error correction circuit operates on the error locator polynomial in the first mode.

### Claim 15 (depends on 14)

The Reed-Solomon decoder of claim 14, wherein the error locator polynomial is determined to be the final error locator polynomial if the error locator polynomial is a only polynomial in a set of polynomials that has not been determined to be invalid.

### Claim 16

A Reed-Solomon decoder for producing a dataword based on a decision-codeword, the decoder comprising:
error correction means for identifying error locations and computing error values for the decision-codeword, said error correction means being configurable to operate in a first mode and a second mode, where a amount of time required to identify error locations when operating in the first mode is greater than a amount of time required to identify error locations when operating in the second mode.

### Claim 17 (depends on 16)

The Reed-Solomon decoder of claim 16, wherein producing the decision codeword comprises:
generating a set of error locator polynomials corresponding to a received codeword; and
evaluating an error locator polynomial selected from a set of error locators polynomials.

### Claim 18 (depends on 17)

The Reed-Solomon decoder of claim 17, wherein if the selected error locator polynomial corresponds to a final error locator polynomial remaining to be validated, the selected error locator polynomial is evaluated in the first mode.
