Back to Search
Start Over
A Coding-Theoretic Application of Baranyai’s Theorem.
- Source :
-
IEEE Transactions on Information Theory . Nov2014, Vol. 60 Issue 11, p6988-6992. 5p. - Publication Year :
- 2014
-
Abstract
- Baranyai’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\choose 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’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. [ABSTRACT FROM PUBLISHER]
- Subjects :
- *HYPERGRAPHS
*HADAMARD codes
*CODING theory
*EXPONENTS
*COMBINATORICS
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 60
- Issue :
- 11
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 99041665
- Full Text :
- https://doi.org/10.1109/TIT.2014.2352638