Codes Correcting Transpositions of Consecutive Symbols

The problem of correcting transpositions (or swaps) of consecutive symbols in q-ary strings is studied. A family of codes correcting a transposition at an arbitrary location is described and proved to have asymptotically optimal redundancy. Additionally, an improved construction is given over a binary alphabet. Bounds on the cardinality of codes correcting t = const transpositions are obtained. A lower bound on the achievable asymptotic rate of optimal codes correcting $ t = τn $ transpositions is derived. Finally, a construction of codes correcting all possible patterns of transpositions is presented, and the corresponding lower bound on the zero-error capacity of the q-ary transposition channel is stated.