Comparing the bit-MAP and block-MAP decoding thresholds of Reed-Muller codes on BMS channels

S. Kudekar, S. Kumar, M. Mondelli, H.D. Pfister, R. Urbankez, in:, 2016 IEEE International Symposium on Information Theory , IEEE, 2016, pp. 1755–1759.


Conference Paper | Published | English
Author
Kudekar, Shrinivas; Kumar, Santhosh; Mondelli, MarcoIST Austria ; Pfister, Henry D.; Urbankez, Rudiger
Abstract
The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding. In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as N -δ , for some δ > 0. Then, the block-MAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.
Publishing Year
Date Published
2016-08-11
Proceedings Title
2016 IEEE International Symposium on Information Theory
Page
1755-1759
Conference
ISIT: International Symposium on Information Theory
Conference Location
Barcelona, Spain
Conference Date
2016-07-10 – 2016-07-15
IST-REx-ID

Cite this

Kudekar S, Kumar S, Mondelli M, Pfister HD, Urbankez R. Comparing the bit-MAP and block-MAP decoding thresholds of Reed-Muller codes on BMS channels. In: 2016 IEEE International Symposium on Information Theory . IEEE; 2016:1755-1759. doi:10.1109/isit.2016.7541600
Kudekar, S., Kumar, S., Mondelli, M., Pfister, H. D., & Urbankez, R. (2016). Comparing the bit-MAP and block-MAP decoding thresholds of Reed-Muller codes on BMS channels. In 2016 IEEE International Symposium on Information Theory (pp. 1755–1759). Barcelona, Spain: IEEE. https://doi.org/10.1109/isit.2016.7541600
Kudekar, Shrinivas, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, and Rudiger Urbankez. “Comparing the Bit-MAP and Block-MAP Decoding Thresholds of Reed-Muller Codes on BMS Channels.” In 2016 IEEE International Symposium on Information Theory , 1755–59. IEEE, 2016. https://doi.org/10.1109/isit.2016.7541600.
S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, and R. Urbankez, “Comparing the bit-MAP and block-MAP decoding thresholds of Reed-Muller codes on BMS channels,” in 2016 IEEE International Symposium on Information Theory , Barcelona, Spain, 2016, pp. 1755–1759.
Kudekar S, Kumar S, Mondelli M, Pfister HD, Urbankez R. 2016. Comparing the bit-MAP and block-MAP decoding thresholds of Reed-Muller codes on BMS channels. 2016 IEEE International Symposium on Information Theory . ISIT: International Symposium on Information Theory 1755–1759.
Kudekar, Shrinivas, et al. “Comparing the Bit-MAP and Block-MAP Decoding Thresholds of Reed-Muller Codes on BMS Channels.” 2016 IEEE International Symposium on Information Theory , IEEE, 2016, pp. 1755–59, doi:10.1109/isit.2016.7541600.
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 IST Research Explorer

Sources

arXiv 1601.06048

Search this title in

Google Scholar