# US 2019/0319643 A1 · Reed solomon decoder and semiconductor device including the same

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

- Number: US 2019/0319643 A1
- Document ID: US20190319643A1
- Status: Published application
- Kind: A1
- Application number: 16/239,460
- Filed: 2019-01-03
- Published: 2019-10-17
- Earliest claimed: 2018-04-16
- Assignees: SK hynix Inc.; Korea Advanced Institute of Science and Technology (KAIST)
- Applicants: SK hynix Inc.; Korea Advanced Institute of Science and Technology (KAIST)
- Inventors: Hyunho KIM; Incheol PARK; Wooyoung KIM; Youngook SONG; Sanggu JO
- Web page: https://patentgrep.com/patent/US20190319643A1

## CPC

- H03M 13/1515: {Reed-Solomon codes}
- H03M 13/154: {Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial}
- 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/1555: {Pipelined decoder implementations}
- H03M 13/1585: {Determination of error values}
- H03M 13/159: {Remainder calculation, e.g. for encoding and syndrome calculation}
- 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

A Reed Solomon decoder may include a syndrome calculation (SC) circuit configured to calculate a codeword from a syndrome ; a key equation solver (KES) circuit configured to calculate an error location polynomial and an error evaluation polynomial from the syndrome; and a Chien search and error evaluation (CSEE) circuit configured to calculate an error location and an error value from the error location polynomial and the error evaluation polynomial, wherein the KES circuit comprises a plurality of sub-KES circuit and each of the plurality of sub-KES circuit, the SC circuit and the CSEE circuit constitutes pipeline stages respectively.

## Claims

### Claim 1

A Reed Solomon decoder comprising:
a syndrome calculation (SC) circuit configured to calculate a codeword from a syndrome;
a key equation solver (KES) circuit configured to calculate an error location polynomial and an error evaluation polynomial from the syndrome; and
a Chien search and error evaluation (CSEE) circuit configured to calculate an error location and an error value from the error location polynomial and the error evaluation polynomial,
wherein the KES circuit comprises a plurality of sub-KES circuits and each of the plurality of sub-KES circuits, the SC circuit, and the CSEE circuit respectively comprise pipeline stages.

### Claim 2 (depends on 1)

The Reed Solomon decoder of claim 1, further comprising a first-in, first-out (FIFO) queue configured to queue the codeword; and an error correction circuit configured to produce and output error corrected data using an output from the FIFO queue and the error location and the error value.

### Claim 3 (depends on 1)

The Reed Solomon decoder of claim 1, wherein each of the plurality of sub-KES circuits comprises a plurality of processing element (PE) circuits connected in series and a control circuit configured to control the plurality of PE circuits.

### Claim 4 (depends on 3)

The Reed Solomon decoder of claim 3, wherein a number of the plurality of sub-KES circuits is t (t is a natural number) and a number of the plurality of PE circuits is 3t+1.

### Claim 5 (depends on 3)

The Reed Solomon decoder of claim 3, wherein each of the plurality of PE circuits comprises a first operation circuit configured to perform a first operation and a second operation circuit configured to perform a second operation,
wherein the control circuit comprises a first control circuit configured to control the first operation circuits of the PE circuits and a second control circuit configured to control the second operation circuits of the PE circuits, and
wherein the control circuit controls the first operation circuits and the second operation circuits so that the second operation is performed after the first operation is completed.

### Claim 6 (depends on 1)

The Reed Solomon decoder of claim 1, wherein the SC circuit comprises a plurality of sub-SC circuits each configured to calculate a syndrome element of the syndrome from the codeword.

### Claim 7 (depends on 6)

The Reed Solomon decoder of claim 6, wherein the plurality of sub-SC circuits operates in parallel to each other.

### Claim 8 (depends on 1)

The Reed Solomon decoder of claim 1, wherein the CSEE circuit comprise:
a Chien search (CS) circuit configured to determine the error location from the error location polynomial; and
an error evaluation (EE) circuit configured to determine the error value from the error evaluation polynomial and the error location.

### Claim 9

A semiconductor device comprising:
an error correction encoder configured to output a codeword by encoding data;
a memory cell array configured to store the codeword output from the error correction encoder; and
an error correction decoder configured to output error corrected data by decoding a codeword output from the memory cell,
wherein the error correction decoder comprises:
a SC circuit configured to calculate a codeword from a syndrome;
a KES circuit configured to calculate an error location polynomial and an error evaluation polynomial from the syndrome; and
a CSEE circuit configured to calculate an error location and an error value from the error location polynomial and the error evaluation polynomial,
wherein the KES circuit comprises a plurality of sub-KES circuit and each of the plurality of sub-KES circuits, the SC circuit, and the CSEE circuit respectively comprise pipeline stages.

### Claim 10 (depends on 9)

The semiconductor device of claim 9, further comprising:
an input buffer configured to output the data to the error correction encoder by buffering input data; and
an output buffer configured to provide output data by buffering the error corrected data.

### Claim 11 (depends on 9)

The semiconductor device of claim 9, wherein the codeword includes a data part and a parity part, and
wherein the memory cell array comprises a main cell array to store the data part and a parity cell array to store the parity part.

### Claim 12 (depends on 9)

The semiconductor device of claim 9, wherein the error correction decoder further comprises a first-in, first-out (FIFO) queue configured to queue the codeword; and an error correction circuit configured to produce and output error corrected data using an output from the FIFO queue and the error location and the error value.

### Claim 13 (depends on 9)

The semiconductor device of claim 9, wherein each of the plurality of sub-KES circuit comprises a plurality of PE circuits connected in series and a control circuit configured to control the plurality of PE circuits.

### Claim 14 (depends on 13)

The semiconductor device of claim 13, wherein a number of the plurality of sub-KES circuits is t (t is a natural number) and a number of the plurality of PE circuits is 3t+1.

### Claim 15 (depends on 13)

The semiconductor device of claim 13, wherein each of the plurality of PE circuits comprises a first operation circuit configured to perform a first operation and a second operation circuit configured to perform a second operation and wherein the control circuit comprises a first control circuit configured to control the first operation circuits of the PE circuits and a second control circuit configured to control the second operation circuits of the PE circuits.

### Claim 16 (depends on 9)

The semiconductor device of claim 9, wherein the SC circuit comprises a plurality of sub-SC circuits each configured to calculate a syndrome element of the syndrome from the codeword.

### Claim 17 (depends on 16)

The semiconductor device of claim 16, wherein the plurality of sub-SC circuits operates in parallel to each other.

### Claim 18 (depends on 9)

The semiconductor device of claim 9, wherein the CSEE circuit comprise:
a Chien search (CS) circuit configured to determine the error location from the error location polynomial; and
an error evaluation (EE) circuit configured to determine the error value from the error evaluation polynomial and the error location.