Bounds on Codes Correcting Transpositions of Consecutive Symbols

The problem of correcting transpositions (or swaps) of consecutive symbols in $q$-ary strings is studied. Lower bounds on asymptotically achievable rates of codes correcting $t=\tau n$ transpositions are derived. The first bound is obtained by analyzing the average cardinality of ``transposition balls’’ and evaluating the appropriate version of the generalized Gilbert–Varshamov bound, while the second bound follows from a construction of codes correcting an arbitrary number of transpositions (i.e., zero-error codes). Asymptotic bounds on the cardinality of optimal codes correcting $t=\text{const}$ transpositions are also derived.