US3745528A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Error correction for two tracks in a multitrack system
Assignee: International Business Machines Corp
•
Filing: 1971-12-27
•
Granted: 1973-07-10
•
Expires: 1991-12-27
Abstract
Abstract A system for correcting two tracks in error in a multi-track data arrangement is provided. The message data Z1, Z2, . . . Zk is encoded by adding two check bytes C1 and C2 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 X m and m and b are integers >1 and k is an integer 2<k<2b. The check bytes are generated in accordance with the equations:
Inventors
- 👤 A Patel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 15:27
CPC Classifications
G; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1833
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
388 words
A system for correcting two tracks in error in a multi-track data arrangement, comprising: means for providing message data Z1, Z2, Z3, . . . Zk arranged in blocks having k bytes arranged in a cross track direction, each byte having f bits of data where f b X m where b and m are integers >1 and k is an integer 2<k<2b; means connected to said means for providing message data for generating two check bytes from said message data in accordance with the equations: C1 Z1 + Z2 + Z3 . . . + Zk and C2 T Z1 + T2 Z2 + . . . + Tk Zk where T is the companion matrix of a binary primitive polynomial g(x) of degree f and lambda is any integer given by the expression t(2b-1)/(2b-1) in which t is any positive integer prime to 2b-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 Z1'', Z2'', . . . Zk'', C1'', C2''; said decoding means including first and second shift registers for generating first and second syndromes S1 and S2 from said encoded message in accordance with the equations: S1 C1'' + Z1'' Z2'' + . . . + Zk'' and S2 C2'' + T Z1'' + T2 Z2'' + . . . + Tk Zk'' 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 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.
Claim 2
Independent Claim
388 words
A system for correcting two tracks in error in a multi-track data arrangement, comprising: means for providing message data Z1, Z2, Z3, . . . Zk arranged in blocks having k bytes arranged in a cross track direction, each byte having f bits of data where f b X m where b and m are integers >1 and k is an integer 2<k<2b; means connected to said means for providing message data for generating two check bytes from said message data in accordance with the equations: C1 Z1 + Z2 + Z3 . . . + Zk and C2 T Z1 + T2 Z2 + . . . + Tk Zk where T is the companion matrix of a binary primitive polynomial g(x) of degree f and lambda is any integer given by the expression t(2b-1)/(2b-1) in which t is any positive integer prime to 2b-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 Z1'', Z2'', . . . Zk'', C1'', C2''; said decoding means including first and second shift registers for generating first and second syndromes S1 and S2 from said encoded message in accordance with the equations: S1 C1'' + Z1'' Z2'' + . . . + Zk'' and S2 C2'' + T Z1'' + T2 Z2'' + . . . + Tk Zk'' 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 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.
Claim 3
Dependent Claim
88 words
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.
Claim 4
Dependent Claim
93 words
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 Tf , the positions of the 1''s 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.
Claim 5
Dependent Claim
79 words
A system according to claim 1, wherein said error track parameters signal generating means receives error track pointer signals P1, P2, . . . Pk, Pk 1, Pk 2 from said means for providing error track pointer signals and generates parameters x and y as binary numbers, new pointers I1, I2, . . . Ik identifying the first erroneous data track, and the signals N0, N1 and N3 indicating respectively, 0, 1 and more than 2 tracks in error.
Claim 6
Dependent Claim
120 words
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 P1, P2, . . . Pk from said means for providing pointer signals arranged in groups of increasing order by a pointer value of 1 starting with P1, P1P2, P1P2P3, . . . P1P2P3 . . . Pk, all the pointer signals except the additional pointer signal in each group being connected through one of said NOT circuits so that an output Ii is obtained from the AND circuit in which the additional pointer signal has a ''''1'''' input thereby identifying the first data track in error.
Claim 7
Dependent Claim
64 words
A system according to claim 5, wherein said error track parameters signal generating means further includes a first plurality of OR circuits, said Ii 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.
Claim 8
Dependent Claim
188 words
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 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 kth group being all possible pairs separated by k-1 error track pointer signal inputs, the outputs of each of said groups of 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.
Claim 9
Dependent Claim
83 words
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 N0, N1 and N3 as outputs therefrom, respectively, representing 0, 1 and more than two tracks in error.
Claim 10
Dependent Claim
98 words
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 ej computation which is computed from the syndromes S1 and S2 according to: ej Tx (S1 + Ty S2).
Claim 11
Dependent Claim
40 words
A system according to claim 9, wherein inhibiting means are provided connected to the output of shift register SR2 for inhibiting the ej output when j k+2 and pointer Pk 2 is on indicating the k+2 track is in error.
Claim 12
Dependent Claim
43 words
A system according to claim 10, wherein said error correcting means includes means for adding (modulo 2) error pattern ej, erroneous read bytes Z1'', Z2'', . . . Zk'' and syndrome S1 to obtain the corrected bytes Z1, Z2, . . . Zk.
Claim 13
Dependent Claim
108 words
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 N0, N1, and N3 signals, and to said shift registers SR1 and SR2 which provide syndrome S1 and error pattern ej signals, respectively; said N3 signal indicating that more than two tracks are in error, and said N1 signal indicating that only one track is in error and that ej is not 0 in all bit positions, and said N0 signal indicating that no track is in error when ej or S1 is not 0 in all bit positions.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1976-07-09 | 1977-01-08 | 1977-07-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1980-07-09 | 1981-01-08 | 1981-07-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1984-07-09 | 1985-01-08 | 1985-07-10 | $7700.00 | Window Closed / Lapsed |