AUTOMATIC DOUBLE ERROR DETECTION AND CORRECTION DEVICE

• US 3,685,014 A
• Filed: 10/09/1970
• Issued: 08/15/1972
• Est. Priority Date: 10/09/1970
• Status: Expired due to Term

• Current Assignee: My-Yue Hsiao, Wadie F. Mikhail
• Original Assignee: My-Yue Hsiao, Wadie F. Mikhail
• Inventors: Mikhail, Wadie F., Hsiao, My-Yue
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US05/079,553
• Time in Patent Office: 676 Days
• Field of Search: 340/146.1AL,172.5 235/153
• US Class Current: 714/753
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence

Abstract

A method and apparatus are provided for detecting and correcting double errors and detecting triple errors by generating syndrome S bits from check bits and data bits of a binary word. The syndrome S bits themselves are decoded to locate and correct single errors. Code bit combinations h1, h2,-hn which indicate the location of the single errors are compared with the syndrome S bits by successive half add operations to produce successive results R1, R2,-Rn. If double errors occur in the binary word, the syndrome S bits reflect the double error by the relationship S hi V hj. When i compare or half add operations are performed, the result Ri yields a discrete combination of code bits which indicates the location of one of the double errors because Rx S V hi hj. Then hj is decoded to correct one of the double errors. When one of the double errors is corrected, a new set of syndrome S bits is generated, and this yields S hi. The syndrome S bits are decoded next to correct the second error in the binary word. Thus double errors occurring in bits i and j of the binary word are detected and corrected.

Claims

1. An error detection and correction device including:

register means which stores bits of a binary word having check bits and data bits, checking means connected to the register means which compares each check bit with various data bits thereby to generate syndrome S bits, a source of signals representing discrete code bit combinations h1, h2,-hn of a matrix H, third means connected to the checking means and said source of signals to generate a result Ri where Ri S V hi hj when errors occur in word bits i and j of the register means, and fourth means connected to the checking means, the third means, and the register means which corrects word bits i and j of the register means.

2. providing discrete code bit combinations h1, h2,-hn of a matrix H,

3. The apparatus of claim 2 wherein the half adder means is composed of Exclusive Or circuits.

4. using Ri hj to correct bit j of the word, 5 then generating syndrome bits S hi and using the syndrome bits to correct bit i of the word.

5. The apparatus of claim 4 wherein:

the third means includes a compare circuit connected to the second means and said source of signals, and said source of signals includes fifth means connected to the compare circuit which supplies the discrete code bit combinations h1, h2,-hn successively to the compare circuit until the result Ri is generated.

6. An error detection and correctIon arrangement including:

register means to store a binary word having bits 1, 2,-n which includes a check bits C1, C2,-Cr and data bits DB1, DB2,-DBn r second means connected to the register means which responds to the check bits and data bits and generates syndrome bits where S s1, s2,-sr and S hi V hj when word bits i and j are in error, third means for supplying successive discrete combinations of code bits from a matrix H where H h1, h2,-hn code combinations, half adder means connected between the second means and the third which performs half add operations on the syndrome bits S and the successive discrete combinations of the code bits h1, h2,-hn ultimately generates a result Ri S V hi hj when word bits i and j are in error, and fourth means connected between the half adder means, the second means, and the register means which corrects the word bits i and j of the register means after Ri is determined.

7. An error detection and correction arrangement including:

first means to store a binary word having bits 1, 2,-n which includes check bits C1, C2,-Cr and data bits DB1, DB2,-DBn r second means connected to the first means which responds to the check bits and data bits and generates syndrome bits where S s1, s2,-sr and S hi V hj when word bits i and j are in error, third means for supplying successive discrete combinations of code bits from a matrix H where H h1, h2,-hn code combinations, comparing means, means connecting the second means and the third means to the comparing means, said comparing means ultimately generating a result Ri S V hi hj when word bits i and j are in error, and fourth means connected between the comparing means and the first means which responds to the result Ri to correct word bit j of the first means.

8. The apparatus of claim 7 wherein the fourth means corrects word bit j and thereafter the second means generates a new set of syndrome bits S, and fifth means connected between the second means and the fourth means which supplies the syndrome bits S to the fourth means when a single error exists in the word bits of the first means, whereby the syndrome bits S operate the fourth means to correct the remaining single error in word bit i of the first means.

9. An error detection and correction device including:

a register for holding word bits of a binary word having check bits and data bits, an Exclusive Or tree connected to said register for generating syndrome bits from the check bits and data bits, error detector means connected to the Exclusive Or tree which energizes a first line to indicate no error, a second line to indicate an even number of errors, and a third line to indicate an odd number of errors, a first set of gates, a second set of gates, and a third set of gates, means connecting said first set of gates to said register, a load device connected to said first set of gates, means connecting said first line to control said first set of gates whereby the content of the first register is transferred to the load device when no error is indicated, means connecting the Exclusive Or tree to the second set of gates, a decoder, means connecting the second set of gates to said decoder, means connecting the third line to control the second set of gates whereby the syndrome bits are supplied to the decoder when an odd Number of errors is indicated, a linear feedback shift register for generating successive error correction codes h1, h2,-hn, a compare circuit connected to the Exclusive Or tree and the linear feedback shift register which performs a half add operation on the error correction codes and the syndrome bits to generate a result, means connecting the compare circuit to the third set of gates, means connecting the second line to control the third set of gates whereby the result from the compare circuit is supplied to the decoder when an even number of errors is indicated, and means connecting said decoder to said register for modifying the content of said register, and the decoder responding to the result from the compare circuit or syndrome bits from the Exclusive Or tree to correct any check bit or data bit in said register.

10. The apparatus of claim 9 further including a syndrome register, means connecting the syndrome register between the Exclusive Or tree and the compare circuit, and means connecting the syndrome register to the second set of gates.

11. An error detection and correction device including:

a register for holding word bits of a binary word having check bits and data bits, an Exclusive Or tree connected to the register which compares each check bit with various data bits thereby to generate syndrome S bits, a source of signals representing discrete code bit combination h1, h2,-hn of a matrix H, first means connected to the Exclusive Or tree and said source of signals which compares the syndrome S bits with discrete code bit combinations h1, h2-hn of a matrix H to generate a result Ri where Ri S hi hj when errors occur in word bits i and j of said register, and second means connected to the first means and the register when responds to the result R1 and corrects word bit j in said register.

12. The apparatus of claim 11 further including third means connected between the Exclusive Or tree and the second means for supplying the syndrome S bits to the second means, and said second means responds to the syndrome S bits to correct word bit i in said register after word bit j of said register is corrected.

13. The method of detecting and correcting errors in word bits of a binary word having check bits and data bits, the method comprising the steps of:

14. The method of detecting and correcting errors in word bits of a binary word having check bits and data bits, the method comprising the steps of:

15. The method of detecting and correcting errors in word bits of a binary word having check bits C1, C2,-Cr and data bits DB1, DB2,-DBn r the method of comprising the steps of:

16. The method of detecting and correcting errors in word bits of a binary word having check bits C1, C2,-Cr and data bits DB1, DB2,-DBn r the method of comprising the steps of: