Back to Search
Start Over
List-Decodable Zero-Rate Codes.
- Source :
-
IEEE Transactions on Information Theory . Mar2019, Vol. 65 Issue 3, p1657-1667. 11p. - Publication Year :
- 2019
-
Abstract
- We consider list decoding in the zero-rate regime for two cases—the binary alphabet and the spherical codes in Euclidean space. Specifically, we study the maximal $\tau \in [{0,1}]$ for which there exists an arrangement of $M$ balls of relative Hamming radius $\tau $ in the binary hypercube (of arbitrary dimension) with the property that no point of the latter is covered by $L$ or more of them. As $M\to \infty $ the maximal $\tau $ decreases to a well-known critical value $\tau _{L}$. In this paper, we prove several results on the rate of this convergence. For the binary case, we show that the rate is $\Theta (M^{-1})$ when $L$ is even, thus extending the classical results of Plotkin and Levenshtein for $L=2$. For $L=3$ , the rate is shown to be $\Theta (M^{-({2}/{3})})$. For the similar question about spherical codes, we prove the rate is $\Omega (M^{-1})$ and $O(M^{-({2L}/{L^{2}-L+2})})$. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 65
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 134886975
- Full Text :
- https://doi.org/10.1109/TIT.2018.2868957