States encoding in multi-bit flash cells for optimizing error rate

• US 20060101193A1
• Filed: 03/14/2005
• Published: 05/11/2006
• Est. Priority Date: 11/08/2004
• Status: Active Grant

• Current Assignee: Western Digital Israel Limited (Western Digital Corporation)
• Original Assignee: M-Systems Flash Disk Pioneers Ltd. (Western Digital Corporation)
• Inventors: Murin, Mark
• Granted Patent: US 7,493,457 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G11C 11/5628 Programming or writing circuits; Data input circuits

Abstract

To store N bits of M≧2 logical pages, the bits are interleaved and the interleaved bits are programmed to ┐N/M└ memory cells, M bits per cell. Preferably, the interleaving puts the same number of bits from each logical page into each bit-page of the ┐N/M└ cells. When the bits are read from the cells, the bits are de-interleaved. The interleaving may be deterministic or random, and may be effected by software or by dedicated hardware.

Claims

1. A method of storing N input bits of data, comprising the steps of:

(a) providing ┌

N/M┐

cells, wherein M is at least 2;

(b) interleaving the N input bits, thereby providing N interleaved bits; and

(c) programming each said cell with up to M of said interleaved bits.

2. The method of claim 1, wherein M is at least 3.

3. The method of claim 1, further comprising the step of:

(d) partitioining the N input bits among M logical pages;

and wherein said interleaving provides each bit-page of said ┌

N/M┐

cells with a substantially same number of input bits from each said logical page.

4. The method of claim 1, wherein said interleaving is deterministic.

5. The method of claim 4, wherein said interleaving is effected by steps including:

(i) arranging the N input bits in at least one M×

M matrix; and

(ii) transposing each said at least one matrix.

6. The method of claim 5, wherein each matrix element of each said matrix includes a single input bit.

7. The method of claim 5, wherein the N input bits are arranged in a single said M×

M matrix and wherein each matrix element of said matrix includes N/M² input bits.

8. The method of claim 1, wherein said interleaving is random.

9. The method of claim 1, further comprising the steps of:

(d) reading said N interleaved bits from said cells; and

(e) de-interleaving said N interleaved bits that have been read from said cells.

10. A memory device comprising:

(a) a memory that includes at least K cells; and

(b) a controller operative to store N input bits of data in said cells by steps including;

(i) interleaving said N input bits, thereby providing N interleaved bits, and

(ii) programming each of K cells of said memory with up to M=┌

N/K┐

of said interleaved bits;

wherein M is at least 2.

11. The memory device of claim 10, wherein M is at least 3.

12. The memory device of claim 10, wherein said controller includes a mechanism for effecting said interleaving of said N input bits.

13. The memory device of claim 12, wherein said mechanism effects said interleaving by executing software.

14. The memory device of claim 12, wherein said controller includes dedicated hardware for effecting said interleaving.

15. The memory device of claim 10, wherein said memory includes dedicated hardware for effecting said interleaving.

16. The memory device of claim 10, wherein said memory is a flash memory.

17. A system for storing data, comprising:

(a) a memory device that includes a memory, said memory including at least K cells;

(b) a host of said memory device, for providing N input bits of data to store; and

(c) an interleaving mechanism for interleaving said N input bits, thereby providing N interleaved bits, each of K cells of said memory then being programmed with up to M=┌

N/K┐

of said interleaved bits;

wherein M is at least 2.

18. The system of claim 17, wherein M is at least 3.

19. The system of claim 17, wherein said interleaving mechanism effects said interleaving by executing software.

20. The system of claim 19, wherein said interleaving mechanism is included in said host.

21. The system of claim 19, wherein said interleaving mechanism is included in a controller of said memory, said controller being included in said memory device.

22. The system of claim 17, wherein said interleaving mechanism includes dedicated hardware for effecting said interleaving.

23. The system of claim 22, wherein said interleaving mechanism is included in a controller of said memory, said controller being included in said memory device.

24. The system of claim 22, wherein said interleaving mechanism is included in said memory.

25. The system of claim 17, wherein said memory is a flash memory.

26. A method of storing N data bits, comprising the steps of:

(a) partitioning the N data bits among M input logical pages, wherein M is at least 2;

(b) appending at least one redundancy bit to each said input logical page, thereby providing L≧

N+M input bits;

(c) providing ┌

L/M┐

cells;

(d) interleaving said L input bits, thereby providing L interleaved bits; and

(e) programming each said cell with up to M of said interleaved bits.

27. The method of claim 26, wherein M is at least 3.

28. The method of claim 26, wherein each said cell has a state transition probability P and wherein, for each said input logical page, a number of said at least one redundancy bit thereof is selected in accordance with an error probability of about P/M.

29. The method of claim 26, further comprising the steps of:

(f) reading said interleaved bits from said cells;

(g) de-interleaving said interleaved bits that have been read from said cells, thereby providing M output logical pages of de-interleaved bits, each said output logical page including at least one error correction bit; and

(h) for each said output logical page, correcting said de-interleaved bits of said each output logical page in accordance with said at least one error correction bit thereof.

30. A memory device for storing N data bits partitioned among M≧

2 logical pages, the memory device comprising;

(a) a mechanism for appending at least one redundancy bit to each said logical page, thereby providing L≧

N+M input bits;

(b) a memory that includes at least K=┐

L/M└

cells; and

(c) a controller operative to;

(i) interleave said L input bits, thereby providing L interleaved bits, and

(ii) program each of K cells of said memory with up to M of said interleaved bits.

31. The memory device of claim 30, wherein said mechanism is included in said controller.

32. The memory device of claim 30, wherein M is at least 3.

33. A system for storing data, comprising:

(a) a host that provides N data bits partitioned among M logical pages, wherein M is at least 2;

(b) an error correction mechanism for appending at least one redundancy bit to each said logical page, thereby providing L≧

N+M input bits;

(c) a memory device that includes a memory, said memory including at least K=┌

L/M┐

cells; and

(d) an interleaving mechanism for interleaving said L input bits, thereby providing L interleaved bits, each of K cells of said memory then being programmed with up to M of said interleaved bits.

34. The system of claim 33, wherein M is at least 3.