Decoding frequency permutation arrays under Chebyshev distance

Min-Zheng Shieh*, Shi-Chun Tsai

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

A frequency permutation array (FPA) of length n=mλ and distance d is a set of permutations on a multiset over m 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 Chebyshev distance, we first prove lower and upper bounds on the size of FPA. Then we give several constructions of FPAs, and some of them come with efficient encoding and decoding capabilities. Moreover, we show one of our designs is locally decodable, i.e., we can decode a message bit by reading at most λ + 1 symbols, which has an interesting application to private information retrieval.

Original languageEnglish
Article number5605363
Pages (from-to)5730-5737
Number of pages8
JournalIEEE Transactions on Information Theory
Volume56
Issue number11
DOIs
StatePublished - 1 Nov 2010

Keywords

  • Chebyshev distance
  • frequency permutation array (FPA)
  • locally decodable code
  • permanent
  • permutation array (PA)

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

Cite this