Decoding frequency permutation arrays under infinite norm

Min-Zheng Shieh*, Shi-Chun Tsai

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication2009 IEEE International Symposium on Information Theory, ISIT 2009
Pages2713-2717
Number of pages5
DOIs
StatePublished - 19 Nov 2009
Event2009 IEEE International Symposium on Information Theory, ISIT 2009 - Seoul, Korea, Republic of
Duration: 28 Jun 20093 Jul 2009

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8102

Conference

Conference2009 IEEE International Symposium on Information Theory, ISIT 2009
CountryKorea, Republic of
CitySeoul
Period28/06/093/07/09

Fingerprint Dive into the research topics of 'Decoding frequency permutation arrays under infinite norm'. Together they form a unique fingerprint.

  • Cite this

    Shieh, M-Z., & Tsai, S-C. (2009). Decoding frequency permutation arrays under infinite norm. In 2009 IEEE International Symposium on Information Theory, ISIT 2009 (pp. 2713-2717). [5205867] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2009.5205867