Method of facilitating reliable access of flash memory

A method of facilitating reliably accessing flash memory is provided. During the write-in process, the present invention utilizes the steps of coding write-in data to generate extra data, and then generating the first error correction code by performing an error-correcting operation on the write-in data and the extra data. Finally, store the N write-in data and the generated K extra data into the data area and the first ECC into the spare area. During read process, the present invention utilizes the steps of reading data from the data area of the target flash-memory page to generate the second ECC, counting with the counter a number of bit differences between the first ECC and the second ECC, and selecting M data from the N write-in data and the K extra data as decoding factors to retrieve the N write-in data. The higher the counter values, the lower the likelihood the corresponding bit is selected to be retrieved.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a method capable of facilitating reliably accessing flash memory, and more particularly, a method capable of facilitating reliably accessing flash memory by coding on writing process, decoding on reading process and comparing the first and the second error correction codes.

2. Description of the Related Art

Flash memory is widely used in a computer host or consumer electronic products, such as USB portable devices, MP3 players. However, considering the present technology, flash memory block may fail to access when in excess of 100,000 times of erasures and the block is considered to be worn out.

On account of a limited life of flash memory, it is an important subject to accurately read out data when some flash-memory block is worn out. There are two kinds of resolutions: One resolution utilizes improvements of hardware to facilitate the reliability of flash memory; the other resolution is to correct errors by means of Error Correction Code (ECC), yet this is limited to the size of spare area of flash-memory page. Regarding a page of 512 bytes, a 24-bit ECC is essential for detection of 2 bits error, and correction of 1 bit error. That is, few bits are allowed to be erred, thereby restricting the ability to error-correcting, and reliability and efficiency of data access.

As shown inFIG. 1depicting a structure of a conventional flash-memory page, when data Al is written into data area A2, an ECC A3is simultaneously stored into the spare area A4. It is more unreliable for such structure for use in a Multi-Level Cell (MLC) flash memory. Despite a cell of the MLC flash memory could store two or more bits, but this raises the possibility of misreading the values of bits. Although expanding a used number of spare area to supply more ECC space may improve above-mentioned problem, a substantial investment for upgrading present system and hardware is also necessary; therefore, it is not beneficial in doing this way.

Furthermore, for efficient usage of flash memory, one way is to monitor times of erasure to each flash block. If the number of erasure times for a block is close to 100,000, data will not be overwritten into the block. Monitoring each block must utilize substantial system resources and memory capacity, but not all blocks will be worn out when erased over 100,000 times, on the contrary, part blocks may not be accessible, as erased with less than 100,000 times. In other words, monitoring each block fails to completely reflect whether each block is useable, and possibly resulting in a waste of flash memory because of suspicious reliability.

Despite Taiwan Patent No. 575806 proposes an enhancement to error correction of flash memory, yet it still does not overcome the problem of low tolerance of two bits and failure to reflect whether each block is useable. Therefore, the situation of misreading remains.

SUMMARY OF THE INVENTION

Accordingly, a primary objective of the present invention is to provide a method of facilitating reliably accessing flash memory, so that a greater number of bits of flash memory are allowed for fault tolerance.

According to the present invention, a method of facilitating reliably accessing flash memory comprises the steps of:(a) determining whether data is to be read out or write in;(b) if the result of step (a) is to write-in, coding a number of N write-in data to generate a number of K extra data, generating the first error-correction code by using an error-correcting operation to the N+K data, and storing the N write-in data and the generated K extra data into the data area and the first ECC into the spare area; and(c) if the result of step (a) is to read-out, allocate a plurality of counters in the main memory;(d) each bit in the target page's data area corresponds to a counter for accumulating a number of differences between the first and the second error correction codes (ECCs) associated to the target page;(e) reading data from the data area of the target page to generate the second ECC and reading the first ECC from the spare area of the target page. Compare each bit in the first and the second ECC, each bit dominates a set of bits in the data area. If a bit in the first and the second ECC disagree, counters corresponding to the bit are increased by 1. Preferring those data with smaller counter values, select a number of M data from the N write-in data and the K extra data as decoding factors to retrieve the N write-in data by using reverse operation of original adopted operation of coding in step (b).

In one aspect of the present invention, the step (b) of the present invention comprises:(b1) coding the N write-in data by using coding operation to generate the K extra data;(b2) performing error-correcting with the N write-in data and the K extra data to generate the first error correction code; and(b3) storing the N write-in data and the K extra data into a data area111of the assigned flash-memory page, and storing the first ECC into the spare area112of the assigned flash-memory page.

In another aspect of the present invention, the step (e) comprises:(e1) reading the N write-in data and the K extra data stored in the data area and the corresponding first error correction code in the spare area;(e2) selecting a number of M data from the N write-in data and K extra data as factors for data retrieving;(e3) retrieving the N write-in data D1˜Dnby decoding the selected M data;(e4) determining whether the decoded data is correct? If it is, go to step (e6), if not go to step (e5);(e5) determining whether the repeated times over a threshold regarding to an upper limitation of misreading? If it is, go to step (e51), if not, go to step (e52);(e51) alarm a failure of reading operation of the flash-memory page; and(e52) selecting another set of M data from the N write-in data D1˜Dnand K extra data T1˜Tkstored in the data area; and(e6) returning the correct data.

In still another aspect of the present invention, the step (e2) comprises:(e21) clearing the counter corresponding to each bit in the data area of the target flash-memory page;(e22) reading the N write-in data and the K extra data stored in the data area111of the target flash-memory page;(e23) reading the first ECC stored in the spare area of the target flash-memory page;(e24) calculating the second ECC based on the N write-in data and K extra data;(e25) comparing the first ECC and the second ECC bit by bit;(e26) determining whether the compared bit of the first ECC and second ECC are identical, if it is, go to step (e262), if not, go to step (e261);(e261) For those bits in the data area dominated by the ECC bit, adding the values of their corresponding counters by one;(e262) determining whether the compared bit is the last bit, if it is, go to step (e27), if not, go to step (e263);(e263) keeping on a comparison of the next bit; and(e27) preferring those data with smaller counter values, randomly select a number of M data. Note that in step (e52), it might be required to select another set of M data. We must ensure that each time the selection of a number of M data differs. This could be done by given different weight to counter values and take other factors into consideration.

The present invention will be described with reference to the accompanying drawings, which show exemplary embodiments of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

Please refer toFIGS. 2,3,4, and5.FIG. 2illustrates a flowchart of a method of accessing data of flash memory according to the present invention. The method occurs as follows:(10) Start.(20) Determine whether data is to be read out or write in. If it is to be read out, go to step40; otherwise, go to step30.(30) Coding write-in data, with reference toFIG. 4, is performed. A number of N write-in data D1˜Dnis coded by using some coding technique, e.g., Tornado coding technique in this embodiment, to generate a number of K extra data T1˜Tk, where N>K. Each K extra data T1˜Tkis obtained by using exclusive OR operation of part of N write-in data D1˜Dn. For example, T6=D4D6D9. It is noted that other logical operation used for the coding also belong to the scope of the present invention. An ECC is produced by using error-correcting operation with N write-in data D1˜Dnand K extra data T1˜Tk. Thereafter, the N write-in data D1-Dnand K extra data T1˜Tkare stored in data area111of the flash-memory page110, and the ECC is stored in the spare area112. As long as a number of M data is randomly selected from the N write-in data D1˜Dnand K extra data T1˜Tk, where N<M<N+K, the N write-in data D1˜Dncan be retrieved by decoding the M random-selected data. The ECC, which is traditionally used to correct 1-bit error, is now used to help selecting a number of M data according to the present invention.(40) Allocate a plurality of counters120in main memory. The plurality of counters120are composed of a counter array in characteristic of sequential addresses.(50) Each bit1111in the target flash-memory page's data area corresponding to a counter120which is used for accumulating a number of differences between the first and the second ECCs of the target flash-memory page100.(60) Reading data from the data area111of the target flash-memory page110is performed to generate the second ECC. The counter120counts a number of dominating bits differences between the second ECC and the first ECC stored in the spare area112. The values of counts are as a criterion of improving reliably accessing each page110of flash memory100. A reliable data group, i.e., the number of M data, is randomly selected from N write-in data D1˜Dnand K extra data T1-Tkas decoding factors. Then N write-in data D1˜Dnis retrieved by using exclusive OR operation or reverse operation of original adopted operation for the selected M data.(70) End.

Referring toFIG. 6illustrating a flowchart of writing process of accessing data in flash memory according to the present invention, i.e., detailed flowchart of step30inFIG. 2, it occurs as follows:(31) Start.(32) Coding the N write-in data D1˜Dnby using coding operation to generate K extra data T1-Tkis performed.(33) Performing error-correcting with N write-in data D1˜Dnand K extra data T1-Tkto generate the first ECC.(34) The N write-in data D1˜Dnand K extra data T1-Tkgenerated from step32are stored into the data area111of the assigned flash-memory page110, while the first ECC generated from step33is stored into the spare area112of the assigned flash-memory page110.(35) End.

Referring toFIG. 7illustrating a flowchart of a reading process of accessing data from flash memory according to the present invention, i.e., detailed flowchart of step60inFIG. 2, it occurs as follows:(61) Start.(62) Read the N write-in data D1˜Dnand K extra data T1˜Tkstored in the data area111and the corresponding first ECC from spare area112.(63) Select a number of M data from the N write-in data D1˜Dnand K extra data T1˜Tkas factors for data retrieving.(64) Retrieve the N write-in data D1˜Dnby decoding the selected M data in step63.(65) Is the decoded data is correct? If it is, go to step67, if not, go to step66.(66) Is the repeated times over a threshold regarding to an upper limitation of misreading? If it is, go to step661, if not, go to step662.(661) Alarm a failure of reading operation of the flash-memory page110.(662) Select another set of M data from the N write-in data D1˜Dnand K extra data T1˜Tkstored in the data area111, and then back to step64.(67) Return the correct data.(68) End.

With reference toFIG. 8illustrating a detailed flowchart of step63inFIG. 7, it occurs as follows:(631) Start.(632) Clearing the counter120corresponding to each bit1111in the data area111of a flash-memory page110is performed.(633) Read the N write-in data D1˜Dnand K extra data T1˜Tkstored in the data area111of the assigned flash-memory page110.(634) Read the first ECC stored in the spare area112of the assigned flash-memory page110.(635) Calculate the second ECC based on the N write-in data D1˜Dnand K extra data T1˜Tkof step633.(636) Compare the first ECC of step634and the second ECC of step635bit by bit.(637) Is the content of the compared bits identical? If it is, go to step6372, if not, go to step6371.(6371) Since each bit dominates a set of data, add the value of those counters corresponding to the bit by one.(6372) Is it the last bit? If it is, go to step638, if not, go to step6373.(6373) Keeping on a comparison of the next bit is performed.(638) preferring those data with smaller counter values, randomly select a number of M data. Note that in step (662), it might be required to select another set of M data. We must ensure that each time the selection of a number of M data differs. This could be done by given different weight to counter values and take other factors into consideration.(639) End.

Please refer toFIG. 9which shows an example of a traditional way to generate the error-correction code. InFIG. 9, the data area111is 512 bytes, and the spare area112is 16 bytes, which includes an error correction code of 24 bits (bit LP0˜LP17and bit CP0˜CP5). Such error-correction code detects two error bits and corrects one error bit. Each ECC bit dominates a set of bits in data area111, for instance, LP0indicating to the result of exclusive-OR operating with all bits within Bytes0, Byte2, Byte4, . . . , Byte510. Thereafter, during reading process, the first ECC stored in the spare area112compares with the second ECC calculated on a basis of the data stored in data area111, so as to determine whether the first ECC is identical to the second ECC and thus being the basis for selecting M data.

Preferably, the data area of a single-level cell flash-memory page111is 512 bytes, and the corresponding ECC is 24 bits. The counter120corresponding to a bit in the data area may record a value between 0˜12 (4 bits is required). Each bit in data area111of 512×8 bits corresponding to one counter120amounts to 16 KB.

When any bit difference between the first and the second ECCs is detected, the corresponding counters120will add the count value with 1.

As shown inFIG. 9, if the bit LP0corresponding to the first and of the second ECCs are different, the bits marked with oblique area may be erred. Similarly, if the value of bit CP5is not identical, the bits marked with doted area may be erred. Therefore, the larger the overlapped area is, the higher the error possibility is. Consequently, after all ECCs are compared, the higher the counter120counts, the lower the likelihood the corresponding bit is selected to be retrieved.

Referring toFIG. 10illustrating logical voltage levels when the present invention applied in a Multi-Level Cell (MLC) flash memory according to the present invention, where vertical axis stands for a number of memory units and the horizontal axis stands for logical voltage VT, four voltage levels representing logical levels “11,” “10,” “01,” and “00” are shown, respectively. As shown, in order to facilitate reliably accessing an MLC flash memory, a value of bit A, for example, between logical levels “11” and “10” but neither in a domain region of logical levels “11” nor of logical levels “10”, should not be selected as one of M data for retrieving N write-in data.