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.
Kovačević et al. (Mon,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: