MEMORY CONTROLLER AND DECODING METHOD

• US 20160246603A1
• Filed: 06/18/2015
• Published: 08/25/2016
• Est. Priority Date: 02/20/2015
• Status: Active Grant

• Current Assignee: Kioxia Corporation
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: WATANABE, Daiki, Fujiwara, Daisuke, Yamaki, Ryo
• Granted Patent: US 9,588,772 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields
• CPC Class Codes: G11C 16/26 Sensing or reading circuits; Data output circuits
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/3707 Adaptive decoding and hybrid decoding, e.g. decoding methods or techniques providing more than one decoding algorithm for one code
• CPC Class Codes: H03M 13/451 using a set of candidate code words, e.g. ordered statistics decoding [OSD]
• CPC Class Codes: H03M 13/458 by updating bit probabilities or hard decisions in an iterative fashion for convergence to a final decoding result

Abstract

According to one embodiment, a memory controller includes a decoder configured to perform approximate maximum likelihood decoding, the decoder including: an initial value generation unit configured to calculate first data on the basis of a received word read from a non-volatile memory; a storage unit configured to store the first data and a predetermined number of second data; an update unit configured to calculate new second data by using the predetermined number of second data stored and update the storage unit; an arithmetic unit configured to output an addition result of the first data and the latest second data as decoded word information; and a selection unit configured to select a decoded word with the maximum likelihood on the basis of a plurality of the decoded word information.

Claims

1. A memory controller comprising a decoder configured to perform approximate maximum likelihood decoding of a linear code on a received word, the received word being read from a non-volatile memory,

the decoder including:

a generation unit configured to output a plurality of decoded word information on the basis of the received word, each of the plurality of decoded word information identifying each of a plurality of decoded word being a candidate for a decoded result of the received word; and

a selection unit configured to select a decoded word with the maximum likelihood from among the plurality of decoded words,

the generation unit including;

an initial value generation unit configured to calculate first data on the basis of the received word;

a storage unit configured to store the first data and a predetermined number of second data;

an update unit configured to calculate new second data by using the predetermined number of second data stored in the storage unit and update the predetermined number of second data stored in the storage unit with the new second data; and

an arithmetic unit configured to add the first data and the latest second data stored in the storage unit and output a result of the addition as the decoded word information.

2. The memory controller according to claim 1,

wherein the first data is an addition result of third data calculated on the basis of the received word and fourth data generated on the basis of an index indicating the decoded word to be generated.

3. The memory controller according to claim 1,

wherein the update unit calculates the new second data by using a linear recurrence on the basis of predetermined number of second data stored in the storage unit.

4. The memory controller according to claim 1,

wherein the decoded word information is the decoded word.

5. The memory controller according to claim 1,

wherein the decoded word information is information indicating a difference between the received word and the decoded word.

6. The memory controller according to claim 1,

wherein the linear code is a Bose-Chaudhuri-Hocquenghem code.

7. The memory controller according to claim 1,

wherein the linear code is a Reed-Solomon code.

8. A storage device comprising:

a non-volatile memory;

a memory interface configured to read a received word from the non-volatile memory; and

a decoder configured to perform approximate maximum likelihood decoding of a linear code on the received word,

the decoder including;

a generation unit configured to output a plurality of decoded word information on the basis of the received word, each of the plurality of decoded word information uniquely identifying each of a plurality of decoded word being a candidate for a decoded result of the received word; and

a selection unit configured to select a decoded word with the maximum likelihood from among the decoded words on the basis of the decoded word information,

the generation unit including;

an initial value generation unit configured to calculate first data on the basis of the received word;

a storage unit configured to store the first data and a predetermined number of second data;

an update unit configured to calculate new second data by using the predetermined number of second data stored in the storage unit and update the predetermined number of second data stored in the storage unit with the new second data; and

an arithmetic unit configured to add the first data and the latest second data stored in the storage unit and output a result of the addition as the decoded word information.

9. The storage device according to claim 8,

wherein the first data is an addition result of third data calculated on the basis of the received word and fourth data generated on the basis of an index indicating the decoded word to be generated.

10. The storage device according to claim 8,

wherein the update unit calculates the new second data by using a linear recurrence on the basis of predetermined number of second data stored in the storage unit.

11. The storage device according to claim 8,

wherein the decoded word information is the decoded word.

12. The storage device according to claim 8,

wherein the decoded word information is information indicating a difference between the received word and the decoded word.

13. The storage device according to claim 8,

wherein the linear code is a Bose-Chaudhuri-Hocquenghem code.

14. A decoding method which performs approximate maximum likelihood decoding of a linear code on a received word read from a non-volatile memory, the method comprising:

calculating first data on the basis of the received word;

storing the first data and a predetermined number of second data into a storage unit;

performing second data calculation processing of calculating new second data by using a predetermined number of second data stored in the storage unit;

updating the predetermined number of second data stored in the storage unit with the new second data;

adding the first data and the latest second data stored in the storage unit and outputting an addition result as a decoded word information;

the decoded word information uniquely identifying each of a plurality of decoded words, each of the plurality of decoded words being a candidate for a decoded result of the received word; and

selecting, as a decoded result, a decoded word with the maximum likelihood from among the plurality of decoded words on the basis of a plurality of the decoded word information.

15. The decoding method according to claim 14,

wherein the first data is the sum of third data calculated on the basis of a received word and fourth data generated on the basis of an index indicating the decoded word to be generated.

16. The decoding method according to claim 14,

wherein the second data calculation processing is calculating the new second data by using a linear recurrence on the basis of predetermined number of second data stored in the storage unit.

17. The decoding method according to claim 14,

wherein the decoded word information is the decoded word.

18. The decoding method according to claim 14,

wherein the decoded word information is information indicating a difference between the received word and the decoded word.

19. The decoding method according to claim 14,

wherein the linear code is a Bose-Chaudhuri-Hocquenghem code.

20. The decoding method according to claim 14,

wherein the linear code is a Reed-Solomon code.