Decoding Frequency Permutation Arrays under Infinite norm

Abstract

A frequency permutation array (FPA) of length n = rn lambda), and distance d is a set of permutations on a multiset over m symbols, where each symbol appears exactly lambda times and the distance between any two elements in the array is at least d. FPA generalizes the notion of permutation array. In this paper, under the distance metric l(infinity)-norm, we first prove lower and upper bounds on the size of FPA. Then we give a construction of FPA with efficient encoding and decoding capabilities. Moreover, we show our design is locally decodable, i.e., we can decode a message bit by reading at most lambda + 1 symbols, which has an interesting application for private information retrieval.