Upper Bound on List-Decoding Radius of Binary Codes

DOI10.1109/TIT.2016.2516560MaRDI QIDQ2976947zbMATH OpenOpenAlexFDO

Authors Yury Polyanskiy

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.7765

Mathematics Subject Classification ID

Combinatorial codes (94B25) Decoding (94B35) Bounds on codes (94B65)

Abstract: Consider the problem of packing Hamming balls of a given relative radius subject to the constraint that they cover any point of the ambient Hamming space with multiplicity at most $L$. For odd $Lge3$ an asymptotic upper bound on the rate of any such packing is proven. Resulting bound improves the best known bound (due to Blinovsky'1986) for rates below a certain threshold. Method is a superposition of the linear-programming idea of Ashikhmin, Barg and Litsyn (that was used previously to improve the estimates of Blinovsky for $L=2$) and a Ramsey-theoretic technique of Blinovsky. As an application it is shown that for all odd $L$ the slope of the rate-radius tradeoff is zero at zero rate.

Cited in

(2)

• Combinatorial Limitations of Average-Radius List Decoding
• The List Decoding Radius of Reed-Muller Codes over Small Fields

This page was built for publication: Upper Bound on List-Decoding Radius of Binary Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976947)