Dynamic interleaver change for bit line failures in NAND flash storage

1. A non-volatile data storage device, comprising:

memory cells arranged in a two-dimensional array having rows and columns, each row associated with a word line and each column associated with a bit line, memory cells associated with each bit line include multiple data bits and a parity bit derived from the data bits, a parity word line includes a parity bit from each bit line;

a memory controller coupled to the memory cells for controlling operations of the memory cells;

wherein the memory controller is configured to:

perform a read operation in response to a read command from a host;

decode data from the read operation to identify error count in each bit line and determine that there are M failed bit lines that have error counts exceeding a threshold value;

perform interleave of data bits to form parity bits by:

for each data word line, grouping data bits into subsets of M data bits, including a subset composed of M data bits from the M failed bit lines; and

for a parity word line, forming subsets of parity bits, wherein each subset of parity bits are computed for a group of data bits comprising one subset from each word line and including only one subset of data bits from the M failed bit lines;

whereby each group includes at most one error bit from the M failed bit lines; and

perform data write operations including using the interleave of data bits to form parity bits.

2. The non-volatile data storage device of claim 1 , wherein the memory controller is further configured to perform interleave of data bits to form parity bits by:

forming a first group of data bits comprising a first subset of data bits from the M failed bit lines and one subset from each word line other than the word line associated with the first subset of data bits;

computing a first subset of parity bits for the first group of data bits;

forming a second group of data bits comprising a second subset of data bits from the M failed bit lines and one previous unused subset from each word line other than the word line associated with the second subset of data bits;

computing a second subset of parity bits for the second group of data bits;

forming a new group of data bits comprising a new subset of data bits from the M failed bit lines and one previous unused subset from each word line other than the word line associated with the new subset of data bits;

compute a new subset of parity bits for the new group of data bits.

3. The non-volatile data storage device of claim 2 , wherein the memory controller is further configured to perform interleave of data bits to form parity bits by:

forming a new group of data bits comprising one previous unused subset from each word line; and

computing a new subset of parity bits for the new group of data bits.

4. The non-volatile data storage device of claim 1 , wherein the memory controller is further configured to perform interleave of data bits to form parity bits by:

comparing the count of failed bit lines M with a threshold for triggering dynamic interleave;

upon determining that M is greater than the threshold for triggering dynamic interleave, performing interleave of data bits to form parity bits.

5. The non-volatile data storage device of claim 4 , wherein the memory controller is configured to determine heuristically the threshold for dynamic interleave.

6. The non-volatile data storage device of claim 4 , wherein the memory controller is configured to vary the threshold for dynamic interleave during a life time of the non-volatile data storage device.

7. The non-volatile data storage device of claim 1 , wherein the memory controller is configured to compute parity bits by an exclusive-OR (XOR) operation of selected data bits.

8. A non-volatile data storage device, comprising:

memory cells arranged in a two-dimensional array having rows and columns, each row associated with a word line and each column associated with a bit line;

a memory controller coupled to the memory cells for controlling operations of the memory cells;

wherein the memory controller is configured to:

decode data from a read operation to identify error count in each bit line and determine that there are M failed bit lines that have error counts exceeding a threshold value;

perform interleave of data bits to form parity bits by:

forming multiple groups of data bits, wherein each group of data bits includes one data bit from each word line and each group of data bits includes at most one data bit from any of the M failed bit lines, and

computing a parity bit for each group of data bits;

whereby each group of data bits includes at most one error bit from the M failed bit lines;

perform data write operations including using the interleave of data bits to form parity bits.

9. The non-volatile data storage device of claim 8 , wherein the memory controller is further configured to perform interleave of data bits to form parity bits by:

for each data word line, grouping data bits into subsets of M data bits, including a subset composed of M data bits from the M failed bit lines; and

for a parity word line, forming subsets of parity bits, wherein each subset of parity bits are computed for a group of data bits comprising one subset from each word line and including only one subset of data bits from the M failed bit lines.

10. The non-volatile data storage device of claim 9 , wherein the memory controller is further configured to perform interleave of data bits to form parity bits by:

forming a first group of data bits comprising a first subset of data bits from the M failed bit lines and one subset from each word line other than the word line associated with the first subset of data bits;

computing a first subset of parity bits for the first group of data bits;

forming a second group of data bits comprising a second subset of data bits from the M failed bit lines and one previous unused subset from each word line other than the word line associated with the second subset of data bits;

computing a second subset of parity bits for the second group of data bits;

forming a new group of data bits comprising a new subset of data bits from the M failed bit lines and one previous unused subset from each word line other than the word line associated with the new subset of data bits;

compute a new subset of parity bits for the new group of data bits.

11. The non-volatile data storage device of claim 10 , wherein the memory controller is further configured to perform interleave of data bits to form parity bits by:

forming a new group of data bits comprising one previous unused subset from each word line; and

computing a new subset of parity bits for the new group of data bits.

12. The non-volatile data storage device of claim 8 , wherein the memory controller is further configured to perform interleave of data bits to form parity bits by:

comparing the count of failed bit lines M with a threshold for triggering dynamic interleave;

upon determining that M is greater than the threshold for triggering dynamic interleave, performing interleave of data bits to form parity bits.

13. The non-volatile data storage device of claim 12 , wherein the memory controller is configured to vary the threshold for dynamic interleave during a life time of the non-volatile data storage device.

14. The non-volatile data storage device of claim 8 , wherein the memory controller is configured to compute parity bits by an exclusive-OR (XOR) operation of selected data bits.

15. A method of controlling a storage system, the storage system including memory cells arranged in a two-dimensional array having rows and columns, each row associated with a word line and each column associated with a bit line and a memory controller coupled to the memory cells for controlling operations of the memory cells, the method comprising:

performing a read operation in response to a read command from a host;

decoding data from the read operation to identify error count in each bit line and determine that there are M failed bit lines that have error counts exceeding a threshold value;

performing interleave of data bits to form parity bits by:

forming multiple groups of data bits, wherein each group of data bits includes one data bit from each word line and each group of data bits includes at most one data bit from any of the M failed bit lines, and

performing data write operations including using the interleave of data bits to form parity bits.

16. The method of claim 15 , further comprising performing interleave of data bits to form parity bits by:

for each data word line, grouping data bits into subsets of M data bits, including a subset composed of M data bits from the M failed bit lines; and

for a parity word line, forming subsets of parity bits, wherein each subset of parity bits are computed for a group of data bits comprising one subset from each word line and including only one subset of data bits from the M failed bit lines.

17. The method of claim 16 , further comprising performing interleave of data bits to form parity bits by:

forming a first group of data bits comprising a first subset of data bits from the M failed bit lines and one subset from each word line other than the word line associated with the first subset of data bits;

computing a first subset of parity bits for the first group of data bits;

forming a second group of data bits comprising a second subset of data bits from the M failed bit lines and one previous unused subset from each word line other than the word line associated with the second subset of data bits;

computing a second subset of parity bits for the second group of data bits;

forming a new group of data bits comprising a new subset of data bits from the M failed bit lines and one previous unused subset from each word line other than the word line associated with the new subset of data bits;

compute a new subset of parity bits for the new group of data bits.

18. The method of claim 17 , further comprising performing interleave of data bits to form parity bits by:

forming a new group of data bits comprising one previous unused subset from each word line; and

computing a new subset of parity bits for the new group of data bits.

19. The method of claim 15 , wherein further comprising performing interleave of data bits to form parity bits by:

comparing the count of failed bit lines M with a threshold for triggering dynamic interleave;

upon determining that M is greater than the threshold for triggering dynamic interleave, performing interleave of data bits to form parity bits.

20. The method of claim 19 , further comprising varying the threshold for dynamic interleave during a life time of the storage system.