Efficient encoding and decoding with permutation arrays

Abstract

An (n, d) permutation array (PA) is a subset of S <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</inf> with the property that the distance (under any distance metric, such as Hamming) between any two permutations in the array is at least d, which becomes popular recently for communication over power line. We use l <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</inf> -norm to measure the distance between permutations, and give a construction of permutation arrays under l <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</inf> -norm together with efficient encoding and decoding algorithms. This construction is the first of its kind.