1. Flash Memory and Retention Error

NAND flash can be classified into SLC and MLC types. SLC stores one bit in a cell while MLC stores two bits or more in a cell. MLC flash memory cell represents $n$ bits using 2$^{n}$ threshold voltage levels. The voltage level of a flash memory cell is related to the quantity of charged electrons. Furthermore, the encoding of voltage level is different for each flash memory product. Fig. 1 shows the threshold voltage distribution of a flash memory cell. Some MLC products encode each voltage level as shown in Fig. 1. Meanwhile, other flash memory products may adopt entirely different encoding schemes.

Fig. 2. NAND flash organization of (a) SLC and MLC flash memory, (b) floating gate transistor.

A NAND flash memory chip is an array of floating gate transistors. Fig. 2 shows the NAND flash memory cell organization and floating gate transistor structure. A NAND flash is organized as a block-page hierarchy. A page is the basic data unit of flash memory, and each block is composed of multiple pages (e.g., 64 pages = 1 block), which is a group of wordlines. Most of NAND flash products include single plane, which is comprised of multiple blocks. Nowadays, some products are composed of multiple planes to provide a higher storage capacity.

Flash memory stores data in a corresponding page using group of cells on a corresponding bitline that belong to the same wordline group. To store data, charged electrons are trapped in floating gate as shown in Fig. 2(b). SLC flash stores each page to each corresponding wordline, while MLC flash group wordlines into an even group and an odd group and store 2 bits in a single cell. However, data stored in the same location for a long period (e.g., 1 year) could be corrupted due to gradual leakage of charged electrons through the floating gate. This type of data corruption is called retention error ⁽¹⁾, which holds the highest proportion of flash memory error. Leakage of electrons decreases the voltage level close to the threshold voltage of the flash memory cell and can cause the misreading of data. To cope with these errors and to enhance the voltage level sensing precision of overlapping voltage lever, G. Dong et al. ⁽⁸⁾ introduced the usage of soft-decision ECC and non-uniform voltage sensing scheme for NAND flash memory.

Fig. 3. A single iteration of soft-decision LDPC Bit error probability ${P}_{error} : 0 < {P}_{error} < 1$ (${P}_{error} = error$ probability of bit node).

2. Flash Memory and Retention Error

Generally, a flash memory chip uses several error correction techniques (e.g. turbo code, BCH, LDPC) to detect and correct errors ^(2,5). In early lifetime of flash memory, hard-decision BCH code is applied. However, to ensure the longer lifetime and data integrity of high-capacity flash memory (e.g., MLC flash memory), stronger ECC is required. Thus, soft-decision LDPC is adopted to handle the large number of errors that occur in MLC flash memory.

Soft-decision LDPC is an iteration-based block code that uses the soft log-likelihood-ratio (LLR) to determine the value of bit node. LLR is calculated using the bit error probability ${p}_{error}$ (1)as shown in Eqs. (2-4) ^(8,9). During the decoding procedure, the higher bit error probability means that the bit node has more chance of error, therefore makes the bit node to be flipped easily. Its decoding procedure is depicted in Fig. 3. The bit node passes the soft-decision LLR value to the connected check node. Then the check node calculates the next LLR value and transmits the calculated value to connected bit nodes. Then, the check node calculates the next LLR value and transmits the calculated value to connected bit nodes. This is called as iteration of LDPC decoding ⁽¹⁰⁾. After a single iteration, the bit node updates the LLR value to the received LLR value from the connected check node. After iteration, syndrome is calculated by using parity check matrix of ${H}$ and decoded codeword ${c}$. By using Eq. (5), decoder gets the syndrome ${S}$. If the syndrome is 0, iteration is terminated, then data is extracted from codeword. Else, iteration is repeated until the syndrome becomes 0 or the iteration count reaches the maximum limitation of iteration.

Typically, soft-decision LDPC is adopted in flash memory that requires a high correction ability. However, soft-decision LDPC can cause read latency due to its iteration. To handle the latency problem, S.Tanakamaru et al. ⁽⁹⁾ proposed error-prediction LDPC (EP-LDPC) and error recover schemes to reduce read latency and extend data retention time by using an accurate error probability table based on the number of ‘1’s in data, p-e cycle, and stored location (upper or lower page). By using an accurate error probability table during the LDPC decoding, the retention time of stored data is enhanced.

Additional parity bits can also improve the correction ability of ECCs; however, this type of approach requires excessive space overhead. To reduce the overhead, H. Park et al. proposed incremental redundancy (IR) that only reinforces the minimum redundancy ⁽¹¹⁾. IR monitors the retention time of cold data and adaptively assign the minimal number of pages for incremental redundancy after a safe period. Therefore, the retention of cold data and the correction ability of ECC are enhanced.

3. Flash Memory Refresh (reprogramming)

Flash memory operates on an erase-before-program basis due to the features of a flash memory cell. As shown in Fig. 1, a flash memory cell represents data using several voltage levels. A flash memory cell should be erased to program new data if the target cell is once programmed. However. a flash memory cell can be selectively reprogrammed through refresh ⁽⁶⁾. For example, a SLC flash memory cell can be reprogrammed from ‘1’ to ‘0’. In case of MLC flash memory, reprogramming is more restricted than SLC flash memory because an MLC flash memory cell uses four voltage levels to represent data. Thus, reprogramming is only available in the direction of higher voltage level (e.g., from ‘11’ to ‘10’).

To correct the retention error with refresh, a flash-correct-and-refresh (FCR) technique has been studied by Cai et al.⁽⁶⁾. They introduced an in-place reprogramming based on FCR, adaptive-rate FCR, and hybrid FCR mechanism. Hybrid FCR selectively applies refreshing or remapping, based on the bit error rate. The remapping moves the corrupted data, instead of refreshing it. Adaptive-rate FCR refreshes the flash memory cell less frequently for small retention errors. For both cases, refreshing reduces the p-e cycle and enhances the flash memory lifetime. However, unlike the cell-level approach, in-place reprogramming is hard to be achieved at the system-level. As described above, NAND flash memory can be reprogrammed in a direction of higher voltage level at the memory cell level. On the other hand, it is hard to apply reprogramming technique in system-level because data stored in paired pages may change unexpectedly if the paired page is already programmed. Additionally, even if the target page is safe to perform in-place reprogramming, refresh should be performed carefully in system-level. It is noted that if the program operation is abnormally aborted, data stored in a paired page might be damaged ^(16,17). It indicates that not only the data of single page is damaged when program operation is not successful, but also the data stored in paired page may corrupted by unsuccessful program operation.

Generally, MLC flash memory applies incremental step pulse programming (ISPP), which programs upper page first ^(12,13), to properly program the data in both paired page. Thus, unintended interference can occur in the upper page if the reprogramming operation is done in lower page. For example, as shown in Fig. 2(a), data stored in upper page (page 124) might be unintentionally changed when the reprogramming is occurred in lower page (page 118). Therefore, reprogramming should be performed only if the data in both page is not altered by its operation.

1. Reprogramming MLC Flash in System Level

During the lifetime of flash memory, any type of error can occur in the flash memory. According to Cai et al. ⁽¹⁾, some errors can be corrected by refresh. Refresh can reduce the number of errors in a codeword (page), thus the retention time and lifetime of flash memory are extended by reducing the p-e cycle. However, overly frequent refreshing can degrade the lifetime and performance of flash memory. Y. Di et al.proposed a process variation (PV) based refresh minimization scheme for flash memory to reduce the number of refresh operation ⁽⁷⁾.

Although in-place reprogramming has the advantages of extending lifetime and improving performance of flash memory, it can corrupt data stored in paired pages when performed at the system-level, as described in section II-3. Thus, safe in-place reprogramming should be applied to guarantee the data integrity while taking advantages of in-place reprogramming.

To perform the safe in-place reprogramming at system level, the flash memory chips were verified for all available cases where in-place reprogramming is performed. Based on the datasheet of several flash memory products ^(14,17), whole pages in same block are pre-programmed before in-place reprogramming. Then, the data that overwrites ‘00’, ‘01’, ‘10’, ‘11’ to same flash memory cell is overwritten to paired page to verify safe reprogramming operation for each memory chip product.

Fig. 4. State diagram of a reprogramming operation (cell-level) for four MLC flash memory chip products (at the system level).

In this paper, four different NAND flash memory chips have considered. Fig. 4 shows the reprogramming state diagrams of each MLC flash memory product ^(14,17) at the system level. In Fig. 4, each arrow indicates the safe reprogramming operation (in memory cell-level) which does not affect data stored in paired pages while correcting the erroneous bits. Each table at the right side of Fig. 4 indicates the result of reprogramming operation. In Fig. 4(a), it is observed that the data is properly reprogrammed if ‘11’ is preprogrammed in certain memory cell. However, if ‘00’ is preprogrammed, there is no data that can change the state of memory cell by reprogramming. For example, for Fig. 4(d) chip, a reprogrammed value of ‘01’ can be achieved by reprogramming either ‘00’ or ‘10’ when ‘11’ is already stored. Thus, some erroneous bits can be corrected by using the proposed in-place reprogramming at system-level.

Fig. 5. Generating uncorrected error count information during decoding procedure.

As shown in Fig. 4, the reprogramming is restricted to some directions at the system-level. Thus, we propose a safe system level reprogramming scheme for MLC flash memory that considers the operational characteristic of each chip. In Fig. 4(a), system level reprogramming does not disturb the paired page when ‘11’ is overwritten on preprogrammed data. On the other hand, for the Fig. 4(b) chip, reprogramming is more restricted than for the Fig. 4(a) chip. Meanwhile, reprogramming of Fig. 4(d) chip is only available for ‘11’${\rightarrow}$’01’ direction. Thus, system-level reprogramming should be performed using the proper data for each chip.

As a result of proposed in-place reprogramming scheme, correctable retention errors that occurred in stored data can be corrected safely at system level. As a result, only small number of uncorrected errors remain in codeword. Therefore, performance of flash memory is enhanced since LDPC decoder causes less iteration to decode codeword, and lifetime of flash memory is also extended without degrading reliability of stored data.

However, as depicted in Fig. 4, every flash memory product requires different safe reprogramming operation. And the efficiency of reprogramming varies because each flash memory product has different reprogramming result. Nevertheless, still proposed reprogramming method is effective to reduce the amount of retention error. According to M. Zhang et al. ⁽¹⁸⁾, the most common type of retention errors are “00”${\rightarrow}$”01”, “01${\rightarrow}$10”, “01”${\rightarrow}$”11”, and “10”${\rightarrow}$“11”, with their relative percentages over all retention errors being 46%, 44%, 5%, and 2%, respectively. Among these retention errors, “00”${\rightarrow}$”01”, “01”${\rightarrow}$”11”, and “10”${\rightarrow}$”11” are correctable for Fig. 4(a) flash memory chip. Therefore, 53% of retention errors can be corrected for Fig. 4(a) chip. In the same way, 51%, 53%, and 5% of retention errors can be corrected for Fig. 4(b)-(d), respectively.

Fig. 5 shows the procedure to the uncorrected error information for the Fig. 4(a) chip. First, the codeword is read from flash memory and corrected by LDPC ECC. Then, reprogrammable errors are partially corrected to good values through system-level reprogramming. In Fig. 5, errors marked by black rectangles are overwritten by using the reprogram data; however, errors marked by red rectangles are not corrected because reprogramming operations of ”00”${\rightarrow}$”10” and “10”${\rightarrow}$”11” are not available for Fig. 4(a) chip. During this process, the upper page and lower page for a codeword would be read simultaneously, and properly processed by LDPC ECC.

Fig. 6 shows an example of correction procedure with the proposed partial reprogramming scheme for the Fig. 4(a) chip. Two codewords in upper and lower pages are decoded by LDPC ECC and system level reprogramming is performed for both upper and lower page. To correct an erroneous page, ‘1101111111101111’ and ‘1111110111111111’ are overwritten to the same page. Then data stored in the corrected pages is ‘0100101011101011’ and ‘0110010110110110’. It is noted that uncorrectable errors and correct data need to be overwritten with ‘11’ for the Fig. 4(a) chip to avoid the unintended change of data.

2. Utilizing Error Information while LDPC Decoding

After performing the proposed system level in-place reprogramming, each codeword may still contain some uncorrected errors. Using the information about the uncorrected errors, the correction ability and decoding performance of LDPC decoder can be further improved with accurate LLR input values. Precise LLR values for each code is known to be very helpful for improving the decoding performance of soft-decision LDPC ⁽¹⁸⁾.

Fig. 6. System-level reprogramming for a codeword

As shown in Fig. 3, soft-decision LDPC calculates log-likelihood ratio (LLR) with each iteration. The LLR indicates that each bit node is more likely ‘0’ or ‘1’. To calculate the LLR value, the error probability (1)is assigned to Eqs. (2, 3). In proposed decoding scheme, the number of uncorrected errors is given as additional input for decoding to get the precise LLR. In the early lifetime of flash memory, low bit error probability (e.g., 10$^{-7}$) is assigned for decoding. However, a higher bit error probability (e.g., 10$^{-4}$, 10$^{-3}$) is required to handle potentially massive errors after the p-e cycle exceeds a certain level (e.g., 10k p-e cycles). Accordingly, the bit error probability of each bit node is adaptively assigned in proposed scheme.

To improve the performance of LDPC decoding, the number of uncorrected errors after reprogramming is given as additional input of LDPC decoder. The proposed scheme utilizes spare area to indicate the number of uncorrected errors. Each bit of error information area can be marked to ‘0’ to store information about the number of errors in each codeword. The input BER used for decoding is given to decoder based on error information and predetermined BER table. Each input BER is determined as a value between 10$^{-7}$ and 10$^{-4}$, and the value is determined by how many bits are flipped to ‘0’. In Fig. 7, codeword 1 have four uncorrected errors and two bits of uncorrected error count field of codeword 1 are flipped to ‘0’. Then, the input BER (Bit error probability) used for decoding is determined as BER$_{2}$. Likewise, BER$_{3}$ is given as input BER for decoding of codeword 2. However, if the decoding is performed first time, error information cannot be provided to decoder. Therefore, the uncorrected error information is given as input after the first decoding as shown in Fig. 8.

Fig. 7. Decision of input BER (Bit error probability) based on uncorrected error information.

Fig. 8. Flow of proposed decoding scheme and codeword structure.

As shown in Fig. 7 and 8, implementation of proposed scheme requires additional space to indicate the level of error. For example, 1Mbytes of dedicated space (2 byte per page$\times $524,288 pages) is required for 2 Gbyte NAND flash memory chip (4K page$\times $524,288) to store error information when each codeword contains additional 2 bytes of error information field. The space overhead may be different for other NAND flash chips which uses different page size. To implement the proposed scheme, spare area can be considered as dedicated space for storing the additional error information. In general, spare area is reserved area for system usage (e.g., bad block management, garbage collection). However, spare area is not fully utilized during the lifetime of SSDs. Thus, remaining empty space in spare area can be used for implementation of proposed method.

As discussed above, proposed method dynamically assigns the input BER depending on the number of uncorrected errors after performing LDPC decoding and proposed reprogramming scheme. Error prediction ⁽⁹⁾ scheme can also calculate proper input BER value for decoding when the system requests a lot of sequential read. However, its prediction performance is limited when a lot of random read operations occurred in system level. This is because the estimation algorithm of error prediction scheme can only utilize the number of ‘1’s in left and right cell, while it requires additional parameters like BER and number of ‘1’s (initial value and measured value) of lower page, p-e cycle, retention day, and coupling information. These additional parameters for error prediction help to calculate accurate BER value of certain cell, but at the expense of more complex calculation and resulting in longer delay.

On the other hand, the proposed methods can be applied to any systems where both sequential reads and random reads occur frequently. It is because the proposed method only requires the uncorrected error count after decoding codewords and correction of correctable retention errors. Although the proposed method requires additional space to store the uncorrected error information, proposed method reduces the number of error in each codeword and enhances the reliability of stored data. As a result, the proposed method reduces the RBER (Raw bit error rate) and increases the chance of successful decoding of codeword. In addition, low read latency is also achievable by reducing the RBER of flash memory. According to Y. Du et al.⁽²⁵⁾, higher RBER causes longer read latency. Thus, the read latency of flash memory can be further reduced by using the proposed input BER optimization method along with proposed reprogramming scheme.

In some flash memories, spare area can be used instead of using extra space to reduce overhead. However, still some of the uncorrected error information field may contain correctable retention errors. In this case, additional BER information bits are also reprogrammed along with the reprogramming of codewords to prevent the corruption of BER information field. Despite the BER information field has been reprogrammed, this field still may contain some errors which has not been restored by reprogramming. Thus, this field may require ECC to ensure higher reliability of proposed methods. However, the error information field is unlikely to contain multiple bit errors. Thus, among several ECCs, SEC-DED is a feasible solution because it requires less delay and hardware overhead. Since the size of additional BER information field is small (e.g. 8 or 16 bits for 2Gbyte NAND flash memory chip) and reprogramming operation reduces the number of errors, SEC-DED code is strong enough to recover the retention error occurred in error information field.