A Coding-Theoretic Application of Baranyai%26apos;s Theorem

作者：Zhang Liang Feng^*

来源：IEEE Transactions on Information Theory, 2014, 60(11): 6988-6992.

DOI：10.1109/TIT.2014.2352638

• Baranyai%26apos
• s theorem
• locally decodable codes

Baranyai%26apos;s theorem is well known in the theory of hypergraphs. A corollary of this theorem says that one can partition the family of all u-subsets of an n-element set into ((n-1)(u-1)) subfamilies such that each subfamily forms a partition of the n-element set, where n is divisible by u. In this paper, we present a coding-theoretic application of Baranyai%26apos;s theorem. More precisely, we propose a combinatorial construction of locally decodable codes. Locally decodable codes are error-correcting codes that allow the recovery of any message symbol by looking at only a few symbols of the codeword. The number of looked codeword symbols is called query complexity. Such codes have attracted a lot of attention in recent years. The Walsh-Hadamard code is a well-known binary two-query locally decodable code of exponential length that can recover any message bit using 2 bits of the codeword. Our construction can give locally decodable codes over small finite fields for any constant query complexities. In particular, it gives a ternary two-query locally decodable code of length asymptotically shorter than the Walsh-Hadamard code.

• 出版日期2014-11
• 单位The University of Calgary; University of calgary