Granted Patent B2

US 8,887,025 · App. 13/649,072 · Granted Nov 11, 2014

Abstract

Claims (45)

1. A data storage system comprising:

a memory circuit; and

a control circuit to receive data bits provided for storage in memory cells of the memory circuit,

wherein the control circuit compares each of the data bits provided for storage in a corresponding one of the memory cells having a stuck-at fault to a value of the stuck-at fault, wherein the control circuit inverts each of the data bits having a different value than the value of the stuck-at fault of the corresponding one of the memory cells to generate encoded data bits, and

wherein the control circuit generates redundant bits that indicate the encoded data bits to invert to regenerate the data bits.

2. The data storage system of claim 1 , wherein the control circuit inverts digital values of a first subset of the data bits having a first set of bit positions to generate a first subset of the encoded data bits, wherein the first subset of the data bits are provided for storage in a first subset of the memory cells that has at least one memory cell having a stuck-at fault and at least one memory cell without a stuck-at fault, and wherein the control circuit generates the redundant bits to indicate the first set of the bit positions.

3. The data storage system of claim 2 , wherein the control circuit maintains digital values of a second subset of the data bits having a second set of bit positions to generate a second subset of the encoded data bits, wherein the second subset of the data bits are provided for storage in a second subset of the memory cells that has at least one memory cell having a stuck-at fault and at least one memory cell without a stuck-at fault, and wherein the control circuit generates the redundant bits to indicate the second set of the bit positions.

4. The data storage system of claim 3 , wherein the control circuit selects the first and the second sets of bit positions based on a bit at a bit location in each of the bit positions in the first and the second sets such that the bits at the bit location in the bit positions of the data bits in the first subset have a first digital value and the bits at the bit location in the bit positions of the data bits in the second subset have a second digital value.

5. The data storage system of claim 1 , wherein the control circuit encodes the data bits to generate the encoded data bits using a binary tree, wherein the binary tree comprises leaves and internal nodes, wherein each of the internal nodes corresponds to a unique bit location in bit positions of the data bits, wherein each of the leaves corresponds to a subset of the data bits that have one of a first type or a second type, wherein the control circuit inverts the data bits of the first type to match values of corresponding stuck-at faults, and wherein the control circuit maintains values of the data bits of the second type to match values of corresponding stuck-at faults.

6. The data storage system of claim 5 , wherein the binary tree comprises first and second binary sub-trees that are used to generate the redundant bits.

7. The data storage system of claim 1 , wherein the control circuit divides the data bits into first and second halves and exchanges the data bits between the first and the second halves to cause the data bits in the first half to be provided for storage in a first subset of the memory cells that have a first number of stuck-at faults and to cause the data bits in the second half to be provided for storage in a second subset of the memory cells that have the first number of stuck-at faults, and wherein the control circuit generates the redundant bits based on bit positions of the encoded data bits within the first and the second halves.

8. The data storage system of claim 7 , wherein the control circuit divides the data bits in the first half into first and second quarters and exchanges the data bits in the first half between the first and the second quarters to cause the data bits in the first quarter to be provided for storage in a third subset of the memory cells having a second number of stuck-at faults and to cause the data bits in the second quarter to be provided for storage in a fourth subset of the memory cells having the second number of stuck-at faults,

wherein the control circuit divides the data bits in the second half into third and fourth quarters and exchanges the data bits in the second half between the third and the fourth quarters to cause the data bits in the third quarter to be provided for storage in a fifth subset of the memory cells having the second number of stuck-at faults and to cause the data bits in the fourth quarter to be provided for storage in a sixth subset of the memory cells having the second number of stuck-at faults, and

wherein the control circuit generates the redundant bits based on bit positions of the encoded data bits within the first, the second, the third, and the fourth quarters.

9. The data storage system of claim 8 , wherein the control circuit continues to subdivide the data bits into subdivisions each having an equal number of data bits until each of the subdivisions is provided for storage in a subset of the memory cells having only one stuck-at fault.

10. A data storage system comprising:

a memory circuit; and

a control circuit to receive data bits provided for storage in memo cells of the memory circuit,

wherein the control circuit compares each of the data bits provided for storage in a corresponding one of the memory cells having a stuck-at fault to a value of the stuck-at fault wherein the control circuit inverts each of the data bits having a different value than the value of the stuck-at fault of the corresponding one of the memory cells to generate encoded data bits,

wherein the control circuit generates redundant bits that indicate the encoded data bits to invert to regenerate the data bits, and wherein the control circuit generates the redundant bits to indicate a bit position of each of the encoded data bits that is stored in one of the memory cells having one of the stuck-at faults.

11. A method comprising:

receiving data bits that are provided for storage in memory cells of a memory circuit;

comparing each of the data bits provided for storage in a corresponding one of the memory cells having a stuck-at fault to a value of the stuck-at fault;

generating encoded data bits by inverting each of the data bits having a different value than the value of the stuck-at fault of the corresponding one of the memory cells; and

generating redundant bits that indicate at least one operation to perform on the encoded data bits to regenerate the data bits.

12. The method of claim 11 , wherein generating redundant bits that indicate at least one operation to perform on the encoded data bits to regenerate the data bits further comprises generating the redundant bits to indicate a bit position of each of the encoded data bits that is stored in one of the memory cells having one of the stuck-at faults.

13. The method of claim 11 , wherein generating encoded data bits by inverting each of the data bits having a different value than the value of the stuck-at fault of the corresponding one of the memory cells further comprises inverting digital values of a first subset of the data bits having a first set of bit positions to generate a first subset of the encoded data bits, wherein the first subset of the data bits are provided for storage in a first subset of the memory cells that has at least one memory cell having a stuck-at fault and at least one memory cell without a stuck-at fault, and wherein the redundant bits indicate the first set of the bit positions.

14. The method of claim 13 , wherein generating encoded data bits by inverting each of the data bits having a different value than the value of the stuck-at fault of the corresponding one of the memory cells further comprises maintaining digital values of a second subset of the data bits having a second set of bit positions to generate a second subset of the encoded data bits, wherein the second subset of the data bits are provided for storage in a second subset of the memory cells that has at least one memory cell having a stuck-at fault and at least one memory cell without a stuck-at fault, and wherein the redundant bits indicate the second set of the bit positions.

15. The method of claim 14 , wherein generating encoded data bits by inverting each of the data bits having a different value than the value of the stuck-at fault of the corresponding one of the memory cells further comprises selecting the first and the second sets of bit positions based on a bit at a bit location in each of the bit positions in the first and the second sets such that the bits at the bit location in the bit positions of the data bits in the first subset have a first digital value and the bits at the bit location in the bit positions of the data bits in the second subset have a second digital value.

16. The method of claim 11 , wherein generating encoded data bits by inverting each of the data bits having a different value than the value of the stuck-at fault of the corresponding one of the memory cells further comprises:

generating a binary tree that comprises leaves and internal nodes, wherein each of the internal nodes corresponds to a unique bit location in bit positions of the data bits, and wherein each of the leaves corresponds to a subset of the data bits that have one of a first type or a second type;

inverting the data bits of the first type to match values of corresponding stuck-at faults to generate a first subset of the encoded data bits; and

maintaining values of the data bits of the second type to match values of corresponding stuck-at faults to generate a second subset of the encoded data bits.

17. The method of claim 16 , wherein generating a binary tree that comprises leaves and internal nodes further comprises generating first and second binary sub-trees that are used to generate the encoded data bits.

18. The method of claim 11 , wherein generating redundant bits that indicate at least one operation to perform on the encoded data bits to regenerate the data bits further comprises:

dividing the data bits into first and second halves;

exchanging the data bits between the first and the second halves to cause the data bits in the first half to be provided for storage in a first subset of the memory cells that have a first number of stuck-at faults and to cause the data bits in the second half to be provided for storage in a second subset of the memory cells that have the first number of stuck-at faults; and

generating the redundant bits based on bit positions of the encoded data bits within the first and the second halves.

19. The method of claim 18 , wherein generating redundant bits that indicate at least one operation to perform on the encoded data bits to regenerate the data bits further comprises:

dividing the data bits in the first half into first and second quarters;

exchanging the data bits in the first half between the first and the second quarters to cause the data bits in the first quarter to be provided for storage in a third subset of the memory cells having a second number of stuck-at faults and to cause the data bits in the second quarter to be provided for storage in a fourth subset of the memory cells having the second number of stuck-at faults;

dividing the data bits in the second half into third and fourth quarters;

exchanging the data bits in the second half between the third and the fourth quarters to cause the data bits in the third quarter to be provided for storage in a fifth subset of the memory cells having the second number of stuck-at faults and to cause the data bits in the fourth quarter to be provided for storage in a sixth subset of the memory cells having the second number of stuck-at faults; and

generating the redundant bits based on bit positions of the encoded data bits within the first, the second, the third, and the fourth quarters.

20. The method of claim 19 , wherein generating redundant bits that indicate at least one operation to perform on the encoded data bits to regenerate the data bits further comprises continuing to subdivide the data bits into subdivisions each having an equal number of data bits until each of the subdivisions is provided for storage in a subset of the memory cells having only one stuck-at fault.

Assignments (10)