GB1053174A - - Google Patents

Abstract

1,053,174. Error detection and correction. INTERNATIONAL BUSINESS MACHINES CORPORATION. March 9, 1965 [April 6, 1964 (3)], No. 9873/65. Heading G4C. The position of an erroneous bit in an incorrect byte in a group of bytes is detected with the aid of redundancy in each byte and a cyclic redundancy check byte provided for the group of bytes, two byte indications being placed in respective cyclic shift registers and one shifted until a comparison indicates equality, the number of shifts indicating the said position. Data is recorded on magnetic tape as a block of data bytes followed by a cyclic redundancy check (CRC) byte and a longitudinal redundancy check (LRC) byte. Each data byte has internal redundancy (a parity bit, or the number of ONE bits is always the same). The LRC byte provides a parity bit for each track of the tape (i.e. corresponding bit positions in all the other bytes). The mathematical theory of the cyclic checking (CRC) is given in the Specification. During writing on the tape, as the data bytes are sent to the tape, they are also sent to a feedback-connected CRC shift register (CRCR) where each byte is EX-ORed with the present contents of the register and the result shifted one position. When the last data byte has been received, the contents of the CRC register are given one extra shift and then with certain bits complemented, are passed to the tape via a read-write (R/W) register as the CRC byte. Then the LRC byte is recorded on the tape. The bytes are read again concurrently with the writing operation, and vertical redundancy checks (VRC, the internal redundancy of each byte) and LRC performed. During reading from the tape, the bytes are transferred via the R/W register to the CRCR (except the LRC byte) and a VRC is performed on each byte. In detection of a VRC error, a ONE is entered in a feedback-connected error pattern register (EPR) which is being shifted in synchronism with the CRCR. If a CRC, VRC or LRC error has occurred during reading, the tape is backspaced and the track in error determined as follows. The contents of the EPR are transferred to the R/W register (previously cleared) and a ONE inserted in the top position of the EPR (otherwise clear). The EPR and CRCR are shifted together until the contents of the CRCR equal those of the R/W register, as determined by an all ZEROES output from EX-OR gates 16 (Fig. 2, not shown). The position of the ONE bit in the EPR then gives the track in error, and the CRCR is reset. A second reading of the tape commences and on detection of a VRC error in a byte, the contents of the EPR are supplied to the EX-OR gates 16 (not shown) through which the tape byte is passing to complement the bit which is in the erroneous channel. The bytes, after correction, are sent to the CRCR. When all the bytes have been received, the CRCR is sampled for a CRC error. Also, an LRC register (LRCR) which received the uncorrected bytes is sampled for an LRC error, positions in which an error correction took place being ignored for this purpose. Backwards read may be performed by reversing directions of shift or having reversible input connections.