Coding for the ℓ∞-limited permutation channel Conference Paper uri icon


  • 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 = (x1, ..., xn) is corrupted by a permutation π ∈ Sn to yield the received word y = (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.

publication date

  • January 1, 2015