Character correcting coding system and method for deriving the same

Claim 2

A character correcting coding system for use in a data communications system wherein four bits may be simultaneously transmitted and received in each transmission bit time, said coding system comprising: encoding means for generating a parity check bit stream from an input of first, second and third information bit stream, said encoding means simultaneously generating an output of said first, second and third information bit streams and said parity check bit stream, each parity check bit of said parity check bit stream being formed by simultaneous modulo-2 summation of the fifth and 11th prior information bits of said first information bit stream, the third and seventh prior information bits of said second information bit stream and the second and 10th prior information bits of said third information bit stream said parity check bit stream and said first, second and third information bit streams being transmitted simultaneously to a receiving section by said data communication system; storage means in said receiving section of said data communications system for successively storing eleven prior received information bits for each of said first, second and third information bit streams; summation means connected to said storage means for forming a successive modulo-2 sum of the fifth and 11th prior received information bits of said first information bit stream, the third and seventh prior received information bits of said second information bit stream, the second and tenth prior received information bits of said third information bit streams and the immediately received parity check bit from said received parity check bit stream the successive modulo-2 summation forming a syndrome bit stream; syndrome bit storage means connected to said summation means for successively storing said syndrome bit stream; combining means connected to said syndrome bit storage means for combining a presently generated syndrome bit with the sixth previously generated syndrome bit to form a first correction signal for said first information bit stream, for combining the fourth and seventh previously generated syndrome bits to form a second correction signal for said second information bit stream and for combining the first and sixth previously generated syndrome bits to form a third correction signal for said third information bit stream, each of said first, second and third correction signals being modulo-2 added to the 11th prior received information bits of said respective first, second and third information bit streams to correct said 11th prior received information bits.

Claim 3

The character correcting coding system of claim 1 wherein an interleaving factor of six is provided by expanding all storage times by a factor of six whereby six successive erroneously received characters may be corrected.

Claim 4

The character correcting coding system of claim 1, wherein said encoding means includes three shift registers for storing each of said three information bit streams, the shift register for a first information bit stream being tapped at the fifth and 11th bit position, the shift register for a second information bit stream being tapped at the third and seventh bit position and the shift register for a third information bit stream being tapped at the second and 10th bit position, the output of all of said taps being modulo-2 added to form saId parity check bit stream; said storage means includes shift registers having 11bit positions for each of said three information bit streams, the shift register for said first information bit stream being tapped at the fifth and 11th bit positions, the shift register for said second information bit stream being tapped at the third and seventh bit position and the shift register for said third information bit stream being tapped at the second and 10th bit positions; said summation means forms the modulo-2 sum of the outputs of all of said taps; said syndrome bit storage means is a shift register tapped at the first, fourth, sixth, seventh and ninth bit positions; said combining means forms the logical AND of the input to the syndrome bit shift register and the output of the sixth tap of the register to form a correction signal for said first information bit stream, forms the logical AND of the outputs of the fourth and seventh taps of the register to form a correction signal for said second information bit stream, and forms the logical AND of the outputs of the first and ninth taps of the register to form a correction signal for said third information bit stream; said correcting means includes a first exclusive-OR logic gate having as its inputs the output of the shift register for said first information bit stream and said correction signal for said first information bit stream, a second exclusive-OR logic gate having as its inputs the output of the shift register for said second information bit stream and said correction signal for said second information bit stream, and a third exclusive-OR logic gate having as its inputs the output of the shift register for the third information bit stream and said correction signal for said third information bit stream, the outputs of said exclusive-OR logic gates being the corrected information bit streams.

Claim 5

The character correcting coding system of claim 3 including means for feeding back said correction signals to the tap positions which generated them to cancel the outputs.

Claim 6

The character correcting coding system of claim 4 wherein said means for feeding back are exclusive-OR logic gates having as their inputs the tap position output and a correction signal and the outputs of said gates being the inputs to the next shift register bit position.

Claim 7

A character correcting coding system for use in a data communications system wherein a plurality of data bits may be simultaneously transmitted and received in each transmission bit time, said coding system comprising: encoding means for generating a parity check bit stream from an input of plurality of information bit streams, said check bit stream being formed by simultaneous modulo-2 summations of two prior information bit values from each information bit stream, said two prior information bit values from each information bit stream being selected by means of a code operator having the following characteristics; a. said code operator includes in a plurality of row vectors arrayed as a matrix, one row vector for said parity check bit stream and one row vector each for said information bit streams; b. said parity check row vector having a ''''1'''' value in its first column position and ''''0'''' values thereafter; c. each of said information bit stream row vectors having a ''''0'''' in its first column position and no more than two ''''1''''''s in the remainder of its column positions'' d. each column of said arrayed vectors has only one ''''1'''' value; and e. the inner product of each of said information bit stream row vectors and a syndrome vector produce no more than one correcting signal as the row vector is horizontally displaced until a first ''''1'''' each of said information bit stream row vectors is in the first column position, the syndrome vector being defined as the modulo-2 summation of each cOlumn of the arrayed information bit stream row vectors and the parity check row vector, said plurality of information bit streams being simultaneously transmitted with said parity check bit stream by said data communications system to a receiving section of said communication system; storage means in said receiving section of said data communications system for successively storing received information bits of each of said plurality of information bit streams; summation means connected to said storage means for forming a modulo-2 summation of two predetermined stored prior received information bits from each of said stored plurality of information bit streams and received check bit stream, said predetermined stored prior received information bits being selected by means of said code operator, the successive summation generating a syndrome bit stream; syndrome bit storage means connected to said summation means for successively storing said syndrome bit stream; combining means connected to said syndrome bit storage means for combining two previously generated syndrome bits for each information bit stream to produce correction signals for each of said information bit streams; delay means connected to said information bit stream storage means for each information bit stream for further storing each information bit stream by an amount necessary for the production of said correction signal; and correcting means connected to said delay means and said combining means for combining information bits in each information bit stream at the output of said delay means with said correction signals to produce corrected information bit streams.

Claim 8

A character correcting coding system for use in a data communications system wherein a plurality of data bits may be simultaneously transmitted and received in each transmission bit time, said coding system comprising: encoding means for generating a parity check bit stream from an input of plurality of information bit streams, said check bit stream being formed by simultaneous modulo-2 summations of two prior information bit values from each information bit stream, said two prior information bit values from each information bit stream being selected by means of a code operator having the following characteristics; a. said code operator includes in a plurality of row vectors arrayed as a matrix, one row vector for said parity check bit stream and one row vector each for said information bit streams; b. said parity check row vector having a ''''1'''' value in its first column position and ''''0'''' values thereafter; c. each of said information bit stream row vectors having a ''''0'''' in its first column position and no more than two ''''1''''''s in the remainder of its column positions'' d. each column of said arrayed vectors has only one ''''1'''' value; and e. the inner product of each of said information bit stream row vectors and a syndrome vector produce no more than one correcting signal as the row vector is horizontally displaced until a first ''''1'''' each of said information bit stream row vectors is in the first column position, the syndrome vector being defined as the modulo-2 summation of each cOlumn of the arrayed information bit stream row vectors and the parity check row vector, said plurality of information bit streams being simultaneously transmitted with said parity check bit stream by said data communications system to a receiving section of said communication system; storage means in said receiving section of said data communications system for successively storing received information bits of each of said plurality of information bit streams; summation means connected to said storage means for forming a modulo-2 summation of two predetermined stored prior received information bits from each of said stored plurality of information bit streams and received check bit stream, said predetermined stored prior received information bits being selected by means of said code operator, the successive summation generating a syndrome bit stream; syndrome bit storage means connected to said summation means for successively storing said syndrome bit stream; combining means connected to said syndrome bit storage means for combining two previously generated syndrome bits for each information bit stream to produce correction signals for each of said information bit streams; delay means connected to said information bit stream storage means for each information bit stream for further storing each information bit stream by an amount necessary for the production of said correction signal; and correcting means connected to said delay means and said combining means for combining information bits in each information bit stream at the output of said delay means with said correction signals to produce corrected information bit streams.

Claim 9

The character correcting coding system of claim 6 wherein interleaving is provided by expanding all storage times and delays by an interleaving factor whereby the plurality of successively erroneously received characters up to the numerical value of the interleaving factor may be corrected.