Coding for the $\boldsymbol \ell _\infty $ -Limited Permutation Channel
Michael L. Langberg, Moshe Schwartz, Eitan Yaakobi · IEEE Transactions on Information Theory · 2017
We consider the communication of information in the presence of synchronization errors. Specifically, we consider permutation channels in which a transmitted codeword x = (x1, ... , xn) is corrupted by a permutation π ∈ Snto yield the received wordy = (y1, . . . , yn), where yi= 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.