Operating method of flash memory system

Abstract

An operation method of a flash memory system includes reading data stored in a memory device, wherein the data is encoded by units of message blocks each including a row constituent code and a column constituent code by using a block-wise concatenated Bose-Chadhuri-Hocquenghem (BC-BCH) method; performing a hard decision decoding on the read data; determining, when the hard decision decoding fails, a reference voltage for a message block having an error among the message blocks of the read data; and performing a soft decision decoding by using the determined reference voltage.

Claims

1. An operation method of a flash memory system, comprising: reading data stored in a memory device, wherein the data is encoded by units of message blocks each including a row constituent code and a column constituent code by using a block-wise concatenated Bose-Chadhuri-Hocquenghem (BC-BCH) method; performing a hard decision decoding on the read data; determining, when the hard decision decoding fails, a reference voltage for a message block having an error among the message blocks of the read data; and performing a soft decision decoding by using the determined reference voltage, wherein the reference voltage is determined to maximize average numbers of error bits included in bits that are randomly selected among bits having low reliability in the message block having the error, during the soft decision decoding.

2. The operation method of claim 1, wherein the soft decision decoding includes a turbo BC-BCH code decoding.

3. The operation method of claim 2, wherein the turbo BC-BCH code decoding is performed based on a chase decoding.

4. The operation method of claim 1, wherein the reference voltage is determined according to Equation 1.
{circumflex over (x)}=arg max.sub.x E[n.sub.fe|dF],[Equation 1] Wherein {circumflex over (x)} represents the reference voltage, n.sub.fe represents a number of error bits of the message block having an error with a value in the range 0 <n.sub.fe <p, dF represents the message block having an error due to the failed hard decision decoding, E [n.sub.fe |dF]represents the average number of error bits included in the bits that are randomly selected among the bits having low reliability in the message block having an error when the hard decision decoding fails, and p represents the bits that are randomly selected among the bits having low reliability in the message block having an error.

5. The operation method of claim 4, wherein the average number of error bits (E [n.sub.fe |dF]) is determined according to Equation 2. $\begin{array}{cc}\begin{array}{c}E\left[n_{\mathrm{fe}}.Math.\mathrm{dF}\right]=\underset{n_{\mathrm{fe}}}{.Math.}{n}_{\mathrm{fe}}p\left(n_{\mathrm{fe}}.Math.\mathrm{dF}\right)\\ =\underset{n_{\mathrm{fe}}}{.Math.}{n}_{\mathrm{fe}}\underset{n_u}{.Math.}\underset{n_e}{.Math.}\underset{n_{\mathrm{ue}}}{.Math.}\underset{n_{\mathrm{bf}}}{.Math.}p\left(n_u,n_e,n_{\mathrm{ue},}{n}_{\mathrm{fe}},n_{\mathrm{bf}}.Math.\mathrm{dF}\right)\\ =\underset{n_{\mathrm{fe}}}{.Math.}\frac{n_{\mathrm{fe}}}{p\left(\mathrm{dF}\right)}\underset{n_u}{.Math.}\underset{n_e}{.Math.}\underset{n_{\mathrm{ue}}}{.Math.}\underset{n_{\mathrm{bf}}}{.Math.}p\left(n_u,n_e,n_{\mathrm{ue},}{n}_{\mathrm{fe}},n_{\mathrm{bf}},\mathrm{dF}\right)\end{array}p\left(n_u,n_e,n_{\mathrm{ue}},n_{\mathrm{fe}},n_{\mathrm{bf}},\mathrm{dF}\right)=p\left(n_{\mathrm{fe}},\mathrm{dF}.Math.n_u,n_e,n_{\mathrm{ue}},n_{\mathrm{bf}}\right)p(n_{\mathrm{ue}},n_e.Math.n_u,n_{\mathrm{bf}})p\left(n_u.Math.n_{\mathrm{bf}}\right)p\left(n_{\mathrm{bf}}\right)\begin{array}{c}p\left(n_{\mathrm{ue}},n_e.Math.n_u,n_{\mathrm{bf}}\right)=p\left(n_{\mathrm{ue}},n_e.Math.n_u,n_{\mathrm{bf}}{S}_b+n-k-n_u\right)\\ =p\left(n_{\mathrm{ue}},n_{\mathrm{re}}.Math.n_u,n_{\mathrm{bf}}{S}_b+n-k-n_u\right)\end{array}\begin{array}{c}p\left(n_{\mathrm{ue}},n_{\mathrm{re}}.Math.n_u,n_{\mathrm{bf}}{S}_b+n-k-n_u\right)=p\left(n_{\mathrm{ue}},n_{\mathrm{re}}.Math.n_u,n_{\mathrm{tr}}\right)\\ =p\left(n_{\mathrm{ue}}.Math.n_u,n_{\mathrm{tr}}\right)p\left(n_{\mathrm{ue}}.Math.n_u,n_{\mathrm{tr}}\right)\\ =p\left(n_{\mathrm{ue}}.Math.n_u\right)p\left(n_{\mathrm{re}}.Math.n_{\mathrm{tr}}\right)\end{array}p\left(n_{\mathrm{fe}},\mathrm{dF}.Math.n_u,n_e,n_{\mathrm{ue}},n_{\mathrm{bf}}\right)=\frac{\left(\begin{array}{c}{n}_{\mathrm{ue}}\\ n_{\mathrm{fe}}\end{array}\right)\left(\begin{array}{c}{n}_{\mathrm{ue}}-n_u\\ p-n_{\mathrm{fe}}\end{array}\right)}{\left(\begin{array}{c}{n}_u\\ p\end{array}\right)}& \left[\mathrm{Equation}2\right]\end{array}$ Wherein n.sub.u represents the number of bits having low reliability in the message block, n.sub.e represents a number of error bits of the message block, n.sub.ue represents a number of real error bits included in quantized bits of low reliability range in the message block, n.sub.bf represents a number of message blocks having an error among the message blocks, p(n.sub.bf ) represents a probability distribution for the message blocks that failed in the hard decision decoding among the message blocks, p(n.sub.u |n.sub.bf ) represents a probability of bits having low reliability in the message block having the error, S.sub.b represents a number of bits of a single message block, n represents length of the message block to be decoded, k represents a number of bits of the message blocks, n.sub.bf S.sub.b +n.sub.ck.sub.c, n.sub.u represents a number of bits having high reliability included in the message block having an error, n.sub.re represents a number of real error bits included in the quantized bits of the high reliability range in message block, n.sub.tr represents a number of the bits having the high reliability included in the message block, p(n.sub.re |n.sub.tr) represents probability of error bits in the high reliability range, and p(n.sub.ue |n.sub.u) represents a probability of error bits in the low reliability range.

6. The operation method of claim 1, wherein the soft decision decoding is performed by obtaining soft decision information using the determined reference voltage.

7. The operation method of claim 1, further comprising transferring a decoding fail signal to a host when the soft decision decoding fails.

8. The operation method of claim 1, further comprising transferring the read data to a host when the soft decision decoding is successful.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIGS. 1(A) to 1(D) are a diagram illustrating distributions of threshold voltages according to a number of bits stored in a flash memory cell.

(2) FIG. 2 is a diagram for describing a structure of a flash memory.

(3) FIG. 3A is a diagram for describing a block-wise concatenated BCH code that is concatenated in parallel.

(4) FIG. 3B is a diagram for describing a block-wise concatenated BCH code that is concatenated in series.

(5) FIG. 4 is a diagram for describing a block-wise concatenated BCH code that is concatenated in parallel in accordance with an embodiment of the present invention.

(6) FIG. 5 is a flow chart for describing an operation method of a memory system using a block-wise concatenated BCH code in accordance with an embodiment of the present invention.

(7) FIG. 6 is a graph illustrating a binary input addictive white Gaussian noise (BI-AWGN) channel in accordance with an embodiment of the present invention.

(8) FIGS. 7A, 7B and 8 are graphs analysing values according to a change of quantization range and a result of error rates obtained through simulation in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION

(9) Various embodiments will be described below in more detail with reference to the accompanying drawings. The present invention may, however, be embodied in different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete and will fully convey the scope of the present invention to those skilled in the art. The drawings are not necessarily to scale, and in some instances, proportions may have been exaggerated to clearly illustrate features of the embodiments. Throughout the disclosure, reference numerals correspond directly to the like parts in the various figures and embodiments of the present invention. It is also noted that in this specification, connected/coupled refers to one component not only directly coupling another component but also indirectly coupling another component through an intermediate component. In addition, a singular form may include a plural form as long as it is not specifically mentioned in a sentence. It should be readily understood that the meaning of on and over in the present disclosure should be interpreted in the broadest manner such that on means not only directly on but also on something with an intermediate feature(s) or a layer(s) therebetween, and that over means not only directly on top but also on top of something with an intermediate feature(s) or a layer(s) therebetween. When a first layer is referred to as being on a second layer or on a substrate, it not only refers to where the first layer is formed directly on the second layer or the substrate but also to where a third layer exists between the first layer and the second layer or the substrate.

(10) In general, a flash memory device has dies coupled to one another in parallel, and the die has a plurality of memory blocks each of which is a unit of the erase operation. Each memory block has a plurality of pages, which is the unit of the program/read operations. Therefore, the error correction operation is performed per single page. The size of a single page is 1 KB for a single level cell and 4 KB or 8 KB for a multi-level cell, generally.

(11) The flash memory device as a storage device needs high reliability, and thus should operate with very low error rates when working with an error correction code. Also, flash memory devices require limited delay times, limiting the complexity of the encoder and decoder therein, for fast program and read speeds. Additionally, the flash memory device has a limiting ratio of parity bits to the rest of the stored data due to limited storage space for extra data, other than the user data, for storage efficiency. Therefore, as well as high coding rates, for example over 0.9, the error correction code for the flash memory device should have a no error floor, or at least an error floor that is solved with a short delay time and low complexity.

(12) The block-wise concatenated BCH (BC-BCH) code that may be applied to an embodiment of the present invention may include a block as a unit. When the BC-BCH code does not include the block but a bit as a unit for better error correction performance than the conventional BCH code, the BC-BCH code may include a plurality of short length BCH constituent codes.

(13) The short length BCH constituent code has very low error correction performance that may correct 1 or 2 bits due to the high coding rate required for the flash memory device. Therefore, in a flash memory device that is only capable of the hard decision, there may easily be the short length BCH constituent code of the BC-BCH code including the bit as a unit that fails in the error correction, and thus the BC-BCH code including the bit as a unit may have low error correction performance. In this case, the BC-BCH code including the bit as a unit may have improved error correction performance when using additional information. However, there may be relatively longer delay times and higher complexity of the decoding because the additional information is required for every decoding process.

(14) The BC-BCH code that may be applied to an embodiment of the present invention fits the flash memory device. The BC-BCH code may include a small number of long length BCH constituent codes. The long length BCH constituent code has error correction performance for the high coding rate required for the flash memory device. For example, the BC-BCH code may include a long length BCH constituent code capable of correcting 10-bit and 14-bit errors. Therefore, in a flash memory device only capable of the hard decision, there may hardly be any long length BCH constituent code of the BC-BCH code that fails in the error correction, and thus the BC-BCH code including the long length BCH constituent code may have higher error correction performance than the BC-BCH code including the bit as a unit.

(15) The BC-BCH code may fail in decoding by an error block because the BC-BCH code includes the block as a unit. For example, there may be the error floor due to the lower bound. The error floor may occur mainly because of a small numbers of the error blocks.

(16) Hereinafter, an embodiment of the present invention will be described with reference to accompanying drawings.

(17) FIG. 2 is a diagram for describing a structure of a flash memory. Hereinafter, the structure of the flash memory device, unit of encoding/decoding of the error correction code, and an interference channel environment will be described with reference to FIG. 2.

(18) Referring to FIG. 2, the error correction code of the flash memory may be programmed and read by a unit of a single page. A single block may include a plurality of word lines (Word Line 0 to Word Ling N.sub.p-1) as well as bit lines (Bit Line 0 to Bit Line N.sub.b-1). A single word line may be coupled to odd and even bit lines, and may have a plurality of pages according to bits of a single cell. For example, in a multi-level cell for storing 2-bit information, a single word line may be coupled to the odd and even bit lines and may have 2 pages for the least significant bit (LSB) and the most significant bit (MSB) per a single bit line and a total of 4 pages for the odd and even bit lines. As described above, the error correction code of the flash memory device may correct errors of the cells by a unit of the single page.

(19) FIG. 3A is a diagram for describing a BC-BCH code that is concatenated in parallel (i.e., a parallel-concatenated BC-BCH code). FIG. 3B is a diagram for describing a BC-BCH code that is concatenated in series (i.e., a serial-concatenated BC-BCH code).

(20) The block of the BC-BCH code is different from the memory block. The block of the BC-BCH code is a bundle of bits, which are sequentially arranged in line although the block of the BC-BCH code is illustrated as a square in FIGS. 3A and 3B. The BC-BCH code may include a message block and a parity block, or may include a message-parity block, in which the message block is combined with the parity block at the end thereof.

(21) The BC-BCH code may include 2 kinds of the BCH constituent codes: a row BCH constituent code and a column BCH constituent code.

(22) The row BCH constituent code may be the same as the column BCH constituent code in the parallel-concatenated BC-BCH code.

(23) In the serial-concatenated BC-BCH code, the row BCH constituent code may serve as an outer code and the column BCH constituent code may serve as an inner code. A single row BCH constituent code may share a single block of BC-BCH code with a single column BCH constituent code. A single row BCH constituent code may share a single block with each of the column BCH constituent codes. A sing column BCH constituent code may share a single block with each of the row BCH constituent codes.

(24) Both of the row BCH constituent code and the column BCH constituent code are BCH codes. The row BCH constituent code may correct t.sub.r bit-errors in n.sub.r bits having k.sub.r bits of a message to be protected and m.sub.r parity bits. The column BCH constituent code may correct t.sub.c bit-errors in n.sub.c bits having k.sub.c bits of a message to be protected and m.sub.c parity bits. Hereinafter, it is assumed that the amount of data to be protected by the BC-BCH code is k, where k is a natural number.

(25) FIG. 3A is a diagram for describing a block-wise concatenated BCH code that is concatenated in parallel.

(26) Referring to FIG. 3A, the data may correspond to a message matrix the size of which is k.sub.r.sup.Bk.sub.c.sup.B of message blocks B.sub.i,j. A single row BCH constituent code may include k.sub.c.sup.B message blocks and one or more parity blocks. A single column BCH constituent code may include k.sub.r.sup.B message blocks and one or more parity blocks.

(27) For example, the BC-BCH code may include a plurality of message blocks, each of which is n.sub.B bits, as follows. Referring to FIG. 3A, an i.sup.th row BCH constituent code may include the message blocks of the i.sup.th row and the parity blocks of the i.sup.th row, as shown in Equation 1.
C.sub.i.sup.r=[B.sub.i,1 . . . B.sub.i,k.sub.c.sub.BR.sub.i.sup.r][Equation 1]

(28) Referring to FIG. 3A, j.sup.th column BCH constituent code may include the message blocks of the j.sup.th column and the parity blocks of the j.sup.th column, as shown in Equation 2.
C.sub.j.sup.c=[B.sub.i,j . . . B.sub.k.sub.c.sub.b.sub.jR.sub.j.sup.c][Equation 2]

(29) The message length of the row BCH constituent code is shown in Equation 3.
k.sub.r=k/k.sub.r.sup.B=n.sub.Bk.sub.r.sup.B[Equation 3]

(30) The code length of the row BCH constituent code is shown in Equation 4.
n.sub.r=k.sub.r+m.sub.r[Equation 4]

(31) The message length of the column BCH constituent code is shown in Equation 5.
k.sub.c=k/k.sub.c.sup.B=n.sub.Bk.sub.r.sup.B[Equation 5]

(32) The code length of the column BCH constituent code is shown in Equation 6.
n.sub.c=k.sub.c+m.sub.c[Equation 6]

(33) The code rate of the BC-BCH code is shown in Equation 7.

(34) $\begin{array}{cc}R=\frac{k}{\left(k+m_r{k}_r^B+m_c{k}_c^B\right)}& \left[\mathrm{Equation}7\right]\end{array}$

(35) In the above case, a single message block may include n.sub.B=k/(k.sub.r.sup.Bk.sub.c.sup.B) bits, which is the same as the other message blocks.

(36) When interleaving in order for each row BCH constituent code to have a different size of message block from the other row BCH constituent code, while all the message blocks in a same row of BCH constituent code have the same size, row i.sup.th BCH constituent code may include the message blocks of the i.sup.th row and the parity blocks of the i.sup.th row, as shown as Equation 1, and j.sup.th column BCH constituent code may include the message blocks of the j.sup.th column and the parity blocks of the j.sup.th column, as shown as Equation 8.
C.sub.j.sup.C=[B.sub.1f(j)B.sub.2f(j+1) . . . B.sub.k.sub.r.sub.B.sub.f(j+k.sub.r.sub.B.sub.1)R.sub.j.sup.c], where f(x)={(x1) mod k.sub.c.sup.B}+1[Equation 8]

(37) FIG. 3B is a diagram for describing a block-wise concatenated BCH code that is concatenated in series.

(38) Referring to FIG. 3B, the data may be assigned to the message block, and the last block of each row BCH constituent code may be the parity block for the row BCH constituent code or the message-parity block for the row BCH constituent code. Except for the parity block for the column BCH constituent code, the message matrix may have the size of k.sub.r.sup.Bk.sub.c.sup.B of message blocks B.sub.i,j and include the message block, the message-parity block for the row BCH constituent code, and an extra parity block in each row. A single row BCH constituent code may include k.sub.c.sup.B-1 number of message blocks and a single message-parity block. A single column BCH constituent code may include k.sub.r.sup.B number of message blocks or the message-parity blocks and a single parity block. The serial-concatenated BC-BCH code may be designed so that the row BCH constituent code may correct more errors than the column BCH constituent code may correct (t.sub.rt.sub.c).

(39) For example, the serial-concatenated BC-BCH code may be designed so that each of the message blocks and the message-parity blocks may include n.sub.B bits as follows. Referring to FIG. 3B, i.sup.th row BCH constituent code may include the message blocks and the parity blocks of i.sup.th row as shown above in Equation 1.

(40) Referring to FIG. 3B, i.sup.th column BCH constituent code may include the message blocks and the parity blocks of j.sup.th column as shown as equation 9 when 1jk.sub.c.sup.B.
C.sub.j.sup.c=[B.sub.i,j . . . B.sub.k.sub.r.sub.B.sub.jR.sub.j.sup.c][Equation 9]

(41) The j.sup.th column BCH constituent code may include the message blocks and the parity blocks of j.sup.th column as shown as Equation 10 when j=k.sub.c.sup.B.
C.sub.j.sup.c=[{B.sub.i,j,R.sub.i.sup.c} . . . {B.sub.k.sub.r.sub.B.sub.j,R.sub.k.sub.r.sub.B.sup.r}R.sub.j.sup.c][Equation 10]

(42) The length of the message of the re BCH constituent code may be represented as shown in Equation 11.
k.sub.r=k/k.sub.r.sup.B[Equation 11]

(43) The length of the code of the row BCH constituent code may be represented as shown in Equation 12.
n.sub.r=k.sub.r+m.sub.r=n.sub.Bk.sub.c.sup.B[Equation 12]

(44) The length of the message of the column BCH constituent code may be represented as shown in Equation 13.
k.sub.c=n.sub.Bk.sub.r.sup.B[Equation 13]

(45) The length of the code of the column BCH constituent code may be represented as shown in Equation 6.

(46) The code rate of the serial-concatenated BC-BCH code may be represented as above-described Equation 7.

(47) In the serial-concatenated BC-BCH code, each of the message blocks and the message-parity blocks has the same number of bits, which is represented as n.sub.B=(k+m.sub.rk.sub.r.sup.B)/(k.sub.r.sup.Bk.sub.c.sup.B)=n.sub.r/k.sub.c.sup.B.

(48) When interleaving, in order for each row BCH constituent code to have different sizes of message blocks from the other row BCH constituent code, while all the message blocks in a single row BCH constituent code have the same size, the row BCH constituent code and the column BCH constituent code may be represented similarly to the above-described Equations 1 and 8, respectively.

(49) For convenience, the parallel-concatenated BC-BCH code will be described hereinafter. However, the description will be applied to the serial-concatenated BC-BCH code.

(50) FIG. 4 is a diagram of a parallel-concatenated BC-BCH code in accordance with an embodiment of the present invention.

(51) The decoding according to the BC-BCH code is an iterative decoding by which the row BCH constituent code and the column BCH constituent code are alternately decoded. When such iterative decoding fails, new information from an iterative hard decision that is very similar to the result from the soft decision may be transferred to the decoder and the decoder may perform the chase decoding. The new information transferred to the decoder may be limited to decoding-failed parity blocks like the failed message block.

(52) FIG. 4 shows the failed BC-BCH code due to a decoding fail of a pair of BCH constituent codes. FIG. 4 exemplarily shows a decoding fail of each of 2.sup.nd row BCH constituent code and 2.sup.nd column BCH constituent code after iterations of the hard decision decoding.

(53) The decoding error rate of the BC-BCH code is very low because the error correction capability of the BCH constituent code of the BC-BCH code is greater than the product code. Therefore, when the BCH constituent code of the BC-BCH code succeeds in decoding, all of the errors are corrected. When the decoding fails due to an error message block, since the BC-BCH code includes blocks, the decoding may be retried by reading again the message block having the error. However, as described above, re-reading the page that has been read requires higher complexity and decoding delay time. Therefore, it is important to improve the performance through the result of the hard decision decoding without re-reading the message block.

(54) FIG. 5 is a flow chart for describing an operation method of a memory system using the BC-BCH code in accordance with an embodiment of the present invention.

(55) Before describing the operation method with reference to FIG. 5, a prior condition will be described with reference to FIG. 6. The prior condition is the single level cell (SLC) that stores a single bit. However, the prior condition may expand to the multi-level cell (MLC), the triple-level cell (TLC) and so forth.

(56) Also, the prior condition assumes that the soft information is 2-bit quantized information through 3 read times of a flash memory. That is, the prior condition assumes that each of information stored as 0 and 1 is read with the 2-level reliability information. Referring to FIG. 6, there may 4 channel outputs when 1.sup.st to 3.sup.rd reference voltages are set to 0, and , respectively. may be the optimal reference voltage. When read by the reference voltages, bits located between and may be determined to have low reliability and thus may be included in n.sub.u numbers of bits while bits located outside of and may be determined to have high reliability and thus may be included in n.sub.r numbers of bits.

(57) Especially for the soft decision decoding, or for the decoding through the turbo BC-BCH code, among the constituent codes (the row BCH constituent code and the column BCH constituent code) included in the BC-BCH code, p number of bits having the lowest reliability may be selected and may be flipped with the 2.sup.p numbers of cases according to the chase decoding. Each of the n.sub.u numbers of bits having low reliability may have small absolute values of the likelihood ratio between being 0 and 1.

(58) When the n.sub.u numbers of bits having the low reliability are greater than p, p numbers of bits may be randomly selected among the n.sub.u numbers of bits having the low reliability. In general, when the n.sub.u numbers of bits having the low reliability are smaller than p, there may be high probability that n.sub.r numbers of bits having the high reliability are included in the selected p numbers of bits. That is, the performance of the decoder may not be improved through the chase decoding because there is low probability that the n.sub.r numbers of bits having the high reliability have errors. That is, the performance of the decoder may be improved when the quantization range is sufficiently wide and thus the n.sub.u numbers of bits having the low reliability are greater than p. Therefore, it can be assumed that the n.sub.u numbers of bits having the low reliability are greater than p (n.sub.u>p).

(59) Referring to FIG. 5 at step S501 a controller may read data from the memory block of the flash memory device by using a read voltage.

(60) At step S503, the controller may perform the hard decision decoding on the data read from the memory block for the error detection and the error correction. At step S505, the controller may determine whether the hard decision decoding is successful.

(61) When the hard decision decoding is determined to be successful as a result of step S505, the controller may transfer the read data to a host.

(62) However, the hard decision decoding may not correct the error.

(63) When the hard decision decoding is determined to fail as the result of step S505, the controller may obtain the location and the number of error blocks from the failed result of the hard decision decoding at step S507. That is, the controller may obtain the location and the number of the error blocks from the failed result of each of row and column BCH constituent codes included in the BC-BCH code.

(64) At step S509, the controller may determine the optimal reference voltage using the location and number of the error blocks obtained at step S507 for maximizing the average number of error bits during the decoding with the turbo BC-BCH code or the chase code.

(65) That is, when iteration ends during the hard decision decoding of the BC-BCH code, the controller may determine whether the hard decision decoding is successful, and may perform the soft decision decoding or the chase decoding when the hard decision decoding is determined to have failed. To improve performance of the chase decoding, the p numbers of bits having the lowest reliability, which are selected among the n.sub.u numbers of bits having low reliability, should include a lot of error bits when the decoding is performed with the BCH constituent code. In this situation, there may be a lot of error bits to be flipped and the success probability of the decoding with the BCH constituent code may be elevated during the chase decoding, and the performance of the decoding through the turbo BC-BCH code may be improved.

(66) That is, the optimal reference voltage should be determined so that the p numbers of bits having the lowest reliability that are selected among the n.sub.u numbers of bits having low reliability include a lot of error bits. Therefore, the optimal reference voltage should be determined so that n.sub.fe number of the error bits included in the p number of bits having the lowest reliability that are selected among the n.sub.u numbers of bits having low reliability may be maximized on average while the p number of bits having the lowest reliability that are selected among the n.sub.u numbers of bits having low reliability may be flipped, which is represented in Equation 14.
{circumflex over (x)}=arg max.sub.x E[n.sub.fe|dF][Equation 14]

(67) E[n.sub.fedF] represents the average number of error bits included in the bits that are randomly selected among the bits having low reliability in the message block having the errors when the hard decision decoding fails. dF the failed case of the hard decision decoding. {circumflex over (x)} represents the reference voltage to be determined. When {circumflex over (x)} is determined, the reference voltages may be {{circumflex over (x)}, 0, {circumflex over (x)}} for 3 times of the soft reads.

(68) The number of error bits included in the BCH constituent code may be represented as n.sub.e, the number of real error bits included in the quantized bits of the low reliability range in the BCH constituent code may be represented as n.sub.ue, the number of the decoding-failed message blocks included in the BCH constituent code during the iterative hard decision decoding may be represented as n.sub.bf, and E[n.sub.fe|dF] may be represented as shown in Equation 15.

(69) $\left[\mathrm{Equation}15\right]$$\begin{array}{c}E\left[n_{\mathrm{fe}}.Math.\mathrm{dF}\right]=\underset{n_{\mathrm{fe}}}{.Math.}{n}_{\mathrm{fe}}p\left(n_{\mathrm{fe}}.Math.\mathrm{dF}\right)\\ =\underset{n_{\mathrm{fe}}}{.Math.}{n}_{\mathrm{fe}}\underset{n_u}{.Math.}\underset{n_e}{.Math.}\underset{n_{\mathrm{ue}}}{.Math.}\underset{n_{\mathrm{bf}}}{.Math.}p\left(n_u,n_e,n_{\mathrm{ue},}{n}_{\mathrm{fe}},n_{\mathrm{bf}}.Math.\mathrm{dF}\right)\\ =\underset{n_{\mathrm{fe}}}{.Math.}\frac{n_{\mathrm{fe}}}{p\left(\mathrm{dF}\right)}\underset{n_u}{.Math.}\underset{n_e}{.Math.}\underset{n_{\mathrm{ue}}}{.Math.}\underset{n_{\mathrm{bf}}}{.Math.}p\left(n_u,n_e,n_{\mathrm{ue},}{n}_{\mathrm{fe}},n_{\mathrm{bf}},\mathrm{dF}\right)\end{array}$

(70) It is difficult to directly draw the probability p(n.sub.u, n.sub.e, n.sub.ue, n.sub.fe, n.sub.bf, n.sub.bf, dF), and thus the probability p(n.sub.u, n.sub.e, n.sub.ue, n.sub.fe, n.sub.bf, dF) may be represented as Equation 16 when using the characteristics of the conditional probability.
p(n.sub.u, n.sub.e, n.sub.ue, n.sub.fe, n.sub.bf, dF)=p(n.sub.fe, dF|n.sub.u, n.sub.e, n.sub.ue, n.sub.bf)p(n.sub.ue, n.sub.e|n.sub.u, n.sub.bf)p(n.sub.u|n.sub.bf)p(n.sub.bf)[Equation 16]

(71) Each term of Equation 16 will be described hereinafter. E[n.sub.fe|dF] may be represented as the function of the reference voltage due to each term and {circumflex over (x)} may be determined.

(72) When the probability of n.sub.u number of bits having low reliability is defined as p.sub.u and the number of bits included in a single block is defined as S.sub.bfp(n.sub.u|n.sub.bf) may follow the binominal distribution of B(n.sub.bfS.sub.b+n.sub.ck.sub.c, n.sub.u, p.sub.u). n.sub.ck.sub.c may have the same size as the parity block included in the BCH constituent code and may be replaced with above-described m.sub.c. Also, the binominal distribution may be defined as B(n.sub.bfS.sub.b+n.sub.ck.sub.c, n.sub.u, p.sub.u). Referring to FIG. 6, the probability p.sub.u of the n.sub.u numbers of bits having low reliability may be determined through the characteristics of the Gaussian distribution.

(73) The length n of the BCH constituent code for the decoding, and k number of message bits of the BCH constituent code may not be the probability variables. Also, when the number of real error bits included in the quantized bits of the high reliability range in the BCH constituent code is defined as n.sub.re, it may be true that n.sub.re+n.sub.ue=n.sub.e. Then, p(n.sub.u, n.sub.e|n.sub.ue, n.sub.bf) may be represented as Equation 17.
p(n.sub.ue, n.sub.e|n.sub.u, n.sub.bf)=p(n.sub.ue, n.sub.e|n.sub.u, n.sub.bfS.sub.b+nkn.sub.u)
=p(n.sub.ue, n.sub.re|n.sub.u, n.sub.bfS.sub.b+nkn.sub.u)[Equation 17]

(74) When the n.sub.u numbers of bits having low reliability and n.sub.bfS.sub.b+nkn.sub.u number of bits having high reliability in the BCH constituent code for the decoding are given, there may be n.sub.ue number of bits only in the n.sub.u number of bits having low reliability and there may be n.sub.re number of bits only in the n.sub.bfS.sub.b+nkn.sub.u number of bits having high reliability. Therefore, when the n.sub.u number of bits having low reliability and n.sub.bfS.sub.b+nkn.sub.u number of bits having high reliability in the BCH constituent code for the decoding are given, the n.sub.ue number of bits and the n.sub.re number of bits may be the conditional independence. The reason why the number of bits having high reliability is represented as n.sub.bfS.sub.b+nkn.sub.u is because the part of the BCH constituent code to be really soft-decision decoded is limited to the sum (n.sub.bfS.sub.b+n.sub.Ck.sub.C) of lengths of the message blocks and the parity blocks that failed in the hard decision decoding, and all of the bits are determined to have low or high reliability.

(75) Therefore, when the n.sub.bfS.sub.b+nkn.sub.u number of bits having high reliability among the bits of the BCH constituent code is defined as n.sub.tr, Equation 17 may be represented as Equation 18.
p(n.sub.ue, n.sub.re|n.sub.u, n.sub.bfS.sub.b+nkn.sub.u)=p(n.sub.ue, n.sub.re|n.sub.u, n.sub.tr)=p(n.sub.ue|n.sub.u, n.sub.tr)p(n.sub.u, n.sub.tr)=p(n.sub.ue|n.sub.u)p(n.sub.re|n.sub.tr)[Equation 18]

(76) When the probability of error in the high reliability range is defined as p.sub.re and the probability of error in the low reliability range is defined as p.sub.ue, p(n.sub.re|n.sub.tr) may be represented as the binominal distribution of B(n.sub.tr, n.sub.re, p.sub.re) and p(n.sub.ue|n.sub.u) may be represented as the binominal distribution of B(n.sub.u, n.sub.ue, p.sub.ue). The probability p.sub.re and the probability p.sub.ue may be obtained from the Gaussian distribution shown in FIG. 6.

(77) The probability p(n.sub.fe, dF|n.sub.u, n.sub.e, n.sub.ue, n.sub.bf) may be represented as Equation 19 because n.sub.up.

(78) $\begin{array}{cc}p\left(n_{\mathrm{fe}},\mathrm{dF}.Math.n_u,n_e,n_{\mathrm{ue}},n_{\mathrm{bf}}\right)=\frac{\left(\begin{array}{c}{n}_{\mathrm{ue}}\\ n_{\mathrm{fe}}\end{array}\right)\left(\begin{array}{c}{n}_{\mathrm{ue}}-n_u\\ p-n_{\mathrm{fe}}\end{array}\right)}{\left(\begin{array}{c}{n}_u\\ p\end{array}\right)}& \left[\mathrm{Equation}19\right]\end{array}$

(79) n.sub.fe may have a value in the range 0n.sub.fep, and the number of remaining error bits should be greater than the error correction capability of the BCH constituent code for the decoding. This is basically because the failure probability of the hard decision decoding should be determined. p(n.sub.bf) is the probability distribution for the decoding-failed blocks in the BCH constituent code. To obtain p(n.sub.bf) after the hard decision decoding, the probability distribution for the number of error message blocks when the hard decision decoding fails. However, it is difficult to obtain the probability distribution for the numbers of error message blocks. Therefore, the distribution for the number of error message blocks in the row BCH constituent code after the soft decision decoding may be replaced through the distribution for the number of column BCH constituent codes that fail in the hard decision decoding.

(80) When a raw bit error rate (BER) of the NAND flash memory device is defined as p.sub.e, probability p(d.sub.cf) of decoding failure of the column BCH constituent code and probability p(n.sub.bf) that is approximated to the probability of the number of decoding-failed column BCH constituent codes being n.sub.bf may be represented as Equation 20.

(81) $\begin{array}{cc}\begin{array}{c}p\left(d_{\mathrm{cf}}\right)={}_{i=t_c+1}^{n_c}\left(\begin{array}{c}{n}_c\\ i\end{array}\right){p_e^i\left(1-p_e\right)}^{n_c-i}\\ p\left(n_{\mathrm{bf}}\right)\left(\begin{array}{c}\frac{k}{S_b}\\ n_{\mathrm{bf}}\end{array}\right){p\left(d_{\mathrm{cf}}\right)}^{n_{\mathrm{bf}}}{\left(1-p\left(d_{\mathrm{cf}}\right)\right)}^{\frac{k}{S_b}-n_{\mathrm{bf}}}\end{array}& \left[\mathrm{Equation}20\right]\end{array}$

(82) t.sub.c may represent the error correction capability of the column BCH constituent code or the BCH constituent code for next decoding.

(83) As described above, the probability such as p(n.sub.fe, dF|n.sub.u, n.sub.e, n.sub.ue, n.sub.bf), p(n.sub.u, n.sub.e|n.sub.ue, n.sub.bf), p(n.sub.ue|n.sub.bf), p(n.sub.bf) for obtaining E[n.sub.fe|dF] may be obtained through utilization of the probabilities p.sub.u, p.sub.ue, p.sub.r, p.sub.re, p.sub.e for the binominal distribution, which may be represented as the function of the quantization range x as shown in FIG. 6. When the Binary Additive White Gaussian Noise (BI-AWGN) is assumed and the variance of the noise is represented as .sup.2, the probabilities may be represented as Equation 21.

(84) $\begin{array}{cc}\begin{array}{c}{p}_u=Q\left(\frac{1-x}{}\right)-Q\left(\frac{1+x}{}\right)\\ p_{\mathrm{ue}}=\frac{Q\left(\frac{1}{}\right)-Q\left(\frac{1+x}{}\right)}{p_u}\\ p_r=1-p_u\\ p_{\mathrm{re}}=Q\left(\frac{1+x}{}\right)/p_r\\ p_e=Q\left(\frac{1}{}\right)\end{array}& \left[\mathrm{Equation}21\right]\end{array}$

(85) Therefore, the optimal reference voltage may be determined by changing the reference voltage that is the quantization range, detecting the error bits when the hard decision decoding fails, and determining the reference voltage for maximizing the average number of error bits.

(86) Referring back to FIG. 5, at step S511, the controller may obtain soft decision information according to the optimal reference voltage obtained at step S509. The soft decision information may be obtained by performing the chase decoding.

(87) At step S513, the memory controller may perform the soft decision decoding according to the soft decision information obtained at step S511. At step S515, the controller may determine whether the soft decision decoding is successful.

(88) When the soft decision decoding is determined to fail as a result of the step S515, the read operation to the memory cell of the memory block may be finally determined to fail at step S517. That is, the controller may transfer a decoding fail signal to the host when the soft decision decoding fails.

(89) When the soft decision decoding is determined to be successful as the result of the step S515, the controller may transfer the soft-decision decoded data to the host.

(90) FIGS. 7A, 7B and 8 are graphs illustrating analysing values according to a change of quantization range and a result of error rate obtained through simulation iii accordance with an embodiment of the present invention.

(91) FIGS. 7A, 7B and 8 show a result of performance simulation of the BC-BCH code (36568, 32768) including 38 numbers of the row BCH constituent code and 38 numbers of the column BCH constituent code.

(92) Referring to FIGS. 7A and 7B, the simulation is taken under the assumption of a raw BER of 0.0085 and a Binary Additive White Gaussian Noise (BI-AWGN) channel. FIG. 7A shows the quantization range of 0.1 where E[n.sub.fe|dF] is maximized or the average number of the error bits is maximized. FIG. 7B also shows the quantization range of 0.1 around which the error rate is minimized.

(93) FIG. 8 shows a comparison result between the quantization methods of the conventional technology and an embodiment of the present invention.

(94) FIG. 8 shows comparison result of decoding performance of the soft decision decoding with the BC-BCH code between different read operations to the flash memory device. Referring to FIG. 8, it may be seen that the decoding performance of the BC-BCH code depends on the method of determination of the reference voltage. The conventional quantization methods compared with the embodiment of the present invention are (1) maximizing mutual information and (2) quantization methods where the product of the probability of the low reliability range and the BCH constituent code is the number of flipped bits (probabilistic approach).

(95) Referring to FIG. 8, the quantization method that has most similar decoding capability to the soft decision decoding (using soft information) is the quantization method proposed according to the embodiment of the present invention (proposed algorithm). It may be seen that the similar decoding capability to the soft decision decoding is achieved even though 3 times of data read according to the determined reference voltages.

(96) While the present invention has been described with respect to the specific embodiments, it will be apparent to those skilled in the art that various changes and modifications may be made without departing from the spirit and scope of the invention as defined in the following claims.