期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 68, 期 2, 页码 923-939出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2021.3127126
关键词
Coding theory; random linear codes; list-decoding and recovery; threshold rates
资金
- NSF [CCF-1563742, CCF-1814603, CCF-1527110, CCF-1618280, CCF-1910588]
- Simons Investigator Award
- NSF-CAREER [CCF-1844628]
- NSF-U.S.-Israel Binational Science Foundation (BSF) [CCF-1814629]
- NSF Graduate Research Fellowship Program (GRFP) [DGE-1656518]
- Sloan Research Fellowship [2020.9]
- NSF CAREER Award [CCF-1750808]
- ERC [74079]
- NSF-BSF [CCF-1814629]
- Google Graduate Fellowship
This work investigates the list size of random linear codes for both list-decoding and list-recovery as the rate approaches capacity. Lower and upper bounds are obtained by exhibiting explicit subsets of codewords and strengthening existing results.
A family of error-correcting codes is list-decodable from error fraction p if, for every code in the family, the number of codewords in any Hamming ball of fractional radius p is less than some integer L. It is said to be list-recoverable for input list size l if for every sufficiently large subset of at least L codewords, there is a coordinate where the codewords take more than l values. In this work, we study the list size of random linear codes for both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below q is the alphabet size, and epsilon > 0 is the gap to capacity). (1) A random linear code of rate 1 - log(q) (l) - epsilon requires list size L >= l(Omega(1/epsilon)) for list-recovery from input list size l. (2) A random linear code of rate 1 - h(q)(p) - epsilon requires list size L >= left perpendicularh(q)(p)/epsilon + 0.99right perpendicular for list-decoding from error fraction p. (3) A random binary linear code of rate 1-h(2)(p)-epsilon is list-decodable from average error fraction p with list size with L <= left perpendicularh(2)(p)/epsilon right perpendicular + 2. Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset-or some symbol-wise permutation of it-lies in a random linear code with high probability. Our upper bound follows by strengthening a result of (Li, Wootters, 2018).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据