TY - GEN

T1 - Decoding frequency permutation arrays under infinite norm

AU - Shieh, Min-Zheng

AU - Tsai, Shi-Chun

PY - 2009

Y1 - 2009

N2 - A frequency permutation array (FPA) of length n = mλ and distance d is a set of permutations on a multiset over rri symbols, where each symbol appears exactly λ 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∞-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 λ+ 1 symbols, which has an interesting application for private information retrieval.

AB - A frequency permutation array (FPA) of length n = mλ and distance d is a set of permutations on a multiset over rri symbols, where each symbol appears exactly λ 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∞-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 λ+ 1 symbols, which has an interesting application for private information retrieval.

UR - http://www.scopus.com/inward/record.url?scp=70449475702&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2009.5205867

DO - 10.1109/ISIT.2009.5205867

M3 - Conference contribution

AN - SCOPUS:70449475702

SN - 9781424443130

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2713

EP - 2717

BT - 2009 IEEE International Symposium on Information Theory, ISIT 2009

T2 - 2009 IEEE International Symposium on Information Theory, ISIT 2009

Y2 - 28 June 2009 through 3 July 2009

ER -