DETECTING SUBSTITUTIONS AND TRANSPOSITIONS OF CHARACTERS

Substitution errors, where individual characters are altered, and tran sposition errors, where two consecutive characters are interchanged, a re commonly caused by human operators. In this paper, codes that detec t a single substitution error or a single transposition error are stud ied. In particular, it is shown that such codes of length it over an a lphabet of q characters have at most q(n-1) codewords if q greater tha n or equal to 3 and at most inverted right perpendicular 2(n)/3 invert ed left perpendicular codewords if q = 2, Codes which have that many c odewords are called optimal codes. We present optimal codes for all va lues of n and q, Simple encoding techniques for these codes are also d escribed.