Patent US3582878A successfully refreshed from Google Patents.
US3582878A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiple random error correcting system
Assignee: International Business Machines Corp
•
Filing: 1969-01-08
•
Granted: 1971-06-01
•
Expires: 1989-01-08
Abstract
Abstract The error correcting system is capable of correcting multiple random errors in data messages of k m2 data bits where m is an integer. The message is encoded by adding 2m check bits for each additional error correcting capability. The encoded message after data transfer and storage is decoded by parity checking and threshold logic decision circuits. The parity checking circuits are constructed in modular form. Each additional module adds a further error correcting capability. The outputs from each module form inputs to the threshold logic decision circuit where the error correction is made. Detection of an additional error can be simply achieved by an overall parity circuit.
Inventors
- 👤 Douglas C Bossen
- 👤 Robert T Chien
- 👤 Mu-Yue Hsiao
- 👤 Frederick F Sellers Jr
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 07:58
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/004; H04L1/0056; H04L1/0057; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/19; H04L1/0041
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
101 words
A multiple random error correcting system for correcting messages of k( m2) data bits where m is an integer greater than 2 comprising: encoding means for adding 2m check bits to said data bits for each of a plurality of error correcting capabilities to generate 2mt check bits for t error correcting capabilities; and decoding means including an error correcting circuit for each of said data bits and a linear logic circuit module for each error correcting capability for performing parity checks for each data bit, the outputs of each linear logic circuit module forming inputs to said error correcting circuit.
Claim 2
Dependent Claim
101 words
A multiple random error correcting system for correcting messages of k( m2) data bits where m is an integer greater than 2 comprising: encoding means for adding 2m check bits to said data bits for each of a plurality of error correcting capabilities to generate 2mt check bits for t error correcting capabilities; and decoding means including an error correcting circuit for each of said data bits and a linear logic circuit module for each error correcting capability for performing parity checks for each data bit, the outputs of each linear logic circuit module forming inputs to said error correcting circuit.
Claim 3
Dependent Claim
36 words
A system in accordance with claim 1, wherein each linear logic circuit module includes two EXCLUSIVE OR circuits each having m input terminals to which are applied m-1 data bit inputs and a check bit input.
Claim 4
Dependent Claim
36 words
A system in accordance with claim 2, wherein any two of said EXCLUSIVE OR circuits from any combination of said linear logic circuit modules are interchangeable to produce an output representative of the same data bit.
Claim 5
Dependent Claim
62 words
A system in accordance with claim 1, wherein said error correcting circuit comprises a threshold logic circuit for each of said data bits where the threshold has been fixed so as to produce an output signal representative of the outputs of the associated linear logic circuit modules forming data bits if the majority of the data bit inputs thereto are the same.
Claim 6
Dependent Claim
33 words
A system in accordance with claim 4, wherein each threshold logic circuit contains an additional input for a signal representative of the data bit itself which the respective threshold logic circuit is correcting.
Claim 7
Dependent Claim
76 words
A system in accordance with claim 1, wherein said encoding means includes 2M EXCLUSIVE OR circuits for each error correcting capability each EXCLUSIVE OR circuit having m inputs for receiving different combinations of said k data bits, pairs of said 2m EXCLUSIVE OR circuits having a common data bit input and having no other data bit in common, the output from each of said EXCLUSIVE OR circuits representing a different one of said 2m check bits.
Claim 8
Dependent Claim
44 words
A system in accordance with claim 6, wherein said different combinations of said m2 data bits applied to the inputs of each EXCLUSIVE OR circuit are determined in accordance with the orthogonality of a pair of orthogonal Latin squares for each error correcting capability.
Claim 9
Dependent Claim
55 words
A system in accordance with claim 7, wherein said different combinations of said k data bits for each EXCLUSIVE OR circuit for the first error correcting capability are obtained by applying the data bits in each row and each column of a basic square array of the data to inputs of respective EXCLUSIVE OR circuits.
Claim 10
Dependent Claim
78 words
A system in accordance with claim 8, wherein said different combinations of said k data bits for each EXCLUSIVE OR circuit for the second and succeeding error correcting capabilities are obtained by applying those data bits to the inputs of respective EXCLUSIVE OR circuits which correspond in position in said basic square array of data to the position of digits which are the same in each of a pair of orthogonal Latin squares for each error correcting capability.
Claim 11
Independent Claim
152 words
A method for correcting multiple random errors in a data processing system parallel bit message of k( m2) data bits where m is an integer > 2 comprising the steps of: generating 2mt check bits simultaneously for said message from predetermined groups of said message bits where t is equal to the number of errors that can be corrected, each data bit appearing in exactly 2t of these 2mt groups, each 2t of these groups contains a common data bit and has no other data bits in common, said grouping of said bit message being formed in accordance with the orthogonality of orthogonal Latin squares for the integer m; generating a first redundant bit for each common data bit appearing in 2t of the 2mt groups; and generating a further redundant bit when the majority of said first redundant bits and said common data bit agree, thereby correcting up to t errors.
Claim 12
Independent Claim
152 words
A method for correcting multiple random errors in a data processing system parallel bit message of k( m2) data bits where m is an integer > 2 comprising the steps of: generating 2mt check bits simultaneously for said message from predetermined groups of said message bits where t is equal to the number of errors that can be corrected, each data bit appearing in exactly 2t of these 2mt groups, each 2t of these groups contains a common data bit and has no other data bits in common, said grouping of said bit message being formed in accordance with the orthogonality of orthogonal Latin squares for the integer m; generating a first redundant bit for each common data bit appearing in 2t of the 2mt groups; and generating a further redundant bit when the majority of said first redundant bits and said common data bit agree, thereby correcting up to t errors.
Claim 13
Dependent Claim
37 words
A method according to claim 13, wherein a check bit is added to said message for each row and each column of a basic square array of said m2 data bits for the first error correcting capability.
Claim 14
Dependent Claim
73 words
A method according to claim 11, wherein said 2mt check bit output equations are formed for two or more error correcting capabilities by adding a check bit for each group of data bits in said basic square array which correspond in position to similar digits in each of a pair of orthogonal Latin squares for k data bits, a further pair of orthogonal Latin squares are used for each successive error correcting capability.
References Cited (Backward Citations)
US2978678A
Cited
US3037697A
Cited
US3183483A
Cited
US3200374A
Cited
US3234510A
Cited
US3222644A
Cited
US3164804A
Cited
US3369184A
Cited
US3404373A
Cited
US3439332A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1974-05-31 | 1974-11-30 | 1975-06-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1978-05-31 | 1978-11-30 | 1979-06-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1982-05-31 | 1982-11-30 | 1983-06-01 | $7700.00 | Window Closed / Lapsed |