Address error detection by merging a polynomial-based CRC code of address bits with two nibbles of data or data ECC bits

• US 7,203,890 B1
• Filed: 06/16/2004
• Issued: 04/10/2007
• Est. Priority Date: 06/16/2004
• Status: Expired due to Fees

• Current Assignee: Azul Systems Incorporated
• Original Assignee: Azul Systems Incorporated
• Inventors: Normoyle, Kevin B.
• Primary Examiner(s): DILDINE JR, R STEPHEN
• Application Number:
  US10/710,066
• Time in Patent Office: 1,028 Days
• Field of Search: 714/763, 714/768
• US Class Current: 714/768
• CPC Class Codes: G06F 11/1016 Error in accessing a memory location, i.e. addressing error
• CPC Class Codes: G11C 2029/0409 Online test
• CPC Class Codes: G11C 8/00 Arrangements for selecting an address in a digital store for stores using transistors G11C11/407, G11C11/413

Abstract

A memory system provides data error detection and correction and address error detection. A Single-byte Error-Correcting/Double-byte Error-Detecting (SbEC/DbED) code with the byte being a 4-bit nibble is used to detect up to 8-bit errors and correct data errors of 4 bits or less. Rather than generating address parity, which is poor at detecting even numbers of errors, a cyclical-redundancy-check (CRC) code generates address check bits. A 32-bit address is compressed to just 4 address check bits using the CRC code. The 4 address check bits are merged (XOR'"'"'ed) with two 4-bit nibbles of the data SbEC/DbED code to generate a merged ECC codeword that is stored in memory. An address error causes a 2-nibble mis-match due to the redundant merging of the 4 address check bits with 2 nibbles of data correction code. The CRC code is ideal for detecting even numbers of errors common with multiplexed-address DRAMs.

Claims

1. An error-correcting memory controller comprising:

a data error-correction code (ECC) generator, receiving write data, for generating data ECC bits containing correction code capable of correcting an error in B data bits, and also capable of detecting an error in 2*B data bits;

an address linear block code generator, receiving a write address corresponding to the write data, for generating address check bits from the write address using a linear block code function;

wherein the address check bits comprise B bits, and the write address comprises at least 4×

B bits, wherein the linear block code function compresses the write address;

a first merge unit, receiving a first B-bit portion of the data ECC bits and receiving the address check bits, for merging the first B-bit portion of the data ECC bits with the address check bits to generate a first merged B-bit portion of a merged ECC codeword;

a second merge unit, receiving a second B-bit portion of the data ECC bits and receiving the address check bits, for merging the second B-bit portion of the data ECC bits with the address check bits to generate a second merged B-bit portion of the merged ECC codeword;

wherein the merged ECC codeword has a third portion that contains data ECC bits from the data ECC generator that are not input to the first or second merge units;

a write interface to a memory for writing the merged ECC codeword to the memory that stores the write data at a location determined by the write address;

a read interface to the memory for reading a stored ECC codeword and read data from a location determined by a read address;

a second ECC generator, receiving the read data from the memory, for generating read ECC bits;

a second address linear block code generator, receiving the read address corresponding to the read data, for generating read address check bits from the read address using the linear block code function;

a first de-merge unit, receiving a first B-bit portion of the stored ECC codeword and receiving the read address check bits, for de-merging the first B-bit portion of the stored ECC codeword from the read address check bits to generate a first de-merged B-bit portion of a de-merged ECC codeword;

a second de-merge unit, receiving a second B-bit portion of the stored ECC codeword and receiving the read address check bits, for de-merging the second B-bit portion of the stored ECC codeword from the read address check bits to generate a second de-merged B-bit portion of a de-merged ECC codeword;

a comparator, receiving the read ECC bits from the second ECC generator and receiving the de-merged ECC codeword, for signaling an address error when first B-bit portions and second B-bit portions of the read ECC bits and the de-merged ECC codeword mis-match; and

a data corrector, coupled to the comparator, for correcting up to B bits of the read data to generate corrected data using the de-merged ECC codeword to locate errors in the read data when the address error is not signaled by the comparator determines that the read ECC bits do not match the de-merged ECC codeword,

whereby data is corrected and address errors are signaled using merged ECC codewords stored in the memory.

2. The error-correcting memory controller of claim 1 wherein the correction code contained in the data ECC bits is a Single-byte Error-Correcting/Double-byte Error-Detecting (SbEC/DbED) code wherein a byte length is a whole number of at least 2.

3. The error-correcting memory controller of claim 2 wherein the B bits comprise 4 bits;

wherein the address check bits comprise 4 bits;

whereby the write address is compressed to 4 bits of the address check bits before merging with two nibbles of the data ECC bits.

4. The error-correcting memory controller of claim 3 wherein the correction code contained in the data ECC bits is S4EC/D4ED code wherein the byte length is four.

5. The error-correcting memory controller of claim 2 wherein the first merge unit, the second merge unit, the first de-merge unit, and the second de-merge unit each comprise a multi-input exclusive-OR (XOR) gate, or each comprise a multi-input exclusive-NOR (XNOR) gate.

6. The error-correcting memory controller of claim 2 wherein the write address comprises 32 bits;

whereby 32 address bits are compressed to 4 bits by the linear block code function.

7. The error-correcting memory controller of claim 2 wherein the linear block code function is a cyclical-redundancy-check (CRC) function.

8. The error-correcting memory controller of claim 7 wherein the linear block code function is X**4+X+1 wherein X is a value of the write address or a value of the read address.

9. The error-correcting memory controller of claim 7 wherein the address linear block code generator comprises four XOR gates each receiving at least 18 address bits of the write address, each of the four XOR gates generating one of the address check bits.

10. The error-correcting memory controller of claim 2 wherein the first B-bit portion, the second B-bit portion, and the third portion are non-overlapping portions of the merged ECC codeword.

11. A method for detecting address errors and data errors using merged error-detection bits comprising:

generating a data-error codeword from write data to be written to a memory at a location indicated by a write address;

generating address check bits from the write address, wherein each of the address check bits is generated as a compressing function of at least two-thirds of address bits in the write address;

merging the address check bits with a first portion of the data-error codeword to generate a first portion of a merged codeword;

merging the address check bits with a second portion of the data-error codeword to generate a second portion of the merged codeword;

wherein the merged codeword has a third portion that contains a third portion of the data-error codeword that is not merged with the address check bits;

storing the merged codeword in an error-check portion of the memory at a location indicated by the write address;

storing the write data to a data portion of the memory at a location indicated by the write address;

reading read data from the data portion of the memory at a location indicated by a read address;

reading a stored codeword from the error-check portion of the memory at a location indicated by the read address;

generating a read-data-error codeword from the read data read from the memory;

generating address read-check bits from the read address, wherein each of the address read-check bits is generated as the compressing function of at least two-thirds of address bits in the read address;

extracting the address read-check bits from a first portion of the stored codeword to generate a first portion of an extracted codeword;

extracting the address read-check bits from a second portion of the stored codeword to generate a second portion of the extracted codeword;

wherein the extracted codeword has a third portion that contains a third portion of a recovered data-error codeword that was not merged with the address check bits;

comparing the extracted codeword to the read-data-error codeword to determine mis-matches;

when no mis-matches are detected, sending the read data to a requestor;

when the first portion and the second portion of the extracted codeword to the read-data-error codeword mis-match by a same difference, signaling an address error;

when the extracted codeword to the read-data-error codeword mis-matches, using a difference of the extracted codeword to locate and correct a correctable error in the read data to generate corrected read data, or using the difference of the extracted codeword to locate but not correct an un-correctable error in the read data and signaling a data error;

sending the corrected read data or signaling the data error or the address error to the requestor,

whereby data correction is attempted in a subset of mismatches, but the address error is signaled when the first portion and the second portion of the extracted codeword to the read-data-error codeword mis-match by a same difference, and the third portion matches.

12. The method of claim 11 further comprising:

when the address error is signaled, re-executing reading of the memory by sending a re-generated read address to the memory.

13. The method of claim 11 wherein the read address and the write address each have at least 30 address bits, and the address check bits comprise 4 or fewer bits;

whereby the write address is compressed to four or fewer bits.

14. The method of claim 11 wherein address errors containing an even number of address bits in error are detected at a rate of at least 90 percent, the even number being and even number of two or more.

15. The method of claim 11 wherein the compressing function for generating the address check bits from the write address comprises a cyclical-redundancy-check (CRC) function.

16. The method of claim 15 wherein the CRC function is X**4+X+1 wherein X is a value of the write address or a value of the read address.

17. The method of claim 11 wherein the data-error codeword is a code capable of detecting an error that has up to one pair of B bits in error in the read data;

wherein the data-error codeword is the code capable of correcting the error that has up to B bits in error in the read data,

wherein the code detects data errors of 2*B bits and corrects data errors of B bits, and wherein the B bits are aligned to B-bit boundaries.

18. An error detecting and correcting memory subsystem comprising:

host interface means for receiving from a host a write address and write data;

data correction-code generator means, coupled to the host interface means, for generating a write data codeword encoded using a Single-byte Error-Correcting/Double-byte Error-Detecting (SbEC/DbED) code wherein a byte length b is a whole number of bits between 3 to 8 inclusive;

address check-code-generator means, receiving the write address from the host interface means, for generating b address check bits as a check-code-generator function of the write address;

wherein the write address contains at least four times b address bits;

first merge means, coupled to the data correction-code generator means and to the address check-code-generator means, for merging the b address check bits with a first b bits of the write data codeword to generate a first b bits of a merged codeword;

second merge means, coupled to the data correction-code generator means and to the address check-code-generator means, for merging the b address check bits with a second b bits of the write data codeword to generate a second b bits of the merged codeword;

codeword write means, receiving the merged codeword from the first merge means, the second merge means, and the data correction-code generator means, for writing the merged codeword to a memory that stores the write data at the write address;

read means, coupled to read the memory at a read address, for reading a stored codeword from the memory and for reading read data from the memory at a read address;

read-data correction-code generator means, coupled to the read means, for generating a read data codeword encoded using the Single-byte Error-Correcting/Double-byte Error-Detecting (SbEC/DbED) code;

read-address check-code-generator means, receiving the read address, for generating b read-address check bits as the check-code-generator function of the read address;

first de-merge means, coupled to the read means and to the read-address check-code-generator means, for extracting the b read-address check bits from a first b bits of the stored codeword to generate a first b bits of an extracted codeword;

second de-merge means, coupled to the read means and to the read-address check-code-generator means, for extracting the b read-address check bits from a second b bits of the stored codeword to generate a second b bits of the extracted codeword;

address error means, coupled to the first and second demerge means, for comparing the first b bits to the second b bits of the extracted codeword and for signaling an address error when the first b bits match the second b bits and the first b bits and the second b bits indicate an error; and

data correction means, activated when the address error is not signaled, for comparing the read data codeword to the extracted codeword to locate errors in the read data, and for correcting errors in the read data to generate corrected data;

wherein the corrected data is sent to the host.

19. The error detecting and correcting memory subsystem of claim 18 further comprising:

memory modules containing the memory;

wherein the memory modules contain memory chips with multiplexed address pins that each carry 2 address bits in a time-multiplexed fashion;

wherein the check-code-generator function of the address check-code-generator means detects 2-bit address errors.

20. The error detecting and correcting memory subsystem of claim 18 wherein the address error means detects at least 93% of 2-bit errors wherein 2 bits in the read address are faulty and detects at least 93% of 1-bit errors wherein only 1 bit in the read address is faulty.