MEMORY SYSTEM AND METHOD OF CONTROLLING NONVOLATILE MEMORY

• US 20190087265A1
• Filed: 03/12/2018
• Published: 03/21/2019
• Est. Priority Date: 09/15/2017
• Status: Active Grant

• Current Assignee: Kioxia Corporation
• Original Assignee: Toshiba Memory Corporation (Kioxia Corporation)
• Inventors: KIFUNE, Naoko, UCHIKAWA, Hironori, WATANABE, Daiki
• Granted Patent: US 10,452,476 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G11C 2029/0411 Online error correction
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: H03M 13/3905 Maximum a posteriori probability [MAP] decoding or approximations thereof based on trellis or lattice decoding, e.g. forward-backward algorithm, log-MAP decoding, max-log-MAP decoding
• CPC Class Codes: H03M 13/45 Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence
• CPC Class Codes: H03M 13/451 using a set of candidate code words, e.g. ordered statistics decoding [OSD]

Abstract

According to an embodiment, a memory system includes: a test pattern decoding unit that detects an intermediate decoding word from a plurality of test patterns; a Euclid distance calculating unit that calculates a Euclid distance between the intermediate decoding word and a received word; and a maximum likelihood decoding word selecting unit that maintains a maximum likelihood decoding word candidate. In a case where a Euclid distance of the intermediate decoding word is shorter than a Euclid distance of the maximum likelihood decoding word candidate, the maximum likelihood decoding word selecting unit updates the maximum likelihood decoding word candidate by using the intermediate decoding word and the test pattern decoding unit does not execute decoding of a test pattern having no possibility that the Euclid distance of the intermediate decoding word becomes shorter than the Euclid distance of the maximum likelihood decoding word candidate.

Claims

1. A memory system comprising:

a nonvolatile memory;

a soft decision value converting unit that converts a received word read from the nonvolatile memory into a received word having a soft decision value;

a list generating unit that generates a list of a plurality of test patterns for the received word having the soft decision value;

a test pattern decoding unit that detects an intermediate decoding word from the test pattern included in the list;

a Euclid distance calculating unit that calculates a Euclid distance between the intermediate decoding word detected by the test pattern decoding unit and the received word; and

a maximum likelihood decoding word selecting unit that maintains a maximum likelihood decoding word candidate,

wherein, in a case where a Euclid distance of a first intermediate decoding word that is an intermediate decoding word detected by the test pattern decoding unit is shorter than a Euclid distance of the maintained maximum likelihood decoding word candidate, the maximum likelihood decoding word selecting unit updates the maintained maximum likelihood decoding word candidate by using the first intermediate decoding word and outputs the maximum likelihood decoding word candidate that is finally maintained as a soft decision output value, and

the test pattern decoding unit does not execute decoding of a test pattern having no possibility that the Euclid distance of the intermediate decoding word becomes shorter than the Euclid distance of the maximum likelihood decoding word candidate maintained by the maximum likelihood decoding word selecting unit.

2. The memory system according to claim 1, wherein the list generating unit generates the list not including the test pattern having no possibility that a Euclid distance of a code word detected by the test pattern decoding unit is shorter than the Euclid distance of the maximum likelihood decoding word candidate maintained by the maximum likelihood decoding word selecting unit on the basis of an absolute value of the soft decision value of a bit that is a flip target of each of the test patterns.

3. The memory system according to claim 1, further comprising a test pattern reducing unit that deletes a test pattern having no possibility that a Euclid distance of a code word detected by the test pattern decoding unit is shorter than the Euclid distance of the maximum likelihood decoding word candidate maintained by the maximum likelihood decoding word selecting unit from the list on the basis of an absolute value of the soft decision value of a bit that is a flip target of each of the test patterns.

4. The memory system according to claim 1, further comprising a test pattern execution determining unit that skips decoding using the test pattern decoding unit for a test pattern having no possibility that a Euclid distance of a code word detected by the test pattern decoding unit is shorter than the Euclid distance of the maximum likelihood decoding word candidate maintained by the maximum likelihood decoding word selecting unit among the test patterns included in the list generated by the list generating unit on the basis of an absolute value of the soft decision value of a bit that is a flip target of each of the test patterns.

5. The memory system according to claim 2,

wherein the list generating unit generates a list of test patterns that are different for each number of bits to be flipped, and

the test pattern decoding unit sequentially executes decoding from test patterns included in the list having a smaller number of bits to be flipped including a case where the number of bits to be flipped is “

0”

.

6. The memory system according to claim 1, wherein the test pattern decoding unit decodes a test pattern having a bit having low reliability as a flip target with a high priority level among the test patterns included in the list.

7. The memory system according to claim 1, wherein the Euclid distance calculating unit calculates a total sum of absolute values of one or more soft decision values corresponding to a bit flipped by the list generating unit and one or more error bits detected by the test pattern decoding unit as the Euclid distance.

8. The memory system according to claim 2,

wherein the predetermined algorithm is a Chase decoding algorithm, and

the list generating unit, when a correctable number of the code word is t, the number of bits to be flipped is f, and, a is an arbitrary natural number, in a case where the maximum likelihood decoding word selecting unit maintains the maximum likelihood decoding word candidate having a Euclid distance of “

(f+t)a+t+1”

, generates the list not including a test pattern of which an absolute value of the soft decision value of a bit that is a flip target is greater than “

a”

.

9. The memory system according to claim 3,

wherein the predetermined algorithm is a Chase decoding algorithm, and

the test pattern reducing unit, when a correctable number of the code word is t, the number of bits to be flipped is f, and, a is an arbitrary natural number, in a case where the maximum likelihood decoding word selecting unit maintains the maximum likelihood decoding word candidate having a Euclid distance of “

(f+t)a+t+1”

, deletes a test pattern of which an absolute value of the soft decision value of a bit that is a flip target is greater than “

a”

from the list.

10. The memory system according to claim 4,

wherein the predetermined algorithm is a Chase decoding algorithm, and

the test pattern execution determining unit, when a correctable number of the code word is t, the number of bits to be flipped is f, and, a is an arbitrary natural number, in a case where the maximum likelihood decoding word selecting unit maintains the maximum likelihood decoding word candidate having a Euclid distance of “

(f+t)a+t+1”

, skips decoding by using the test pattern decoding unit for a test pattern of which an absolute value of the soft decision value of a bit that is a flip target is greater than “

a”

.

11. The memory system according to claim 2,

wherein the predetermined algorithm is an ordered statistics decoding (OSD) algorithm, and

the list generating unit, in a case where the maximum likelihood decoding word candidate having a Euclid distance of “

c”

is maintained by the maximum likelihood decoding word selecting unit, generates the list not including a test pattern in which a sum of absolute values of soft decision values of bits that are flip targets is larger than “

c”

.

12. The memory system according to claim 3,

wherein the predetermined algorithm is an OSD algorithm, and

the test pattern reducing unit, in a case where the maximum likelihood decoding word candidate having a Euclid distance of “

c”

is maintained by the maximum likelihood decoding word selecting unit, deletes a test pattern in which a sum of absolute values of soft decision values of bits that are flip targets is larger than “

c”

front the list.

13. The memory system according to claim 4,

wherein the predetermined algorithm is an OSD algorithm, and

the test pattern execution determining unit, in a case where the maximum likelihood decoding word candidate having a Euclid distance of “

c”

is maintained by the maximum likelihood decoding word selecting unit, skips decoding using the test pattern decoding unit for a test pattern in which a sum of absolute values of soft decision values of bits that are flip targets is larger than “

c”

.

14. The memory system according to claim 2,

wherein the predetermined algorithm is an OSD algorithm, and

the list generating unit, in a case where the maximum likelihood decoding word candidate having a Euclid distance of “

c”

is maintained by the maximum likelihood decoding word selecting unit, when the correctable number of the code word is t, the number of bits to be flipped is j, and a sum of absolute values of soft decision values of (t+1−

j) bits in order from a bit of which the absolute value of the soft decision value is smallest in the code word is m, generates the list not including a test pattern of which a sum of absolute values of soft decision values of bits that are flip targets is larger than “

c−

m”

.

15. The memory system according to claim 3,

wherein the predetermined algorithm is an OSD algorithm, and

the test pattern reducing unit, in a case where the maximum likelihood decoding word candidate having a Euclid distance of “

c”

is maintained by the maximum likelihood decoding word selecting unit, when the correctable number of the code word is t, the number of bits to be flipped is j, and a sum of absolute values of soft decision values of (t+1−

j) bits in order from a bit of which the absolute value of the soft decision value is smallest in the code word is m, deletes a test pattern of which a sum of absolute values of soft decision values of bits that are flip targets is larger than “

c−

m”

from the list.

16. The memory system according to claim 4,

wherein the predetermined algorithm is an OSD algorithm, and

the test pattern execution determining unit, in a case where the maximum likelihood decoding word candidate having a Euclid distance of “

c”

is maintained by the maximum likelihood decoding word selecting unit, when the correctable number of the code word is t, the number of bits to be flipped is j, and a sum of absolute values of soft decision values of (t+1−

j) bits in order from a bit of which the absolute value of the soft decision value is smallest in the code word is m, skips decoding using the test pattern decoding unit for a test pattern of which a sum of absolute values of soft decision values of bits that are flip targets is larger than “

c−

m”

.

17. The memory system according to claim 1, further comprising a hard decision value converting unit that converts the soft decision output value output from the maximum likelihood decoding word selecting unit into a code word having a hard decision value.

18. A method of controlling a nonvolatile memory, the method comprising:

reading a received word from the nonvolatile memory;

converting the read received word into a received word having a soft decision value;

generating a list of a plurality of test patterns for the received word having the soft decision value;

detecting a first intermediate decoding word from a first test pattern included in the list;

calculating a first Euclid distance between the first intermediate decoding word and the received word;

maintaining the first intermediate decoding word as a maximum likelihood decoding word candidate;

detecting a second intermediate decoding word from a second test pattern included in the list;

calculating a second Euclid distance between the second intermediate decoding word and the received word;

updating the maintained maximum likelihood decoding word candidate by using the second intermediate decoding word in a case where the second Euclid distance is shorter than the first Euclid distance; and

outputting the maximum likelihood decoding word candidate that is finally maintained as a soft decision output value,

wherein a test pattern having no possibility that a Euclid distance of the detected intermediate decoding word becomes shorter than the first Euclid distance is not used in the detection of the second intermediate decoding word.

19. The controlling method according to claim 18, wherein, in the generating of a list, the list is generated not to include the test pattern having no possibility that a Euclid distance is shorter than the Euclid distance of the maximum likelihood decoding word candidate maintained by the maximum likelihood decoding word selecting unit on the basis of an absolute value of the soft decision value of a bit that is a flip target of each of the test patterns.

20. The controlling method according to claim 18, further comprising deleting a test pattern having no possibility that a Euclid distance is shorter than the Euclid distance of the maximum likelihood decoding word candidate maintained by the maximum likelihood decoding word selecting unit from the list on the basis of an absolute value of the soft decision value of a bit that is a flip target of each of the test patterns.