# US 12,112,041 B2 · Out-of-order bit-flipping decoders for non-volatile memory devices

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

- Number: US 12,112,041 B2
- Document ID: US12112041B2
- Status: Granted
- Kind: B2
- Application number: 17/950,528
- Filed: 2022-09-22
- Published: 2024-03-28
- Granted: 2024-10-08
- Earliest claimed: 2022-09-22
- Assignees: SK hynix Inc.
- Applicants: SK hynix Inc.
- Inventors: Fan Zhang; Meysam Asadi; Haobo Wang
- Web page: https://patentgrep.com/patent/US12112041B2

## CPC

- G06F 3/0611: {in relation to response time}
- H03M 13/116: {Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices}
- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- H03M 13/1108: {Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping}
- H03M 13/1111: {Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms}
- H03M 13/1128: {Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations}
- H03M 13/114: {Shuffled, staggered, layered or turbo decoding schedules}
- H03M 13/09: Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- 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

Devices, systems, and methods for reducing a latency of a decoder in a non-volatile memory are described. An example method includes receiving a noisy codeword that is based on a transmitted codeword generated from a low-density parity-check (LDPC) code, the LDPC code having an associated parity matrix comprising a plurality of columns of circulant matrices, performing a sorting operation that sorts the plurality of columns of circulant matrices in a descending order of a first quality metric to generate a plurality of sorted columns of circulant matrices, the first quality metric indicative of a number of errors in a corresponding column of circulant matrices, and iteratively processing the plurality of sorted columns of circulant matrices to determine a candidate version of the transmitted codeword.

## Claims

### Claim 1

A method for reducing a latency of a decoder in a non-volatile memory, comprising:
receiving a noisy codeword that is based on a transmitted codeword generated from a low-density parity-check (LDPC) code, the LDPC code having an associated parity matrix comprising a plurality of columns of circulant matrices;
performing a sorting operation that sorts the plurality of columns of circulant matrices in a descending order of a first quality metric to generate a plurality of sorted columns of circulant matrices, the first quality metric indicative of a number of errors in a corresponding column of circulant matrices; and
iteratively processing the plurality of sorted columns of circulant matrices to determine a candidate version of the transmitted codeword,
wherein, for each column of the plurality of sorted columns of circulant matrices, iteratively processing the plurality of sorted columns comprises:
determining a second quality metric indicative of the number of errors in the column,
comparing the second quality metric to at least one threshold, and
in response to the comparing, selectively processing the column in an order determined by the sorting operation,
wherein the selectively processing the column comprises performing a message passing algorithm between a plurality of variable nodes and a plurality of check nodes that represent the parity matrix of the LDPC code to determine the candidate version of the transmitted codeword.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
prior to performing the sorting operation, determining, for each circulant column of the plurality of columns of circulant matrices, the first quality metric, wherein the first quality metric is based on a number of unsatisfied check nodes associated with a bit in the corresponding circulant column.

### Claim 3 (depends on 2)

The method of claim 2, wherein the first quality metric is a maximum value of the number of unsatisfied check nodes across all bits in the corresponding circulant column.

### Claim 4 (depends on 2)

The method of claim 2, wherein the first quality metric is an average value of the number of unsatisfied check nodes across all bits in the corresponding circulant column.

### Claim 5 (depends on 1)

The method of claim 1, wherein the second quality metric is a checksum.

### Claim 6 (depends on 5)

The method of claim 5, wherein the first quality metric is a checksum.

### Claim 7 (depends on 1)

The method of claim 1, wherein the at least one threshold is selected from a plurality of thresholds that comprises a first threshold (T1), one or more intermediate thresholds (TN-1), and a final threshold (TN), and wherein T1<TN-1<TN.

### Claim 8 (depends on 7)

The method of claim 7, wherein the at least one threshold is the first threshold, and wherein the method, as part of the selectively processing the column, comprises:
in response to the second quality metric exceeding the first threshold, refraining from processing the column corresponding to the second quality metric.

### Claim 9 (depends on 7)

The method of claim 7, wherein the at least one threshold is one of the one or more intermediate thresholds, and wherein the method, as part of the selectively processing the column, comprises:
in response to the second quality metric being less than the one of the one or more intermediate thresholds,
processing the column corresponding to the second quality metric in the order determined by the sorting operation, and
computing a cyclic redundancy check (CRC) for the plurality of columns of circulant matrices.

### Claim 10 (depends on 9)

The method of claim 9, wherein the at least one threshold is the final threshold, and wherein the method, as part of the selectively processing the column, comprises:
in response to the second quality metric being less than the final threshold and the CRC passing, refraining from performing a subsequent iteration.

### Claim 11

A system reducing a latency of a decoder in a non-volatile memory, comprising:
a processor and a memory including instructions stored thereupon, wherein the instructions, upon execution by the processor, cause the processor to:
receive a noisy codeword that is based on a transmitted codeword generated from a low-density parity-check (LDPC) code, the LDPC code having an associated parity matrix comprising a plurality of columns of circulant matrices;
perform a sorting operation that sorts the plurality of columns of circulant matrices in a descending order of a first quality metric to generate a plurality of sorted columns of circulant matrices, the first quality metric indicative of a number of errors in a corresponding column of circulant matrices; and
iteratively process the plurality of sorted columns of circulant matrices to determine a candidate version of the transmitted codeword,
wherein, for each column of the plurality of sorted columns of circulant matrices, the instructions upon execution by the processor cause the processor, as part of iteratively processing the plurality of sorted columns, to:
determine a second quality metric indicative of the number of errors in the column,
compare the second quality metric to at least one threshold, and
in response to comparing, selectively process the column in an order determined by the sorting operation,
wherein processing the column comprises performing a message passing algorithm between a plurality of variable nodes and a plurality of check nodes that represent the parity matrix of the LDPC code to determine the candidate version of the transmitted codeword.

### Claim 12 (depends on 11)

The system of claim 11, wherein the instructions, upon execution by the processor, cause the processor to:
prior to performing the sorting operation, determine, for each circulant column of the plurality of columns of circulant matrices, the first quality metric, wherein the first quality metric is based on a number of unsatisfied check nodes associated with a bit in the corresponding circulant column.

### Claim 13 (depends on 11)

The system of claim 11, wherein the first quality metric is a maximum value or an average value of a number of unsatisfied check nodes across all bits in the corresponding circulant column.

### Claim 14 (depends on 11)

The system of claim 11, wherein the at least one threshold is selected from a plurality of thresholds that comprises a first threshold (T1), one or more intermediate thresholds (TN-1), and a final threshold (TN), and wherein T1<TN-1<TN.

### Claim 15 (depends on 14)

The system of claim 14, wherein the at least one threshold is the first threshold, and wherein the instructions, upon execution by the processor, cause the processor, as part of selectively processing the column, to:
in response to the second quality metric exceeding the first threshold, refrain from processing the column corresponding to the second quality metric.

### Claim 16 (depends on 14)

The system of claim 14, wherein the at least one threshold is one of the one or more intermediate thresholds, and wherein the instructions, upon execution by the processor, cause the processor, as part of selectively processing the column, to:
in response to the second quality metric being less than the one of the one or more intermediate thresholds,
process the column corresponding to the second quality metric in the order determined by the sorting operation, and
compute a cyclic redundancy check (CRC) for the plurality of columns of circulant matrices.

### Claim 17 (depends on 16)

The system of claim 16, wherein the at least one threshold is the final threshold, and wherein the instructions, upon execution by the processor, cause the processor, as part of selectively processing the column, to:
in response to the second quality metric being less than the final threshold and the CRC passing, refrain from performing a subsequent iteration.

### Claim 18 (depends on 11)

The system of claim 11, wherein the instructions, upon execution by the processor, cause the processor, as part of selectively processing the column, to:
process the column in a first order in response to the second quality metric being greater than the at least one threshold; and
process the column in a second order in response to the second quality metric being less than or equal to the at least one threshold.

### Claim 19 (depends on 11)

The system of claim 11, wherein the instructions, upon execution by the processor, cause the processor, as part of selectively processing the column, to:
process the column in the order determined by the sorting operation in response to the second quality metric being less than or equal to the at least one threshold; and
refrain from processing the column in response to the second quality metric being greater than the at least one threshold.

### Claim 20

A non-transitory computer-readable storage medium having instructions stored thereupon for reducing a latency of a decoder in a non-volatile memory, the instructions, when executed by a processor, cause the processor to perform operations comprising:
receiving a noisy codeword that is based on a transmitted codeword generated from a low-density parity-check (LDPC) code, the LDPC code having an associated parity matrix comprising a plurality of columns of circulant matrices;
performing a sorting operation that sorts the plurality of columns of circulant matrices in a descending order of a first quality metric to generate a plurality of sorted columns of circulant matrices, the first quality metric indicative of a number of errors in a corresponding column of circulant matrices; and
iteratively processing the plurality of sorted columns of circulant matrices to determine a candidate version of the transmitted codeword,
wherein, for each column of the plurality of sorted columns of circulant matrices, iteratively processing the plurality of sorted columns comprises:
determining a second quality metric indicative of the number of errors in the column,
comparing the second quality metric to at least one threshold, and
in response to the comparing, selectively processing the column in an order determined by the sorting operation,
wherein processing the column comprises performing a message passing algorithm between a plurality of variable nodes and a plurality of check nodes that represent the parity matrix of the LDPC code to determine the candidate version of the transmitted codeword.