# US 11,444,638 B2 · Quality-based dynamic scheduling LDPC decoder

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

- Number: US 11,444,638 B2
- Document ID: US11444638B2
- Status: Granted
- Kind: B2
- Application number: 17/023,981
- Filed: 2020-09-17
- Published: 2022-03-17
- Granted: 2022-09-13
- Earliest claimed: 2020-09-17
- Assignees: SK hynix Inc.
- Applicants: SK hynix Inc.
- Inventors: Meysam Asadi; Fan Zhang; Aman Bhatia
- Web page: https://patentgrep.com/patent/US11444638B2

## CPC

- H03M 13/1131: {Scheduling of bit node or check node processing}
- H03M 13/096: {Checksums}
- H03M 13/1111: {Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms}
- H03M 13/116: {Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices}
- H03M 13/1575: {Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance}
- H03M 13/2948: {Iterative decoding (H03M13/2957 takes precedence)}
- H03M 13/6502: {Reduction of hardware complexity or efficient processing}
- H03M 13/6577: {Representation or format of variables, register sizes or word-lengths and quantization}
- 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

Techniques related to improving power consumption of an LDPC decoder are described. In an example, the LDPC decoder uses a message passing algorithm between variable nodes and check nodes. A check node processing unit that generates check node to variable node messages implements a plurality of check node processing mode. Operation in each mode consumes a certain amount of power while providing a certain accuracy. Depending on a reliability of a variable node to check node message received by the check node processing unit, an appropriate check node processing mode is selected and used to generate a corresponding check node to variable node message. The reliability can be estimated for a set of variable node to check node messages based on, for instance, syndrome-related parameters.

## Claims

### Claim 1

A method for decoding a low-density parity-check code (LDPC) codeword, the method implemented on a computing device and comprising:
determining a variable node to check node (V2C) message, wherein the V2C message corresponds to a variable node that is connected to a check node;
determining a reliability of a set of V2C messages comprising the V2C message, the reliability representing a certainty of decoding the LDPC codeword, wherein each V2C message in the set of V2C messages corresponds to a different variable node from a set of variable nodes, and wherein the set of variable nodes corresponds to a variable node circulant matrix;
selecting, based on the reliability, a check node processing mode from a plurality of check node processing modes that have different error correction capabilities;
determining a check node to variable node (C2V) message based on selection of the check node processing mode; and
decoding the LDPC codeword based on the C2V message.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
during a decoding iteration:
determining a syndrome of the LDPC codeword;
increasing a decoding iteration number;
determining that the increased decoding iteration number does not exceed a maximum number; and
determining that the syndrome of the LDPC codeword is not zero.

### Claim 3 (depends on 2)

The method of claim 2, further comprising:
during a next decoding iteration corresponding to the increased decoding iteration number:
(a) updating the V2C message corresponding to the variable node;
(b) determining that the variable node is associated with a “j” variable node circulant matrix;
(c) determining that the check node connected to the variable node is associated with a “k” check node circulant matrix;
(d) determining the reliability of the set of V2C messages as rk,j=number of ones in Sk/CS, where rk,j is the reliability, Sk is a partial checksum computed based on the “k” check node circulant matrix, and CS is a checksum determined from the syndrome of the LDPC codeword;
(e) comparing rk,j to a reliability threshold, wherein the check node processing mode is selected based on the comparing; and
(f) updating the partial checksum Sk.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
during the next decoding iteration, repeating steps (a)-(f) for remaining variable node circulant matrices and remaining check node circulant matrices.

### Claim 5 (depends on 1)

The method of claim 1, wherein the reliability of the set of V2C messages is determined based on a syndrome of the LDPC codeword.

### Claim 6 (depends on 5)

The method of claim 5, wherein the reliability of the set of V2C messages is further determined based on a partial syndrome associated with a circulant matrix, wherein the check node is associated with the circulant matrix.

### Claim 7 (depends on 1)

The method of claim 1, wherein the check node is associated with a check node circulant matrix, wherein the reliability is determined based on a syndrome of the LDPC codeword and a partial syndrome, wherein the partial syndrome is computed based on the check node circulant matrix.

### Claim 8 (depends on 7)

The method of claim 7, wherein the reliability is determined as r=number of ones in Sk/CS, where r is the reliability, Sk is the partial syndrome, and CS is a checksum determined from the syndrome of the LDPC codeword.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
comparing the reliability to a reliability threshold, wherein the check node processing mode is selected based on the comparing.

### Claim 10 (depends on 9)

The method of claim 9, wherein the plurality of different check node processing modes comprises a first check node processing mode and a second check node processing mode, wherein the first check node processing mode approximates a log likelihood ratio of the variable node based on a first quantization level, wherein the second check node processing mode approximates the log likelihood ratio of the variable node based on a second quantization level, wherein the second quantization level is larger than the first quantization level, wherein the first check node processing mode is selected if the reliability is smaller than the reliability threshold, and wherein the second check node processing mode is selected if the reliability is larger than the reliability threshold.

### Claim 11 (depends on 9)

The method of claim 9, wherein the reliability threshold is defined based on a decoding iteration number.

### Claim 12 (depends on 9)

The method of claim 9, wherein the reliability threshold is defined based on a degree of the variable node.

### Claim 13 (depends on 9)

The method of claim 9, wherein the reliability threshold is defined based on a degree of the check node.

### Claim 14

A device comprising:
a memory storing a low-density parity-check code (LDPC) codeword; and
a set of processing units configured to:
determine a variable node to check node (V2C) message, wherein the V2C message corresponds to a variable node that is connected to a check node;
determine a reliability of a set of V2C messages comprising the V2C message, the reliability representing a certainty of decoding the LDPC codeword, wherein each V2C message in the set of V2C messages corresponds to a different variable node from a set of variable nodes, and wherein the set of variable nodes corresponds to a variable node circulant matrix;
select, based on the reliability, a check node processing mode from a plurality of check node processing modes that have different error correction capabilities; and
determine a check node to variable node (C2V) message based on selection of the check node processing mode,
wherein the LDPC codeword is decoded based on the C2V message.

### Claim 15 (depends on 14)

The device of claim 14, wherein the set of processing units is further configured to:
during a decoding iteration:
determine a syndrome of the LDPC codeword;
increase a decoding iteration number;
determine that the increased decoding iteration number does not exceed a maximum number; and
determine that the syndrome of the LDPC codeword is not zero.

### Claim 16 (depends on 15)

The device of claim 15, wherein the set of processing units is further configured to:
during a next decoding iteration corresponding to the increased decoding iteration number:
(a) update the V2C message corresponding to the variable node;
(b) determine that the variable node is associated with a “j” variable node circulant matrix;
(c) determine that the check node connected to the variable node is associated with a “k” check node circulant matrix;
(d) determine the reliability of the set of V2C messages as rk,j=number of ones in Sk/CS, where rk,j is the reliability, Sk is a partial syndrome computed based on the “k” check node circulant matrix, and CS is a checksum determined from the syndrome of the LDPC codeword;
(e) compare rk,j to a reliability threshold, wherein the check node processing mode is selected based on the comparing; and
(f) update the partial syndrome Sk.

### Claim 17 (depends on 16)

The device of claim 16, wherein the set of processing units is further configured to:
during the next decoding iteration, repeat steps (a)-(f) for remaining variable node circulant matrices and remaining check node circulant matrices.

### Claim 18

An error correction (ECC) system comprising:
a set of processing units configured to:
receive an LDPC codeword from a memory;
determine a variable node to check node (V2C) message, wherein the V2C message corresponds to a variable node that is connected to a check node;
determine a reliability of a set of V2C messages comprising the V2C message, the reliability representing a certainty of decoding the LDPC codeword, wherein each V2C message in the set of V2C messages corresponds to a different variable node from a set of variable nodes, and wherein the set of variable nodes corresponds to a variable node circulant matrix;
select, based on the reliability, a check node processing mode from a plurality of check node processing modes that have different error correction capabilities; and
determine a check node to variable node (C2V) message based on selection of the check node processing mode,
wherein the LDPC codeword is decoded based on the C2V message.

### Claim 19 (depends on 18)

The ECC system of claim 18, wherein the reliability of the set of V2C messages is determined based on a syndrome of the LDPC codeword and based on a partial syndrome associated with a circulant matrix, wherein the check node is associated with the circulant matrix.