Character-error and burst-error correcting systems utilizing self-orthogonal convolution codes

Claim 2

A data error-correcting system comprising: means for generating the syndrome of blocks of data characters which have been encoded into code words of a t character errorcorrecting self-orthogonal convolution code, said data characters comprising elements of a finite field GF(p ), threshold logic means connected to said generating means for generating a signal when the number of nonzero elements in a portion S0, S1,...,S2t 1 of said syndrome exceeds a threshold value t, computing means connected to said generating means and responsive to a signal from said threshold logic means for computing solutions e1,...,et , of simultaneous equations Si Alpha r ie1+...+ Alpha r iet , where t'' is the number of errors in a block ranging from 1 to t and is determined as that value which satisfies t+1 or more of the equations Si, i 0,..., 2t-1, and Alpha is the primitive root of GF(p ), and means for subtracting modulo p each ei obtained by said computing means from the character in position ri of said block of characters.

Claim 3

A system as in claim 1 further including means for multiplying each ei by Alpha j(i 1) and means for subtracting each product thereof from the corresponding syndrome component Sj, where j 0,...,2t-1.

Claim 4

In a data processing system in which data characters have been encoded into a t character error-correcting self-orthogonal convolution code of rate (b-1)/b and constraint length Nb, said characters comprising elements of a finite field GF(p ), a first shift register for storing N(b-1) of said encoded data characters, where the ith encoded one of said stored characters is designated ri, a modulo p adder connected to said first shift register for generating the modulo p sum of certain of the characters stored in said shift register or multiples thereof, a second shift register connected to said modulo p adder for storing the sums generated by said adder, a modulo p subtractor for subtracting each of said sums from a different one of the parity characters of said encoded data characters to thereby generate syndrome components of the data characters stored in said first shift register, a syndrome storage unit connected to said subtractor for storing said syndrome components, a majority logic unit connected to said syndrome storage unit for generating a signal when the number of nonzero components in a portion S0, S1,...,S2t 1 of said syndrome exceeds t, and logic means for generating the values e1,...,et of the equations Si Alpha r ie1+...+ Alpha r iet , where t'' is the number of errors in a block of b-1 characters stored in said first shift register ranging from 1 to t and is determined as that value which satisfies t+1 or more of the equations Si, i 0,...,2t-1, and Alpha is the primitive root of GF(p ).

Claim 5

In a data processing system in which data characters have been encoded into a t character error-correcting self-orthogonal convolution code of rate (b-1)/b and constraint length Nb, said characters comprising elements of a finite field GF(p ), a first shift register for storing N(b-1) of said encoded data characters, where the ith encoded one of said stored characters is designated ri, a modulo p adder connected to said first shift register for generating the modulo p sum of certain of the characters stored in said shift register or multiples thereof, a second shift register connected to said modulo p adder for storing the sums generated by said adder, a modulo p subtractor for subtracting each of said sums from a different one of the parity characters of said encoded data characters to thereby generate syndrome components of the data characters stored in said first shift register, a syndrome storage unit connected to said subtractor for storing said syndrome components, a majority logic unit connected to said syndrome storage unit for generating a signal when the number of nonzero components in a portion S0, S1,...,S2t 1 of said syndrome exceeds t, and logic means for generating the values e1,...,et of the equations Si Alpha r ie1+...+ Alpha r iet , where t'' is the number of errors in a block of b-1 characters stored in said first shift register ranging from 1 to t and is determined as that value which satisfies t+1 or more of the equations Si, i 0,...,2t-1, and Alpha is the primitive root of GF(p ).

Claim 6

The system of claim 3 further comprising means responsive to a signal from said majority logic means for subtracting (modulo p) each ei generated by said logic circuit from the character ri stored in said first shift register thereby correcting the characters.

Claim 7

The system of claim 4 further comprising means for multiplying each ei by Alpha j(i 1) and means for subtracting each product thereof from the corresponding syndrome component Sj, where j 0,...,2t-1.

Claim 8

In a data processing system comprising a source of data characters, an encoder for encoding said data characters in a double character error-correcting self-orthogonal convolution code of rate 2/3, the characters of which constitute elements of a finite field GF(2 ), said encoder comprising a 13 character shift register for temporarily storing data characters from said source, a first modulo-2 adder interconnected with said shift register in accordance with the AN matrix of the code whose bottom row contains the entries 1 Alpha 30 000 1 Alpha 20 000 000 1 Alpha 0 111 for generating a parity character from the characters stored in said shift register, a first single character shift register for temporarily storing the parity character generated by said adder, and means for alternately applying two data characters from said source and a parity character generated by said adder to a communication channel.

Claim 9

In a data processing system comprising a source of data characters, an encoder for encoding said data characters in a double character error-correcting self-orthogonal convolution code of rate 2/3, the characters of which constitute elements of a finite field GF(2 ), said encoder comprising a 13 character shift register for temporarily storing data characters from said source, a first modulo-2 adder interconnected with said shift register in accordance with the AN matrix of the code whose bottom row contains the entries 1 Alpha 30 000 1 Alpha 20 000 000 1 Alpha 0 111 for generating a parity character from the characters stored in said shift register, a first single character shift register for temporarily storing the parity character generated by said adder, and means for alternately applying two data characters from said source and a parity character generated by said adder to a communication channel.

Claim 10

The arrangement of claim 6 further including a 14 character shift register for storing and shifting therethrough 14 characters at a time represented as C1,...C14, where Ci represents the ith stored character of each group of 14 characters, a second modulo-2 adder, means connected to said communication channel for alternately applying two data characters from said channel to said 14 character shift register and a parity character from said channel to said second modulo-2 adder, a third modulo-2 adder connected to said 14 character shift register for generating a parity character from the characters stored in said 14 character shift register, a second single character shift register for temporarily storing the parity characters generated by said third modulo-2 adder, said second modulo-2 adder being further arranged to add each parity character received from said channel to a parity character stored in said second single character shift register to thereby generate syndrome components of the data characters stored in said 14 character shift register, and a syndrome storage unit connected to said second modulo-2 adder for storing said syndrome componentS, the first, second, fifth, and seventh of such components stored therein being designated S0, S1, S2, and S3, respectively.

Claim 11

The arrangement of claim 7 further including means connected to said syndrome storage unit for generating a first signal when three or more of the components of the group S0, S1, S2, and S3 are equal, means responsive to said first signal for adding one of said equal components to the character C1 as it is shifted from said 14 character shift register, means for dividing S1, S2, and S3 by Alpha , Alpha 2, and Alpha 3, respectively, to obtain S1'', S2'', and S3'', respectively, means connected to said dividing means and said syndrome storage unit for generating a second signal when three or more of the components S0, S1'', S2'', and S3'' are equal, means responsive to said second signal for adding one of said equal components of the components S0, S1'', S2'', and S3'' to the character C2 as it is shifted from said 14 character shift register, means connected to said syndrome storage unit for generating a third signal when S0+S1 Alpha 1(S1+S2) Alpha 2(S2+S3), means for adding S0, S1, and S3 to obtain a first sum, means for adding S1 and S3 to obtain a second sum, and means responsive to said third signal for adding said first sum to the character C1 as it is shifted from said 14 character shift register and for adding said second sum to the character C2 as it is shifted from said 14 character shift register.

Claim 12

The arrangement of claim 8 further including means responsive to said first signal for adding one of the equal components of the group S0, S1, S2, and S3 to S1, S2, and S3 when three or more of the components of the group S0, S1, S2, and S3 are equal, means responsive to said second signal for adding one of the equal components of the group S0, S1'', S2'', and S3'' to S1, S2, and S3 when three or more of the components of the group S0, S1'', S2'', and S3'' are equal, and means responsive to said third signal for setting the components S1, S2, and S3 to zero.