Patent GB-1207443-A (GB)
Title: Receiver for a data transmission system
IPC: H04L1/00
Filed: 1968-01-08
Abstract: 1,207,443. Error detection and correction. INTERNATIONAL BUSINESS MACHINES CORP. 8 Jan., 1968 [10 April, 1967], No. 1043/68. Headings G4A and G4C. A data transmission receiver generates a check word, from a receiver message having information and check digits, stores the check word and information digits, and corrects errors in a random error correction mode or a burst error correction mode using a shift register, a feedback path of which is rendered inoperative in response to detection, from the check word, of a correctable burst of error in the received message. A terminal can act as a transmitter in which case it sends a message consisting of 1600 data  bits, followed by check bits calculated by dividing the data bits by a coding polynomial in a feedback shift register (i.e. using modulo-2 addition) to obtain the remainder. The terminal can also act as a receiver in which case it uses a feedback shift register to derive a check word from the data and check bits, each check bit being discarded after use, and the data bits and check word being stored in a memory prior to correction of the data bits in correction logic controlled by decision logic itself controlled by the check word. Derivation of the check word is described briefly and may be as in Specification 1,198,510 which is referred to. Processing of successive messages can be overlapped. Decision logic (Fig. 3). The coding polynomial is of degree 1600 obtained by " interleaving " 200 polynomials of degree 8, all the degree 8 polynomials being identical, viz. the coding polynomial is P(X) = P 1  (X<SP>200</SP>) where P 1  (X)=X<SP>8</SP>+X<SP>7</SP>+X<SP>6</SP>+X<SP>4</SP>+X<SP>2</SP>+X+1 The 1600 data bits and the check word (also 1600 bits) will be regarded as stored in a matrix array having 200 rows and 16 columns, filled column by column, first with the data bits then with the bits from the check word. Consequently, because of the polynomial " interleaving," the check word bits in a given row can be used to locate and correct errors in the data bits of that row. Referring to Fig. 3, the check word bits of each matrix row in turn are placed in 8-stage feedback shift register 100 and shifted 17 times, then deleted and replaced by the check word bits from the next row. During this shifting, AND 111 is enabled at its rightmost two inputs and EXCL-OR 186 passes bits without change. End-around shift registers 116, 122 are shifted concurrently. Any 1 bit coming from the highest-order stage 58 of register 100 is entered into register 116 via OR 114. Any 1 bit coming from stage S1 of register 100 at the same time as a 1 bit is about to be entered into the low-order end of register 116 is entered into register 122 via AND 118 and OR 120. Each matrix row having no more than a single error will produce an output from AND 112 since stages S2-S8 of register 100 will all contain 0 at some stage in the shifting. The output will reset flip-flop 124 which is set by line 128 after each matrix row. Accordingly, counter 134 will count the number of rows having more than a single error. A count of 20 enables AND 136 and prevents further counting. During dealing with the last matrix row, unequal bits in two adjacent stages of register 122 causes EXCL-OR 140 to increment counter 144 (incrementing above 3 being prevented via inverter 148). A count of 1 or 2 produces an output from EXCL-OR 146 to AND 150 which together with an output from AND 136 sets a flip-flop 154 to " burst," when a sample pulse appears at 152. Otherwise flip-flop 154 is set to " random." Flip-flop 154 causes the correction logic (see below) to operate in a burst-error correction mode or a random-error correction mode according to its setting. Correction logic: burst-error correction mode (Fig. 4). The check word bits of the first matrix row are taken from the memory and placed in register 100 (Fig. 3) and registers 100, 122 are shifted eight times. Detection of an O bit in the highest order stage of register 122 sets flip-flop 162 to disable (via inverter 165 and AND 111) feedback in register 100 during the rest of the shifts, and permit each 1 bit appearing in stage S8 of register 100 to set flip-flop 170 via AND 164. Flip-flop 170 is reset after each bit time. After the eight shifts, registers 100, 122 will be shifted once more and the first data bit of the first matrix row will be inverted at EXCL-OR 172 if incorrect, due to the set state of flip-flop 170. Flip-flop 162 is now reset. Register 100 is shifted once, then its contents are loaded back into the memory. Register122 is shifted eight more times to return it to its initial state. The first data bit of each of the other matrix rows are now corrected in turn using the check word bits of the respective matrix rows in the same way except that after the correction in the last row flip-flop 162 will not be reset and register 122 will be shifted once rather than eight times. The second data bits of the various matrix rows are then corrected in turn in the same way, then the third bits and so on. Correction logic: random-error correction mode (Fig. 4). The matrix rows are dealt with in turn, each as follows. The check word bits in the row are placed in register 100 (Fig. 3) and shifted twice with feedback, line 188 being energized on the second shift to invert the bit passing through EXCL-OR 186. Flip-flop 170 is reset. Register 100 is shifted sixteen times. If a correctable error occurred and the first data bit of the row is erroneous, the check word bit corresponding to that error was the one inverted by EXCL-OR 186 (see below) and during the sixteen shifts, AND 112 will detect all zeros in stages S2-S8 of register 100 to set flip-flop 170 to correct the first data bit of the row at EXCL-OR 172 (Fig. 4). Register 100 is now shifted once, line 188 being energized if the first data bit was not in error to put the check word bits in register 100 back into their previous form. The remaining data bits are corrected in turn in a similar way except that the very first shift mentioned above does not occur (except in the case of the first data bit). After the last data bit of the row has been corrected and the check word bits in register 100 have been returned to their previous form if necessary (see above), occurrence of a detectable but uncorrectable error in the row is detected as follows. Register 100 is shifted, with feedback, nine times. Then a signal on line 182 (Fig. 4) disables feedback (via inverter 184 and AND 111) and permits counter 176 to count 1 bits at stage S8 of register 100 during eight further shifts of the register 100. A count of more than two indicates an uncorrectable error.