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}=(x_{1},\ldots ,x_{n})$ is corrupted by a permutation $\pi \in S_{n}$ to yield the received word ${y}=(y_{1},\ldots ,y_{n})$ , where $y_{i}=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$ .