Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels
Consider a binary linear code of length N, minimum distance d-{\min}, transmission over the binary erasure channel with parameter 0 < \epsilon < 1 or the binary symmetric channel with parameter 0 < \epsilon < \frac{1}{2}, and block-MAP decoding. It was shown by Tillich and Zemor that in...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121969 |
| _version_ | 1811072575158091776 |
|---|---|
| author | Ordentlich, Or 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 Ordentlich, Or Polyanskiy, Yury |
| author_sort | Ordentlich, Or |
| collection | MIT |
| description | Consider a binary linear code of length N, minimum distance d-{\min}, transmission over the binary erasure channel with parameter 0 < \epsilon < 1 or the binary symmetric channel with parameter 0 < \epsilon < \frac{1}{2}, and block-MAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the block-MAP decoder transitions 'quickly' from \delta to 1-\delta for any \delta > 0 if the minimum distance is large. In particular the width of the transition is of order O(1/\sqrt{d-{\min}}). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as \Theta(1/N^{\frac{1}{2}-\kappa}), for any \kappa > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since \Theta(1/N^{\frac{1}{2}}) is the smallest transition possible for any code, we speak of 'almost' optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma. |
| first_indexed | 2024-09-23T09:08:13Z |
| format | Article |
| id | mit-1721.1/121969 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:08:13Z |
| publishDate | 2019 |
| publisher | IEEE |
| record_format | dspace |
| spelling | mit-1721.1/1219692022-09-26T10:43:28Z Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels Ordentlich, Or Polyanskiy, Yury Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Consider a binary linear code of length N, minimum distance d-{\min}, transmission over the binary erasure channel with parameter 0 < \epsilon < 1 or the binary symmetric channel with parameter 0 < \epsilon < \frac{1}{2}, and block-MAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the block-MAP decoder transitions 'quickly' from \delta to 1-\delta for any \delta > 0 if the minimum distance is large. In particular the width of the transition is of order O(1/\sqrt{d-{\min}}). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as \Theta(1/N^{\frac{1}{2}-\kappa}), for any \kappa > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since \Theta(1/N^{\frac{1}{2}}) is the smallest transition possible for any code, we speak of 'almost' optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma. 2019-08-07T12:22:46Z 2019-08-07T12:22:46Z 2018-06 2019-07-01T17:40:59Z Article http://purl.org/eprint/type/ConferencePaper 9781538647813 2157-8117 https://hdl.handle.net/1721.1/121969 Hassani, Hamed, Shrinivas Kudekar, Or Ordentlich, Yury Polyanskiy and Rüdiger Urbanke. "Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels." In 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA, 17-22 June 2018. en 10.1109/isit.2018.8437453 2018 IEEE International Symposium on Information Theory (ISIT) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE arXiv |
| spellingShingle | Ordentlich, Or Polyanskiy, Yury Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels |
| title | Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels |
| title_full | Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels |
| title_fullStr | Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels |
| title_full_unstemmed | Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels |
| title_short | Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels |
| title_sort | almost optimal scaling of reed muller codes on bec and bsc channels |
| url | https://hdl.handle.net/1721.1/121969 |
| work_keys_str_mv | AT ordentlichor almostoptimalscalingofreedmullercodesonbecandbscchannels AT polyanskiyyury almostoptimalscalingofreedmullercodesonbecandbscchannels |