Bounds on Codes Correcting Adjacent Transpositions

Abstract

We study the problem of correcting pairwise disjoint adjacent transpositions (or swaps) in $q$-ary strings. Equivalently, the model we assume is the radius-one instance of the so-called ${\ell }_{\infty }$-limited permutation channel. We first study the relevant combinatorial properties of the appropriately defined transposition distance, including center-specific and average ball sizes. We then derive two lower bounds and one upper bound on the asymptotic rates of optimal codes correcting $t=\tau n$ transpositions. The first achievability result is a generalized Gilbert--Varshamov bound, while the second follows from a construction of codes correcting all possible patterns of adjacent transpositions and therefore represents a lower bound on the zero-error capacity of this model. This construction improves the classical general-alphabet construction for $3⩽q⩽8$ as well as the recent bounds for $q=4,5$. The upper bound is obtained by a packing argument adjusted to the run-structure of a given code. To the best of our knowledge, these are the first nonconstant, $\tau$-dependent lower and upper bounds developed for the pairwise disjoint $q$-ary model throughout the linear regime. We also derive asymptotic bounds on the cardinality of optimal codes correcting $t=\text{const}$ pairwise disjoint adjacent transpositions.

Substantially revised version; proofs and presentation tightened; the zero-error construction in Section 3.2 replaced by an improved construction; new Section 3.3 provides an upper bound