# US 7,613,988 B1 · Degree limited polynomial in Reed-Solomon decoding

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

- Number: US 7,613,988 B1
- Document ID: US7613988B1
- Status: Granted
- Kind: B1
- Application number: 11/254,218
- Filed: 2005-10-18
- Granted: 2009-11-03
- Earliest claimed: 2005-10-18
- Assignees: Link—A—Media Devices Corporation
- Inventors: Yingquan Wu; Yu Kou
- Web page: https://patentgrep.com/patent/US7613988B1

## CPC

- H03M 13/153: {using the Berlekamp-Massey algorithm}
- H03M 13/1525: {Determination and particular use of error location polynomials}
- 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

Processing Reed Solomon data is disclosed. A scratch polynomial having a degree is obtained using an inversionless Berlekamp-Massey process. The degree of the scratch polynomial is limited. A magnitude of an error associated with the Reed Solomon data is determined based at least in part on information associated with the degree limited scratch polynomial. In some embodiments, determining the magnitude of an error using the degree limited scratch polynomial enables a smaller device.

## Claims

### Claim 1

A method of processing Reed Solomon data, including:
generating, at a processor, a degree limited scratch polynomial having a degree that is limited to a defined value using an inversionless Berlekamp-Massey process, wherein generating includes shifting out at least one zero root in a polynomial being operated on in the event the degree of the polynomial being operated on exceeds the defined value, wherein the defined value is t−1 and t is an error correction capability of a code used to generate the Reed Solomon data; and
determining a magnitude of an error associated with the Reed Solomon data using the processor based at least in part on information associated with the degree limited scratch polynomial.

### Claim 2

A system for processing Reed Solomon data, including a processor configured to:
obtain generate a degree limited scratch polynomial having a degree that is limited to a defined value using an inversionless Berlekamp-Massey process, wherein generating includes shifting out at least one zero root in a polynomial being operated on in the event the degree of the polynomial being operated on exceeds the defined value, wherein the defined value is t−1 and t is an error correction capability of a code used to generate the Reed Solomon data; and
determine a magnitude of an error associated with the Reed Solomon data based at least in part on information associated with the degree limited scratch polynomial; and a memory configured to be accessible to the processor.

### Claim 3 (depends on 2)

The system as recited in claim 2, wherein the processor includes a plurality of devices and each of the plurality of devices is configured to generate (1) a coefficient of the scratch polynomial and (2) a coefficient of an error locator polynomial.

### Claim 4 (depends on 2)

The system as recited in claim 2, wherein the processor includes a plurality of devices and each of the plurality of devices has the same structure.

### Claim 5 (depends on 2)

The system as recited in claim 2, wherein the processor includes a plurality of devices and the number of the plurality of devices varies in accordance with an error correction capability.

### Claim 6 (depends on 2)

The system as recited in claim 2, wherein limiting the degree of the scratch polynomial allows at least one configuration with fewer components compared to a system in which the degree of the scratch polynomial is not limited.

### Claim 7 (depends on 2)

The system as recited in claim 2, wherein the processor is further configured to perform a Chien search.

### Claim 8 (depends on 2)

The system as recited in claim 2, wherein at least one zero root is not removed from the scratch polynomial.

### Claim 9 (depends on 2)

The system as recited in claim 2, wherein the processor is further configured to obtain a syndrome polynomial.

### Claim 10 (depends on 2)

The system as recited in claim 2, wherein the processor is further configured to determine a location of the error.

### Claim 11 (depends on 2)

The system as recited in claim 2, wherein the processor is further configured to obtain roots of an error locator polynomial.

### Claim 12 (depends on 2)

The system as recited in claim 2, wherein the processor is further configured to determine a location of the error, including using a Chien search.

### Claim 13 (depends on 2)

The system as recited in claim 2 wherein information associated with an error evaluator polynomial is not used in determining the magnitude.

### Claim 14 (depends on 2)

The system as recited in claim 2, wherein the processor is further configured to obtain an error locator polynomial.

### Claim 15 (depends on 2)

The system as recited in claim 2, wherein the processor is further configured to obtain an error locator polynomial, including by suing an iterative process.

### Claim 16 (depends on 2)

The system as recited in claim 2, wherein the processor is further configured to obtain an error locator polynomial, including by using an iterative process such that the iterative process is stopped in the event a criterion associated with an error correction capability is satisfied.

### Claim 17 (depends on 2)

The system as recited in claim 2, wherein the inversionless Berlekamp-Massey process includes simultaneously performing at least a portion of processing associated with discrepancy computation and at least a portion of processing associated with error locator update.

### Claim 18 (depends on 2)

The system as recited in claim 2, wherein the processor is further configured to perform a Chien search, wherein at least part of the Chien search and at least part of determining the magnitude of the error are performed simultaneously.

### Claim 19 (depends on 2)

The system as recited in claim 2, wherein the Reed Solomon data is obtained from a storage device.

### Claim 20

A computer program product for processing Reed Solomon data, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:
generating a degree limited scratch polynomial having a degree that is limited to a defined value using an inversionless Berlekamp-Massey process, wherein generating includes shifting out at least one zero root in a polynomial being operated on in the event the degree of the polynomial being operated on exceeds the defined value, wherein the defined value is t−1 and t is an error correction capability of a code used to generate the Reed Solomon data; and
determining a magnitude of an error associated with the Reed Solomon data based at least in part on information associated with the degree limited scratch polynomial.