# US 11,309,916 B2 · Error correction circuit and memory controller having the same

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

- Number: US 11,309,916 B2
- Document ID: US11309916B2
- Status: Granted
- Kind: B2
- Application number: 16/673,684
- Filed: 2019-11-04
- Published: 2020-10-22
- Granted: 2022-04-19
- Earliest claimed: 2019-04-17
- Assignees: SK hynix Inc.
- Applicants: SK hynix Inc.
- Inventors: Dae Sung Kim; Jang Seob Kim
- Web page: https://patentgrep.com/patent/US11309916B2

## CPC

- H03M 13/116: {Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices}
- G06F 11/1012: {using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence)}
- H03M 13/114: {Shuffled, staggered, layered or turbo decoding schedules}
- H03M 13/1185: {wherein the parity-check matrix comprises a part with a double-diagonal}
- H03M 13/3776: {using a re-encoding step during the decoding process}
- H03M 13/616: {Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations}
- 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)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Disclosed are devices, systems and methods for error correction encoding and decoding. A memory controller includes an error correction encoder for generating a codeword by performing error correction encoding, using a parity check matrix including a plurality of sub-matrices; and an error correction decoder for performing error correction decoding on a read vector corresponding to the codeword on a column layer basis while sequentially selecting column layers of the parity check matrix used for the error correction encoding, in the error correction decoding, the column layer including a set of columns of the parity check matrix. Rows included in the parity check matrix are grouped into a plurality of row groups, and at most one cyclic permutation matrix (CPM) is included for each column layer in each of the row groups.

## Claims

### Claim 1

An error correction circuit, comprising:
an error correction decoder configured to perform error correction decoding on a read vector on a column layer basis while sequentially selecting column layers of a parity check matrix including a plurality of sub-matrices, wherein the column layer includes a set of columns of the parity check matrix, and
wherein the error correction decoder includes:
a plurality of memory areas configured to store values of a plurality of check nodes corresponding to the parity check matrix; and
a check node processor including a plurality of check node units and configured to access one or more of the plurality of memory areas corresponding to cyclic permutation matrices (CPMs) included in a currently selected column layer, and update values of check nodes stored in the accessed one or more memory areas,
wherein rows included in the parity check matrix are grouped into a plurality of row groups, and at most one CPM is included for each column layer in each of the row groups, and
wherein the plurality of check node units for the currently selected column layer does not access two or more memory areas.

### Claim 2 (depends on 1)

The error correction circuit of claim 1, wherein the memory areas are grouped into a plurality of memory area groups corresponding to each of the row groups, and
wherein the check node processor includes a plurality of check node unit groups each configured to access a corresponding memory area group among the plurality of memory area groups and update values of check nodes stored in the accessed memory area group.

### Claim 3 (depends on 2)

The error correction circuit of claim 2, wherein each of the plurality of memory area groups include two or more memory area sub-groups, and a number of memory areas included in each of memory area sub-groups is determined based on a size of each of the sub-matrices,
wherein each of the check node unit groups is accessible to the two or more memory area sub-groups included in a corresponding memory area group among the memory area groups.

### Claim 4 (depends on 3)

The error correction circuit of claim 3, wherein each of the check node unit groups is configured to access a memory area sub-group corresponding to a first CPM included in the currently selected column layer among the accessible two or more memory area sub-groups.

### Claim 5 (depends on 4)

The error correction circuit of claim 4, wherein each of the check node unit groups includes check node units, a number of the check node units being determined based on the size of each of the sub-matrices,
wherein each of the check node units is accessible to any one memory area among memory areas included in a corresponding memory area sub-group with respect to each of the two or more memory area sub-groups.

### Claim 6 (depends on 2)

The error correction circuit of claim 2, wherein a number of the check node unit groups matches a number of the row groups.

### Claim 7 (depends on 2)

The error correction circuit of claim 2, wherein the check node unit groups update values of check nodes corresponding to a cyclic permutation matrix (CPM) included in the currently selected column layer in parallel.

### Claim 8 (depends on 1)

The error correction circuit of claim 1, further comprising an error correction encoder configured to perform error correction encoding by using the parity check matrix used for the error correction decoding.

### Claim 9

A memory controller comprising:
an error correction encoder configured to generate a codeword by performing error correction encoding, using a parity check matrix including a plurality of sub-matrices; and
an error correction decoder configured to perform error correction decoding on a read vector corresponding to the codeword on a column layer basis while sequentially selecting column layers of the parity check matrix used for the error correction encoding, in the error correction decoding, wherein the column layer includes a set of columns of the parity check matrix,
wherein rows included in the parity check matrix are grouped into a plurality of row groups, and at most one cyclic permutation matrix (CPM) is included for each column layer in each of the row groups, and
wherein the error correction decoder includes a plurality of check node units, and the plurality of check node units for a currently selected column layer does not access two or more memory areas.

### Claim 10 (depends on 9)

The memory controller of claim 9, wherein the error correction decoder includes:
a plurality of memory areas configured to store values of a plurality of check nodes corresponding to the parity check matrix; and
a check node processor configured to access one or more of the plurality of memory areas corresponding to cyclic permutation matrices (CPMs) included in the currently selected column layer, and update values of check nodes stored in the accessed memory areas.

### Claim 11 (depends on 10)

The memory controller of claim 10, wherein the memory areas are grouped into a plurality of memory area groups corresponding to each of the row groups,
wherein the check node processor includes a plurality of check node unit groups each configured to access a corresponding memory area group among the plurality of memory area groups and update values of check nodes stored in the accessed memory area group.

### Claim 12 (depends on 11)

The memory controller of claim 11, wherein each of the plurality of memory area groups include two or more memory area sub-groups, and a number of memory areas included in each of memory area sub-groups is determined based on a size of each of the sub-matrices,
wherein each of the check node unit groups is accessible to the two or more memory area sub-groups included in a corresponding memory area group among the memory area groups.

### Claim 13 (depends on 12)

The memory controller of claim 12, wherein each of the check node unit groups is configured to access a memory area sub-group corresponding to a first CPM included in the currently selected column layer among the accessible two or more memory area sub-groups.

### Claim 14 (depends on 13)

The memory controller of claim 13, wherein each of the check node unit groups includes check node units, a number of the check node units being determined based on the size of each of the sub-matrices,
wherein each of the check node units is accessible to any one memory area among memory areas included in a corresponding memory area sub-group with respect to each of the two or more memory area sub-groups.

### Claim 15 (depends on 11)

The memory controller of claim 11, wherein a number of the check node unit groups matches a number of the row groups.

### Claim 16 (depends on 11)

The memory controller of claim 11, wherein the check node unit groups update values of check nodes corresponding to a cyclic permutation matrix (CPM) included in the currently selected column layer in parallel.