Coding for the ℓ ∞ -limited permutation channel Academic Article 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 = (x 1 , …, x n ) is corrupted by a permutation π ∈ S n to yield the received word y = (y 1 , …, 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 l ∞ -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