Coding for the ℓ_∞-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₁,..,x_n) is corrupted by a permutation π S_n to yield the received word y=(y₁,..,y_n), where y_i=xπ (i). We initiate the study of worst case (or zero-error) communication over permutation channels that distort the information by applying permutations π, which are limited to displacing any symbol by at most r locations, i.e., permutations π with weight at most r in the ℓ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.