Header menu link for other important links
X
Lower Bounds on List Decoding Capacity using Error Exponents
Published in Institute of Electrical and Electronics Engineers Inc.
2022
Volume: 2022-June
   
Pages: 1324 - 1329
Abstract
We study the problem of characterizing the maximal rates of list decoding in Euclidean spaces for finite list sizes. For any positive integer L ≥ 2 and real N > 0, we say that a subset C ⊂ Rn is an (N,L - 1)-multiple packing or an (N,L- 1)-list decodable code if every Euclidean ball of radius √ nN in ℝn contains no more than L - 1 points of C. We study this problem with and without ℓ2 norm constraints on C, and derive the best-known lower bounds on the maximal rate for (N,L-1) multiple packing. Our bounds are obtained via error exponents for list decoding over Additive White Gaussian Noise (AWGN) channels. We establish a curious inequality which relates the error exponent, a quantity of average-case nature, to the list-decoding radius, a quantity of worst-case nature. We derive various bounds on the error exponent for list decoding in both bounded and unbounded settings which could be of independent interest beyond multiple packing. © 2022 IEEE.
About the journal
JournalData powered by TypesetIEEE International Symposium on Information Theory - Proceedings
PublisherData powered by TypesetInstitute of Electrical and Electronics Engineers Inc.
ISSN21578095