Abstract A single error correcting system for correcting messages of any number of data bits comprises encoding means and decoding means. The encoding means adds r check bits, each check bit representative of at most r-1 data bits and, on the average, each check bit representative of >r/2 data bits; each check bit is representative of no more than one common data bit; and each data bit is represented by exactly two check bits. The decoding means for each data bit has an error correcting circuit receiving three inputs from input circuitry, one input being the data bit itself and the other two inputs being combinations, respectively, of one of the two check bits and other data bits representative of the received data bit. The error correcting circuit is capable of producing an output correctly corresponding to the data bit if no more than one input thereto was in error. A double error detecting system, useful with this single error correcting system, inputs syndrome bits representative of each check bit and of an added parity bit to an OR circuit and to an ADDER circuit, and compares the output from these circuits.
The system of claim 1 wherein said error correcting circuit comprises a threshold logic circuit for each of said data bits with said threshold fixed to produce an output signal of a value corresponding to that of the majority of inputs to said logic circuit.
Claim 2
Dependent Claim
34 words
The system of claim 1 wherein said input circuitry comprises two EXCLUSIVE OR circuits for each data bit each having inputs consisting of up to r-1 data bits and one of said check bits.
Claim 3
Dependent Claim
9 words
The system of claim 1 wherein r-1)(r)/2 k>(r-1)(r-2)/2 .
Claim 4
Dependent Claim
21 words
The system of claim 4 wherein said k data bits are distributed among said r check bits as evenly as possible.
Claim 5
Dependent Claim
9 words
The system of claim 4 wherein k ( ).
Claim 6
Dependent Claim
223 words
In combination with the single error correcting system of claim 1, a double error detecting system comprising an OR circuit and an ADDER circuit, arranged in parallel, input circuitry for transmitting identical inputs to said OR and ADDER circuits, said inputs consisting of r+1 syndrome bits, S, where each Sr syndrome bit represents one check bit and the data bits represented by said check bits, each Sr having one value when its check bit and data bits correspond, and the opposite value when its check bit and data bits do not correspond, and the SR 1 syndrome bit represents both a parity bit representative of the sum of k data bits and the said data bits, Sr 1 having one value when its parity bit and data bits correspond and the opposite value when its parity bit and data bits do not correspond, said OR circuit producing an error output when at least one of said Sr 1 syndrome bits is of said opposite value, and said ADDER circuit producing an error output when an odd number of said Sr 1 syndrome bits are of said opposite value, and a comparison circuitry for comparing the outputs of said OR circuit and said ADDER circuit to produce an error signal when only said OR circuit has an error output, indicating a double handling error.
Claim 7
Dependent Claim
56 words
The double error detecting system of claim 7 wherein said comparison circuit consists of an inverter for inverting the output of said ADDER circuit and an AND circuit having one input from said OR circuit and the other input from said inverter, said AND circuit producing an error signal when said inputs are both error inputs.