-
公开(公告)号：CA935930A
公开(公告)日：1973-10-23
申请号：CA71348
申请日：1970-01-05
Inventor： CHIEN R , HSIAO MU-YUE , SELLERS F JR , BOSSEN D
Abstract: 1,247,823. Error-correcting systems. INTERNATIONAL BUSINESS MACHINES CORP., and ROBERT TIENWEN CHIEN. 8 Jan., 1970 [8 Jan., 1969], No. 1041/70. Heading G4A. A message containing k data bits has 2m check bits added to it (k#m 2 , where m=integer greater than 1) for each of t error-correcting capabilities (t#1), and a decoder comprises t parity-checking circuits supplying outputs to an error-correcting circuit for that bit. As an example, where k=25 and m=5, the message bits d 0 -d 24 are considered arranged as a 5 x 5 matrix, check bits c 1 -c 5 are derived by exclusive OR operation on the matrix rows (e.g. c 1 =EXOR (do, d 1 , d 2 , d 3 , d 4 ) and check bits c 6 -c 10 are similarly derived from the matrix columns (e.g. c 6 =EXOR d 0 , d 5 , d 10 , d 15 , d 20 ) to provide for single error correction. For each additional error correction capability, a pair of orthogonal Latin squares such as L 1 , L 2 and L 3 , L 4 , Fig. 4, is used to select two groups of 5 bits from the matrix, each group comprising bits located in positions marked with the same number in the Latin squares, the additional check bits c 11 -c 15 (L 1 ), C 16 -C 20 (L 2 ) again being derived by exclusive OR operation on the 5 selected bits. Each bit d 0 -d 24 therefore occurs in only two of the equations defining each set of mt check bits. For each bit, such as d 0 , the error-correcting decoder comprises a module I-III, Fig. 5, for each error-correcting capability, each module consisting of a pair of exclusive OR circuits such as 30, 32 receiving inputs corresponding to the check bit equations in which that bit occurs, e.g. for do circuit 30 has inputs d 1 -d 4 and c 1 . Each circuit 30, 32 provides an output which should be a copy of the corresponding bit, and these copies, together with the original bit are supplied to a majority logic gate 38 to provide a corrected output, assuming not more than the number of random errors allowed for have occurred. For the ease where k
-
公开(公告)号：US3825893A
公开(公告)日：1974-07-23
申请号：US36448073
申请日：1973-05-29
Applicant: IBM
CPC classification number: G06F11/1012 , H03M13/19
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.
-
Patent Agency Ranking
公开(公告)号：US3812336A
公开(公告)日：1974-05-21
申请号：US31616372
申请日：1972-12-18
Applicant: IBM
CPC classification number: G11C29/88
Abstract: This specification describes a scheme for swapping bits between words of a memory when a multiple error condition is detected in any word of the memory by a single error correction and multiple error detection system monitoring the memory. The swapping of the bits between the words is done in terms of orthogonal Latin squares insuring that no combination of any two bits is repeated in the reconfigured words. This insures that with a single swapping of the bits the detected multiple error condition is eliminated and makes it highly unlikely that another double error condition will be produced by the swapping.
-
公开(公告)号：BR7404579A
公开(公告)日：1976-02-10
申请号：BR457974
申请日：1974-06-04
Applicant: IBM
Inventor： PATEL A , BOSSEN D , MU-YUE HSIAO
Abstract: 1440285 Error correction INTERNATIONAL BUSINESS MACHINES CORP 24 April 1974 [4 June 1973] 18002/74 Heading G4A Data is stored on a plurality of independently accessible storage units, e.g. magnetic tape cartridges, and check bits, each of which is a function of a corresponding bit from each data storage unit, are stored on a check unit which may be used, in the event of a catastrophic loss of data on one of the data storage units and detected by an error checking facility associated with that unit, to restore the data on that unit. Extension of the system to include more than one check unit, each of which stores the check bits for one position of a Hamming code, is also mentioned. In normal operation, one of the data storage units is selected and data thereon is updated by read before write heads 15, 21. The difference e jk between each old bit and the corresponding new bit is EXORed with the corresponding old parity bit p k from the check unit to update the parity bits. The parity bits are initially recorded by successively (or simultaneously) reading the data storage units to record the modulo 2 sums of the corresponding bits, and data restoration is similar reading from the good data storage units and the check unit.
-
公开(公告)号：CA935932A
公开(公告)日：1973-10-23
申请号：CA106344
申请日：1971-02-26
Applicant: IBM
Inventor： HSIAO MU-YUE , BOSSEN D
IPC: H03M13/43
Abstract: A multiple error correcting system for correcting t (t 2) errors in message of k data bits, m2 k (m+1)2, where m is an integer of at least three, comprises encoding means and decoding means. The encoding means adds r check bits, each check bit corresponding to a number of data bits; each data bit is represented by 2t check bits; these 2t check bits have only the one data bit in common; and, the number, r, of check bits is: 2mt r 2(m+1)t. The decoding means for each data bit has an error correcting circuit receiving 2t+1 inputs from input circuitry, the inputs being the data bit itself, and 2t combinations of check bits and other data bits representing the data bit. The error correcting circuit is capable of producing an output signal correctly corresponding to a data bit if no more than t inputs thereto for that data bit were in error. A coding system for generating these r check bits by augmenting Latin square codes is described.
-
公开(公告)号：BR7404579D0
公开(公告)日：1975-01-07
申请号：BR457974
申请日：1974-06-04
Applicant: IBM
Abstract: 1440285 Error correction INTERNATIONAL BUSINESS MACHINES CORP 24 April 1974 [4 June 1973] 18002/74 Heading G4A Data is stored on a plurality of independently accessible storage units, e.g. magnetic tape cartridges, and check bits, each of which is a function of a corresponding bit from each data storage unit, are stored on a check unit which may be used, in the event of a catastrophic loss of data on one of the data storage units and detected by an error checking facility associated with that unit, to restore the data on that unit. Extension of the system to include more than one check unit, each of which stores the check bits for one position of a Hamming code, is also mentioned. In normal operation, one of the data storage units is selected and data thereon is updated by read before write heads 15, 21. The difference e jk between each old bit and the corresponding new bit is EXORed with the corresponding old parity bit p k from the check unit to update the parity bits. The parity bits are initially recorded by successively (or simultaneously) reading the data storage units to record the modulo 2 sums of the corresponding bits, and data restoration is similar reading from the good data storage units and the check unit.
-
公开(公告)号：CA932466A
公开(公告)日：1973-08-21
申请号：CA103622
申请日：1971-01-25
Applicant: IBM
Inventor： BOSSEN D
Abstract: 1279793 Error-correcting systems INTERNATIONAL BUSINESS MACHINES CORP 11 Jan 1971 [12 Feb 1970] 1255/71 Heading G4A From a block of data comprising K bytes (D 1 , D 2 , ... D K ) each of b bits, two check bytes C 1 and C 2 are computed from the relationships C 1 = ID 1 + 1D 2 + ... +ID K C 2 =A 1 D 1 +A 2 D 2 + ... + A K D K where I is the identity element and A 1 to A K are distinct non-zero elements of Galois Field (2 b ), (the indicated multiplication and addition being Galois Field defined operations), and a decoder recovers the data from the transmitted data and check bytes without error when any number of bits are in error in any single received byte. The decoder may compute two syndrome bytes S1 and S2 each of b bits from the relationships S1 = ID 1 1 + ID 2 1 + ... + ID K 1 + IC 1 1 S2 = A 1 D 1 1 + A 2 D 2 1 + ... + A K D K 1 + IC 2 1 the primes denoting a received byte, and correction of the jth byte is indicated by the zero condition of a correction criterion B j = A j S 1 + IS 2 correction being effected by adding S 1 to the jth byte. Computation of check bits, syndrome bits and error criteria are performed using parallel adders.
-
-
-
-
-
-
Search Results
7
records
(took 0.022 seconds)
