Methods and apparatus for providing error correction to unwritten pages and for identifying unwritten pages in flash memory
View Patent ↗Provided are methods for error correction coding (ECC) for flash memory pages which have been erased but have not been programmed. In one method, each ECC code word is bitwise inverted before being programmed into a page, and bitwise inverted again after being read back from the page before entering the decoder. Thus an unwritten page, whose bits are all ones when random errors are absent, appears to the decoder as all zeros, which form a valid code word(s) in linear block codes. In another method, in both page programming and page read, the parity section of each ECC code word is bitwise XORed with the complement of a parity calculated from a message whose bits are all ones. Thus an unwritten page appears to the decoder as a valid ECC code word(s) when random errors are absent. Further provided is an apparatus for determining after a page read whether or not the read page has been programmed by comparing the number of read code word symbols which do not have the default erased value and the maximum number of symbol errors correctable by the ECC.
1. A method for providing error correction coding (ECC) by a host system which employs flash memory, wherein bits in a flash memory page which has been erased but has not been programmed have the default value of one, wherein the code used as the ECC is a linear block code, the method comprising steps:
a) encoding user data into encoded data by using an ECC encoder;
b) inverting all bits of the encoded data, wherein the inverted encoded data are transferred to the flash memory to be stored therein;
c) inverting all bits of data read from the flash memory; and
d) decoding the inverted read data to attempt to restore user data by using an ECC decoder,
wherein steps a) and b) of said method may optionally be omitted when the host system reads a flash memory page which has not been programmed since the last erasure of said page.
2. A method for providing error correction coding (ECC) by a host system which employs flash memory, the method comprising steps:
a) encoding user data into encoded data by using a systematic ECC encoder, wherein said encoder encodes each section of user data into an ECC code word comprising said section of user data and a parity section;
b) performing a first bitwise exclusive OR of the parity section of each ECC code word with a pre-computed bit sequence, wherein the message section of said ECC code word and the result of said first exclusive OR are transferred to the flash memory to be stored therein;
c) performing a second bitwise exclusive OR of the parity section of each ECC code word read from the flash memory with the same pre-computed bit sequence as in step b); and
d) decoding each read ECC code word whose message section is read from the flash memory unaltered and whose parity section is the result of said second bitwise exclusive OR to attempt to restore the user data by using an ECC decoder.
3. The method as defined in claim 2 , wherein the pre-computed bit sequence is the bitwise complement of the parity section of the ECC code word whereby all bits in its message section have the value of one.
4. The method as defined in claim 2 , wherein bits in a flash memory page which has been erased but has not been programmed have the default value of one, wherein the code used as the ECC is a linear block code.
5. The method as defined in claim 2 , wherein said steps
a) and b) are omitted when the host system reads a flash memory page which has not been programmed since the last erasure of said page.
6. An apparatus residing in a host system which employs flash memory and error correction coding (ECC) for protecting data stored therein, wherein the apparatus determines whether a read flash memory page has been programmed since the last erasure of said page, the apparatus comprising:
a detector unit configured to receive from the host system data words read from a flash memory page and to count and output the number of non-default symbols contained in each data word, wherein a non-default symbol is a symbol whose value is different from the default value of a symbol in an erased flash memory page;
a counter unit coupled to the detector unit and configured to accumulate and output the number of non-default symbols in each read data word output by the detector unit, wherein the counter unit may be initialized to zero when it is reset;
a comparing unit coupled to the counter unit and configured to output either a first binary value if the output of the counter unit is less than or equal to an integer T, or a second binary value if the output of the counter unit is greater than said integer T, wherein said first binary value and said second binary value are different; and
a register unit coupled to the comparing unit and configured to be initialized to said first binary value when it is reset, to latch the output of the comparing unit when it is enabled, and to retain its content once its content becomes said second binary value even when it is enabled until it is reset, wherein the output of the register unit is coupled to a status signal readable by the host system.
7. The apparatus as defined in claim 6 , wherein said integer T is the maximum number of symbol errors correctable by the ECC employed by said host system.
8. A method for the host system to operate the apparatus as defined in claim 6 , the method comprising steps:
a) resetting the register unit before reading a flash memory page;
b) resetting the counter unit before reading each ECC code word from said page;
c) reading an ECC code word from said page and inputting each data word read from said page to the detector unit;
d) enabling the register unit to latch the output of the comparing unit;
e) checking whether all ECC code words stored in said page have been read and, if so, moving to step f), otherwise, repeating steps b), c) d) and e);
f) determining whether said page has been programmed since its last erasure by reading the status signal, wherein it is determined that said page has not been programmed if the status signal indicates said first binary value, wherein it is determined that said page has been programmed if the status signal indicates said second binary value.