JPH04308947A - Error detecting/correcting apparatus - Google Patents

Abstract

PURPOSE: To minimize the time needed to detect and correct an error. CONSTITUTION: This error detecting and correcting device includes a 1st logical network 40 which receives write data, generates new check bits, and writes them in a memory in relation with the write data and a 2nd logical network 60 which receives read data and check bits read out of the memory and generates a syndrome relating to them. This device is interposed between a processor and the memory, and the write and read data are passed. The 1st and 2nd networks consist of plural exclusive OR gates. An instruction signal is supplied corresponding to a syndrome reflecting whether or not there is an error in read data detected. In a preferable example, a correction part generates a correction signal according to the syndrome to correct the read data.

Description

[Detailed description of the invention]

0001

TECHNICAL FIELD This invention relates generally to the field of electronic systems that utilize memory devices for storing and retrieving data, and more particularly to providing error detection and correction of data stored in such systems. This relates to a device for

0002

BACKGROUND OF THE INVENTION As the trend in semiconductor memory design continues to increase chip density and expand storage capacity, system reliability, especially with regard to data integrity, has increased. Gender is becoming increasingly important. As chip density and storage capacity increase, the probability of data read errors increases, making data integrity more important. In this regard, several methods are used to determine whether the data read from memory is the same as the data originally stored in memory, and to modify the retrieved data if it differs from the originally stored data. Error detection/correction (EDC) schemes have been devised. One common technique for ensuring data integrity is the use of error correction codes.

Typically, before writing data to memory, the data is passed through a logic network in which the individual bits of the data word are combined in a predetermined manner to create a series of check bits. Check bits are stored in memory in association with data bits. When reading or retrieving data from memory, the data is passed through the same logical network to generate new check bits. A comparison is then made between the new check bit and the previously stored check bit. If a data read error occurs, the new check bits will not match the original check bits. The result of comparing the new check bit with the original check bit is called a syndrome. Once enough check bits are generated, data can be modified. The particular error correction code selected determines the type or design of the logical network utilized, the manner in which data is provided to that network, and the possible scope of correction.

[0004] To ensure data integrity, several error correction codes were developed, the earliest of which were:
R. W. There is a so-called single error correction and double error detection (SEC-DED) code developed by R.W. Hamming. This SEC-D
Since the development of the ED code, there have been several modifications to this code, namely Odd Weight Column (OWC) code, Single Byte Error Detection (SBD) code, Single Byte Error Correction Double Byte Error Detection (SBC-DBD)
Code and double error correction triple error detection (
DEC-TED) code has been devised. For information on these codes and their uses, see C. L. Chen (C.L.
．． "Error correction code for semiconductor memory applications" (IBM J. Res. Develop
．． Published by A State-of-the-Art R
review Vol. 28 No. 2 (March 1984) 124
(pages 1 to 133). Although the present invention is useful with almost any coding scheme, it will be specifically described herein with reference to SEC-DED codes.

Traditionally, SEC-DEC codes utilize a single first-order XOR tree, a pyramidal network of exclusive-OR gates, to generate check bits that are stored in memory during write operations. , generated a new check bit for comparison during read operations. Comparisons of newly generated check bits and originally stored check bits were generally performed with smaller 2nd order XOR trees. The performance of such devices was limited by the speed of the primary XOR tree and the time required to provide the necessary check bits to the secondary XOR tree.

[0006]Furthermore, such error detection and correction
This is usually done using the so-called "bus monitoring" method. That is, a primary XOR tree and a data bus are connected in parallel to "observe" the data passing through and, based on these observations, generate error signals for use by the processor or some type of memory controller. One error detection/correction device intended for use in this manner is the IDT49C460,32 sold by Integrated Device Technology, Inc. of Santa Clara, Calif.
There is a bit CMOS error detection/correction device. As is well known, the time required to detect and correct read errors is important to system performance because it directly affects the speed at which data can be read from memory.

Another factor that affects the performance of these prior systems is the read-modify-write (RMW)
There is movement. Words required for error detection and correction (ED
When writing a word with a smaller number of bits than a word (C word) to memory, it must be written in an RMW operation. For example, if the error detection/correction word is 64 bits wide and the word written to memory is only 32 bits wide, then an RMW operation needs to be performed. During RMW operation, previously stored data that is to be logically contiguous with the new data is read from memory during storage. Sufficient stored data is read to fill the bit difference between the EDC word and the data word. The stored data is combined with the generated check bits and new data. The new data and check bits are then written or stored in memory.

Traditionally, RMW operations have been performed in one of two ways. Data that has already been stored or read can be considered correct, when new or written data is combined with the stored data.
Check bits are generated and new data and check bits are stored as quickly as possible. Next, a check is made in the XOR tree to see if there are any errors in the read data, and if there are any errors, they are corrected. If the read data is modified, the modified data is combined with new data and the cycle is repeated. In this technique, the initial write cycle is aborted and a read data check is performed with a row address strobe (R) applied to the memory by the memory controller device.
AS) must be able to overlap with the pre-charging time of the signal. These techniques are extremely complex to control. Additionally, this technique requires significant data retention and requires extra memory cycles when an error is detected. As can be seen, complexity, data retention, and extra cycles affect time and thus system performance.

Alternative RMW techniques require modification of read data before being combined with write data. This technique simplifies control considerably, but performance is significantly compromised. In fact, the read data must be passed through the XOR tree twice before a new check bit is generated. A variation of this technique is
All you have to do is check the read data and make corrections if necessary. However, the read data is still
It is necessary to pass it through the XOR tree twice.

[0010]Therefore, there remains a need for an error detection/correction device that can detect and correct errors in a minimum amount of time, thereby maximizing system performance, and that exhibits this minimum amount of time even during RMW operation. do.

[0011]

SUMMARY OF THE INVENTION The advantages of the invention are obtained by a method and apparatus for use in error detection and correction. A first logical network connected to receive write data generates new check bits to be stored in memory in association with the write data, and connected to receive read data and check bits retrieved from memory. A second logical network generated simultaneously generates syndromes associated with read data and check bits. The device will be inserted between the processor and the memory, and write and read data will be passed through the device. The first and second logical networks are each comprised of a plurality of exclusive OR gates or XOR trees. An indication signal is issued in response to the syndrome reflecting whether an error has been detected in the read data. In a preferred embodiment, the modification section generates a modification signal in response to the syndrome and modifies the read data in response to the modification signal. In connection with a read/modify/write operation, a combining unit combines write data and read data, sends the combined write and read data to first and second logical networks, and converts the combined write and read data into write data by the first logical network. Associated new check bits are generated and, at about the same time, the read data is checked for errors by a second logic network.

[0012] The present invention will be better understood and its numerous advantages will become apparent by reference to the following detailed description of the invention and the drawings.

[0013]

[Example] Figure 1 shows a new error detection/correction device (hereinafter referred to as
10 (referred to as an EDC device) is shown. EDC device 10 is shown for use in a system having a microprocessor 12, memory 14, and memory controller 16. microprocessor 12
issues read and write commands. write data is stored in the memory 14 in response to the write command;
Read data is read from memory 14 in response to a read command. The nature of the data stored in or read from memory is clearly the same. "write"
The names data and "read" data are used herein only to distinguish between data written to memory and data read from memory.

One novel aspect of the present invention is that instead of monitoring data sent to and from memory 14 in a "bus monitoring" manner, an EDC is provided between microprocessor 12 and memory 14. The device 10 is inserted so that write data and read data pass therethrough.

Of course, the data consists of several binary numbers, or bits, and is transmitted to EDC device 10 via bus 18.
and processor 12 , and between memory 14 and EDC device 10 via bus 20 . memory 1
Data to be written or stored in EDC 4 is sent from microprocessor 12 to EDC device 10, while data required by processor 12 is sent in the opposite direction. Control of such transmission can be done in any known manner. Also, clearly, error detection and correction
This is usually done in conjunction with a predetermined number of bits, ie an EBC word. In the preferred embodiment, the EDC word consists of 64 bits.

EDC device 10 in relation to read data
Check bits to be stored in memory 14 in connection with a particular EDC word or check bit being read from memory 14 for use by are transmitted via bus 22 . For the preferred embodiment, SEC-DE
D code is implemented. Since an EDC word contains 64 bits, there must be 8 check bits for each EDC word. As will be particularly clear in connection with the description of FIG. 2, the EDC device 10 and the memory 1
4 is responsive to memory controller 16. Memory controller 16 is further under control of microprocessor 12 via address bus 24 and control bus 26. When data is to be read from memory or data is to be written to memory, the actual data is
0, address and control information is sent to controller 16 via buses 24 and 26. Address information is also sent to memory 14 via bus 28. Other control signals are provided by memory controller 16 to memory 14 via connection 30.

As seen in connection with FIG. 2, once an error is detected, EDC device 10 provides an indication of such error to memory controller 16. Detection of errors in the EDC word is communicated to the memory controller 16 via connection 32 . Multiple error detection in the EDC word is carried out by the controller 1 via connection 34.
6. If the read data is detected and is to be modified, an authorization signal is sent by the controller 16 to the EDC device 10 via the connection 36. Various other permission signals are provided by controller 16 to EDC device 10 via bus 38.

Referring now to FIG. 2, EDC device 10 is shown in further detail. EDC device 10 includes a first logical network 40 for generating new check bits that are stored in association with write data in memory 14, as shown in the figure. Network 40 is connected to receive write data via a series of registers and tri-state buffers. It is noted that several tri-state buffers are shown in FIG. These buffers are substantially identical except for the number of inputs and outputs associated with each buffer. As is well known, a tri-state buffer is a logic high;
Alternatively, it is a logic device that is supplied with an input signal representing logic low information and provides three outputs: a logic high, a logic low, and a high impedance or off output. A high impedance output creates the electronic effect that there is an open circuit at that point. As an example, consider the tri-state buffer 44. Upon receiving the appropriate signal from bus 38,
Buffer 44 delivers a high impedance output, creating the effect of an open circuit. During this "tri-state", write data provided on bus 18 by processor 12 is prevented from passing through buffer 44 and is instead sent to a series of bit registers 46, 48, 50, 52. The control and operation of the various tri-state buffers is simple and will now be explained in more detail.

Data to be written to memory 14 is provided to various bit registers 46-52 via bus 18. The storage of such data in any particular bit register is accomplished by clock inputs 47, 49, 51, 53.
depending on the permission signal supplied to any one of them. For example, assume that memory 14 stores 64 bits of data. Since bus 18 can handle 32 bits in parallel as shown, processor 12 first sends 32 bits of write data via bus 18 to be stored in bit register 46 . The second 32-bit write data is then transferred to bus 18.
and stored in bit register 48. In addition, the write data stored in registers 46, 48 is provided to first logic network 40 as 64-bit EDC words by feeding them onto buses 54 and 50 via tri-state buffers that are enabled accordingly. The check bits generated by the first logic network 40 are sent to the memory via the bus 22, while the write data stored in the registers 46, 48 are sent to the data bus 20 via the bus 58.

EDC device 10 also includes a second logic network 60 that generates syndromes associated with check bits and read data read from memory 14.
Also includes. Second logic network 60 is connected to receive read data and check bits from memory 16 via data latch 62 and check bit latch 64 . Data read from memory 16 is stored in latch 62 in response to appropriate grant signals on grant bus 38. Similarly, the check bits read from the memory 16 in which the check bits are stored in association with the read data read out are read from the memory 16 in preparation for subsequent operation by the second logic network 60 by the appropriate enable signal on the bus 38. is held in latch 64 by.

In the preferred embodiment, logical network 4
0 and 60 are formed from a plurality of exclusive OR gates, which are further configured to form an exclusive OR tree. Such exclusive OR trees have several levels, as is well known, and the data provided to such a tree is applied to the primary input level. In such a case, each exclusive OR gate is provided with two bits of data. Therefore, the 5-level exclusive OR
Tree, i.e. 32 inputs (1
An exclusive OR tree with 6 exclusive OR gates) is available. In the preferred embodiment of the invention, logic network 40 includes eight exclusive-OR trees each having at least 30 inputs at the primary input level, and logic network 60 includes primary inputs Eight exclusive logical OR trees with at least 31 inputs at a level are included. The check bits are fed directly to the second logic network 60, so that they can be sent directly to each of the XOR trees at the primary input level. Therefore, the syndrome is the direct synthetic output of the XOR tree. Similarly, the output of each XOR tree in the first logical network 40 constitutes a check bit.

As will be apparent to those skilled in the art, the application of write data to network 40 and the application of read data and check bits to network 60 can be implemented in many ways. EDC word has 6
Since there are 4 bits involved and each network includes approximately 8 combinations of 30 or 31 bits, a large number of combinations can be implemented. It will also be obvious to those skilled in the art that the particular combination of bits utilized will depend on the particular EDC code utilized. The present invention provides specific ED
No such explanation was given, as it is not dependent on the C code, and many codes are available and well known, including the required bit combinations. It is within the scope of the present invention to use such codes or bit combinations to generate check bits and to generate syndromes.

EDC device 10 also includes an indication circuit connected to receive the syndrome and ultimately generate an indication signal in response to the syndrome. The indication signal reflects whether a single error or multiple errors are detected. If a single error is detected, a signal is sent to the memory controller 16 via connection 32 only. Further, if a multiple error is detected, a signal is sent to the memory controller 16 via both the connection section 32 and the connection section 34.

The instruction signal is generated by decoding the syndrome in the decoder 66. In the preferred embodiment, decoder 66 includes an eight-input NAND gate 72. As with feeding the multiple XOR trees included in networks 40 and 60, the combination of bits provided to the NAND gates of decoder 66 depends on the particular EDC code used. SEC-
For codes such as DED codes, the syndrome bits may have to be processed along with the inverted syndrome bits. In such a case, an appropriate inverter (not shown) can be used to generate an inverted syndrome bit. The combination of syndrome bits and inversion syndrome bits for decoding associated with a particular code is well known. The particular combinations of syndrome bits are not essential to understanding the present invention, so such combinations will not be specifically described. Known combinations can be utilized to decode the particular EDC code selected.

Generally, the decoder 66 analyzes the syndrome and, in the case of a single bit error, detects where the error occurs and outputs from its output a correction signal, ie, the latch 62.
Generates 64-bit read data and 8 check bits used for modifying read data stored in .

If each bit of the correction signal, ie, 72 bits, reflects a logical high, then the read data contains multiple errors. Each bit of the modified signal is connected to an input of AND gate 68. If the inputs to AND gate 68 are all high, a logical high output is provided by AND gate 68 to the input of NAND gate 70.

The syndrome is also provided to an OR gate 72. If any single bit of the syndrome, of which there are eight in the preferred embodiment, is a logic high, then OR gate 72 causes NAND gate 70 to
, 74. Another input of NAND gate 70 and another input of NAND gate 74 are connected to a detection enable output 75 of control register 77 . Detection authorization output 75 can be any one of the register outputs as long as processor 12 knows the particular output. control register 7
7, bus 1 is activated each time read error detection is desired.
Data is provided from processor 12 via 8. In the preferred embodiment, processor 12 controls whether an error is detected by controlling the sending of a logic high signal at output 75.

As shown in FIG. 2, NAND gates 70,
As a result of supplying a logic high signal to the input of O
If the output of R gate 72 is also a logic high, i.e. O
Only if any one of the inputs to R gate 72 is high;
A read data error is indicated. Similarly, the multiple error signal is provided by NAND gate 70 only if the outputs of OR gate 72 and AND gate 68 are both high. As shown in FIG. 2, the output of NAND gate 70 is provided to flip-flop 76. FIG. 2 also shows that the syndrome is provided to syndrome register 78 for temporary storage. EDC device 10 also includes a modification circuit that generates modification signals in response to the syndrome and modifies read data stored in latch 62 in response to such modification signals, as shown. . The modification signals clearly include 64 parallel modification signals, ie modification words 64 bits wide.

The output of decoder 66 is provided as an input to NOR gate 80. In a preferred embodiment, NO
R-gate 80 actually includes 64 two-input NOR gates, with the enable (detection and modification) signal provided by connection 36 being provided as one input to each of the NOR gates, and the other One input of
It is noted that it is connected to receive one of the data bits output from decoder 66. In this way, NOR gate 80 decodes (corrects)
The signal is passed through to generate an inverted correction signal.

The inverse modification signal is provided as an input to exclusive OR gate 82. It is noted that exclusive OR gate 82 actually includes 64 two-input exclusive OR gates. One of the inputs of each exclusive OR gate is connected to one of the inverted modification signals, while the other bit of each exclusive OR gate is connected to one of the bits of the read data stored in latch 62. connected to receive one. The output of exclusive OR gate 82 is the modified read data. Such modified data is stored in latch 84. A secondary latch 86 is also provided for this purpose in the preferred embodiment. The modified read data is then output from latch 84 through the tri-state buffer onto data bus 18.

As is clear from the foregoing, an indication signal reflecting the multiple errors present in the read data is generated in response to both the syndrome and the correction signal. It is noted that another latch 88 is provided to store the check bit contained in latch 64.

During operation of the EDC device 10, it is often the case that the data being written to the memory in the form of digital words contains fewer bits than the EDC words, ie the number of bits to be written in each word is less than 64. be. In such cases, read/modify/write (RMW)
) action is required. In such an operation, it is necessary to read data from the memory that is logically contiguous with the data to be written to the memory, and to generate a check bit after combining the read data with the write data. Conventionally, when errors exist in read data, detecting and correcting such errors has not only been time consuming but also cumbersome from a control standpoint.

The configuration obtained by the present invention, namely:
In the configuration using the first network 40 and the second network 60, read data and write data are combined to generate check bits, and at the same time, it is possible to check the read data for errors. In the preferred embodiment, memory controller 1
6 controls such operations via a connection 30 to which a write strobe signal to the memory 14 is supplied and a connection 36 to which a modify enable signal is supplied. Memory controller 16 initially inhibits error correction via connection 36 . During RMW operation, if an error is detected in the read data, the write cycle is extended by delaying the write strobe via connection 30, allowing error correction via connection 36, and then the ED
It merely allows the C device 10 to modify the read data and combine the modified read data and write data to generate new check bits. Furthermore, the memory controller 16 to the memory 1
A connection 30 to 4 allows the completion of the RMW cycle to be asserted.

Various tri-state buffers and buses 58
acts as a combination device for combining read data stored in latch 62 and write data stored in registers 46-52 during RMW operation. In addition to tristate buffer 90, bus 54
and a tri-state buffer attached to bus 56 form part of the combinational device. For purposes of illustration, the combinational device and sample RMW operation will be described in conjunction with bus 58 and tri-state buffers 90-94. As previously mentioned, the tri-state buffer is connected to receive byte grant signals via bus 38. This byte grant signal is generated by the memory controller 16 to obtain the following combinations.

Write data is sent on bus 18 from processor 12 to registers 46 and 48. As may be recalled, the specific registers in which data is stored are
Inputs 47, 49, 51 by memory controller 16
, 53 on the connection 38. For purposes of illustration, registers 46, 48 have been selected for storage of write data. However, the number of received bits is
This is insufficient to complete a 64-bit EDC word. Read data sufficient to complete an EDC word is read from memory 14 and stored in latch 62. This read data is sent to tri-state buffer 90 via exclusive OR gate 82. When a byte grant signal is generated by memory controller 16 and provided to tri-state buffers 90-94, write data is sent by tri-state buffers 92, 94 onto some of the 64-bit paths in bus 58, and read data is bus 58 by tri-state buffer 90
The rest of the bits are sent to the path. The combined write and read data is provided to logic network 40 for generation of check bits.

At the same time, the read data and associated check bits retrieved from memory 14 are analyzed by second logic network 60 . What attracts attention is
In order to correct the error, the memory controller 16
is necessary to supply a suitable authorization signal to connection 36. If no errors are detected in the read data, the write data stored in registers 46, 48 is sent to data bus 20 via buses 54, 56, 58 and stored in memory 14. New check bits generated by first logic network 40 are sent to check bit bus 22 and stored in memory 14 in association with the write data.

However, if an error is detected in the read data, the correction permission signal is sent to the memory controller 16.
is sent to NOR gate 80 via connection 36. As previously discussed, the read data stored in latch 62 is modified by passing it through exclusive OR gate 82 along with the modification signal generated by decoder 66 and NOR gate 80. The modified read data is then sent to bus 58 via tri-state buffer 90 for combination with the write data stored in registers 46,48. In combination with the modified read data, check bits are generated for storage in memory 14 in association with the write data. Memory controller 16 then asserts a write strobe via connection 30, stores the write data and check bits in memory 14, and completes the RMW cycle.

Although the present invention has been described and illustrated with reference to specific embodiments, those skilled in the art will appreciate that the principles of the invention as set forth in the foregoing detailed description and in the claims will be readily apparent to those skilled in the art. Modifications and changes may be made without departing from the guidelines. For example, although the invention has been described in connection with the use of SEC-DED codes for error detection and correction, other codes may be used without departing from the spirit of the invention.

[0039]

According to the present invention, as described above, the first logical network connected to receive write data generates a new check bit to be stored in the memory in association with the write data, and A second logical network connected to receive the bits simultaneously generates the read data and syndromes associated with the check bits, minimizing error detection and correction time and maximizing system performance. It becomes possible to do so.

[Brief explanation of drawings]

FIG. 1 is a block diagram illustrating a microprocessor-based system including an error detection/correction apparatus according to the present invention.

FIG. 2 is a more detailed block diagram of the error detection/correction apparatus of FIG. 1;

[Explanation of symbols]

10 EDC device 12 Microprocessor 14 Memory 16 Memory controller 40 First logical network 60 Second logical network

Claims (1)

[Claims] 1. Error detection in a system having a processing device that generates read and write commands, and a memory in which write data is stored in response to a write command and read data and check bits are read in response to a read command. a first logical network connected to receive write data and to generate and store new check bits in association with the write data in the memory; a second logical network connected to receive data and check bits and generate a syndrome in relation to the read data and the check bits, the apparatus being connected between the processing unit and the memory; An error detection/correction device, characterized in that the error detection/correction device is inserted into the device, and the write data and the read data pass through the device.