Method and Apparatus for Performing Error Detection and Correction With Memory Devices

The present invention relates to a method and apparatus for supporting error detection and error correction modes in a memory system, and more particularly to a method and apparatus for supporting error detection and error correction modes in a memory system that utilizes memory devices which include at least one error bit, also called a "check bit", for each byte of data.

Today, the performance of microprocessors is increasing rapidly due to rapidly advancing electronics technologies, so that processors require higher memory bandwidth. The bandwidth of the commonly used dynamic random access memory (DRAM) device is becoming insufficient to satisfy the needs of system designers. Cache memory is commonly used to fill the bandwidth gap, but its additional cost is prohibitive in cost sensitive systems, such as consumer personal computers (PCs). New types of DRAM devices are being proposed to help alleviate the memory bottleneck problem. These proposed devices are intended to deliver high memory bandwidth by running at very high clock speeds.

The extremely high clock frequency of these devices, together with the high speeds of today's microprocessors, create a system environment that is increasingly noisy. Thus, data in these high speed systems becomes more vulnerable to errors caused by transient electrical and electromagnetic phenomena. Although a well-designed memory subsystem is extremely reliable, even the best memory subsystem, especially one incorporating fast DRAM devices, has the possibility of a memory device failure.

Operating memory devices at higher frequencies generally increases the likelihood and frequency of memory failures or faults. Memory device failures fall generally into two categories. The first category is a soft error, which refers to those errors where data stored at a given memory location change, but where subsequent accesses can store the correct data to the same location with no more likelihood of returning incorrect data than from any other location. Soft errors of this type are generally caused by loss of charge in the DRAM cell. The second category of error is a hard error, which refers to those errors in which data can no longer reliably be stored at a given memory location. Either of these types of errors can lead to catastrophic failure of the memory subsystem.

In an effort to minimize failures due to memory subsystem errors, various error checking schemes have been developed to detect, and in some cases correct, errors in data read from memory. The most simple of the error checking schemes is parity. In a byte-wide parity system, one extra parity bit is appended to every eight bits of data. For "even parity" systems, the parity bit is set such that the total number of ones in the nine-bit word is even. For "odd parity" systems, the parity bit is set to make the total number of ones odd. When data is read from memory, if one of the nine bits changes from one to zero or vice versa, the parity will be incorrect and the error will be detected. This system is limited, however, because there is no way to know which of the nine bits changed. Therefore, single bit errors can only be detected, not corrected. Also, if two bits change, the parity will again be correct and no error will be detected. Parity therefore is capable of detecting only odd numbers of bit errors.

Other considerations, such as whether to use error checking and correction (ECC), error detection code (EDC), such as parity, or byte mask circuitry, has also influenced the design of systems. For consumer desktops, for example, memory bandwidth is an important consideration for increased system performance. Conversely, designers of high-end systems, such as servers, are more inclined to design systems that include ECC or EDC to ensure data integrity. While detection of errors is very useful, it also is desirable to be able to correct certain errors. ECC techniques have been developed that both detect and correct certain errors. Generally speaking, the goal of ECC is to correct the largest possible number of errors with the smallest possible overhead (in terms of extra error bits and wait states) to the system.

The "Hamming codes" constitute one well-known class of ECCs and are widely used for error control in digital communications and data storage systems. The Hamming Codes are described in Lin et al., "Error Control Coding, Fundamentals and Applications", Chapter 3 (1982). One subclass of the Hamming codes that is particularly well-suited for memory subsystems includes the single-error-correcting and double-error detecting (SEC-DED) codes. In these codes, the check bits are generated prior to data being written to memory using a parity-check matrix implemented in ECC hardware. In the Hamming code for 72-bit words, which include 64 data bits, eight error bits are generated. The error bits, or check bits, are then stored in memory together with the data. When a memory read occurs, the ECC hardware retrieves both the data and the corresponding check bits from memory. The ECC hardware then applies the parity check matrix to the data and the check bits, producing a code of "syndrome bits." If the syndrome bits are all zeros, this indicates there are no errors. If the syndrome bits contain ones, the data are possibly invalid. In the case of a single bit error, the syndrome bits will indicate which bit is in error, and thus allow correction, but complimenting the erroneous bit. In the case of double bit errors, the error will be detected, but correction is not possible. A description of the SEC-DED Hamming codes is found in Lin et al, supra, Chapter 16. Table 1 illustrates the required number of error bits for a given range of data bits.

In general, for error correction to be accomplished successfully, the relationship between the number of data bits, n, to be checked and the number of error bits, k, associated with those n data bits is as follows: 2.sup.k -1-k.gtoreq.n.

Another well-known ECC is the "Reed-Solomon code", which is widely used for error correction by the compact disk industry. A detailed description of this ECC is found in Hove et al., "Error Correction and Concealment in the Compact Disc System", Philips Technical Review, Vol. 40 (1980), No. 6, pages 166-172. The Reed-Solomon code is able to correct two errors per code word. Other conventional ECC techniques include: the b-adjacent error correction code described in Bossen, "b-Adjacent Error Correction", IBM J. Res. Develop., pp. 402-408 (July, 1970), and the odd weight column codes described in Hsiao, "A Class of Optimal Minimal Odd Weight Column SEC-DED Codes", IBM J. Res. Develop., pp. 395-400 (July, 1970). The Hsiao codes, like the Hamming codes, are capable of detecting double bit errors and correcting single bit errors. The Hsiao codes use the same number of check bits as the Hamming codes (e.g., eight check bits for 64 bits of data), but are superior in that hardware implementation is simplified and the speed of error detection is improved.

It is desired to provide a memory system and method that takes advantage of increased speed and performance of memory devices and memory subsystems while also providing error detection and/or correction.

A memory system according to the present invention for performing error detection and correction includes at least one memory device that stores a plurality of data words, where each data word has a plurality of data bits and at least one associated check bit. The memory system further includes burst circuitry that reads a plurality of data words in multiple cycles into a block word to include a sufficient number of check bits to perform detection of double bit errors and correction of single bit errors, and error logic that receives and performs error detection and correction upon the block word.

In the embodiments illustrated herein, the block word is 72-bits including 64 bits of data and eight (8) check bits. The 72-bit block word is formed by grouping smaller data words retrieved from the memory device. For a 9-bit device with eight data bits and one check bit, eight burst cycles may be used to retrieve a 72-bit data block. Similarly, for 18-bit devices with 16 data bits and two check bits, four burst cycles may be used to retrieve the data block and for 36-bit devices with 32 data bits and four check bits, two burst cycles may be used to retrieve the data block. In general, each data word includes "n" data bits and "k" check bits, and the burst circuitry groups "p" data words to form a block word having (p.multidot.n) data bits and (p.multidot.k) error bits for a total of (p.multidot.n)+(p.multidot.k) bits, where 2.sup.(p.multidot.k) -1-(p.multidot.k).ltoreq.(p.multidot.n). In a first illustrated 9-bit case, n=8, k=1 and p=8. For an 18-bit case, n=16, k=2 and p=4 and for a 36-bit case, n=32, k=4 and p=2.

The error logic preferably generates a syndrome code from a parity matrix and uses the syndrome code to detect single bit errors and to detect double bit errors. The error logic may use a parity-check matrix and a corresponding syndrome table for error detection and/or correction. The memory devices may be one or more burst dynamic random access memory (DRAM) devices or the like, although any type of memory may be used depending upon the memory controller.

A memory system according to the present invention takes advantage of increased speed and performance of newer memory devices and memory subsystems while also providing error detection and/or correction for data integrity.

A better understanding of the present invention can be obtained when the following detailed description of the preferred embodiment is considered in conjunction with the following drawings, in which:

FIG. 1 illustrates a computer system incorporating a memory system which includes a burst DRAM array and ECC logic in accordance with an embodiment of the present invention;

FIG. 2 is a block diagram of an embodiment of the memory system of FIG. 1 which incorporates a memory controller in accordance with an embodiment of the present invention;

FIG. 3 illustrates an embodiment of a data distribution representing a 72-bit word including eight 9-bit data words;

FIG. 4 illustrates an embodiment of a 72-bit wide ECC encoded data word in accordance with the embodiment of FIG. 3;

FIG. 5 is a parity-check matrix in accordance with a 9-bit DRAM embodiment according to the present invention;

FIG. 6 is a syndrome table in accordance with the embodiment of FIG. 5;

FIG. 7 illustrates an embodiment of a data distribution representing a 72-bit word which includes four 18-bit wide data words;

FIG. 8 is a parity-check matrix in accordance with an 18-bit DRAM embodiment according to the present invention;

FIG. 9 is a syndrome table in accordance with the embodiment of FIG. 8;

FIG. 10 illustrates an embodiment of a data distribution representing a 72-bit word which includes two 36-bit wide data words;

FIG. 11 is a parity-check matrix in accordance with a 36-bit DRAM embodiment according to the present invention; and

FIG. 12 is a syndrome table in accordance with the embodiment of FIG. 11;

FIG. 13 illustrates an embodiment of a 72-bit wide ECC encoded data word in accordance with the embodiment of FIG. 7; and

FIG. 14 illustrates an embodiment of a 72-bit wide ECC encoded data word in accordance with the embodiment of FIG. 10.

New types of DRAM devices, such as Rambus and synchronous DRAMs (SDRAMs), are being proposed to help reduce the memory bottleneck faced by system designers. These "burst DRAM" devices are typically programmable and deliver high memory bandwidth by running at a very high clock frequency, such as 200 megahertz (MHz) or greater. An example of such a programmable burst cycle device is a SLDRAM, which is a DRAM configured according to the SyncLink standard for burst DRAM communication promulgated in the publication "Draft Standard for A High-Speed Memory Interface (SyncLink)", copyright 1996, by the Institute of Electrical and Electronics Engineers, Inc. (IEEE). A SLDRAM typically operates in a packet oriented protocol such that it is programmable for a burst of either 4 or 8 clock cycles of data being transferred in any read or write operation cycle.

FIG. 1 is a block diagram representation of a computer system 20 employing burst dynamic random access memory (DRAM) devices and error correction code (ECC) logic in accordance with an embodiment of the present invention. Each DRAM includes n data bits and k extra error bits associated with the n data bits. The system comprises a CPU 55, which may be the P54C processor available from Intel, or may be any one of several microprocessors and supporting external circuitry typically used in PCs, such as the 80386, 80486, Pentium.TM., Pentium II.TM., etc. microprocessors from Intel Corp. The external circuitry preferably includes an external or level two (L2) cache or the like (not shown). A companion CPU socket 57 is also provided for dual processor implementations, and may be the P54CM socket available from Intel. Both CPU 55 and companion CPU socket 57 communicate with a debug port 59 via a debug signal line 61 and with an interrupt controller 63 via a non-maskable interrupt (NMI) line 65.

On-board cache 67 is provided, preferably a 512K L2 cache, that communicates with CPU 55 via processor data (PD) bus 69 and processor address (PA) bus 71. The PD bus 69 is 72 bits wide, and is also applied to data memory control (DMC) 73. Cache and memory control (CMC) 75 communicates with PA bus 71 and also with processor control bus 77. CMC provides DMC control line 79 to DMC 73 and also memory control line 81 to ECC logic 49. A basecamp processor connector 83 provides peripheral interface for both the peripheral component interface (PCI) bus 85 and APIC bus 87. Additional control signals are provided from the CMC 75 to the connector 83 via sideband signal line 89. A clock 91 provides system timing. An input device 12 such as a keyboard, a display device 14 such as a monitor, and an external memory storage device 9 such as a disk drive, are coupled to PCI bus 85. The keyboard 12, display device 14 and the memory storage device 9 may be coupled in any desired fashion as known to those skilled in the art of computer system design and operation.

ECC logic 49 and Burst DRAM application specific integrated circuit (ASIC) Cell (BDAC) 47 are connected via a 72-bit wide bus. The bus connecting burst DRAM ASIC cell (BDAC) 47 and burst DRAM array 93 is "n" bits wide, where n is any positive integer. Preferably, n is a multiple of nine (9) bits, such as 9, 18, 36, depending on the system configuration. Burst DRAM array 93 includes one or more burst DRAMs (shown in FIG. 2). Although BDAC 47, ECC logic 49, and DMC 73 are shown as separate functional elements in the block diagram of FIG. 1, they need not necessarily be separate physical elements. Each of these elements may be implemented in one or more ASICs depending upon the size of available ASIC packaging. Various other alternatives will be apparent to the skilled artisan. Accordingly, it is clear that the particular configuration of these elements is not crucial to the invention.

FIG. 2 illustrates a memory subsystem 90 for use in the computer system 20, where the memory subsystem 90 includes one or more burst DRAM devices 43 implementing the burst DRAM array 93. The DRAM devices 43 communicate with a memory controller 41 via memory bus 45 of n bits wide, where n equals the bit width of each of the burst DRAM devices 43. In one embodiment, the burst DRAM devices 43 are 9-bit devices, where n=9 corresponding to an 8-bit data byte and one error bit, so that the data path to each burst DRAM device 43 is nine bits wide. A memory controller 41 may be of any type known in the art, and is generic to CMC ASIC 19 and DMC ASIC 23 of FIG. 1. In the embodiment shown, the memory controller 41 incorporates the BDAC 47 and the ECC logic 49. The BDAC 47 groups multiple 9-bit bursts in a data format conversion operation, converting the 9-bit wide high speed data output from each burst DRAM 43 into larger block words, each typically a 72-bit block word which includes 64 data bits and 8 parity bits. These larger 72-bit block words are read by memory controller 41 and CPU 55. A simplified interface 56 is shown representing the various buses and devices between the CPU 55 and the memory controller 41.

The ECC logic block 49 performs ECC manipulation on the 72-bit words, which include grouped 9-bit data bursts from the burst DRAM devices 43. For a 9-bit DRAM 43, there is eight data bits and an error bit. Four error bits would be required. As explained above and indicated in Table 1, ECC techniques require a certain number of error bits for a certain number of associated data bits. Grouping two 9-bit words together would result in 16 bits of data with two error bits, which is still not enough to perform an ECC operation on 16 bits of data (five error bits needed).

It is convenient to group an eight cycle burst which includes eight 9-bit words into a larger 72-bit word to take advantage of the fact that an ECC operation can be performed on 64 data bits using a minimum of seven error bits. Since each of the eight 9-bit words includes an associated error bit, the 72-bit word formed includes eight error bits, which is sufficient to perform an ECC operation. Any multiple of 9-bit words greater than five can be bursted to achieve a sufficient number of available error bits for the corresponding data to perform an ECC operation. For an embodiment using 9-bit DRAMs 43, a 72-bit block word is formed in eight burst cycles. For an embodiment using 18-bit DRAMs 43, a 72-bit block word is formed in four burst cycles. To accomplish an ECC operation, four 18-bit words are bursted from the DRAMs 43 and grouped to form a 72-bit block word. Since each of the four 18-bit words includes two associated error bits, the 72-bit word formed includes 64 data bits and eight error bits, which is sufficient to perform an ECC operation. Thus, if 18-bit DRAMs are used in a memory system, four 18-bit words are packaged together by BDAC 47 of memory controller 41 to form the 72-bit block word processed in the ECC operation.

Likewise, in another embodiment using 36-bit DRAMs 43, each 36-bit word includes 32 data bits and four error bits. Two 36-bit words are bursted and grouped together by BDAC 47 to form a 72-bit block word which is to undergo the ECC operation in the ECC logic 49. The 72-bit block word would again includes eight error bits, which is sufficient for an ECC operation on the resulting 64 data bits included in the 72-bit word. If it is desired to always burst in cycles of at least four, then four 36-bit words are bursted and grouped together by the BDAC 47 to form two 72-bit block words or one 144-bit word, where the ECC logic 49 performs ECC operations on the entire 144-bit word or separately on the two 72-bit words.

ECC logic 49 encodes data sent from the CPU 55 to be stored in burst DRAM 43 with an optimized ECC shown in FIG. 3, and described in more detail below. The result is a 72-bit block word 51, of which 64 bits are data and eight bits are error bits, or check bits. BDAC 47 converts this 72-bit word into a 9-bit wide data stream that is then communicated to one or more of the burst DRAMs 43. An illustration of the 72-bit block word 51 within the burst data stream from 9-bit DRAMs is provided in FIG. 3. FIG. 4 illustrates re-conversion of the word 51 by BDAC 47 during a read operation into a 72-bit wide word 53 applied to ECC logic 49. Similarly, an illustration of a 72-bit word 54 within the burst data stream from 18-bit DRAMs 43 is provided in FIG. 7. FIG. 13 illustrates re-conversion of the word 54 by BDAC 47 during a read operation into a 72-bit wide word 56 applied to ECC logic 49. An illustration of a 72-bit word 58 within the burst data stream for 36-bit DRAMs is provided in FIG. 10. FIG. 14 illustrates re-conversion of the word 58 by BDAC 47 during a read operation into a 72-bit wide word 60 applied to ECC logic 49.

FIG. 5 illustrates a parity-check matrix for an error correction code for an embodiment using 9-bit DRAMs 43 in accordance with the present invention. Based upon reliability data of traditional DRAMs, the prevalent memory failures were caused most often by a single bit (soft or hard) error, or the failure of a single DRAM device. The error correction code in accordance with the invention has been designed to maximize memory protection for the data bits, and has been optimized for use with burst DRAM devices. The memory overhead of having this burst DRAM ECC is the same as for byte parity and other ECC schemes such as the (72-bit word, 64-bit data) Hsiao codes. Thus, there is no additional memory cost. In addition, the ECC in accordance with the invention is able to correct random single bit errors and detect random double bit errors.

To generate the error bits for an associated 64 data bits, an exclusive OR (XOR) operation is performed by ECC logic 49 on the data bits in the locations of each row in the matrix of FIG. 5 having ones. Implementation of the XOR function within an ASIC using Boolean logic is straightforward, and will not be described herein in detail. Performing this operation for each of the eight rows produces the eight error bits. The 64 bits of data and eight error bits are then written to burst DRAM array 93 via BDAC 47. When a read operation occurs, the 64 data bits and eight error bits are read from the burst DRAM array 93, and the XOR operation is again performed on each row, this time including all 72 bits. By performing this operation on each of the eight rows of the matrix of FIG. 5, eight syndrome bits S(0-7) are produced, which essentially form the unique error code for each bit location. Similarly, for embodiments using 18-bit and 36-bit DRAMs 43, FIGS. 8 and 11, respectively, illustrate a parity-check matrix for an error correction code for the 18-bit and 36-bit DRAMs of the DRAM array 93, respectively, in accordance with the present invention.

FIG. 6 illustrates a syndrome table corresponding to the matrix of FIG. 5 for the 9-bit DRAM embodiment according to the present invention. The left-hand number in each entry is a hexadecimal number (h) of the eight syndrome bits, and the right-hand value is the type of error and the bit in error, if known. As indicated in the upper left hand corner of the table of FIG. 6, if all eight syndrome bits are all zero (00h) then no error is detected. If the syndrome bits contain any ones, either a single bit (DB), check bit (CB) or multiple bit error (UNCER) is detected. As is apparent from FIG. 6, if the error is a single bit error, i.e., either a single data bit error or a single check bit error, the particular bit in error is identified by the syndrome table and can be corrected by complementing the indicated bit using known methods. For multiple bit errors, an error is detected but the particular bit is uncertain (UNCER) then is not corrected. Preferably, a report of all uncorrectable errors is made to the operating system or appropriate system software to provide notice of the corrupt data so the users or system service personnel can isolate the faults more easily, thus minimizing system down time. In accordance with the invention, any error that is detected or corrected can be reported to the system software or stored in a special archive for later use during servicing.

FIG. 8 illustrates a parity-check matrix for an error correction code for an embodiment using 18-bit DRAMs 43, and FIG. 9 illustrates a syndrome table corresponding to the matrix of FIG. 8. Similarly, FIG. 11 illustrates a parity-check matrix for an error correction code for an embodiment using 36-bit DRAMs 43, and FIG. 12 illustrates a syndrome table corresponding to the matrix of FIG. 11.

In general, for error correction to be accomplished successfully, the relationship between the number of data bits, m, to be checked and the number of error bits, k, associated with those m data bits is as follows: 2.sup.k -1-k.gtoreq.m. If multiple (p) burst data words are grouped to form a block word on which ECC operations are performed, the block word has (p.multidot.m) data bits and (p.multidot.k) error bits for a total of (p.multidot.m)+(p.multidot.k) bits, where the ".multidot." symbol denotes multiplication. Thus, the relationship between the data bits and the error bits for the block word is as follows: 2.sup.(p.multidot.k) -1-(p.multidot.k).gtoreq.(p.multidot.m). The present invention is applicable, in general, to any size of burst memory device with any number of check bits. To illustrate a non-conventional example, an 11-bit memory with 10 data bits and 1 check bit could be used. In this 11-bit case, seven burst cycles are used to collect a 77-bit word with 70 data bits and 7 check bits, where p=7, k=1 and m=70. Although the present invention is illustrated using DRAM devices, it is understood that any type of programmable memory device may be used since the present invention is not limited to any particular memory technology.

It can now be appreciated that a system and method according to the present invention takes advantage of increased speed and performance of proposed burst memory devices and memory subsystems while also providing error detection and/or correction. The present invention was illustrated in a memory subsystem embodiment for a computer system. It is understood, however, that the present invention may be used in any memory system which uses error detection and error correction operations to ensure data integrity.

Although a system and method according to the present invention has been described in connection with the preferred embodiment, it is not intended to be limited to the specific form set forth herein, but on the contrary, it is intended to cover such alternatives, modifications, and equivalents, as can be reasonably included within the spirit and scope of the invention as defined by the appended claims.