Automatic double error detection and correction device

Claim 2

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.

Claim 3

The apparatus of claim 1 wherein the third means includes half adder means connected to the checking means and the source of signals, and said source of signals includes further means which supplies the discrete code bit combinations h1, h2,-hn successively to the half adder means until the result Ri is generated.

Claim 4

comparing the syndrome S bits with discrete code bit combinations h1, h2,-hn of a matrix H to generate a result Ri S V hi hj when word bits i and j are in error,

Claim 5

comparing the syndrome S bits with discrete code bit combinations h1, h2,-hn of a matrix H to generate a result Ri S V hi hj when word bits i and j are in error,

Claim 6

comparing the syndrome S bits with discrete code bit combinations h1,h2,-hn of a matrix H to generate a result Ri S V hi hj when word bits i and j are in error, and

Claim 7

comparing the syndrome S bits with discrete code bit combinations h1,h2,-hn of a matrix H to generate a result Ri S V hi hj when word bits i and j are in error, and

Claim 8

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

Claim 9

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

Claim 10

comparing the syndrome bits S with the discrete combinations of code bits h1, h2,-hn to generate a result Ri S V hi hj when word bits i and j are in error, and

Claim 11

comparing the syndrome bits S with the discrete combinations of code bits h1, h2,-hn to generate a result Ri S V hi hj when word bits i and j are in error, and

Claim 12

correcting word bits i and j after the result Ri is determined.

Claim 13

correcting word bits i and j after the result Ri is determined.

Claim 14

using Ri to correct word bit j,

Claim 15

using Ri to correct word bit j,

Claim 16

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

Claim 17

An error detection and correction device including: first means which stores word bits of a binary word having check bits and data bits, second means connected to the first means which generates syndrome bits S, a source of signals representing discrete code bit combinations h1, h2-hn of a matrix H, third means connected to the second means and said source of signals which compares the syndrome bits S with discrete code bit combinations h1, h2,-hn of a matrix H to generate a result Ri where Ri S V hi hj when errors occur in word bits i and j of the first means, and fourth means connected to the second means, the third means, and the first means which corrects bits i and j of the first means.

Claim 18

An error detection and correction device including: first means which stores word bits of a binary word having check bits and data bits, second means connected to the first means which generates syndrome bits S, a source of signals representing discrete code bit combinations h1, h2-hn of a matrix H, third means connected to the second means and said source of signals which compares the syndrome bits S with discrete code bit combinations h1, h2,-hn of a matrix H to generate a result Ri where Ri S V hi hj when errors occur in word bits i and j of the first means, and fourth means connected to the second means, the third means, and the first means which corrects bits i and j of the first means.

Claim 19

then generating a new set of syndrome S bits where S hi for the remaining single error, and

Claim 20

then generating a new set of syndrome S bits where S hi for the remaining single error, and

Claim 21

correcting word bits i and j after the result Ri is determined.

Claim 22

correcting word bits i and j after the result Ri is determined.

Claim 23

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.

Claim 24

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.

Claim 25

using S hi to correct bit i of the binary word.

Claim 26

using S hi to correct bit i of the binary word.

Claim 27

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.

Claim 28

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.

Claim 29

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.

Claim 30

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.

Claim 31

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.

Claim 32

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.

Claim 33

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.

Claim 34

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.

Claim 35

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.

Claim 36

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.

Claim 37

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.

Claim 38

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.