Memory system and method of controlling non-volatile memory

A memory system of an embodiment includes a memory controller and a non-volatile memory. The memory controller executes error correction encoding on user data received from a host to generate first encoded data, adds the first encoded data to each of one or more pieces of second encoded data, obtained by performing error correction encoding on each of one or more pieces of predetermined data, to generate one or more pieces of third encoded data, obtained by executing error mitigation encoding on the first encoded data, and selects any one piece of encoded data from the first encoded data and the one or more pieces of third encoded data. The non-volatile memory stores the selected encoded data.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is based upon and claims the benefit of priority from Japanese Patent Application No. 2019-027796, filed on Feb. 19, 2019; the entire contents of which are incorporated herein by reference.

FIELD

Embodiments described herein relate genera a memory system.

BACKGROUND

In recent years, the degree of integration of the storage density have increased in storage devices, whereas reliability of one storage element has decreased. In order to maintain practical reliability, many storage devices employ an error correction code (ECC). In the case of a storage element whose reliability changes depending on a pattern of stored information, conversion is sometimes further executed so as to make a pattern less likely to cause an error during writing. Such conversion is called an error mitigation code (ENC) or a constrained code. The error mitigation code can reduce the number of errors, but is generally used together with the error correction code since it is difficult to ensure practical reliability only with the error mitigation code.

DETAILED DESCRIPTION

A memory system of an embodiment includes a memory controller and a non-volatile memory. The memory controller executes error correction encoding on user data received from a host to generate first encoded data, adds the first encoded data to each of one or more pieces of second encoded data, obtained by performing error correction encoding on each of one or more pieces of predetermined data, to generate one or more pieces of third encoded data, obtained by executing error mitigation encoding on the first encoded data, and selects any one piece of encoded data from the first encoded data and the one or more pieces of third encoded data. The non-volatile memory stores the selected encoded data.

Hereinafter, a memory system according to the embodiment will be described in detail below with reference to the attached drawings. Incidentally, the present invention is not limited to the following embodiment.

Hereinafter, it is assumed that the error correction code is a systematic code in which data to be encoded can be clearly distinguished from a redundant part (ECC parity) obtained by the error correction code. Similarly, the error mitigation code is a systematic code in which data to be encoded can be clearly distinguished from a redundant part (EMC flag) obtained by the error mitigation code.

Such error mitigation codes include, for example, asymmetric coding. In the asymmetric coding, when it is determined, based on the numbers of 0 and 1 in a bit sequence of data, that inverting these bits (bit flipping) causes fewer errors, the bits of data are inverted, and information indicating that the bits have been inverted (for example, 1) is written to the EMC flag. Further, when it is determined that errors are reduced in the case of not inverting the bits, the hits of data are not inverted, and information indicating that the bits are not inverted (for example, 0) is written in the EMC flag. The inversion of bits is realized, for example, by calculating exclusive CR with bits having a value of “1” for each bit.

In this manner, the EMC flag is information for identifying processing that has been performed in the error mitigation encoding. As described above, for example, “1” or “0” is set in the EMC flag depending on whether or not the bit has been inverted in the asymmetric coding. Incidentally, a method for setting the EMC flag is not limited thereto, and may be changed according to an error correction code to be applied.

First Embodiment

First, a memory system according to the present embodiment will be described in detail with reference to the drawings.FIG. 1is a block diagram illustrating a schematic configuration example of the memory system according to the present embodiment. As illustrated inFIG. 1, the memory system1includes a memory controller10and a non-volatile memory20. The memory system1is capable of being connected with a host30, andFIG. 1illustrates a state where the memory system1is connected with the host30. The host30may be electronic equipment, for example, a personal computer, a mobile phone, or the like.

The non-volatile memory20is a non-volatile memory that stores data in a non-volatile manner, and is, for example, a NAND flash memory (hereinafter simply referred to as a NAND memory). Although the following description exemplifies a case where a NAND memory is used as the non-volatile memory20, a storage device other than the NAND memory, such as a three-dimensional structure flash memory, a resistive random access memory (ReRAM), or a ferroelectric random access memory (FeRAM), as the non-volatile memory20. Further, it is not essential that the non-volatile memory20be a semiconductor memory, and the present embodiment can be also applied to various storage media other than the semiconductor memory.

The memory system1may be various memory systems including the non-volatile memory20such as a so-called solid state drive (SSD) or a memory card or the like in which the memory controller10and the non-volatile memory20are configured as a single package.

The memory controller10controls write to the non-volatile memory20according to a write request from the host30. Further, the memory controller10controls read from the non-volatile memory20according to a read request from the host30. The memory controller10is a semiconductor integrated circuit configured as, for example, a SoC (System On a Chip). The memory controller10includes a host interface (host I/F)15, a memory interface (memory I/F)13, a control unit11, an encoding unit14, a decoding unit16, and a data buffer12. The host I/F15, the memory I/F13, the control unit11, the encoding unit14, the decoding unit16, and the data buffer12are mutually connected via an internal bus19. Some or all of operations of the respective components of the memory controller10to be described below may be realized by firmware executed by a central processing unit (CPU), or may be realized by hardware.

The host I/F15executes a process according to the interface standard with the host30, and outputs a command, user data to be written, and the like received from the host30to the internal bus19. Further, the host I/F15transmits the user data that has been read from the non-volatile memory20and restored, a response from the control unit11, and the like to the host30.

The memory I/F13performs a write process to the non-volatile memory20based on an instruction of the control unit11. Further, the memory I/F13performs a read process from the non-volatile memory20based on an instruction of the control unit11.

The data buffer12temporarily stores the user data until the memory controller10stores the user data received from the host30the non-volatile memory20. Further, the data buffer12temporarily stores the user data read from the non-volatile memory20until being transmitted to the host30. As the data buffer12, it is possible to use a general-purpose memory, for example, a static random access memory (SRAM), a dynamic random access memory (DRAM), or the like. Incidentally, the data buffer12may be mounted outside the memory controller10without being built in the memory controller10.

The control unit11comprehensively controls various components of the memory system1. In the case of receiving a command from the host30via the host I/F15, the control unit11performs control according to the command. For example, the control unit11instructs the memory I/F13to write the user data and parity to the non-volatile memory20according to the command from the host30. For example, the control unit11instructs the memory I/F13to read the user data and parity from the non-volatile memory20according to the command from the host30.

Further, in the case of receiving the write request of the user data from the host30, the control unit11determines a storage area (memory area) on the non-volatile memory20with respect to the user data to be accumulated in the data buffer12. That is, the control unit11manages a write destination of the user data. An association between a logical address of the user data received from the host30, and a physical address that indicates the storage area on the non-volatile memory20in which the user data is stored, is stored as an address conversion table.

Further, in the case of receiving the read request from the host30, the control unit11converts the logical address designated by the read request into the physical address using the above-described address conversion table, and instructs the memory I/F13to perform reading from the physical address.

In the NAND memory, the write and the read are generally performed in a data unit of a so-called page, and erase is performed in a data unit of a so-called block. In the embodiment, a plurality of memory cells to be connected to the same word line are referred to as a memory cell group. When the memory cell is a single level cell (SLC), one memory cell group corresponds to one page. When the memory cell is a multiple level cell (MLC), one memory cell group corresponds to a plurality of pages. Incidentally, the PLC in the present description includes a triple level cell (TLC) that stores t bits in one memory cell, a quad level cell (QLC) that stores 4 bits in one memory cell, and the like. Further, each memory cell is connected not only to the word line, but also to a bit line. Therefore, each memory cell can be identified by an address that identifies the word line, and an address that identifies the bit line.

The user data transmitted from the host30is transferred to the internal bus19and stored in the data buffer12.

The encoding unit14encodes user data stored in the non-volatile memory20to generate a code word. The encoding unit14includes an ECC encoding unit14aand an error mitigation encoding unit14b. Incidentally, the data to be encoded by the encoding unit14may include control data and the like to be used in the memory controller10in addition to the user data.

The ECC encoding unit14aperforms error correction encoding on the user data stored in the non-volatile memory20. The error mitigation encoding unit14bperforms error mitigation encoding on the data that has been subjected to error correction encoding.

The error mitigation encoding is a process of giving a deviation to a threshold voltage of a memory cell by converting data to be written. Accordingly, cells to be programmed to a threshold voltage, which has bad properties in terms of cell exhaustion and a bit error rate (BER), can be reduced, and cells to be programmed to a threshold voltage having good properties can be increased. The cell exhaustion means an inter-cell interference effect, and exhaustion of memory cells due to write and erase.

For example, the cell exhaustion and PER properties tend to be worse as the threshold voltage is higher in some cases. In such a case, the error mitigation encoding unit14bperforms error mitigation encoding so as to lower an occurrence probability P (Vth) of a memory cell with a high threshold voltage and to increase an occurrence probability P (Vth) of a memory cell with a low threshold voltage.

The decoding unit16decodes reception word read from the non-volatile memory20to restore the user data. The decoding unit16includes an ECC decoding unit16aand an error mitigation decoding unit16b.

The ECC decoding unit16aperforms error correction decoding on the reception word read from the non-volatile memory20. The error mitigation decoding unit16bperforms error mitigation decoding on the data that has been subjected to the error correction decoding.

Next, a write process to the non-volatile memory20according to the present embodiment will be described. The control unit11instructs the encoding unit14to encode user data at the time of writing to the non-volatile memory20. At this time, the control unit11determines a storage location (storage address) of a code word in the non-volatile memory20, and also instructs the memory I/F13of the determined storage location.

The ECC encoding unit14aof the encoding unit14executes error correction encoding on the user data on the data buffer12based on the instruction from the control unit11. Next, the error mitigation encoding unit14breads the user data after having been subjected to the error correction encoding from the data buffer12, and executes error mitigation encoding on the read user data to generate a code word.

As an encoding scheme of the error correction code, for example, an encoding scheme using an algebraic code, such as a Bose-Chaudhuri-Hocquenghem (BCH) code and a Reed-Solomon (RS) code, and an encoding scheme using a code based on a sparse graph such as a low-density parity-check (LDPC) code can be employed. The memory I/F13performs control to store the code word in the storage location on the non-volatile memory20instructed from the control unit11.

Next, a process at the time of reading from the non-volatile memory20of the present embodiment will be described. At the time of reading from the non-volatile memory20, the control unit11designates an address on the non-volatile memory20to instruct the memory I/F13to perform reading. Further, the control unit11instructs the decoding unit16to start decoding. The memory I/F13reads reception word from the designated address of the non-volatile memory20according to the instruction of the control unit11, and inputs the read reception word to the decoding unit16. The ECC decoding unit16aof the decoding unit16executes error correction decoding on the reception word read from the non-volatile memory20. Thereafter, the error mitigation decoding unit16bexecutes error mitigation decoding on the data that has been subjected to the error correction decoding.

Next, flow of encoding and decoding by the memory system1of the present embodiment will be further described.FIG. 2is a diagram for describing the flow of encoding and decoding by the memory system1.

Data201to be encoded is first subjected to error correction encoding by the ECC encoding unit14a. The data that has been subjected to the error correction encoding is subjected to error mitigation encoding by the error mitigation encoding unit14b. Lines211and212inFIG. 2indicate ranges protected by the error mitigation code and the error correction code, respectively. In this manner, according to the present embodiment, all of data202a, an EMC flag202b, and an ECC parity202care protected by both the error mitigation code and the error correction code. The non-volatile memory20stores the data protected in this manner.

At the time of decoding, the reception word read from the non-volatile memory20is passed to the FCC decoding unit16a. The reception word includes data203a, an EMC flag203b, and an ECC parity203c. A mart “x”303dinFIG. 2represents that an error is included in the EMI flag203b.

In the present embodiment, error correction decoding is first executed on the reception word by the ECC decoding unit16a. Data204aand an EMC flag204brepresent data decoded by this error correction decoding. In this example, the error in the EMC flag203bis corrected by the error correction decoding so that the EMC flag204bcontaining no error is obtained. Further, both the data204aand the EMC flag204bare protected by the error mitigation code as illustrated inFIG. 2.

The error mitigation decoding unit16bexecutes error mitigation decoding on the data204aand the EMC flag204b. Since the error included in the EMC flag204bhas been corrected, the error is not amplified. Data205ais data obtained by the error mitigation decoding.

A function to realize the encoding and decoding as illustrated inFIG. 2will be described with reference toFIGS. 3 and 4.FIG. 3is a block diagram illustrating an example of a detailed functional configuration of the error mitigation encoding unit14bof the present embodiment.FIG. 4is a flowchart illustrating an example of flow of an encoding process of the present embodiment.

The ECC encoding unit14aperforms error correction encoding on data301ato be encoded targeting data with an EMC flag301bin which a value indicating that the data is not to be converted by error mitigation encoding has been set (Step S101). When using the asymmetric coding, the ECC encoding unit14aexecutes error correction encoding on the data301aadded with the END flag301bin which “0” indicating that the data is not to be inverted has been set as illustrated inFIG. 3. As a result, the data added with the ECC parity301cis output as encoded data (first encoded data) by the error correction encoding.

The ECC encoding unit14auses an error correction encoding scheme having linearity in common with the error mitigation encoding scheme employed by the error mitigation encoding unit14bfor a finite field of a predetermined order. For example, when using the asymmetric coding, the ECC encoding unit14auses an encoding scheme based on an LDPC code having linearity in a finite field of an order of two. The encoding scheme having the linearity in the finite field of the order of two is not limited to the LDPC code, and for example, a BCH code may be used. Incidentally, a finite field of an order of n will be sometimes described as GF(n) hereinafter. For example, the finite field of the order of two is represented as GF(2).

Further, data set as a unit of error correction encoding and error mitigation encoding will be referred to as a frame hereinafter. A size of a frame (frame size) of the error correction encoding and a frame size of the error mitigation encoding may be the same or different. In the present embodiment, a case where both the sizes are the same will be described.

The entire frame (the data301a, the EMC flag301b, and the ECC parity301c) that has been subjected to the error correction encoding as described above by the ECC encoding unit14ais protected with the error correction.

After the ECC encoding unit14aexecutes the error correction encoding, the error mitigation encoding unit14bexecutes error mitigation encoding on the frame after having been subjected to the error correction encoding. The error mitigation encoding unit14bincludes an addition unit351and a selection unit352.

The addition unit351adds encoded data (second encoded data), obtained by executing error correction encoding on predetermined data, and the encoded data (first encoded data) after having been subjected to the error correction encoding obtained in Step S101to output encoded data (third encoded data) that is an addition result (Step S102).

For example, the predetermined data is data including a value to invert a value of each bit included in encoded data when the encoded data obtained in Step S101is added (for example, data in which all bits are “1”, data311ainFIG. 3). Further, the predetermined data includes a value indicating that data is to be converted by error mitigation encoding, for example, an EMC flag in which “1” is set to indicate that a bit is to be inverted (an EMC flag311binFIG. 3). The encoded data (second encoded data) obtained by executing the error correction encoding on the data set in this manner is data further including an ECC parity311c.

In the example ofFIG. 3, the addition unit331adds the data311ain which all the bits are “1” to a data part (the data301a) of the input frame. As a result, the bits of the data301aare inverted. Further, the addition unit351adds the EMC flag311bin which the bit having the value of “1” has been set, to the EMC flag301b. The addition unit351adds the ECC parity311c, calculated in advance with respect to the data311aand the EMC flag311b, to the ECC parity301c. The addition is, for example, an exclusive OR for each bit. That is, the addition is an addition operation defined by GF(2).

The selection unit352selects and outputs any one of data (a frame) generated by the operation of the addition unit351and the original input frame (encoded data obtained in Step S101) (Step S103). For example, the selection unit352estimates an error occurrence probability of each frame, and selects and outputs a frame with a lower error occurrence probability. Although any method may be used as a method for estimating the error occurrence probability, for example, the following method can be applied.

A frame in which the number of bit values (for example, “1”) having a high error occurrence probability is smaller than the number of bit values (for example, “0”) having a low error occurrence probability is selected as a frame with a low error occurrence probability.

A frame with a fewer bit patterns each having a high error occurrence probability is selected as a frame with a low error occurrence probability. The bit pattern is, for example, a pattern of bits serving as a unit to be written to an MLC. For example, if the memory cell is a TLC, a 3-bit pattern corresponding to data to be written to each memory cell is a bit pattern. More specifically, there are eight bit patterns of “000”, “001”, “010”, “011”, “100”, “101”, “110”, and “111”. When an error occurrence probability for each bit pattern can be calculated, a sum of error occurrence probabilities of bit patterns included in each frame may be obtained, and a frame with the smaller sum may be selected a frame with a low error occurrence probability.

The memory I/F13stores the selected encoded data in the non-volatile memory20(Step S104).

As an example of a configuration in which the error mitigation code is used together with the error correction code, a method of using the error mitigation code is an cuter code and a method of using the error mitigation code as an inner code are conceivable. The method of using the error mitigation code as the outer code is a method of performing error mitigation encoding and then error correction encoding at the time of encoding, and performing error correction decoding and then error mitigation decoding at the time of decoding. The method of using the error mitigation code as the inner code is a method of performing error correction encoding and then error mitigation encoding at the time of encoding, and performing error mitigation decoding and then error correction decoding at the time of decoding.

When the error mitigation code is used as the outer code, data is first subjected to error mitigation encoding. As a result, an error is generally mitigated in the data. Further, depending on the encoding method, it is possible to also mitigate an error of the EMC flag. The error-mitigated data is then subjected to error correction encoding. The ECC parity added at this time is not subjected to an error mitigation process, and thus, has a problem that an error is more likely to occur as compared with the data and the EMC flag.

When the error mitigation code is used as the inner code, the error mitigation process is executed on all of the data, the ECC parity, and the error mitigation code, and thus, error mitigation performance is higher as compared with the case of using the error mitigation code as the outer code. In the case of using the error mitigation code as the inner code, however, there arises a problem that the EMC flag is not protected by the error correction code. For example, error mitigation decoding is performed prior to error correction decoding, but, when an error occurs in the EMC flag, the error is amplified in the stage of the error mitigation decoding. Thus, there is a high possibility that the error correction decoding in the latter stage may fail.

On the other hand, in the present embodiment, even when the error correction code and the error mitigation code are used together, it is possible to suppress the occurrence of the above problems and to execute the error correction with higher accuracy.

That is, the memory system according to the present embodiment can estimate the error occurrence probability using all fields of the data, the EMC flag, and the ECC parity, and select and output the frame with the lower error occurrence probability. In other words, the effect of the error mitigation code is exerted to the entire frame in the present embodiment. Further, in the case of the original input frame (the encoded data obtained in Step S101) in which the output frame is not subjected to bit inversion, the input frame is protected with the error correction, and thus, output frame is protected with the error correction. Further, in the case where the frame in which the output frame has been subjected to bit inversion (the encoded data obtained by Step S102), the output frame is also a code word of the error correction code since data obtained by adding code words of linear codes on GF(2) to each other. That is, even if any frame is selected, the selected frame is in a state where the entire frame has been protected with the error correction.

As described above, the entire data sequence generated by performing the error correction encoding and the error mitigation encoding is protected with the error mitigation and the error correction according to the present embodiment. Since the entire data sequence is error-mitigated, it is possible to reduce errors occurring in the error mitigation code as compared with the case of using the error mitigation code as the outer code. Further, the error correction decoding is first executed at the time of decoding, and the error mitigation, decoding is executed after eliminating the entire error including the EMC flag. Thus, for example, the error amplification at the time of the error mitigation decoding that occurs in the case of using the error mitigation code as the inner code does not occur in the present embodiment.

Next, a case where the frame sizes of the error correction encoding and the error mitigation encoding are different from each other will be described. Hereinafter, a description will be given with an example in which a Hamming code with a frame size of 127 bits and an information length of 120 bits is employed as an error correction code and asymmetric coding with a frame size of 60 bits and an information length of 59 bits is employed as an error mitigation code.FIG. 5is a block diagram illustrating an example of a detailed functional configuration of the error mitigation encoding unit14baccording to such a first modification. In the example ofFIG. 5, two frames of the asymmetric coding (error mitigation code) correspond to one frame of the Hamming code (error correction code).

First, data500aof 118 bits is input to the ECC encoding unit14a. The ECC encoding unit14aadds two “0” bits, as a field501bof an ENC flag, to data501aof 118 bits (the same as the data500a) to make data of 120 bits. The ECC encoding unit14aexecutes error correction encoding using the Hamming code on the 120-bit data, adds a parity bit501cof 7 bits, and outputs a frame of 127 bits.

Next, the error mitigation encoding unit14badds the following three error correction code words prepared in advance to the 127-bit frame obtained by the ECC encoding unit14ato generate four candidates of code words (code word candidates) combined with the original input frame. This addition operation is the addition on GF(2).

Code Word 1: A data part includes data511-1ahaving a value “0” from the first to 59th bits and data511-1bhaving a value “1” from the 60th to 112th bits. As an EMC flag511-1c, “01” is set. This flag indicates that the first to 59th bits are not to be inverted, and the 60th to 118th bits are to be inverted. A parity bit according to the Hamming code with respect to the data part (the data511-1aand the data511-1b) and the EMC flag511-1cis set as a parity bit511-1d.

Code Word 2: A data part includes data511-2ahaving a value “1” from the first to 59th bits and data511-2bhaving a value “0” from the 60th to 118th bits. As an EMC flag511-2c, “10” is set. This flag indicates that the first to 59th bits are to be inverted, and the 60th to 118th bits are not to be inverted. A parity bit according to the Hamming code with respect to the data part (the data511-2aand the data511-2b) and the EMC flag511-2cis set as a parity bit511-2d.

Code Word 3: A data part includes data511-3ahaving a value “1” from the first to 59th hits and data511-3bhaving a value “1” from the 60th to 118th bits. As an EMC flag511-3c, “11” is set. This flag indicates that all the first to 59th bits and the 60th to 112th bits are to be inverted. A parity bit according to the Hamming code with respect to the data part (the data511-3aand the data511-3b) and the EMC flag511-3cis set as a parity bit511-3d.

The error mitigation encoding unit14bof the present modification includes three addition units351-1,351-2, and351-3. The addition units351-1,351-2, and351-3respectively add the above-described Code Words 1, 2, and 3 to the input frame (the data501a, the field501bof the EMC flag, and the parity bit501c).

The selection unit352estimates an error occurrence probability for each of the four code word candidates generated in this manner, and selects and outputs a code word with a lower error occurrence probability. Data including the data502a, the EMC flag502b, and the parity bit502cillustrated inFIG. 5represents the code word selected in this manner.

Incidentally, the error mitigation decoding unit16bcan perform error mitigation decoding on the first to 59th bits and the 60th to 118th bits of the data part by referring to the first bit and the second bit of the EMC flag, respectively.

In this manner, according to the present modification, it is possible to realize the error mitigation protection and the error correction protection for the entire frame even if the frame size of the error correction encoding is different from the frame size of the error mitigation encoding.

Incidentally, the present modification has been described with the example in which one frame of the error correction encoding corresponds to two frames of the error mitigation encoding. The relationship of the frame size of each encoding is not limited thereto. In the case of using another frame size, it is sufficient to use the number of code word candidates according to a difference in frame size of each encoding.

Hereinbefore, the description has been given with the example of using the code having linearity in GF(2) such as LDPC, BCH, and asymmetric coding. The applicable finite field is not limited to GF(2), but the embodiment is also applicable to a finite field of an order other than two as long as both an error correction code and an error mitigation code have linearity for the same finite field.

Hereinafter, a description will be given regarding a modification in the case of using an RS code with a frame size of 256 bytes and an information length of 240 bytes, which has linearity in GF(28), for error correction encoding.FIG. 6is a block diagram illustrating an example of a detailed functional configuration of the error mitigation encoding unit14baccording to such a second modification.

First, data600aof 239 bytes is input to the ECC encoding unit14a. The ECC encoding unit14aadds one “0” byte, as a field601bof an EMC flag, to data601aof 239 bytes (the same as the data600a) to make data of 240 bytes. The ECC encoding unit14aexecutes RS encoding on the 240-byte data, adds an RS code parity601cof 16 bytes, and outputs a frame of 256 bytes.

Next, the error mitigation encoding unit14badds each of 255 error correction code words prepared in advance to the 256-byte frame obtained by the ECC encoding unit14ato generate 256 code word candidates combined with the original input frame. This addition operation is the addition on GF(28).

The 255 error correction code words excluding the original input frame are data in which values of bytes are 1 to 255 (0x01 to 0xFF in hexadecimal), respectively, the value is repeated 240 times, and an RS code parity of 16 bytes is added to each value.

For example, data611-1ainFIG. 6is data of 239 bytes in which a value of each byte is “1”. An EMC flag611-1bis an EMC flag in which a value of each byte is “1”. As an RS code parity611-1c, an RS code parity with respect to the data611-1aand the EMC flag611-1bis set. In the same manner, an error correction code word including data611-2aand an EMC flag611-2bin which a value of each byte is “2”, and an RS code parity611-2cfor these pieces of data is prepared. Further, an error correction code word including data611-255aand an EMC flag611-255bin which a value of each byte is “255”, and an RS code parity611-255cfor these pieces of data is prepared.

The error mitigation encoding unit14bof the present modification includes255addition units351-1to351-255. Each of the addition units351-1to351-255adds one corresponding error correction code word out of the 255 error correction code words to the input frame (the data601a, the field601bof the EMC flag, and the RS code parity601c).

The selection unit352estimates an error occurrence probability for each of the 256 code word candidates generated in this manner, and selects and outputs a code word with a lower error occurrence probability. Data including the data602a, the EMC flag602b, and the RS code parity602cillustrated inFIG. 6represents the code word selected in this manner.

In this manner, it is possible to use various error correction codes such as the RS code as well as the encoding scheme having linearity in GF(2) by employing the error mitigation code in accordance with the finite field in which the error correction code has linearity according to the present modification.

Hereinbefore, the example in which the asymmetric coding is used as the error mitigation code has been described. The applicable error mitigation code is not limited to the asymmetric coding, and any error mitigation code may be used as long as the error mitigation code has linearity in a finite field common to the error correction code to be used. For example, an error mitigation code using a guided scrambling scheme may be used.

In the scheme, for example, a random value (pseudo-random number) generated using a seed is set as a data part, and a plurality of error correction code words obtained by error correction encoding of data in which the seed is set as an EMC flag are prepared using a plurality of the seeds. The error mitigation encoding unit14badds each of the plurality of error correction code words to data, which has been subjected to the error correction encoding, (input frame) obtained by the ECC encoding unit14a. The selection unit552selects and outputs a code word candidate having a lower error occurrence probability from among the plurality of code word candidates combined with the input frame.

Second Embodiment

An error correction code has a property that correction capability increases as a frame size increases. Thus, there is a case where an error correction code with a large frame size is used. Meanwhile, as an error mitigation code encoding scheme, like the asymmetric coding and the guided scrambling scheme described above, there is a scheme in which error occurrence probabilities of plurality of code word candidates are estimated, and a code word estimated to have a lower error occurrence probability is selected.

When such an error mitigation code is encoded according to the configuration of the first modification described above while keeping an encoding rate at a desired value, the number of code word candidates increases exponentially so that an operation scale increases. For example, the frame size of the error correction encoding is twice the frame size of the error mitigation encoding in the first modification, and thus, the number of code word candidates is 22=4. Meanwhile, for example, the number of EMC flags is 10 bits when assuming that a frame size of the error correction code is 1 k bits and an encoding rate of the error mitigation code is 0.99. That is, the number of code word candidates becomes 210=1024, and the operation scale for the addition and selection increases.

Therefore, in the present embodiment, an error correction encoding scheme using a plurality of error correction codes is employed, and the scheme of the first embodiment (or the modification) is applied to one of the plurality of the error correction codes (the error correction code to be applied first). As a result, it is possible to realize the error mitigation encoding for parities of the error correction codes without increasing the operation scale even when the frame size of the error correction encoding is large. Examples of the error correction encoding scheme using the plurality of error correction codes include a multi-dimensional error correction code and a concatenated code.

The multi-dimensional error correction code indicates a scheme in which a symbol, which is at least one or more constituent units of an error correction code, is multiply protected by a plurality of smaller component codes. Further, one symbol is formed of, for example, one bit (an element of a binary filed) or an element of an alphabet such as a finite field other than the binary field.

An example of a two-dimensional error correction code is a product code. The product code has a structure in which each information bit (which may be a symbol) as a constituent unit of a code word is protected by an error correction code in each of a row direction and a column direction.

The concatenated code refers to a scheme in which data encoded with a certain error correction code (an outer code or a first error correction code) is further subjected to encoding with another error correction code (an inner code or a second error correction code).

Hereinafter, a description will be given by exemplifying the case of using the product code.FIG. 7is a block diagram illustrating a schematic configuration example of a memory system according to a second embodiment; and As illustrated inFIG. 7, a memory system1-2of the present embodiment includes a memory controller10-2and the non-volatile memory20. The present embodiment s different from the first embodiment in terms of configurations of an encoding unit14-2in the memory controller10-2(an ECC encoding unit14-2aand an error mitigation encoding unit14-2b) and a decoding unit16-2(an ECC decoding unit16-2aand an error mitigation decoding unit16-2b). The other configurations are the same as those of the first embodiment, and thus, will be denoted by the same reference signs and descriptions thereof will be omitted.

The ECC encoding unit14-2ais different from the ECC encoding unit14aof the first embodiment in terms that error correction encoding is performed using the product code. The error mitigation encoding unit14-2bis different from the error mitigation encoding unit14bof the first embodiment in terms of performing error mitigation encoding on encoded data obtained by error correction encoding in a direction (for example, the row direction) executed first out of error correction encoding in the row direction and error correction encoding in the column direction.

The ECC decoding unit16-2ais different from the ECC decoding unit16aof the first embodiment in terms of performing error correction decoding of the product code. The error mitigation decoding unit16-2bis different from the error mitigation decoding unit16bof the first embodiment in terms of executing error mitigation decoding on the encoded data in a direction of the error mitigation encoding performed by the error mitigation encoding unit14-2b.

FIG. 8is a diagram for describing flow of an encoding process in the case of employing a BCH product code as an error correction code and employing asymmetric coding as an error mitigation code. Encoding with the BCH product code is an encoding scheme in which original data is arrayed in two dimensions, BCH encoding is performed in a row direction to give a row parity, and then, BCH encoding is performed in a column direction to give a column parity.

For example, the ECC encoding unit14-2aarrays input data800ain two dimensions, executes BCH encoding in the row direction first on data including two-dimensionally arrayed data801a(the same as the data800a) and an EMC flag601bin which a value “0” indicating that a bit is not to be inverted has been set, and then, calculates a row parity801c.

Next, the error mitigation encoding unit14-2bexecutes the error mitigation encoding of the first embodiment (or the modification) for each row of the encoded data after having been subjected to the error correction encoding. Data802a, an EMC flag802b, and a row parity802crepresent encoded data output by the error mitigation encoding.

Next, the ECC encoding unit14-2aexecutes BCH encoding in the column direction on the encoded data output by the error mitigation encoding. Data803a, an ENC flag803b, a row parity803c, a column parity803d, a parity803eof the EMC flag, and a column parity803fof the row parity represent encoded data output by the BCH encoding in the column direction.

In this manner, protection with the error mitigation code can be obtained even for the row parity by the BCH code according to the present embodiment. Although the protection with the error mitigation code is not obtained for the column parity by the BCH code, it is possible to ensure high reliability since a frame size of the error correction cede is large. Further, it is possible to execute the error mitigation encoding for each row of the data arrayed in two dimensions even when the frame size is large. Thus, it is possible to avoid an excessive increase in the number of code word candidates and to suppress an increase in operation scale.

Incidentally, the BCH product code may be configured such that a parity is first given in the column direction, and then, a parity is given in the row direction. In this case, the error mitigation encoding may be performed after the BCH encoding in the column direction in which the parity is first given and before the BCH encoding in the row direction.

Further, a component code constituting the product code is not limited to the BCH code, but any code may be used. For example, the LDPC and the RS code (of the second modification) may be used.

Further, in the case of applying the concatenated code, data encoded using an outer code may be subjected to error mitigation encoding, and then, subjected to encoding using an inner code. Error correction codes used for the outer code and the inner code may employ any code.