Patent GB-1445439-A (GB)
Title: Error correction systems for a multichannel data handling  system
IPC: G11B20/18
Filed: 1973-11-20
Abstract: 1445439 Error correction INTERNATIONAL BUSINESS MACHINES CORP 20 Nov 1973 53699/73 Heading G4A A series of n 2 -1 data bytes are supplied over n 1 -1 channels (n 1 >n 2 , e.g. n 1 = n 2  + 1), one bit per channel, and are accompanied by two check bytes of which the first C 1  is an orthogonally symmetric byte given by where T is the companion matrix of an irreducible polynomial g(x) of degree n 2  and the second is a parity byte formed by a parity bit for each of the data bytes and the first check byte, the first check byte being supplied with the data bytes, one bit per channel, and the parity byte being supplied along an additional channel, and a decoding means is responsive to the received data and check bytes and independently generated pointer signals indicative of possibly erroneous channels to correct data supplied along up to two channels. The Specification gives the theory of orthogonally symmetric check bytes which are generated in response to successive data bytes (i.e. cross channel bytes, one bit from each channel) and enable, in conjunction with the parity byte, bits along one erroneous channel to be corrected, and, in conjunction with the parity byte and the error pointer signals, enable bits along two erroneous channels to be corrected. The arrangement is described in terms of a nine track (one parity and eight data tracks) tape, the error pointers being derived in a known manner. The check bytes are encoded by feeding successive data bytes in parallel (i.e. one bit to each stage) to a feedback shift register implementing the polynomial and shifting one stage after each byte to form, at the end of the series of bytes the first check byte C 1 , the parity byte being formed by conventional exclusive-OR operations on each of the data bytes and the first check byte. The data and check bytes are then recorded and on replay are decoded using a similar feedback shift register SR2 to form syndrome S 2  where a second syndrome S 1  being formed in shift register SR3 where with P the received parity byte and P a calculated parity byte for the received data bytes and the received first check byte. S 2  may be formed by premultiplying all received bytes by T<SP>7</SP> and shifting backwards in the feedback shift register SR2. In the absence of errors S 1  and S 2  are both zero and no correction is required. When only one track is in error determined by non-zero syndromes and the error pointers the erroneous track is located by solving for i the following this is performed by shifting S 2  backwards in SR2 and counting (at 70) the shifts until the output equals S1 provided by SR3 and gate 42. The count then identifies the track. Where two tracks are in error, determined by non-zero syndromes and the error pointers the erroneous channels i and j' cannot be identified by the first check byte alone. The erroneous channels are identified using the error pointers to produce signals i and (j'-i). The signal i is used as before to produce T-<SP>i</SP>S 2  in SR2. In both cases T-<SP>i</SP>S 2  together with S 1  is passed to a pattern generator 45 producing The data from channels i and j', Zi and Zj' is corrected using the values determined above to produce corrected data #Zi and #Zj' where