公开(公告)号：CA969666A

公开(公告)日：1975-06-17

申请号：CA125321

申请日：1971-10-18

Applicant: IBM

Inventor： HSIAO MU-YUE ,  MIKHAIL WADIE F

IPC: H03M13/13 ,  G06F11/08

Abstract: A method and apparatus are provided for detecting and correcting double errors automatically by generating syndrome S bits from a binary word having check bits and data bits. The syndrome S bits themselves are decoded to locate and correct single errors. Wen double errors occur in the binary word, the syndrome S bits automatically operate a switching device which changes the bits of the binary word one at a time to correct one of the double errors. If one of the double errors is not corrected when a given bit is changed, this is indicated by the syndrome S bits, and the bit under test is restored as the next bit of the binary word is changed or complemented. Whenever one of the double errors is corrected by the switching device, the syndrome bits then indicate the location of the remaining single error, and the syndrome S bits are decoded to correct the second one of the double errors.

公开(公告)号：DE1499694A1

公开(公告)日：1970-12-23

申请号：DE1499694

申请日：1966-06-07

Applicant: IBM

Inventor： HSIAO MU-YUE ,  YUE SIH KWANG

IPC: H04L1/00 ,  G08B29/00

Abstract: 1,087,685. Error correction. INTERNATIONAL BUSINESS MACHINES CORPORATION. June 2,1966 [June 7, 1965], No. 24603/66. Heading G4A. Error correction apparatus using a feedbackshift register for correcting- input data and buffer means for the data, accepts parallel data input. A plurality of input channels, carrying a block of data. in serial-parallel form comprising: data and. check bitsaccording to a cyclic code,. feeds a set of buffers (one per channel) and a shiftregister having flip-flops, exclusive-or; gates and a plurality of feedback channels.. When. the block has been received, the buffers are shifted, out in synehronism with. recycling of the shift register, AND gates (one per channel) recognise particular bit configurations in the shift register, and control exclusive-or gates to invert erroneous bits (single errors) as they emerge from the buffers: Any such inversion is accompanied. by resetting of all set stages of the shift register. The block of data applied to the input channels above originally obtained its check bits from a further identical shift-register. A further embodiment for correcting burst errorsis described briefly.

公开(公告)号：DE2000565A1

公开(公告)日：1970-07-23

申请号：DE2000565

申请日：1970-01-07

Applicant: IBM

Inventor： CRAIG BOSSEN DOUGLAS ,  HSIAO MU-YUE ,  FAIRBANKS SELLERS JUN FREDERIC ,  TIENWEN CHIEN ROBERT

IPC: H03M13/19 ,  H04L1/00 ,  H04L1/10

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

公开(公告)号：CA990405A

公开(公告)日：1976-06-01

申请号：CA171632

申请日：1973-05-15

Applicant: IBM

Inventor： CHIA DENNIS K ,  HSIAO MU-YUE

IPC: G06F11/22 ,  G01R31/317 ,  G01R31/3183 ,  G01R31/3185

公开(公告)号：DE2456709A1

公开(公告)日：1975-07-10

申请号：DE2456709

申请日：1974-11-30

Applicant: IBM

Inventor： BOSSEN DOUGLAS CRAIG ,  CORDI VINCENT ANTHONY ,  GLICK ELLIS WILLIAM ,  HSIAO MU-YUE ,  SHIFFRIN BARRY NORMAN

IPC: G06F12/16 ,  G06F11/10 ,  H03M13/00 ,  H03K13/32

Abstract: An error correction and detection circuit includes a modular encoder that provides the minimum number of check bits for encoding a particular number of data bits. Means is provided for combining several units to produce the minimum number of code bits when a larger data word is to be encoded. A storage hierarchy system using this error correction circuit is also disclosed.

公开(公告)号：GB1287387A

公开(公告)日：1972-08-31

申请号：GB1576171

申请日：1971-05-19

Applicant: IBM

Inventor： BOSSEN DOUGLAS CRAIG ,  HSIAO MU-YUE

IPC: G06F11/10 ,  H03M13/15

Abstract: 1287387 Error correction-systems INTERNATIONAL BUSINESS MACHINES CORP 19 May 1971 [28 Sept 1970] 15761/71 Heading G4A A syndrome is computed from a code word including check bits, the syndrome is transformed successively through a succession of values, a gate responsive to a predetermined value senses the succession of syndrome values, and a code word bit, in a position corresponding to the number of successive values counted when the gate responds, is inverted to correct an error. In the described embodiment a shortened Bose-Chaudhuri code word containing 15 check bits and 64 data bits is fetched from memory and is entered in a ring counter 114 having a connection from the 00 bit stage 116 to the 78 bit stage 118. An exclusive OR tree syndrome computer 122 derives a 15-bit syndrome by modulo 2 addition of groups of bits. If no error is present the syndrome is all zeros, and a linear feedback shift register 126 arranged according to the generator polynomial of the check bits is successively shifted left so that if an error syndrome is present successive patterns of the syndrome matrix are generated by successive shifts. The register 126 feeds a bank of recognition gates 154 of which a first G oo is used for single error correction and the remainder G 01 -G 78 for double error correction. If two errors are present, the gate corresponding to the difference between the indices of the two erroneous bits responds when the first erroneous bit is in stage 116 of ring counter 114, and a second response is subsequently obtained from G oo , after correction of the first bit, when the second erroneous bit reaches stage 116. The OR'ed outputs of gates 154 are fed to correction gates 158, 159. The number of shifts made is counted at 164, and after 79 shifts, timing gate 162 is closed and data read-out gate 166 is opened. For faster operation, the output of syndrome computer 122 may be connected to conventional circuits for correcting single errors and detecting double errors, only the detected double errors being corrected by the above shift register circuit.

公开(公告)号：DE69127416T2

公开(公告)日：1998-02-26

申请号：DE69127416

申请日：1991-06-21

Applicant: IBM

Inventor： BOSSEN DOUGLAS CRAIG ,  CHEN CHIN-LONG ,  HSIAO MU-YUE ,  MULLIGAN JAMES MICHAEL

IPC: G06K1/12 ,  G06K7/10 ,  G06K19/06

Abstract: A single width bidirectional bar code exhibiting inherent self clocking characteristics is provided so as to be particularly useful in the identification of semiconductor wafers in very large scale integrated circuit manufacturing processes. The codes described herein are robust, reliable and highly readable even in the face of relatively high variations in scanning speed. The codes are also desirably dense in terms of character representations per linear measurements, an important consideration in semiconductor manufacturing wherein space on chips and wafers is at a premium. Additionally, a preferred embodiment of the present invention exhibits a minimum number for the maximum number of spaces between adjacent bars in code symbol sequences.

公开(公告)号：CA1014664A

公开(公告)日：1977-07-26

申请号：CA198776

申请日：1974-05-02

Applicant: IBM

Inventor： BOSSEN DOUGLAS C ,  HSIAO MU-YUE ,  PATEL ARVIND M

IPC: G06F12/16 ,  G06F11/10 ,  G11B20/18 ,  H03M13/00

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.

公开(公告)号：DE2357233A1

公开(公告)日：1974-06-20

申请号：DE2357233

申请日：1973-11-16

Applicant: IBM

Inventor： BOSSEN DOUGLAS CRAIG ,  HAUGH CONNOR FRANCIS ,  HSIAO MU-YUE

IPC: G06F12/16 ,  G06F11/10 ,  G11C29/00 ,  H03M13/00

公开(公告)号：CA935931A

公开(公告)日：1973-10-23

申请号：CA100056

申请日：1970-12-08

Applicant: IBM

Inventor： KOLANKOWSKY E ,  HSIAO MU-YUE

IPC: G06F11/10 ,  H03M13/00 ,  H03M13/19

Abstract: 1315340 Error detection and correction INTERNATIONAL BUSINESS MACHINES CORP 13 Nov 1970 [24 Dec 1969] 54023/70 Heading G4A In data processing apparatus, errors in data words each including k check bits are detected and/or corrected using k syndrome signals each produced by a respective logic circuit, each check bit being provided to precisely one of the logic circuits, and each data bit to three or a larger odd number of the logic circuits, with substantially equal numbers of data and check bits being provided to each logic circuit. Each logic circuit is an EXCL-OR tree providing a syndrome bit. The syndrome bits produce an "error" signal via an OR gate, and also go to an EXCL-OR gate, the "error"signal being ANDed with the output of the EXCL-OR gate to indicate "single error" and with its inverse to indicate "double error". The syndrome bits and their inverses are combined in AND gates enabled by the "single error" signal to locate the single error (if present) this being corrected using a respective EXCL-OR gate of a row of such gates to which the word is fed in parallel. Each "logic circuit" receives a respective 8-bit byte of the 64 information bits in the word (this choice permits the same hardware to be used for byte parity checking elsewhere in the system), others of the information bits, and a respective one of the 8 check bits provided in the word. The check bits were generated from the information bits for inclusion in the word by EXCL-OR trees similar to the "logic circuits" (less the check bit inputs).