New simple constructions of distance-increasing mappings from binary vectors to permutations

Abstract

Distance-increasing mappings (DIMs) are mappings from the set of binary vectors of a fixed length to the set of permutations of the same length that increase Hamming distances except when that is obviously not possible. In this paper, we propose new non-recursive constructions of DIMs which are based on simple compositions of permutations. In comparison with Chang's constructions, our new constructions do not need any table-lookup operations, and usually have better distance expansion distributions when the length is odd. (c) 2006 Elsevier B.V. All rights reserved.