Upper Bound on List-Decoding Radius of Binary Codes
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 L ≥ 3, an asymptotic upper bound on the rate of any such packing is proved. The resulting bound improves the...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121938 |
| _version_ | 1826198548190855168 |
|---|---|
| author | Polyanskiy, Yury |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Polyanskiy, Yury |
| author_sort | Polyanskiy, Yury |
| collection | MIT |
| description | 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 L ≥ 3, an asymptotic upper bound on the rate of any such packing is proved. The resulting bound improves the best known bound (due to Blinovsky'1986) for rates below a certain threshold. The method is a superposition of the linear-programming idea of Ashikhmin, Barg, and Litsyn (that was previously used 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. |
| first_indexed | 2024-09-23T11:06:35Z |
| format | Article |
| id | mit-1721.1/121938 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:06:35Z |
| publishDate | 2019 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1219382022-09-27T17:12:53Z Upper Bound on List-Decoding Radius of Binary Codes Polyanskiy, Yury Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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 L ≥ 3, an asymptotic upper bound on the rate of any such packing is proved. The resulting bound improves the best known bound (due to Blinovsky'1986) for rates below a certain threshold. The method is a superposition of the linear-programming idea of Ashikhmin, Barg, and Litsyn (that was previously used 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. National Science Foundation (U.S.) (Grant CCF-13-18620) National Science Foundation (U.S.). Center for Science of Information (Grant CCF-0939370) 2019-07-23T20:10:51Z 2019-07-23T20:10:51Z 2016-03 2015-12 2019-07-01T17:06:24Z Article http://purl.org/eprint/type/JournalArticle 0018-9448 1557-9654 https://hdl.handle.net/1721.1/121938 Polyanskiy, Yury. "Upper bound on list-decoding radius of binary codes." IEEE Transactions on Information Theory 62, no. 3 (September 2014). en 10.1109/tit.2016.2516560 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Polyanskiy, Yury Upper Bound on List-Decoding Radius of Binary Codes |
| title | Upper Bound on List-Decoding Radius of Binary Codes |
| title_full | Upper Bound on List-Decoding Radius of Binary Codes |
| title_fullStr | Upper Bound on List-Decoding Radius of Binary Codes |
| title_full_unstemmed | Upper Bound on List-Decoding Radius of Binary Codes |
| title_short | Upper Bound on List-Decoding Radius of Binary Codes |
| title_sort | upper bound on list decoding radius of binary codes |
| url | https://hdl.handle.net/1721.1/121938 |
| work_keys_str_mv | AT polyanskiyyury upperboundonlistdecodingradiusofbinarycodes |