Detecting Substitutions and Transpositions of Characters
Khaled Abdel-Ghaffar · The Computer Journal · 1998
Substitution errors, where individual characters are altered, and transposition errors, where two consecutive characters are interchanged, are commonly caused by human operators. In this paper, codes that detect a single substitution error or a single transposition error are studied. In particular, it is shown that such codes of length n over an alphabet of q characters have at most qn−1 codewords if q ≤ 3 and at most [2n/3] codewords if q = 2. Codes which have that many codewords are called optimal codes. We present optimal codes for all values of n and q. Simple encoding techniques for these codes are also described.