Systems and methods for error correction and decoding on multi-level physical media
View Patent ↗Apparatus and methods for operating a flash device characterized by use of Lee distance based codes in a flash device so as to increase the number of errors that can be corrected for a given number of redundancy cells, compared with Hamming distance based codes.
1. A method for error correction encoding of L level application data residing in a memory comprising L level Multi-level cells (MLCs) including at least some Multi-level cells (MLCs) in which the application data is residing and at least some Multi-level cells (MLCs) which are at least partly available to accept data other than the application data, the method comprising:
encoding the L level application data over a prime field thereby to generate non-binary redundancy data;
binarizing at least some of said non-binary redundancy data thereby to generate binarized redundancy data;
effecting binary error-correction encoding of the binarized redundancy data, thereby to generate binary redundancy data;
combining said binarized redundancy data and said binary redundancy data thereby to generate combined binarized/binary redundancy data; and restoring said combined binarized/binary redundancy data to L level form, thereby to generate restored L level redundancy data, and storing said restored L level redundancy data in at least some of said at least partly available L level Multi-level cells (MLCs).
2. A method according to claim 1 and also comprising, for at least one L level MLC, utilizing less than L levels for storing at least a portion of said L level application data and utilizing remaining ones of said L levels for storing at least a portion of said combined binarized/binary redundancy data.
3. A method according to claim 2 wherein said binarizing comprises binarizing only some of said non-binary redundancy data thereby to define a portion of said non-binary redundancy data which is un-binarized, and
wherein said method also comprises L-level transforming said un-binarized non-binary redundancy data to L-level un-binarized non-binary redundancy data.
4. A method according to claim 1 wherein said binarizing comprises binarizing all of said non-binary redundancy data.
5. A method according to claim 1 wherein said binarizing comprises binarizing only some of said non-binary redundancy data thereby to define a portion of said non-binary redundancy data which is un-binarized, and wherein said method also comprises L-level transforming said un-binarized non-binary redundancy data to L-level un-binarized non-binary redundancy data.
6. A method according to claim 5 wherein said binarizing and said L-level transforming are effected by a single transform function.
7. A method according to claim 5 and also comprising storing said L-level un-binarized non-binary redundancy data in said L level Multi-level cells (MLCs).
8. A method according to claim 1 and wherein said encoding over a prime field comprises Reed-Solomon encoding over a prime field.
9. A method according to claim 1 wherein said combining comprises concatenating said binarized redundancy data and said binary redundancy data thereby to generate concatenated binarized/binary redundancy data.
10. A method according to claim 1 wherein said binary error-correction encoding comprises BCH encoding of the binarized redundancy data, thereby to generate BCH-encoded redundancy data.
11. A method according to claim 1 wherein said at least some Multi-level cells (MLCs) which are at least partly available to accept data other than said application data comprise entirely available Multi-level cells (MLCs) in which no L level application data is residing, and wherein said storing comprises storing said restored L level redundancy data in at least some of said entirely available L level Multi-level cells (MLCs).
12. A method for error correction decoding of at least restored L level redundancy data residing in a memory comprising L level Multi-level cells (MLCs) including at least some Multi-level cells (MLCs) in which possibly erroneous L-level application data resides and at least some Multi-level cells (MLCs) which store at least said restored L level redundancy data, the method comprising:
binarizing said at least restored L level redundancy data, thereby to generate binarized restored L level redundancy data;
deriving binary redundancy data from said binarized restored L level redundancy data;
effecting binary error-correction decoding of the binary redundancy data, thereby to generate binarized redundancy data;
transforming said binarized redundancy data to generate non-binary redundancy data; and
decoding said non-binary redundancy data and said possibly erroneous L-level application data over a prime field, thereby to generate decoded L level application data.