H-matrix for error correcting circuitry
View Patent ↗A matrix H for encoding data words is defined for wide word ECC with uniform density and a reduced number of components. The H-matrix is incorporated in an encode unit operable to Hamming encode a data word with a 10×528 matrix generated in groups of four columns wherein; a first column is a complement of a second column; the value of the second column ranges from 9 to 271 in increments of two; a third column is a complement of a fourth column; and the value of the fourth column is the same as the value of the second column less one; and wherein a 528-bit bottom row is added to the 10×528 matrix comprising alternating zeroes and ones starting with a zero creating an 11×528 matrix.
1. A circuit, comprising:
an encode unit adapted to receive a data word and operable to encode the data word using a matrix to generate corresponding check bits, the encode unit including components to implement a matrix having,
11 rows and 528 columns, the matrix having elements generated in groups of four columns for rows 1 - 10 wherein for each group of four columns,
a first column is a complement of a second column;
the value of the second column ranges from 9 to 271 in increments of two;
a third column is a complement of a fourth column; and
the value of the fourth column is the same as the value of the second column minus one;
row 11 is formed by alternating zeroes and ones starting with a zero in column 1 ;
an 11×11 identity matrix concatenated onto end of the 11×528 matrix to form an 11×539 matrix; and
a last 1×11 column matrix concatenated onto the end of the identity matrix to form an 11×540 matrix;
a compare unit coupled to the encode unit to receive the generated check bits and adapted to receive a second set of check bits, and operable to compare the check bits from the encode unit to the second set of check bits and to generate an error signal indicating the result of the comparison;
a buffer adapted to receive and store the data word and operable to provide the data word on an output responsive to an enable signal; and
a corrector unit coupled to the compare unit and to the buffer and operable to activate the enable signal responsive to the error signal indicating no errors have been detected and operable to correct single bit errors in the data word stored in the buffer responsive to the error signal indicating a single bit error and to thereafter activate the enable signal.
2. The circuit of claim 1 wherein the binary values of the elements of the second column and in rows 1 - 10 of the matrix is any number greater than 6 and less than 1024.
3. The circuit of claim 1 wherein the ones are replaced by zeroes in the second row of the 11×528 matrix unless there is a duplication of columns in the 11×540 matrix.
4. The circuit of claim 3 wherein some ones in the second row are not replaced by zeroes.
5. The circuit of claim 1 wherein the 528 bits of the first row of the 11×528 matrix are the complement of the 528 bits in row 11 of the matrix.
6. The circuit of claim 1 wherein any two rows of the 11×540 matrix are swapped.
7. The circuit of claim 1 wherein any two columns of the 11×540 matrix are swapped.
8. The circuit of claim 1 wherein there is circular shifting of the 11×528 matrix.
9. The circuit of claim 1 wherein the encode unit further comprises logic to generate a total parity bit using the top row of the 11×528 matrix and the bottom row of the 11×528 matrix and a bottom check bit row of ‘111111111101’.
10. The circuit of claim 1 wherein the compare unit further comprises logic operable to perform a Hamming SEC-DED decoding.
11. The circuit of claim 1 wherein the corrector unit further comprises logic operable to correct the data word in the buffer based on a Hamming syndrome calculated by the compare unit.
12. A computer memory for storing data for access by an application program being executed on a computer system, the memory comprising:
a data structure stored in the memory and being used by the application program, the data structure comprising an 11×528 matrix for encoding data words, the matrix being represented by the following elements in hexadecimal form where two consecutive rows of hexadecimal numbers represent a corresponding row of the matrix, the matrix comprising:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000AAAAAAAA55555555AAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA5555555555
555555555555555555555555555555555555555555555555555555AAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAA55555555555555555555555555555555AAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAA55555555555555555555555555555555AAAAAAAAAAAA
AAAAAAAA5555555555555555AAAAAAAAAAAAAAAA5555555555555555AAAAAAAAAA
AAAAAA5555555555555555AAAAAAAAAAAAAAAA5555555555555555AAAAAAAAAAAA
55555555AAAAAAAA55555555AAAAAAAA55555555AAAAAAAA55555555AAAAAAAA55
555555AAAAAAAA55555555AAAAAAAA55555555AAAAAAAA55555555AAAAAAAAAAAA
AAAA5555AAAA5555AAAA5555AAAA5555AAAA5555AAAA5555AAAA5555AAAA5555AA
AA5555AAAA5555AAAA5555AAAA5555AAAA5555AAAA5555AAAA5555AAAA55555555
AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA
55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55
A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5
A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5
666666666666666666666666666666666666666666666666666666666666666666
666666666666666666666666666666666666666666666666666666666666666666
555555555555555555555555555555555555555555555555555555555555555555
555555555555555555555555555555555555555555555555555555555555555555.
13. The memory of claim 12 wherein at least some of the hexadecimal 0s in the second row are replaced with hexadecimal A's.
14. A machine readable storage medium for storing data for access by an application program being executed on a computer system, the machine-readable storage medium comprising:
a data structure stored in the machine readable storage medium and being used by the application program, the data structure comprising:
an H-matrix in groups of four columns wherein;
a first column is a complement of a second column;
the value of the second column ranges from 1 to N in increments of two;
a third column is a complement of a fourth column;
the value of the fourth column is the same as the value of the second column less one; and
the H-matrix is shifted left by a number of columns to ensure every column in the matrix is unique.
15. The machine readable storage medium of claim 14 wherein the number of columns by which the matrix is shifted to the left is 16.
16. The machine readable storage medium of claim 15 further comprising replacing ones with zeroes in the second row of the matrix unless there would be column duplication.
17. The machine readable storage medium of claim 16 further comprising generating a bottom row of alternating zeroes and ones starting with a zero.
18. A memory, comprising:
a memory array;
an encode unit coupled to the memory array to receive a data word and operable to encode the data word using a matrix to generate corresponding check bits, the encode unit including components to implement a matrix having,
11 rows and 528 columns, the matrix having elements generated in groups of four columns for rows 1 - 10 wherein for each group of four columns,
a first column is a complement of a second column;
the value of the second column ranges from 9 to 271 in increments of two;
a third column is a complement of a fourth column; and
the value of the fourth column is the same as the value of the second column minus one;
row 11 is formed by alternating zeroes and ones starting with a zero in column 1 ;
an 11×11 identity matrix concatenated onto end of the 11×528 matrix to form an 11×539 matrix; and
a last 1×11 column matrix concatenated onto the end of the identity matrix to form an 11×540 matrix;
a compare unit coupled to the encode unit to receive the generated check bits and adapted to receive a second set of check bits, and operable to compare the check bits from the encode unit to the second set of check bits and to generate an error signal indicating the result of the comparison;
a buffer adapted to receive and store the data word and operable to provide the data word on an output responsive to an enable signal; and
a corrector unit coupled to the compare unit and to the buffer and operable to activate the enable signal responsive to the error signal indicating no errors have been detected and operable to correct single bit errors in the data word stored in the buffer responsive to the error signal indicating a single bit error and to thereafter activate the enable signal.
19. The memory of claim 18 wherein the memory array comprises an array of DRAM memory cells.
20. The memory of claim 18 wherein the binary values of the elements of the second column and in rows 1 - 10 of the matrix is any number greater than 6 and less than 1024.
21. The memory of claim 18 wherein the ones are replaced by zeroes in the second row of the 11×528 matrix unless there is a duplication of columns in the 11×540 matrix.
22. The memory of claim 18 wherein the corrector unit further comprises logic operable to correct the data word in the buffer based on a Hamming syndrome calculated by the compare unit.
23. An electronic system including a memory system, the memory system, comprising:
a memory array;
an encode unit coupled to the memory array to receive a data word and operable to encode the data word using a matrix to generate corresponding check bits, the encode unit including components to implement a matrix having,
11 rows and 528 columns, the matrix having elements generated in groups of four columns for rows 1 - 10 wherein for each group of four columns,
a first column is a complement of a second column;
the value of the second column ranges from 9 to 271 in increments of two;
a third column is a complement of a fourth column; and
the value of the fourth column is the same as the value of the second column minus one;
row 11 is formed by alternating zeroes and ones starting with a zero in column 1 ;
an 11×11 identity matrix concatenated onto end of the 11×528 matrix to form an 11×539 matrix; and
a last 1×11 column matrix concatenated onto the end of the identity matrix to form an 11×540 matrix;
a compare unit coupled to the encode unit to receive the generated check bits and adapted to receive a second set of check bits, and operable to compare the check bits from the encode unit to the second set of check bits and to generate an error signal indicating the result of the comparison;
a buffer adapted to receive and store the data word and operable to provide the data word on an output responsive to an enable signal; and
a corrector unit coupled to the compare unit and to the buffer and operable to activate the enable signal responsive to the error signal indicating no errors have been detected and operable to correct single bit errors in the data word stored in the buffer responsive to the error signal indicating a single bit error and to thereafter activate the enable signal.
24. The electronic system of claim 23 wherein the electronic system comprises a computer system.
25. The memory of claim 23 wherein the memory array comprises an array of DRAM memory cells.