# US 10,374,630 B2 · Low-density parity check decoder, a storage device including the same, and a method

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

- Number: US 10,374,630 B2
- Document ID: US10374630B2
- Status: Granted
- Kind: B2
- Application number: 15/652,260
- Filed: 2017-07-18
- Published: 2018-01-25
- Granted: 2019-08-06
- Earliest claimed: 2016-07-19
- Assignees: Samsung Electronics Co., Ltd.
- Applicants: Samsung Electronics Co., Ltd.
- Inventors: Jiyoup Kim; Dong-Min Shin; Beomkyu Shin; Junjin Kong; Hong Rak Son
- Web page: https://patentgrep.com/patent/US10374630B2

## CPC

- H03M 13/1111: {Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms}
- G06F 11/1012: {using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence)}
- G06F 11/1068: {in sector programmable memories, e.g. flash disk (G06F11/1072 takes precedence)}
- G11C 11/5642: {Sensing or reading circuits; Data output circuits}
- G11C 29/52: Protection of memory contents; Detection of errors in memory contents
- H03M 13/1108: {Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping}
- H03M 13/3707: {Adaptive decoding and hybrid decoding, e.g. decoding methods or techniques providing more than one decoding algorithm for one code}
- H03M 13/3723: {using means or methods for the initialisation of the decoder}
- H03M 13/3746: {with iterative decoding}
- H03M 13/6325: {Error control coding in combination with demodulation}
- 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/1188: {wherein in the part with the double-diagonal at least one column has an odd column weight equal or greater than three}
- 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)
- G11C: STATIC STORES (semiconductor memory devices H10B)

## Abstract

A low-density parity check (LDPC) decoder may include a variable node processing unit and a check node processing unit. The check node processing unit includes memory elements storing a check node value. The memory elements are interconnected through two or more paths, and each of the paths may include a total or partial cyclic permutation of the memory elements to transmit the check node value.

## Claims

### Claim 1

A low-density parity check (LDPC) decoder comprising:
a variable node processor that receives channel information and check node information and calculates variable node information; and
a check node processor that receives the variable node information and calculates the check node information, wherein the check node processor:
comprises K>2 memory elements that provide a K-cycle cyclic permutation and L of the memory elements, where 1<L<K, provide an L-cycle cyclic permutation, and
executes a first LDPC on data stored by the memory elements using the K-cycle cyclic permutation and the L-cycle cyclic permutation, wherein
a number of cycles required to execute the first LDPC is smaller than a number of cycles required to execute a second LDPC on the data using only the K-cycle cyclic permutation.

### Claim 2 (depends on 1)

The LDPC decoder of claim 1, wherein the channel information includes a channel log-likelihood ratio (LLR) for a codeword.

### Claim 3 (depends on 1)

The LDPC decoder of claim 1, wherein:
the check node processor comprises a plurality of check nodes and the variable node processor comprises a plurality of variable nodes, and
each of some, but fewer than all, of the check nodes is interconnected with a different and corresponding one of the variable nodes.

### Claim 4 (depends on 3)

The LDPC decoder of claim 3, wherein the variable node information includes a variable-to-check (V2C) message transmitted from a first variable node, among the variable nodes, to a first check node among the check nodes.

### Claim 5 (depends on 3)

The LDPC decoder of claim 3, wherein the check node information includes a check-to-variable (C2V) message transmitted from a first check node, among the check nodes, to a first variable node among the variable nodes.

### Claim 6 (depends on 5)

The LDPC decoder of claim 5, wherein the check node information includes a first minimum among C2V messages stored in the memory elements, a second minimum among the C2V messages, and position information of the first minimum.

### Claim 7 (depends on 1)

The LDPC decoder of claim 1, wherein each of the cycles required to execute the first LDPC on the data with the LDPC decoder is executed using either a cycle of the K-cycle cyclic permutation or a cycle of the L-cycle cyclic permutation, but not a cycle of each of the K-cycle cyclic permutation and a cycle of the L-cycle cyclic permutation.

### Claim 8 (depends on 7)

The LDPC decoder of claim 7, wherein the check node processor cycles the data stored by the memory elements through the K-cycle cyclic permutation and the L-cycle cyclic permutation using a dual diagonal form to execute the first LDPC on the data.

### Claim 9 (depends on 1)

The LDPC decoder of claim 1, wherein each of the memory elements includes a register.

### Claim 10 (depends on 1)

The LDPC decoder of claim 1, wherein:
L<M<K of the memory elements provide an M-cycle cyclic permutation, and
the check node processor executes the first LDPC on the data stored by the memory elements using the K-cycle cyclic permutation, the L-cycle cyclic permutation, and the M-cycle cyclic permutation.

### Claim 11

A storage device comprising:
a nonvolatile memory (NVM) device that stores a codeword including information and a parity corresponding to the information; and
a memory controller including a low-density parity check (LDPC) decoder that reads the codeword from the NVM device and corrects an error of the codeword, wherein:
the LDPC decoder comprises:
a variable node processor that receives channel information and check node information corresponding to the codeword and updates variable node information; and
a check node processor that receives the variable node information and updates the check node information, and
the check node processor:
comprises K>2 memory elements that provide a K-cycle cyclic permutation and L of the memory elements, where 1<L<K, provide an L-cycle cyclic permutation; and
executes a first LDPC on data stored by the memory elements using the K-cycle cyclic permutation and the L-cycle cyclic permutation, wherein
a number of cycles required to execute the first LDPC is smaller than a number of cycles required to execute a second LDPC on the data using only the K-cycle cyclic permutation.

### Claim 12 (depends on 11)

The storage device of claim 11, wherein the memory controller further includes an LDPC encoder that receives the information from an external device and generates the parity corresponding to the information.

### Claim 13 (depends on 11)

The storage device of claim 11, wherein the LDPC decoder decodes the codeword to hard decision or decodes the codeword to soft decision.

### Claim 14 (depends on 13)

The storage device of claim 13, wherein the LDPC decoder includes a first H matrix for hard decision decoding and a second H matrix for soft decision decoding.

### Claim 15 (depends on 12)

The storage device of claim 12, wherein:
the check node processor includes a plurality of check nodes and the variable node processor includes a plurality of variable nodes, and
each of some, but fewer than all of the check nodes, is interconnected with a different and corresponding one of the variable nodes.

### Claim 16

A method for performing a read operation in a storage device performing hard decision memory sensing in the storage device, the method comprising:
transmitting read data from a non-volatile memory (NVM) device of the storage device to an error correction circuit of a memory controller of the storage device;
in a low-density parity check (LDPC) decoder of the error correction circuit, using LDPC decoding to make a hard decision on the read data;
in the LDPC decoder, determining whether the hard decision was successfully made;
in response to determining that the hard decision was not successfully made, performing soft decision memory sensing on the read data;
transmitting the read data from the NVM device to the error correction circuit of the memory controller;
in the LDPC decoder of the error correction circuit, performing a soft decision using LDPC decoding on the read data; and
in the LDPC decoder, determining whether the soft decision was successfully made, wherein the LDPC decoder:
comprises K>2 memory elements that provide a K-cycle cyclic permutation and L of the memory elements, where 1<L<K, provide an L-cycle cyclic permutation,
executes a first LDPC on data stored by the memory elements using the K-cycle cyclic permutation and the L-cycle cyclic permutation, and
performs the first LDPC decoding to make the hard decisions and the soft decisions, wherein
a number of cycles required to execute the first LDPC is smaller than a number of cycles required to execute a second LDPC on the data using only the K-cycle cyclic permutation.

### Claim 17 (depends on 16)

The method of claim 16, wherein the LDPC decoder uses H matrices, which are identical, to execute the first LDPC decoding.

### Claim 18 (depends on 16)

The method of claim 16, wherein the LDPC decoder uses H matrices, which are different, to execute the first LDPC decoding.