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 = τ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 = \textrm{const}$ transpositions are also derived.

No reviews yet.

No comments yet.