Coding for the $\boldsymbol \ell _\infty $ -Limited Permutation Channel.

We consider the communication of information in the presence of synchronization errors. Specifically, we consider permutation channels in which a transmitted codeword x=(x1,\ldots ,xn) is corrupted by a permutation \pi \in Sn to yield the received word y=(y1,\ldots ,yn) , where yi=x\pi (i) . We initiate the study of worst case (or zero-error) communication over permutation channels that distort the information by applying permutations $\pi $ , which are limited to displacing any symbol by at most $r$ locations, i.e., permutations $\pi $ with weight at most $r$ in the $\ell _\infty $ -metric. We present direct and recursive constructions, as well as bounds on the rate of such channels for binary and general alphabets. Specific attention is given to the case of $r=1$ . [ABSTRACT FROM AUTHOR]