US3697948A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus for correcting two groups of multiple errors
Assignee: International Business Machines Corp
•
Filing: 1970-12-18
•
Granted: 1972-10-10
•
Expires: 1990-12-18
Abstract
Abstract Apparatus including a decoder adapted for recovering the data from a received message corresponding to the sent message but which may be in error wherein the blocks of data consist of k bytes of data (D0, D1, D2,...Dk-1) each of b bits. The sent message comprises the k bytes of data plus two check bytes C1 and C2, each of b bits. The decoder is effective in recovering the data without error when not more than two of the bytes are in error no matter how many bits may be in error in the two bytes. Pointers are required which indicate the two bytes containing errors. In the absence of the pointers or in the presence of a single false pointer, the decoder is effective in recovering the data without error when not more than a single byte is in error no matter how many bits may be in error in the single byte. The message is encoded by computing the check bytes according to the relationship:
Inventors
- 👤 Douglas C Bossen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 22:29
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/004; H04L1/0056; H04L1/0057; G; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1833; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; H03M13/151; H03M13/1575; H03M13/159
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
212 words
Apparatus for encoding a message to be sent and decoding a received message of blocks of data having k bytes of b bits each to correct any two bytes in error regardless of the number of bits in error within said two bytes comprising: an encoder for encoding the data by adding to each block of data two check bytes which are related to the data in accordance with the equation: C1 ID0 + ID1 + ID2 + ID3...IDk 1 and C2 ID0 + TD1 + T2D2 +...+ Tk 1 Dk 1 respectively, wherein I is the identity element and T, T2, T3 ...Tk 1 are distinct non-zero elements of Galois Field (2b), wherein the indicated multiplication and addition are the Galois Field defined operations, and wherein b is an integer > 1, and k is an integer 2 < k < 2b; a decoder including pointer signal receiving means for storing pointer signals which indicate the byte in error; said decoder including an error signal computing means for generating error signals indicative of the bits in error in each of two bytes in error indicated by the pointer signal receiving means; and error correcting means utilizing said error signals from said error signal computing means for correcting said bytes in error.
Claim 2
Dependent Claim
212 words
Apparatus for encoding a message to be sent and decoding a received message of blocks of data having k bytes of b bits each to correct any two bytes in error regardless of the number of bits in error within said two bytes comprising: an encoder for encoding the data by adding to each block of data two check bytes which are related to the data in accordance with the equation: C1 ID0 + ID1 + ID2 + ID3...IDk 1 and C2 ID0 + TD1 + T2D2 +...+ Tk 1 Dk 1 respectively, wherein I is the identity element and T, T2, T3 ...Tk 1 are distinct non-zero elements of Galois Field (2b), wherein the indicated multiplication and addition are the Galois Field defined operations, and wherein b is an integer > 1, and k is an integer 2 < k < 2b; a decoder including pointer signal receiving means for storing pointer signals which indicate the byte in error; said decoder including an error signal computing means for generating error signals indicative of the bits in error in each of two bytes in error indicated by the pointer signal receiving means; and error correcting means utilizing said error signals from said error signal computing means for correcting said bytes in error.
Claim 3
Dependent Claim
72 words
Apparatus according to claim 1, wherein said decoder includes a first and second syndrome computer which computes S1 and S2 syndrome signals from the block of data and the check bits C1 and C2 according to the equations: S1 ID'' 0 + ID'' 1,...ID'' k 1 + IC'' 1 S2 ID'' 0 + TD'' 1 + T2 D'' 2 + T3 D'' 3, . . .Tk 1 D'' 4 3 + C''2
Claim 4
Dependent Claim
67 words
Apparatus according to claim 2, wherein said decoder includes a control signal generator which receives as inputs thereto said S1 and S2 syndrome signals and said pointer signals from said pointer signal receiving means and generates therefrom first byte in error identifying signals I0, I1,...Ik; second byte in error identifying signals J1, J2,...,Jk and distance between first and second byte in error idenTifying signals d1, d2,...,dk 1.
Claim 5
Dependent Claim
63 words
Apparatus according to claim 3, wherein said control signal generator further generates signal N01, indicating one or no errors, signal Ng designating uncorrectable errors exist, signal S0 indicating no errors and signal Se indicating a single byte correction should be done and in the presence of Se, signal Sd indicating the error is in one of the check bytes and not the data.
Claim 6
Dependent Claim
59 words
Apparatus according to claim 3, wherein said error signal computing means includes modulo 2 adder circuits arranged to solve the syndrome equation S3 T 1 S2 + S1 and AND circuits for gating the outputs of said modulo 2 adder circuits by the first byte in error identifying signal I0, I1, I2,...,Ik 1 generated by said control signal generator.
Claim 7
Dependent Claim
72 words
Apparatus according to claim 5, wherein said error signal computing means further includes a second plurality of modulo 2 adder circuits arranged to multiply (modulo 2) syndrome S3 by (Tj i + I) 1 and a second plurality of AND circuits for gating the outputs of said second plurality of modulo 2 adder circuits by said distance signals d to obtain the error signal S4 (Tj i + I) 1 S3 ej.
Claim 8
Dependent Claim
52 words
Apparatus according to claim 6, wherein an EXCLUSIVE OR circuit is provided having as one input thereto the error signals generated by said error signal computing means and the syndrome S1 output from said S1 syndrome computer which produces an output signal in accordance with the equation S5 S1 + S4 ei.
Claim 9
Dependent Claim
33 words
Apparatus according to claim 1, wherein said error correcting means includes modulo 1 adder means for adding the error computed in said decoder to the received data to thereby reproduce the sent data.
Claim 10
Dependent Claim
125 words
Apparatus according to claim 8, wherein said error correcting means includes a third plurality of AND circuits for gating the error signals S4 ej by the J signals from the control signal generating means and the S5 ei signals from said EXCLUSIVE OR circuit by the I signals from the control signal generating means and further includes a third plurality of modulo 2 adder circuits having as inputs thereto the corresponding bit position outputs from said third plurality of AND circuits and the corresponding data bit from the related data byte thereby adding the errors ej and ei computed by said error signal computing means and said EXCLUSIVE OR circuit to said received data D'' 0, D'' 1,...D'' k 1 to reproduce the sent message.
Claim 11
Dependent Claim
39 words
Apparatus according to claim 3, wherein said I signals I0, I1, I2,...,Ik 1 are generated by a fourth plurality of AND gates for gating each pointer signal P with the inverse pointer signal P of each preceding pointer signal.
Claim 12
Dependent Claim
41 words
Apparatus according to claim 10, wherein said J signals J1, J2,...,Jk are generated by a fifth plurality of AND gates for gating each pointer signal P with the inverse of the corresponding I signals to produce the J SIGNALS J1, J2,...,Jk.
Claim 13
Dependent Claim
89 words
Apparatus according to claim 11, wherein a sixth plurality of AND gates are provided for gating each I signal with each adjacent J signal and then each twice removed J signal increasing the distance between signals being gated by one signal each time until reaching the gating of the first I signal I0 with the last J signal Jk 1, the output of each group of AND circuits being OR''ed in a second EXCLUSIVE OR circuit to produce the distance signals d, the subscript integer representing the actual distance.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1975-10-10 | 1976-04-10 | 1976-10-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1979-10-10 | 1980-04-10 | 1980-10-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1983-10-10 | 1984-04-10 | 1984-10-10 | $7700.00 | Window Closed / Lapsed |