Low density parity check decoder and storage device

Patent metadata

Field	Value
Publication number	US-11929762-B2
Application number	US-202217878431-A
Country	US
Kind code	B2
Filing date	Aug 1, 2022
Priority date	Nov 24, 2021
Publication date	Mar 12, 2024
Grant date	Mar 12, 2024

Abstract

A low density parity check (LDPC) decoder initializing variable nodes with a value of a codeword and outputting the updated variable nodes as decoded messages with reference to an irregular parity check matrix. The LDPC decoder includes a plurality of unit logic circuits operating in a single mode in which all the unit logic circuits update one variable node group including at least one variable node, or a multi-mode in which each of the unit logic circuits updates a plurality of variable node groups in parallel by updating different variable nodes, and a mode controller controlling the plurality of unit logic circuits to update a high-degree variable node group having a degree greater than a threshold degree among the variable node groups in the single mode, and update a low-degree variable node group having a degree less than or equal to the threshold degree among the variable node groups in the multi-mode.

First claim

What is claimed is:

1. A low density parity check (LDPC) decoder initializing variable nodes with a value of a codeword and outputting the variable nodes updated with reference to an irregular parity check matrix as decoded messages, comprising:
a plurality of unit logic circuits operating in a single mode in which all the unit logic circuits update one variable node group including at least one variable node, or a multi-mode in which each of the unit logic circuits updates a plurality of variable node groups in parallel by updating different variable nodes; and
a mode controller controlling the plurality of unit logic circuits to update a high-degree variable node group having a degree greater than a threshold degree among the variable node groups in the single mode, and update a low-degree variable node group having a degree less than or equal to the threshold degree among the variable node groups in the multi-mode.

2. The LDPC decoder of claim 1 , wherein the threshold degree is determined based on a maximum degree among degrees of the variable node groups and the number of the plurality of unit logic circuits.

3. The LDPC decoder of claim 1 , wherein each of the plurality of unit logic circuits includes an adder having two or more inputs.

4. The LDPC decoder of claim 3 , wherein the threshold degree is further determined based on the number of inputs of the adder.

5. The LDPC decoder of claim 1 , wherein the plurality of unit logic circuits includes a first unit logic circuit and a second unit logic circuit, and
in the single mode, the first unit logic circuit performs a sum operation on first check nodes among check nodes connected to the one variable node group, and the second unit logic circuit performs a sum operation on second check nodes among the connected check nodes so that the plurality of unit logic circuits update a value of the one variable node group.

6. The LDPC decoder of claim 5 , further includes a plurality of check node buffers for buffering values of check nodes to be processed by each of the plurality of unit logic circuits.

7. The LDPC decoder of claim 1 , wherein the mode controller updates the variable node groups in a predetermined order, and switches an operation mode of the plurality of unit logic circuits in runtime according to a degree of a target variable node group to be updated.

8. The LDPC decoder of claim 1 , wherein the mode controller updates the variable node groups in a predetermined order, and controls the plurality of unit logic circuits to update a first target variable node group in the single mode when the first target variable node group to be updated is a high-degree variable node group, skips the update of the first target variable node group when the first target variable node group is a low-degree variable node group, and controls the plurality of unit logic circuits to update the first variable node group and a second target variable node group in the multi-mode in a turn to update the second target variable node group which is a low-degree variable node group.

9. The LDPC decoder of claim 1 , wherein the mode controller arranges the variable node groups in descending order of degree, controls the plurality of unit logic circuits to update high-degree variable node groups among the variable node groups in the single mode in a first time period, and controls the plurality of unit logic circuits to update low-degree variable node groups among the variable node groups in the multi-mode in a second time period after the first time period.

10. The LDPC decoder of claim 1 , wherein the degree is the number of check nodes connected to one of the variable node groups in the LDPC code represented by the parity check matrix.

11. A low density parity check (LDPC) decoder, comprising:
a data buffer buffering data encoded with an irregular LDPC code and providing a value of the data to variable nodes;
a check node updater updating check nodes connected to the variable nodes;
a variable node updater updating the variable nodes connected to the updated check nodes; and
a syndrome checker outputting the values of the variable nodes as decoded data according to a syndrome check result of the updated variable nodes,
wherein the variable node updater includes one or more unit logic circuit groups, and controls each of the unit logic circuit groups to update one variable node in one cycle or each of the unit logic circuits included in each of the unit logic circuit group to update different variable nodes in parallel in one cycle according to an amount of computation required for each of the variable nodes.

12. The LDPC decoder of claim 11 , wherein the required amount of computation is determined based on the number of check nodes connected to the variable nodes.

13. The LDPC decoder of claim 11 , wherein each of the unit logic circuit groups updates one variable node in which the required amount of computation is greater than a threshold amount of computation in one cycle, or updates a plurality of variable nodes in which the required amount of computation is less than or equal to the threshold amount of computation in one cycle, and
the threshold amount of computation is determined based on a maximum operation amount of each of the plurality of unit logic circuits.

14. The LDPC decoder of claim 11 , wherein the LDPC decoder repeatedly performs an operation of updating the check nodes and an operation of updating the variable nodes when at least one of components of a syndrome vector does not have a value of “0” as a result of a syndrome check of the updated variable nodes.

15. The LDPC decoder of claim 11 , wherein the check node updater updates each of the check nodes by performing a minimum value (min) operation of the variable nodes connected to each of the check nodes, and
the variable node updater updates each of the variable nodes by performing a sum operation of check nodes connected to each of the variable nodes.

16. The LDPC decoder of claim 15 , wherein one unit logic circuit group includes adders for performing a sum operation of the check nodes.

17. The LDPC decoder of claim 11 , wherein the LDPC decoder includes M*N (M and N are a natural number) sub-matrices, and each of the sub-matrices stores a parity check matrix that is a zero matrix or a Q*Q (where Q is a natural number) dimensional cyclic shift identity matrix, and
the variable node updater includes Q unit logic circuit groups each including K (where K is a natural number) unit logic circuits, and the Q unit logic circuit groups include Q variable nodes corresponding to one column or updates Q*K variable nodes corresponding to K columns in parallel.

18. A storage device, comprising:
a memory device storing data encoded with an irregular low density parity check (LDPC) code; and
an LDPC unit initializing variable nodes with a value of data output from the memory device, updating check nodes connected to the variable nodes, updating the variable nodes by repeatedly performing an operation of updating Q (where Q is a natural number) variable nodes in one cycle or simultaneously updating Q*K (where K is a natural number) variable nodes in one cycle depending on whether degrees of each of the variable nodes exceed a threshold degree, and outputting values of the variable nodes according to a syndrome check result of the variable nodes.

19. The storage device of claim 18 , wherein the LDPC unit updates the check nodes and the variable nodes based on a parity check matrix that includes M*N (M and N are a natural number) sub-matrices,

Assignees

• Samsung Electronics Co Ltd

Inventors

• Lee Kangseok
• Yu Geunyeong
• Hwang Youngjun
• Son Hongrak
• Shin Junho
• Jun Bohwan
• Han Hyunseung

Classifications

• H03M13/1137 Primary

  Partly parallel processing, i.e. sub-blocks or sub-groups of nodes being processed in parallel · CPC title

• H03M13/112

  with correction functions for the min-sum rule, e.g. using an offset or a scaling factor · CPC title

• H03M13/1134

  Full parallel processing, i.e. all bit nodes or check nodes are processed in parallel · CPC title

• H03M13/1105 Primary

  Decoding · CPC title

• H04L1/0057 Primary

  Block codes (H04L1/0061, H04L1/0064 take precedence) · CPC title