List decoding random Euclidean codes and Infinite constellations

Zhang Y, Vatedka S. 2022. List decoding random Euclidean codes and Infinite constellations. IEEE Transactions on Information Theory. 68(12), 7753–7786.

Download (ext.)

Journal Article | Published | English

Scopus indexed
Author
Zhang, YihanISTA; Vatedka, Shashank
Department
Abstract
We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints P and N respectively, the list decoding capacity is equal to 1/2logP/N. Random spherical codes achieve constant list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain conjecture that originates in analytic number theory is true, then the list size grows as a polynomial function of the gap-to-capacity.
Publishing Year
Date Published
2022-12-01
Journal Title
IEEE Transactions on Information Theory
Publisher
IEEE
Acknowledgement
This work was done when Shashank Vatedka was at the Chinese University of Hong Kong, where he was supported in part by CUHK Direct Grants 4055039 and 4055077. He would like to acknowledge funding from a seed grant offered by IIT Hyderabad and the Start-up Research Grant (SRG/2020/000910) from the Science and Engineering Board, India. Yihan Zhang has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 682203-ERC-[Inf-Speed-Tradeoff].
Volume
68
Issue
12
Page
7753-7786
ISSN
eISSN
IST-REx-ID

Cite this

Zhang Y, Vatedka S. List decoding random Euclidean codes and Infinite constellations. IEEE Transactions on Information Theory. 2022;68(12):7753-7786. doi:10.1109/TIT.2022.3189542
Zhang, Y., & Vatedka, S. (2022). List decoding random Euclidean codes and Infinite constellations. IEEE Transactions on Information Theory. IEEE. https://doi.org/10.1109/TIT.2022.3189542
Zhang, Yihan, and Shashank Vatedka. “List Decoding Random Euclidean Codes and Infinite Constellations.” IEEE Transactions on Information Theory. IEEE, 2022. https://doi.org/10.1109/TIT.2022.3189542.
Y. Zhang and S. Vatedka, “List decoding random Euclidean codes and Infinite constellations,” IEEE Transactions on Information Theory, vol. 68, no. 12. IEEE, pp. 7753–7786, 2022.
Zhang Y, Vatedka S. 2022. List decoding random Euclidean codes and Infinite constellations. IEEE Transactions on Information Theory. 68(12), 7753–7786.
Zhang, Yihan, and Shashank Vatedka. “List Decoding Random Euclidean Codes and Infinite Constellations.” IEEE Transactions on Information Theory, vol. 68, no. 12, IEEE, 2022, pp. 7753–86, doi:10.1109/TIT.2022.3189542.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Web of Science

View record in Web of Science®

Sources

arXiv 1901.03790

Search this title in

Google Scholar