Error correcting decoder

Claim 2

Apparatus for correcting an error in a codeword made up of a predetermined number of bits including check bits in a sequence of positions, including: means for computing a syndrome for the codeword, means for transforming the computed syndrome successively through a succession of syndrome sequences by successive application of a single transformation function to generate each sequence from the next preceding one, means for making a count of the number of transformations in the succession of syndrome sequences, gate means connected to the output of said means for transforming the computed syndrome for sensing each of the successive syndrome sequences and responsive to a distinct predetermined sequence, means connected to be responsive to said gate means and to said count means for inverting a codeword bit in a position in the bit sequence depending on the count of the number of transformations when said gate means responds.

Claim 3

The apparatus of claim 1 for correcting a codeword having erroneous bits in two of the positions; wherein the code is characterized by a generator polynomial; wherein the transformation function is characterized by the generator polynomial; wherein each syndrome sequence corresponds to a codeword error pattern; wherein each transforming of a syndrome sequence corresponds to displacing the pattern along the sequence of bits of the codeword; and wherein the sensing is effected by a plurality of gates in number one less than the number of bits in the codeword, each gate being responsive to a syndrome sequence corresponding to an error pattern with a distinct interval between the error positions.

Claim 4

Apparatus for correcting errors in a codeword with a predetermined number of bits in a sequence and being encoded according to a code characterized by a generator polynomial, the apparatus comprising: a syndrome computer connected to receive the codeword as an input and compute a syndrome corresponding to the codeword, transform circuitry connected to receive the computed syndrome as input and generate a succession of transformed syndromes each successive syndrome of the succession being generated from the preceding syndrome, circuitry to maintain a count of the generated syndromes, a plurality of gates having as inputs the syndromes generated by the transform circuitry, each gate constructed to emit an output in response to a distinct predetermined syndrome, inversion circuitry connected to receive the bit position of said codeword defined by said count circuitry and connected to respond to the output of said gates to invert a codeword bit position for correcting an error.

Claim 5

Apparatus for correcting errors in a codeword with a predetermined number of bits in a sequence and being encoded according to a code characterized by a generator polynomial, the apparatus comprising: a syndrome computer connected to receive the codeword as an input and compute a syndrome corresponding to the codeword, transform circuitry connected to receive the computed syndrome as input and generate a succession of transformed syndromes each successive syndrome of the succession being generated from the preceding syndrome, circuitry to maintain a count of the generated syndromes, a plurality of gates having as inputs the syndromes generated by the transform circuitry, each gate constructed to emit an output in response to a distinct predetermined syndrome, inversion circuitry connected to receive the bit position of said codeword defined by said count circuitry and connected to respond to the output of said gates to invert a codeword bit position for correcting an error.

Claim 6

The apparatus of claim 3 wherein the syndrome computer comprises an EXCLUSIVE OR tree.

Claim 7

The apparatus of claim 3 wherein the transform circuitry comprises a shift register with feedback corresponding to the generator polynomial. 6. The apparatus of claim 3 wherein each gate is responsive to a syndrome corresponding to a codeword with an error in a predetermined position.

Claim 8

The apparatus of claim 3 wherein the count is maintained by serially shifting the codeword around a ring counter.

Claim 9

The apparatus of claim 7 wherein the inversion circuitry includes an EXCLUSIVE OR circuit having an input connected to the ring counter.

Claim 10

Apparatus for correcting errors in a codeword with a predetermined number of bits in a sequence and being encoded according to a code characterized by a generator polynomial, the apparatus comprising: an EXCLUSIVE OR tree connectEd to receive the codeword as an input and compute a syndrome, a shift register with feedback corresponding to the generator polynomial and connected to receive its input from the tree and to generate a succession of transformed syndromes, each syndrome of the succession being generated from the preceding syndrome, circuitry which maintains a count of the generated syndromes, a plurality of gates, in number equal to one less then the number of bits in the codeword, each gate obtaining inputs from the shift register and connected to emit an output responsive to a distinct syndrome corresponding to a codeword with two errors one of which two errors is in a predetermined position in the sequence, inversion circuitry connected to receive the bit position of said codeword defined by said count circuitry and connected to respond to the output of said gates to invert a codeword bit position for correcting an error.

Claim 11

Apparatus for correcting errors in a codeword with a predetermined number of bits in a sequence and being encoded according to a code characterized by a generator polynomial, the apparatus comprising: an EXCLUSIVE OR tree connectEd to receive the codeword as an input and compute a syndrome, a shift register with feedback corresponding to the generator polynomial and connected to receive its input from the tree and to generate a succession of transformed syndromes, each syndrome of the succession being generated from the preceding syndrome, circuitry which maintains a count of the generated syndromes, a plurality of gates, in number equal to one less then the number of bits in the codeword, each gate obtaining inputs from the shift register and connected to emit an output responsive to a distinct syndrome corresponding to a codeword with two errors one of which two errors is in a predetermined position in the sequence, inversion circuitry connected to receive the bit position of said codeword defined by said count circuitry and connected to respond to the output of said gates to invert a codeword bit position for correcting an error.

Claim 12

The apparatus of claim 9 in which the code is a shortened Bose-Chaudhuri code.