Storage device including error correction decoder and operating method of error correction decoder

Patent metadata

Field	Value
Publication number	US-9778979-B2
Application number	US-201514800012-A
Country	US
Kind code	B2
Filing date	Jul 15, 2015
Priority date	Aug 25, 2014
Publication date	Oct 3, 2017
Grant date	Oct 3, 2017

Abstract

An operating method of an error correction decoder includes receiving data, setting initial log-likelihood values of variable nodes, and decoding the received data by updating a log-likelihood value of a selected variable node by use of a minimum value and a minimum candidate value associated with the selected variable node. The minimum value indicates a minimum value of absolute values of log-likelihood values of first variable nodes sharing a check node with the selected variable node and including the selected variable node. The minimum candidate value indicates one from among absolute values of log-likelihood values of second variable nodes that has the smallest value greater than the minimum value. The second variable nodes are selected later than one from among the first variable nodes corresponding to the minimum value.

First claim

What is claimed is:

1. An operating method executed by an error correction decoder within a storage device comprising a nonvolatile memory and the error correction decoder, the method comprising:
receiving data from the nonvolatile memory;
setting initial log-likelihood values of variable nodes depending on the received data; and
decoding the received data by updating a log-likelihood value of a selected variable node by use of a minimum value and a minimum candidate value associated with the selected variable node, wherein:
the minimum value indicates a minimum value of absolute values of log-likelihood values of first variable nodes sharing a check node with the selected variable node and including the selected variable node, and
the minimum candidate value indicates one from among absolute values of log-likelihood values of second variable nodes that is the smallest value greater than the minimum value, and
the second variable nodes are selected later than one from among the first variable nodes that corresponds to the minimum value.

2. The operating method of claim 1 , wherein:
the log-likelihood value of the selected variable node is updated additionally using a minimum value position and a minimum candidate value position,
the minimum value position indicates a position of one from among the first variable nodes that corresponds to the minimum value and is selected last, and
the minimum candidate value position indicates a position of one from among the second variable nodes that corresponds to the minimum candidate value and is selected last.

3. The operating method of claim 2 , wherein the decoding the received data includes detecting the minimum value and the minimum candidate value from the initial log-likelihood values of the first variable nodes when the selected variable node is one from among the first variable nodes that is first updated.

4. The operating method of claim 3 , wherein:
the decoding the received data further includes:
detecting a second minimum candidate value from among absolute values of log-likelihood values of third variable nodes that is the smallest value greater than the minimum candidate value, wherein the third variable nodes are selected later than one from among the second variable nodes that correspond to the minimum candidate value, and
detecting a K-th minimum candidate value from among log-likelihood values of K+1st variable nodes that is the smallest value greater than a K−1st minimum candidate value, wherein the K+1st variable nodes are selected later than one from among K-th variable nodes corresponding to the K−1st minimum candidate value,
K is a positive integer of 3 or more, and
the detecting a K-th minimum candidate value is repeated until the number of the minimum candidate values and the minimum value have different absolute log-likelihood values.

5. The operating method of claim 2 , wherein the decoding the received data includes:
calculating a first message corresponding to the selected variable node using the minimum value, the minimum value position, the minimum candidate value, and the minimum candidate value position;
updating a log-likelihood value of the selected variable node depending on the first message; and
updating the minimum value, the minimum value position, the minimum candidate value, and the minimum candidate value position according to an updating result of the log-likelihood value of the selected variable node.

6. The operating method of claim 5 , wherein the calculating a first message includes:
calculating the minimum candidate value as the first message when a position of the selected variable node is identical to the minimum value position; and
calculating the minimum value as the first message when a position of the selected variable node is different from the minimum value position.

7. The operating method of claim 5 , wherein the updating a log-likelihood value of the selected variable node includes:
calculating a second message associated with another check node to which the selected variable node belongs; and
updating the log-likelihood value of the selected variable node with a value obtained by calculating an initial log-likelihood value of the selected variable node, the first message, and the second message.

8. The operating method of claim 7 , wherein the second message is calculated using log-likelihood values of variable nodes sharing the other check node with the selected variable node and including the selected variable node.

9. The operating method of claim 5 , wherein in the updating the minimum value, the minimum value position, the minimum candidate value, and the minimum candidate value position, the minimum value and the minimum value position are set to have contents of the minimum candidate value and contents of the minimum candidate value position when a position of the selected variable node is identical to the minimum value position.

10. The operating method of claim 9 , wherein:
in the updating the minimum value, the minimum value position, the minimum candidate value, and the minimum candidate value position, when a position of the selected variable node is identical to the minimum value position, the minimum candidate value and the minimum candidate value position are set to have contents of a second minimum candidate value and contents of a second minimum candidate value position, a K-th minimum candidate value and a K-th minimum candidate value position are set to have contents of a K+1st minimum candidate value and contents of a K+1st minimum candidate value position, a last minimum candidate value and a last minimum candidate value position are reset,
K is a positive integer of 2 or more,
the K-th minimum candidate value is one from among absolute values of log-likelihood values of variable nodes that is the smallest value greater than a K−1st minimum candidate value, wherein the variable nodes are selected later than a variable node from among the first variable nodes corresponding to a K−1st minimum candidate value, and
the K-th minimum candidate value position indicates a position of one from among the first variable nodes that is most recently updated and has the K-th minimum candidate value.

11. The operating method of claim 5 , wherein:
in the updating the minimum value, the minimum value position, the minimum candidate value, and the minimum candidate value position, when a position of the selected variable node is identical to the minimum candidate value position, the minimum candidate value and the minimum candidate value position are set to have contents of a second minimum candidate value and contents of a second minimum candidate value position, and
the second minimum candidate value is one from among log-likelihood values of variable nodes that has the smallest value greater than the minimum candidate value, wherein the variable nodes are selected later than the minimum candidate value from among the first variable nodes, and
the second minimum candidate value position indicates a position of one from among the first variable nodes that is most recently updated and has the second minimum candidate value.

12. The operating method of claim 5 , wherein in updating the minimum value, the minimum value position, the minimum candidate value, and the minimum candidate value position, when the updated log-likelihood value of the selected variable node is smaller than or equal to the minimum value, the minimum value is updated with the updated log-likelihood value, the minimum value position is updated with a position of the selected variable node, and the minimum candidate value and the minimum candidate value position are reset.

Assignees

• Shin Dong-Min
• Lee Myungkyu
• Shin Beom Kyu
• Lee Kijun
• Samsung Electronics Co Ltd

Inventors

• Shin Dong-Min
• Lee Myungkyu
• Shin Beom Kyu
• Lee Kijun

Classifications

• G06F11/1012 Primary

  using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence) · CPC title

• H03M13/1122

  storing only the first and second minimum values per check node · CPC title

• H03M13/114

  Shuffled, staggered, layered or turbo decoding schedules · CPC title

• H03M13/6577

  Representation or format of variables, register sizes or word-lengths and quantization · CPC title

• G11C2029/0411

  Online error correction · CPC title