Error Correction Method and Apparatus

This invention relates to error correction of data stored in binary digital form in memory devices. Such data upon recall from memory may not be the same as that stored in memory because of such things as random errors which will generally result in no more than one error in an eight bit binary byte, and burst errors which can result in multiple digital errors per byte.

The present error correcting technique involves the use of 100% memory redundancy plus a small amount of logic hardware to provide for automatic correction of the above types of errors so long as the number of such errors do not exceed certain limits. Programming techniques have been known through which such errors can be corrected with software, however the rapid decrease in the cost of memory capacity relative to labor intensive software makes the present error correction technique extremely cost effective.

If the data to be stored in memory comprises eight bit bytes represented as x.sub.7, x.sub.6, x.sub.5, x.sub.4, x.sub.3, x.sub.2, x.sub.1, x.sub.0, (or x.sub.7 -x.sub.0), wherein x.sub.0 is the least significant bit and x.sub.7 the most significant, then a redundant byte y.sub.7 -y.sub.0 is generated by modulo 2 addition of adjacent pairs of the bits of the original byte and both the original and redundant bytes are stored in memory. If only random errors are expected the two bytes can be directly stored in memory.

When the data is later read out of or recalled from memory the original and redundant bytes are applied to a decoder comprising two arrays of modulo 2 adders (or exclusive OR gates), each of the arrays comprising a number of such adders equal to the number of bits per byte. One of the arrays of the modulo 2 adders have the bits of the same significance from the recalled original and recalled redundant byte applied to each adder and the other array of adders have the recalled redundant or y bits of significance n and the recalled original or x bits of significance n+1 applied to each adder. The outputs of these two arrays of modulo 2 adders comprise two new binary digital bytes represented as x.sub.b7 -x.sub.b0 and x.sub.c7 -x.sub.c0. An array of majority vote circuits equal to the number of bits per byte has the original byte as read out of memory applied thereto together with the aforementioned new digital bytes. The outputs of the array of majority vote circuits constitutes the corrected code. In order to facilitate correction of burst errors as defined above, the above apparatus and method are employed, but in addition the bits of the original and redundant code are transported to new positions within the bytes before storage in memory, and are re-transposed to their original byte positions after emerging from memory.

It is thus an object of the invention to provide a novel and useful method and apparatus for correcting both random and burst errors in binary digital information to be stored in memory.

A further object of this invention is to correct errors in binary data upon recall from memory by providing redundant memory capacity combined with certain logic elements, which will correct any random errors of no more than one bit per byte, and will correct three adjacent burst errors per byte.

A still further object of the invention is to provide for error correction of data to be stored in memory by utilizing redundant memory capacity plus certain logic elements to achieve automatic error correction at low cost.

Another object of invention is to provide for low cost error correction of digital data to be stored in memory.

These and other objects and advantages of the invention will become apparent from the following detailed description and the drawings.

FIG. 1 is a system block diagram illustrating the operation of the invention.

FIG. 2 is a circuit diagram showing logic which can be used to generate the redundant byte.

FIG. 3 is a diagram of a transpose and re-transpose circuit used to correct burst errors.

FIG. 4 is a diagram of the decoder used to produce the corrected code from erroneous codes read out of memory.

In FIG. 1, the leads x.sub.7 -x.sub.0 applied to encoder 5 represent an original eight bit byte representing a character or word to be stored in memory 8; x.sub.0 being the least significant digit. The encoder circuit 5, shown in detail in FIG. 2, generates a redundant byte, y.sub.7 -y.sub.0, related to the original byte, by means of an array of modulo 2 adders. As seen in FIG. 2, the circuitry comprises an array of eight such adders, 15, equal in number to the number of bits per byte. A modulo 2 adder is also known as an exclusive OR gate and its output will be binary 1 if one and only one of its inputs is binary 1, and will have binary 0 output for all other inputs. The second input of each of the modulo 2 adders of FIG. 2 is the original digit of next higher significance. Thus the adder on the right end of the array 15 has as its inputs x.sub.0 and x.sub.1, and the adder next to it has as its inputs x.sub.1 and x.sub.2, etc. The outputs of the adders of array 15 comprise the redundant byte y.sub.7 -y.sub.0. The logical relationship between the original and redundant byte can be expressed as follows: y.sub.n =x.sub.n .sym.x.sub.n+1, wherein n is the significance of the binary digit involved.

As seen in FIG. 1, the redundant byte y.sub.7 -y.sub.0 plus the original byte x.sub.7 -x.sub.0 are applied to transpose circuit 7, shown in detail in FIG. 3. The transpose circuit re-orders or re-arranges all sixteen bits of the two bytes applied thereto into a sixteen bit word in which the bits of the original and redundant bytes are alternated. Thus it can be seen that none of the leads emerging from transpose circuit 7 has adjacent x and y bits thereon. In addition to this alternation, the significance of the bits are transposed so that none are in proper sequence and that the transposed byte has no adjacent digits with adjacent significance. The diagram of FIG. 3 shows how such transposition of digits can be accomplished by merely cross connecting two sets of terminals 17 and 19 by means of conductors such as 18. As can be seen from FIGS. 1 and 3, this transposing results in a sixteen bit word which can be represented as: y.sub.1, x.sub.7, y.sub.4, x.sub.2, y.sub.7, x.sub.5, y.sub.2, x.sub.0, y.sub.5, x.sub.3, y.sub.0, x.sub.6, y.sub.3, x.sub.1, y.sub.6, x.sub.4. This sixteen bit transposed word is stored in memory 8, as indicated in FIG. 1.

The data recalled from memory may or may not be the same as that stored therein because of the aforementioned errors. The data will be recalled from memory as sixteen bit words. The transposed sixteen bit word as recalled from memory is represented as x.sub.a4, y.sub.a6, x.sub.a1, y.sub.a3, etc., as indicated by the labels on the leads emerging from memory 8, wherein x.sub.a4 =x.sub.4, y.sub.a4 =y.sub.4, etc., in the absence of error. This recalled sixteen bit word is then applied to re-transpose circuit 10 wherein the bits thereof are re-ordered back into their original sequence by simply passing the byte through the circuit of FIG. 3 from bottom to top, as indicated by the arrow labelled "re-transpose". The output of the re-transpose circuit 10 will comprise the original recalled byte x.sub.a7 -x.sub.a0 and the redundant recalled byte y.sub.a7 -y.sub.a0, as indicated at the output of circuit 10. These two bytes are applied to the decoder circuit 12, shown in detail in FIG. 4. This circuit decodes the information in the two bytes applied thereto to produce the original corrected code x.sub.7 -x.sub.0.

As shown in FIG. 4, the decoder 12 comprises two arrays of eight modulo 2 adders, 9 and 11, one adder for each bit applied to the circuit. The first adder array, 9, has as its inputs the recalled original and redundant bits of the same significance. Thus the right hand adder of array 9 has as its inputs y.sub.a0 and x.sub.a0 and the next adder of array 9 has inputs of x.sub.a1 and y.sub.a1, etc. The second array of adders, 11, have as inputs the recalled original bits of given significance, i.e., x.sub.an, plus the recalled redundant bit of next lesser significance, y.sub.a(n-1). The first adder array 9, produces a first new byte referenced as x.sub.c7 -x.sub.c0, wherein x.sub.cn =x.sub.a(n-1) .sym.y.sub.a(n-1), while the second adder array 11, produces a second new byte referenced as x.sub.b7 -x.sub.b0, wherein x.sub.bn =x.sub.a(n+1) .sym.y.sub.an. As shown in FIG. 4, these two new bytes are applied to an array of eight majority vote circuits 13, one for each bit per byte. The third input of each majority vote circuit is the appropriate bit of the recalled original code, x.sub.a7 -x.sub.a0. Each majority vote circuit produces a binary output corresponding to the majority of the binary signals at its inputs. For example if the inputs are binary 1, 1, and 1, or 1, 1 and 0, the output will be binary 1. If the inputs are binary 0, 0, 1 or 0, 0, 0, the output will be binary 0, etc. The outputs of the majority vote circuits comprise the corrected original code, as indicated.

If only random errors of not more than one bit per byte are to be expected and corrected, the circuitry of FIG. 1 can be simplified by omitting both the transpose and re-transpose circuits, 7 and 10. With this simplified circuit the original byte x.sub.7 -x.sub.0 and the redundant byte y.sub.7 -y.sub.0 would be stored in memory and recalled therefrom as bytes x.sub.a7 -x.sub.a0 and y.sub.a7 -y.sub.a0, for direct application to the decoder 12. An example of how this simplified circuitry corrects single bit errors is shown by the following example:

It can be seen that the recalled original code, x.sub.a7 -x.sub.a0, has a single error in that the binary 1 at position n=3 has been recalled from memory as a binary 0, and that the recalled redundant code, y.sub.a7 -y.sub.a0, has no error. It can be seen that the inputs of the least significant or n=0 majority vote circuit are all binary 0, resulting in a 0 output, the inputs of the majority vote circuit for n=1 are also all binary 0, whereas the inputs of the majority vote circuit for n=2 are binary 0, 0, and 1 resulting in a binary 0 output for this digit. For the n=3 digit the majority vote circuit inputs are binary 0, 1 and 1, resulting in an output of binary 1. All of the remaining digits are binary 0s. It can be seen that the erroneous binary 0 at n=3 of the original byte as read out of memory has been outvoted or corrected by the two binary 1s of the newly generated bits x.sub.c3 and x.sub.b3.

The following table illustrates the operation of the apparatus and method for an error in the redundant byte or code as it is recalled from memory, for the simplified circuit mentioned above.

Again it can be seen that the output of the majority vote circuits is the original code corrected for the error in the redundant code as read out of memory.

It can be seen that the operation of the simplified circuit in correcting signal errors depends on the fact that there are no errors in the bits adjacent to the erroneous bit. Thus the simplified circuit may not correct more than one error per byte. However it will also be appreciated that the transposing circuit re-orders the binary digits in memory so that no two of the original or redundant bits are adjacent to each other in memory. Thus if any two adjacent bits of the sixteen bit byte as recalled from memory are in error, the re-transposed bytes y.sub.a7 -y.sub.a0 and x.sub.a7 -x.sub.a0 will each contain only one error, due to the alternating re-ordering of the bits by the transposing circuitry.

A further example will illustrate how the full circuit of FIG. 1 will yield a corrected code if two adjacent bits, for example bits x.sub.a3 and y.sub.a5, as recalled from memory, are both erroneous.

In this example x.sub.a3 and y.sub.a5 which are adjacent bits of the sixteen bit byte as stored and recalled from memory, are both erroneous in that x.sub.a3 should be binary 1 and y.sub.a5 should be binary 0. It can be seen that the re-transposing of the sixteen bit byte, followed by the decoding in circuit 12 has resulted in correction of this burst error.

While the invention has been described in connected with illustrative embodiments, obvious variations therein will occur to those skilled in the art without the exercise of invention, accordingly the invention should be limited only by the scope of the appended claims.