Error correction for two bytes in each code word in a multi-code word system

Abstract

A system for correcting two .[.tracks.]. .Iadd.bytes .Iaddend.in error in .Iadd.each code word of .Iaddend.a .[.multi-track.]. .Iadd.multi-code word .Iaddend.data arrangement is provided. The message data Z 1 , Z 2 , . . . Z k is encoded by adding two check bytes C 1 and C 2 thereto which are generated from the message data which is arranged in blocks of k bytes, where each byte has f bits of data, .[.arranged in a cross track direction.]. where f = b × m and m and b are integers >1 and k is an integer 2<k<2 b . The check bytes are generated in accordance with the equations: C.sub.1 =Z.sub.1 ⊕Z.sub.2 ⊕Z.sub.3 . . . ⊕Z.sub.k and C.sub.2 =T.sup.λZ.sub.1 ⊕T.sup.2 .sup.λ Z.sub.2 ⊕ . . . ⊕T k .sup.λ Z k where T is the companion matrix of a binary primitive polynomial g(x) of degree f and λ is an integer given by the expression: t(2.sup.f -1)/(2.sup.b -1) in which t is any positive integer prime to 2 b -1. The encoded message is decoded after usage (indicated by the ' symbol) by first and second shift registers which generate first and second syndromes from the encoded data in accordance with the equations: S.sub.1 =C.sub.1 '⊕Z.sub.1 '⊕Z.sub.2 '⊕ . . . ⊕Z.sub.k ' S.sub.2 =C.sub.2 '⊕T.sup.λZ.sub.1 '⊕T.sup.2.sup.λ Z 2 '⊕ . . . ⊕T k .sup.λ Z k ' Error pointers are provided for indicating the .[.tracks.]. .Iadd.bytes .Iaddend.in error and the .[.bytes.]. .Iadd.bits .Iaddend.in error in the indicated .[.tracks.]. .Iadd.bytes .Iaddend.are corrected in accordance with the error patterns generated by processing the syndromes.

What is claimed is: 
     
       1. A system for correcting two tracks in error in a multi-track data arrangement, comprising: means for providing message data Z 1 , Z 2 , Z 3 ,...Z k  arranged in blocks having k bytes arranged in a cross track direction, each byte having f bits of data where f = b × m where b and m are integers >1 and k is an integer 2<k< 2 b  ;   means connected to said means for providing message data for generating two check bytes from said message data in accordance with the equations:   C.sub.1 = Z.sub.1 ⊕Z.sub.2 ⊕Z.sub.3...⊕Z.sub.k     and     C.sub.2 = T.sup.λZ.sub.1 ⊕T.sup.2.sup.λ Z.sub.2 ⊕...⊕T.sup.k.sup.λ Z.sub.k     where T is the companion matrix of a binary primitive polynomial g(x) of degree f and λ is any integer given by the expression t(.[.2 b  .]. .Iadd.2 f .Iaddend. -1)/(2 b  -1) in which t is any positive integer prime to 2 b  -1;     means connected to said means for providing message data and to said means for generating two check bytes for appending said two check bytes to said message data to form an encoded message;   means connected to said means for appending said two check bytes to said message data for utilizing said encoded message;   means connected to said utilization means for decoding said encoded message denoted by Z 1  ', Z 2  ',...Z k  ', C 1  ', C 2  '; said decoding means including first and second shift registers for generating first and second syndromes S 1  and S 2  from said encoded message in accordance with the equations:   S.sub.1 = C.sub.1 '⊕Z.sub.1 '⊕Z.sub.2 '⊕...⊕Z.sub.k '     and     S.sub.2 = C.sub.2 '⊕T.sup.λ Z.sub.1 '⊕T.sup.2 .sup.λ Z.sub.2 '⊕...⊕T.sup.k .sup.λ Z.sub.k '       means for providing error track pointer signals as inputs to said decoder which identify the tracks in error;   error .[.track.]. parameters signal generating means connected to said means for providing error .[.track.]. pointer signals for providing fixed signals in accordance with the tracks indicated to be in error;   means connected to said error track parameters signal generating means for generating control signals for the operation of said decoder; and   error correcting means connected to said first and second shift registers, to said means for providing .[.identifying.]. .Iadd.error pointer .Iaddend.signals, to said means for providing control signals, and to said utilization means for providing error correction of the erroneous bytes in any two indicated tracks in error.   
     
     
       2. A system according to claim 1, wherein said means for generating said two check bytes includes a data distributor and first and second feedback shift registers connected to said data distributor, said first shift register providing modulo 2 addition of the information bytes successively applied thereto from said data distributor and said second shift register providing the product of the contents thereof and the incoming byte from said data distributor and the modulo 2 addition thereof with the product of the contents thereof and the next input byte. 
     
     
       3. A system according to claim 2, wherein said second feedback shift register has f data stages and a modulo 2 summing circuit at the input to each stage, the feedback connections of each of said stages of said feedback shift register are determined in accordance with the digital "1" contents of the corresponding column of the matrix T f , the positions of the 1's is in the column determining feedback connections to the modulo 2 summing circuits at the inputs of the shift register stages having corresponding numerical positions in said feedback shift register. 
     
     
       4. A system according to claim 1, wherein said error .[.track.]. parameters signal generating means receives error .[.track.]. pointer signals P 1 , P 2 ,...P k , P k   +2  from said means for providing error .[.track.]. pointer signals and generates parameters x and y as binary numbers, new pointers I 1 , I 2 ,...I k  identifying the first erroneous data track, and the signals N 0 , N 1  and N 3  indicating respectively, 0, 1 and more than 2 tracks in error. 
     
     
       5. A system according to claim 4, wherein said error .[.track.]. parameters signal generating means includes a plurality of logical AND and NOT circuits having as inputs thereto the track in error pointer signals P 1 , P 2 ,...P k  from said means for providing pointer signals arranged in groups of increasing order by a pointer value of 1 starting with P 1 , P 1  P 2  P 1  P 2  P 3 ,...P 1  P 2  P 3 ...P k , all the pointer signals except the additional pointer signal in each group being connected through one of said NOT circuits so that an output I i  is obtained from the AND circuit in which the additional pointer signal has a "1" input thereby identifying the first data track in error. 
     
     
       6. A system according to claim 5, wherein said error .[.track.]. parameters signal generating means further includes a first plurality of OR circuits, and said I i  signals identifying the first track in error are grouped as inputs to said first plurality of OR circuits, the grouping is predetermined in accordance with a table wherein the output y parameter is obtained as a predetermined b-bit binary number. 
     
     
       7. A system according to claim 4, wherein said error track parameters signal generating means, further includes a second plurality of AND circuits and a second and third plurality of OR circuits said second plurality of AND circuits having error track pointer signals as inputs thereto arranged in groups of pairs, said pairs of inputs thereto arranged in groups of pairs, said pairs of said first group being all possible adjacent pairs, said pairs of said second group being all possible pairs separated by one error track pointer signal input, said pairs of said third group being all possible pairs separated by two error track pointer signal inputs, said pairs of said k th  group being all possible pairs separated by k-1 error track pointer signal inputs, the outputs of each of said groups of said second plurality of AND circuits are connected to respective ones of said second plurality of OR circuits whose outputs correspond to the j-i=1 to the j-i=k-1 value; each of the j-i value outputs being connected as inputs to said third plurality of OR circuits, the connections being determined in accordance with a predetermined table giving said x parameter as a b-bit binary number. 
     
     
       8. A system in accordance with claim 4, wherein said error track parameters signal generating means further includes a combination of a plurality of NOT circuits connected to an AND circuit, a `one and only one` circuit, and a threshold circuit, each of said circuits having the error track parameters signals from said error track parameters signal generating means as inputs thereto and having said signals N 0 , N 1  and N 3  as outputs therefrom, respectively, representing 0, 1 and more than two tracks in error. 
     
     
       9. A system in accordance with claim 4, wherein said means for generating control signals includes counting means which are energized to count down simultaneously with the shift signal for said shift registers SR1 and SR2; means for setting said counting means to the binary value of x generated by said error track parameters signal generating means and counting down to 0 in synchronism with the shifting of SR1 and SR2 to introduce the parameter y into the error pattern e j  computation which is computed from the syndromes S 1  and S 2  according to:   e.sub.j = T.sup.x.sup.λ [S.sub.1 ⊕T.sup.y .sup.λ S.sub.2 ].       
     
     
       10. A system according to claim 9, wherein inhibiting means are provided connected to the output of shift register SR2 for inhibiting the e j  output when j = k+2 and pointer P k   +2  is on indicating the k+2 track is in error. 
     
     
       11. A system according to claim 10, wherein said error correcting means includes means for adding (modulo 2) error pattern e j , erroneous read bytes Z 1  ', Z 2  ',...Z k  ' and syndrome S 1  to obtain the corrected bytes Z 1 , Z 2 ,...Z k . 
     
     
       12. A system according to claim 4, wherein said decoding means further includes an uncorrectable error indicating circuit connected to said error track parameters signal generating means which provides said N 0 , N 1 , and N 3  signals, and to said shift registers SR1 and SR2 which provide syndrome S 1  and error pattern e j  signals, respectively; said N 3  signal indicating that more than two tracks are in error, and said N 1  signal indicating that only one track is in error and that e j  is not 0 in all bit positions, and said N 0  signal indicating that no track is in error when e j  or S 1  is not 0 in all bit positions. .Iadd.13. A system for correcting two bytes in error in each code word in a multi-code word data arrangement comprising: means for providing message data Z 1 , Z 2 , Z 3 ,...Z k  arranged in blocks having k bytes, each byte having f bits of data where f = b × m and where b and m are integers >1 and k is an integer 2<k<2 b  ;   means connected to said means for providing message data for generating two check bytes from said message data in accordance with the equations:   C.sub.1 = Z.sub.1 ⊕Z.sub.2 ⊕Z.sub.3...⊕Z.sub.k     and     C.sub.2 = T.sup.λZ.sub.1 ⊕T.sup.2.sup.λ Z.sub.2 ⊕...⊕T.sup.k.sup.λ Z.sub.k     where T is the companion matrix of a binary primitive polynomial g(x) of degree f and λ is any integer given by the expression t(2 f  -1)/(2 b  -1) in which t is any positive integer prime to 2 b  -1;     means connected to said means for providing message data and to said means for generating two check bytes for appending said two check bytes to said message data to form an encoded message;   means connected to said means for appending said two check bytes to said message data for utilizing said encoded message;   means connected to said utilization means for decoding said encoded message denoted by Z 1  ', Z.sub. 2 ',...Z k  ', C 1  ', C 2  '; said decoding means including first and second shift registers for generating first and second syndromes S 1  and S 2  from said encoded message in accordance with the equations:   S.sub.1 = C.sub.1 '⊕Z.sub.1 '⊕Z.sub.2 '⊕...⊕Z.sub.k '     and     S.sub.2 = C.sub.2 '⊕T.sup.λZ.sub.1 '⊕T.sup.2.sup.λ Z.sub.2 '⊕...⊕T.sup.k.sup.λ Z.sub.k '     means for providing error signals as inputs to said decoder which identify the bytes in error:     error parameters signal generating means connected to said means for providing error pointer signals for providing fixed signals in accordance with the bytes indicated to be in error;   means connected to said error parameters signal generating means for generating control signals for the operation of said decoder; and   error correcting means connected to said first and second shift registers, to said means for providing error pointer signals, to said means for providing control signals, and to said utilization means for providing error correction of the erroneous bits in any two indicated bytes in error. .Iaddend.