Decoding Frequency Permutation Arrays under Infinite norm

Details Decoding Frequency Permutation Arrays under Infinite norm Decoding Frequency Permutation Arrays under Infinite norm

2009-01-14

arxiv.org/abs/0901.1971v1

Computer Science

Information Theory

Submitted to ISIT 2009

Scientific paper

A frequency permutation array (FPA) of length $n=m\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 $\ell_\infty$-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.

Affiliated with

Also associated with

No associations

Rating

Decoding Frequency Permutation Arrays under Infinite norm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Decoding Frequency Permutation Arrays under Infinite norm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoding Frequency Permutation Arrays under Infinite norm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-375358