US3825893A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Modular distributed error detection and correction apparatus and method
Assignee: International Business Machines Corp
•
Filing: 1973-05-29
•
Granted: 1974-07-23
•
Expires: 1993-05-29
Abstract
Abstract Errors in code words fetched from memory or utilized in some other device are detected by apparatus distributed throughout the memory and then corrected. Illustratively, a 72-bit parallel code word, comprising a 64-bit information portion and an 8-bit check portion is fetched from the memory. The check bit generator consists of 8 identical modular units which, in the case of use in a memory, can be located at different locations within the memory. The identical modular units are connected in accordance with connections determined by an H matrix. The H matrix is partitioned into eight equal sections associated with eight information bits forming a byte and a single check bit. The rows of each partition or section are cyclically permutated from section to section. For example, the first row of the first section becomes the second row of the second section, etc. Each partition of the H matrix contains the same number of 1''s and each row within a partition is part of a different code group. Each of the identical modular arrangements contains a logic circuit grouping. The input information byte bits are connected to the circuits of the logic grouping so as to produce as circuit outputs the parities of the part of the code groups in the partition or section associated with the module. The identical modular units also contain circuitry to receive the partial code groups parities from the other modular units concerned with the same code group. These partial code group parities and the partial code group parity of the respective module are combined to provide the check bit for the particular module. The partial code group parity outputs from the module are transmitted to the successive other modules to form the partial code group parity inputs for the respective modules. After the information has been utilized such as writing in storage, the information bits and check bits are read into an error detector which compares the check bits generated from the received information bits with the received check bits. An error locator analyzes any mismatch to determine the location of an error. An error corrector then corrects any information or check bit which is identified as incorrect by the error locator. The error detector can consist of the same identical modular units as the check bit generator.
Inventors
- 👤 D Bossen
- 👤 A Patel
- 👤 S Hong
- 👤 M Hsiao
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 11:22
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1008; G06F11/1012; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/19
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
267 words
In a system for detecting and correcting errors in code words having a plurality of information bits and a plurality of check bits, each information bit assigned to a number of code groups, the plurality of code groups being divided into equal length sections, each section forming an information byte of equal number of information bits, an improved check bit generator comprising: input means for accepting signals manifesting information bits; a plurality of identical modular units corresponding in number to the number of said equal length sections; a number of identical logic circuit groupings, one for each byte, one located on each of said plurality of identical modular units; connecting means for connecting each identical logic grouping to the input means to accept those information bit signals that are assigned to the respective section of the code groups, each identical logic grouping supplying at outputs a parity signal for each length of each code group within the section; a second logic circuit means, one located on each of said modules, connected to input means to receive the parity signals from other modules generated in accordance with the lengths of the same code group and generate a parity output representative of said inputs; and third logic circuit means, one located on each of said modules, for combining the parity signal from said second logic circuit means and the parity signal for the length of the same code group generated by the respective module to supply at an output of the respective module one check bit signal manifesting a function of the information bit signals in its code group.
Claim 2
Dependent Claim
267 words
In a system for detecting and correcting errors in code words having a plurality of information bits and a plurality of check bits, each information bit assigned to a number of code groups, the plurality of code groups being divided into equal length sections, each section forming an information byte of equal number of information bits, an improved check bit generator comprising: input means for accepting signals manifesting information bits; a plurality of identical modular units corresponding in number to the number of said equal length sections; a number of identical logic circuit groupings, one for each byte, one located on each of said plurality of identical modular units; connecting means for connecting each identical logic grouping to the input means to accept those information bit signals that are assigned to the respective section of the code groups, each identical logic grouping supplying at outputs a parity signal for each length of each code group within the section; a second logic circuit means, one located on each of said modules, connected to input means to receive the parity signals from other modules generated in accordance with the lengths of the same code group and generate a parity output representative of said inputs; and third logic circuit means, one located on each of said modules, for combining the parity signal from said second logic circuit means and the parity signal for the length of the same code group generated by the respective module to supply at an output of the respective module one check bit signal manifesting a function of the information bit signals in its code group.
Claim 3
Dependent Claim
43 words
In a system for detecting and correcting errors according to claim 1, wherein said identical logic circuit groupings include a plurality of EXCLUSIVE OR circuits, one for each partial code group in the section to which at least one information bit is assigned.
Claim 4
Dependent Claim
58 words
In a system for detecting and correcting errors according to claim 2, wherein said connecting means connecting said logic grouping to said input means includes a connection from the input terminal at which a particular information bit is received to each of said EXCLUSIVE OR circuits representing a partial code group to which said information bit is assigned.
Claim 5
Dependent Claim
40 words
In a system for detecting and correcting errors according to claim 3, wherein said EXCLUSIVE OR circuits in said logic grouping each provide at an output the parity of the partial code group associated with the respective EXCLUSIVE OR circuit.
Claim 6
Dependent Claim
53 words
In a system for detecting and correcting errors according to claim 1, wherein said logic grouping performs the EXCLUSIVE OR operation on each information bit input of said byte thereby providing a parity signal at an output of said logic grouping representing the parity of all the information bits utilized in said module.
Claim 7
Dependent Claim
53 words
In a system for detecting and correcting errors in accordance with claim 1, wherein said second logic circuit is an EXCLUSIVE OR circuit providing as an output the modulo 2 addition of the parity inputs thereto of the partial code groups of the same code group from the other modules of the system.
Claim 8
Dependent Claim
65 words
In a system for detecting and correcting errors in accordance with claim 6, wherein said third logic circuit is an EXCLUSIVE OR circuit for performing the EXCLUSIVE OR function on said output of said second logic circuit and the parity of the byte or partial code group associated with the module to produce as an output therefrom the check bit of the entire code group.
Claim 9
Dependent Claim
295 words
In a system for detecting and correcting errors in code words having a plurality of information bits and a plurality of check bits, each information bit assigned to a number of code groups, the plurality of code groups being divided into equal length sections, each section forming an information byte of equal number of information bits, an improved error detector comprising: input means for accepting signals manifesting information bits; a plurality of identical modular units corresponding in number to the number of said equal length sections; a number of identical logic circuit groupings, one for each byte, one located on each of said plurality of identical modular units; connecting means for connecting each identical logic grouping to the input means to accept those information bit signals that are assigned to the respective section of the code groups, each identical logic grouping supplying at outputs a parity signal for each length of each code group within the section; a second logic circuit means, one located on each of said modules, connected to input means to receive the parity signals from other modules generated in accordance with the lengths of the same code group and generate a parity output representative of said inputs; means located on said module to receive a previously stored check bit associated with said module; third logic circuit means, one located on each of said modules, for combining the parity signal from said second logic circuit means with said received check bit and the parity signal for the length of the same code group generated by the respective module to supply at an output of the respective module a syndrome signal manifesting an error if the correct parity of the code group is not obtained or the received check bit is in error.
Claim 10
Dependent Claim
295 words
In a system for detecting and correcting errors in code words having a plurality of information bits and a plurality of check bits, each information bit assigned to a number of code groups, the plurality of code groups being divided into equal length sections, each section forming an information byte of equal number of information bits, an improved error detector comprising: input means for accepting signals manifesting information bits; a plurality of identical modular units corresponding in number to the number of said equal length sections; a number of identical logic circuit groupings, one for each byte, one located on each of said plurality of identical modular units; connecting means for connecting each identical logic grouping to the input means to accept those information bit signals that are assigned to the respective section of the code groups, each identical logic grouping supplying at outputs a parity signal for each length of each code group within the section; a second logic circuit means, one located on each of said modules, connected to input means to receive the parity signals from other modules generated in accordance with the lengths of the same code group and generate a parity output representative of said inputs; means located on said module to receive a previously stored check bit associated with said module; third logic circuit means, one located on each of said modules, for combining the parity signal from said second logic circuit means with said received check bit and the parity signal for the length of the same code group generated by the respective module to supply at an output of the respective module a syndrome signal manifesting an error if the correct parity of the code group is not obtained or the received check bit is in error.
References Cited (Backward Citations)
US3648239A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1977-07-22 | 1978-01-21 | 1978-07-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1981-07-22 | 1982-01-21 | 1982-07-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1985-07-22 | 1986-01-21 | 1986-07-23 | $7700.00 | Window Closed / Lapsed |