Patent GB-1018744-A (GB)
Title: Improvements relating to apparatus for detecting the transposition of characters of a multi-character word
IPC: G06F11/10
Filed: 1964-09-07
Abstract: 1,018,744. Error detection and correction. INTERNATIONAL BUSINESS MACHINES CORPORATION. Sept. 7, 1964 [Sept. 16, 1963], No. 36634/64. Heading G4A. Apparatus for detecting transpositions (e.g. introduced by a keyboard operator) of characters in a multi-character word comprises means for producing a check word representing the relative magnitudes of numeric equivalents of adjacent characters in said word, and means for comparing the check word with a reference check word and indicating equality. In Figs. 1a, 1b (not shown), a register 10 (Fig. 1a) stores the six 6-bit characters of a word in respective columns of triggers, lowest order character on the right. A 5-bit check character for the word, produced as below, has one bit associated with each adjacent pair of characters in the word, the bit being ONE if the higher order character is greater than the lower, and ZERO otherwise. The word is stored in a shift register 30 (rest of Fig. 1a), one character per column. All the rows of the shift register may be shifted to the right together, bits shifted out being lost. The two lowest order columns may be shifted downwards together, bits shifted out being reinserted at the other end of the columns and also passing to a comparator 40 (Fig. 1b) comprising AND gates and two triggers. By row shift of the shift register, each adjacent pair of characters are placed in turn in the two lowest order columns and then passed corresponding bits at a time, highest order first, by column shift into the comparator. The first pair of bits to be unequal results in the setting to ONE of one of the comparator triggers depending on which bit is greater. All subsequent pairs in the same pair of characters then have no effect on the triggers. The state of one of the comparator triggers after each character pair comparison is passed into a further shift register to form one bit of the check character. When this character is complete it is appended to the word in register 10 (not shown). Figs. 3, 4 (not shown) show means for comparing the check character associated with a word with a new check character generated as before, and indicating the presence of an error if they are not identical. Fig. 5 (not shown) shows a circuit for detecting and correcting single transposition errors in a word, and detecting double transposition errors. The word is stored in each of six shift registers 30, 30a to 30e (Fig. 5, not shown) but with some character transpositions in all but register 30 (not shown). Each shift register is the same as register 30 in Fig. 1a (not shown) except that the rows have feedback loops so data row-shifted out is reinserted. A chain of triggers is provided for passing the contents of each shift register in turn (starting with 30, not shown) to a comparator as in Figs. 1a, 1b (not shown), to produce in each case a check character which is compared for coincidence with the check character originally associated with the word. If the comparison using the first shift register is successful an " error-free " signal is given, the word in register 30 (not shown) is shifted into an output register, and concurrently with the latter the contents of register 30a (not shown) are sent to the comparator producing a no-compare signal. This signal resets all storage and control triggers in the system except those of the output register. On the other hand, if the comparison using register 30 (not shown) is unsuccessful, the contents of all the registers 30a to 30e (not shown) are fed to the comparator in turn and an error indication is given. On a successful comparison, the contents of the shift register concerned are shifted into the output register. Thus the output register will store the correct or corrected word if there was only one successful comparison, but if there was more than one it will store the contents of the shift register associated with the latest successful comparison. Figs. 6, 7 (not shown) show a modified arrangement for check character generation, useful for when the number of characters in a word is too great for the check bits generated as above to fit into one character space. Nine check bits generated as before for a ten-character word are fed in turn to the binary weighted inputs of a modulo-10 accumulator in such a way that the successive nine bits are respectively weighted 1, 2, 4, 9, 7, 5, 1, 2, 4. The accumulator output is a binary-coded decimal digit which is appended to the word as it checks character. The above weightings are such that a single transposition error can be corrected using the above check character.