Coding for the $\ell_{\infty}$-Limited Permutation Channel

In this work 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 \mathrm{S}_{n}$ to yield the received word $y=(y_{1},\ \ldots y_{n})$ where $y_{j}=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$.