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 -