# US 2021/0242882 A1 · Bit-flipping decoder architecture for irregular quasi-cyclic low-density parity-check codes

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

- Number: US 2021/0242882 A1
- Document ID: US20210242882A1
- Status: Published application
- Kind: A1
- Application number: 16/781,913
- Filed: 2020-02-04
- Published: 2021-08-05
- Earliest claimed: 2020-02-04
- Assignees: SK hynix Inc.
- Applicants: SK hynix Inc.
- Inventors: Meysam Asadi; Fan Zhang; Aman Bhatia; Xuanxuan Lu; Haobo Wang
- Web page: https://patentgrep.com/patent/US20210242882A1

## CPC

- H03M 13/1108: {Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping}
- G06F 11/1068: {in sector programmable memories, e.g. flash disk (G06F11/1072 takes precedence)}
- 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/6502: {Reduction of hardware complexity or efficient processing}
- 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

Devices, systems and methods for reducing complexity of a bit-flipping decoder for quasi-cyclic (QC) low-density parity-check (LDPC) codes are described. An example method includes receiving a noisy codeword that is based on a transmitted codeword generated from an irregular QC-LDPC code, the irregular QC-LDPC code having an associated parity matrix, storing, based on a weight of a plurality of columns of the parity matrix of the irregular QC-LDPC code, a portion of the noisy codeword corresponding to the plurality of columns in a first buffer of a plurality of buffers, and accessing and processing the portion of the noisy codeword that includes applying a vertically shuffled scheduling (VSS) scheme that uses a plurality of processing units to determine a candidate version of a portion of the transmitted codeword that corresponds to the portion of the noisy codeword.

## Claims

### Claim 1

A method for reducing complexity of a decoder, comprising:
receiving a noisy codeword that is based on a transmitted codeword generated from an irregular quasi-cyclic low-density parity-check (QC-LDPC) code, the irregular QC-LDPC code having an associated parity matrix;
storing, based on a weight of a plurality of columns of the parity matrix of the irregular QC-LDPC code, a portion of the noisy codeword corresponding to the plurality of columns in a first buffer of a plurality of buffers; and
accessing and processing the portion of the noisy codeword that includes applying a vertically shuffled scheduling (VSS) scheme that uses a plurality of processing units to determine a candidate version of a portion of the transmitted codeword that corresponds to the portion of the noisy codeword,
wherein the processing comprises a performing a message passing algorithm between a plurality of variable nodes and a plurality of check nodes that represent the parity matrix of the irregular QC-LDPC code,
wherein the VSS scheme processes each of the variable nodes one by one in each iteration of the message passing algorithm, and
wherein a number of the plurality of processing units is based on a distribution of column weights in the parity matrix.

### Claim 2 (depends on 1)

The method of claim 1, wherein, upon a determination that the weight of the plurality of columns is smaller than an average weight of all columns of the parity matrix, using the first buffer that comprises a double buffer.

### Claim 3 (depends on 1)

The method of claim 1, wherein, upon a determination that the weight of the plurality of columns is larger than an average weight of all columns of the parity matrix, using the first buffer that comprises an input buffer.

### Claim 4 (depends on 1)

The method of claim 1, wherein the plurality of processing units comprises a plurality of check node processing units (CNPUs) that process each of the plurality of check nodes and a plurality of variable node processing nodes (VNPUs) that process each of the plurality of variable nodes.

### Claim 5 (depends on 4)

The method of claim 4, wherein the parity matrix of the irregular QC-LDPC code comprises a plurality of columns of circulant matrices.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
partitioning the plurality of columns of circulant matrices into a plurality of zones, each comprising consecutive columns of circulant matrices,
wherein the processing comprises processing each of the plurality of zones, and
wherein processing a zone of the plurality of zones comprises concurrently processing all circulant columns in the zone.

### Claim 7 (depends on 6)

The method of claim 6, wherein a number of the plurality of zones is based on a number of the plurality of CNPUs and a number of the plurality of VNPUs.

### Claim 8 (depends on 6)

The method of claim 6, wherein the zone (Zj) comprises a first column (sj) and a last column (ej), wherein the zone is selected such that:
∑
k
=
s
j
e
j
⁢
d
k
≤
min
⁢
⁢
(
N
cnpu
,
N
vnpu
)
circSize
<
∑
k
=
s
j
e
j
+
1
⁢
d
k
wherein Ncnpu is a number of the plurality of CNPUs and Nvnpu is a number of the plurality of VNPUs, wherein dk is a weight of a k-th circulant column, and wherein circSize is a size of a circulant matrix of the circulant matrices.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
determining, based on the candidate version of the portion of the transmitted codeword, a candidate transmitted codeword.

### Claim 10 (depends on 9)

The method of claim 9, further comprising:
performing a subsequent iteration of the decoder upon a determination that a checksum for the candidate transmitted codeword is not equal to zero.

### Claim 11 (depends on 9)

The method of claim 9, further comprising:
refraining from performing a subsequent iteration upon a determination that a checksum for the candidate transmitted codeword is equal to zero or a maximum number of iterations has been performed.

### Claim 12

A system for reducing complexity of a decoder, 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 an irregular quasi-cyclic low-density parity-check (QC-LDPC) code, the irregular QC-LDPC code having an associated parity matrix;
store, based on a weight of a plurality of columns of the parity matrix of the irregular QC-LDPC code, a portion of the noisy codeword corresponding to the plurality of columns in a first buffer of a plurality of buffers; and
access and process the portion of the noisy codeword that includes applying a vertically shuffled scheduling (VSS) scheme that uses a plurality of processing units to determine a candidate version of a portion of the transmitted codeword that corresponds to the portion of the noisy codeword,
wherein the processing comprises a performing a message passing algorithm between a plurality of variable nodes and a plurality of check nodes that represent the parity matrix of the irregular QC-LDPC code,
wherein the VSS scheme processes each of the variable nodes one by one in each iteration of the message passing algorithm, and
wherein a number of the plurality of processing units is based on a distribution of column weights in the parity matrix.

### Claim 13 (depends on 12)

The system of claim 12, wherein, upon a determination that the weight of the plurality of columns is smaller than an average weight of all columns of the parity matrix, the processor is further configured to:
use the first buffer that comprises a double buffer.

### Claim 14 (depends on 12)

The system of claim 12, wherein, upon a determination that the weight of the plurality of columns is larger than an average weight of all columns of the parity matrix, the processor is further configured to:
use the first buffer that comprises an input buffer.

### Claim 15 (depends on 12)

The system of claim 12, wherein the plurality of processing units comprises a plurality of check node processing units (CNPUs) that process each of the plurality of check nodes and a plurality of variable node processing nodes (VNPUs) that process each of the plurality of variable nodes.

### Claim 16

A non-transitory computer-readable storage medium having instructions stored thereupon for reducing complexity of a decoder, comprising:
instructions for receiving a noisy codeword that is based on a transmitted codeword generated from an irregular quasi-cyclic low-density parity-check (QC-LDPC) code, the irregular QC-LDPC code having an associated parity matrix;
instructions for storing, based on a weight of a plurality of columns of the parity matrix of the irregular QC-LDPC code, a portion of the noisy codeword corresponding to the plurality of columns in a first buffer of a plurality of buffers; and
instructions for accessing and processing the portion of the noisy codeword that includes applying a vertically shuffled scheduling (VSS) scheme that uses a plurality of processing units to determine a candidate version of a portion of the transmitted codeword that corresponds to the portion of the noisy codeword,
wherein the processing comprises a performing a message passing algorithm between a plurality of variable nodes and a plurality of check nodes that represent the parity matrix of the irregular QC-LDPC code,
wherein the VSS scheme processes each of the variable nodes one by one in each iteration of the message passing algorithm, and
wherein a number of the plurality of processing units is based on a distribution of column weights in the parity matrix.

### Claim 17 (depends on 16)

The computer-readable storage medium of claim 16, wherein the plurality of processing units comprises a plurality of check node processing units (CNPUs) that process each of the plurality of check nodes and a plurality of variable node processing nodes (VNPUs) that process each of the plurality of variable nodes.

### Claim 18 (depends on 17)

The computer-readable storage medium of claim 17, wherein the parity matrix of the irregular QC-LDPC code comprises a plurality of columns of circulant matrices.

### Claim 19 (depends on 18)

The computer-readable storage medium of claim 18, further comprising:
instructions for partitioning the plurality of columns of circulant matrices into a plurality of zones, each comprising consecutive columns of circulant matrices,
wherein the processing comprises processing each of the plurality of zones, and
wherein processing a zone of the plurality of zones comprises concurrently processing all circulant columns in the zone.

### Claim 20 (depends on 19)

The computer-readable storage medium of claim 19, wherein a number of the plurality of zones is based on a number of the plurality of CNPUs and a number of the plurality of VNPUs.