Patent GB-1369031-A (GB)
Title: Error detecting apparatus
IPC: G11C29/00
Filed: 1971-11-10
Abstract: 1369031 Error correction INTERNATIONAL BUSINESS MACHINES CORP 10 Nov 1971 [23 Nov 1970] 52114/71 Heading G4A Apparatus for detecting errors in a parallel binary data pattern includes a means for detecting whether any bit position in the pattern is in an "inalterable" state, i.e. invariant for successive patterns, means for detecting the presence of bit error conditions and to indicate the bit position involved, the indication having only a limited accuracy, means for detecting a parity error, and means for detecting, when a parity error is present, whether the indicated bit error position coincides with an inalterable bit. As described the invention is concerned with detecting and correcting errors in group of parallel bits (words) read from a group of "tracks" each "track" being formed by a serial read out memory device, e.g. the shift register described in Specification 1,315,528. The system uses the double error detecting/single error correcting Hamming code in conjunction with parity detecting circuits and circuits providing an indication of the number and identity of "stuck" ("inalterable") tracks, e.g. a track whose output is continuously 1 or 0, to increase the error correcting capability of the Hamming code. The Hamming circuits identify properly an erroneous bit only when a single error is present. In the embodiment described each track, of which there are eight, one being a parity bit and the remainder data and Hamming bits, stores 257 bits, the 257th bit being the complement of the 256th. By means of a bit counter, an AND gate, and a bi-stable latch for each track the 256th and 257th bits are checked to determine whether that track is "stuck". A logic circuit generates signals indicating respectively that three or more, two, and one or no tracks are "stuck". The embodiment operates on the algorithm illustrated in Fig. 1. The eight data bits forming a single word are fed via lines 51 (Fig. 3) to exclusive-OR gates 52 controlled by data correctors, two of which are shown in detail in Fig. 4. Initially the correctors produce a 0 output so that the word passes unchanged along lines 54. The word is passed to a parity checker 55 which generates a signal on line 58 indicating an even or odd number of errors. The data is also passed to a Hamming code error detector which generates signals on lines 66 pointing to tracks in error. The Hamming and parity error information is combined in a logic circuit which generates outputs which control the correctors. If three or more tracks are found to be stuck then no error correction is possible and the processing is halted. Considering operation when the parity check shows an odd parity for the word together with a Hamming error. If two, one, or no tracks are "stuck" AND gates 83 in all the correctors are enabled by a signal on line 85. Lines 66 carry the Hamming decoder outputs and lines 84 are up in the case of odd parity so that only the AND gate 83 in the corrector corresponding to the datum indicated by the Hamming decoder to be in error conducts. The resulting signal on line 87 enables exclusive-OR 52 and the corresponding datum is complemented. If there are  not two stuck tracks then the stuck track signal on line 50 is applied via delay 91 to produce a "pass the data" signal, the delay giving time for the correction to be effected. If two tracks were stuck the corresponding signal on line 48 is passed to exclusive-OR 103 and AND 94. AND 94 also receives a signal from OR 100 which is fed with an input 99 from each corrector. The inputs supplied by the correctors are only activated if the Hamming error signal corresponds to a stuck track, the signals on lines 23 (gate input 97) indicating that the track to which the particular corrector corresponds is stuck. Thus if two tracks are stuck and the error is in neither of them a halt signal is produced. If however the error corresponds to a stuck track a "pass data" signal is produced via line 101. Provision may be made to delay production of a halt signal by exclusive-OR gate 103 until its inputs have stabilized, thus preventing the system responding to spurious transient conditions.  Considering operation when the parity check shows an even parity together with a Hamming error. Even parity results in a signal on line 82 (Fig. 3) which is applied to AND gate 107. Since this is the first pass through the circuit of a particular word latch 108 will be reset and gate 107 will conduct. The resulting signal on line 112 sets complement latch 113 whose output is passed to inputs 115 of the AND gates 116 in the correctors. The AND gates 116 cause exclusive -ORs 52 to complement the bits corresponding to stuck tracks, the inputs 23 indicating that the track to which the particular corrector corresponds is stuck. After a delay 118 to give the complementing time to occur, 1st pass latch 108 is set blocking gate 107. The data, including the complemented bits, is applied to the system so that if the complementing results in an odd parity indication the operation is as described above unless there are no remaining errors as indicated by a signal on line 81, which, via OR 83 produces a "pass data" signal. If however the parity is still even the inverted output of the 1st pass latch and the even parity signal produce, at AND 122, a halt signal. A modified algorithm is illustrated in Fig. 6, this algorithm differs from Fig. 1 in that for an even parity indication and on the first pass, a decision is made as to whether only two tracks are "stuck". If the decision is "no" the stuck track is complemented, the 1st pass latch is set and a 2nd pass as above is made. If two "stuck'' tracks are indicated a decision is made as to whether the Hamming identified error bit corresponds to a "stuck" track. If it does not all the stuck tracks are complemented and a 2nd pass made. If it does the non-corresponding "stuck" track is complemented and a second pass made.