Skip to main content

Decoding Reed-Muller Codes Using Minimum- Weight Parity Checks

Publication ,  Journal Article
Santi, E; Hager, C; Pfister, HD
Published in: IEEE International Symposium on Information Theory - Proceedings
August 15, 2018

Reed-Muller (RM) codes exhibit good performance under maximum-likelihood (ML) decoding due to their highly-symmetric structure. In this paper, we explore the question of whether the code symmetry of RM codes can also be exploited to achieve near-ML performance in practice. The main idea is to apply iterative decoding to a highly-redundant parity-check (PC) matrix that contains only the minimum-weight dual codewords as rows. As examples, we consider the peeling decoder for the binary erasure channel, linear-programming and belief propagation (BP) decoding for the binary-input additive white Gaussian noise channel, and bit-flipping and BP decoding for the binary symmetric channel. For short block lengths, it is shown that near-ML performance can indeed be achieved in many cases. We also propose a method to tailor the PC matrix to the received observation by selecting only a small fraction of useful minimum-weight PCs before decoding begins. This allows one to both improve performance and significantly reduce complexity compared to using the full set of minimum-weight PCs.

Duke Scholars

Published In

IEEE International Symposium on Information Theory - Proceedings

DOI

ISSN

2157-8095

Publication Date

August 15, 2018

Volume

2018-June

Start / End Page

1296 / 1300
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Santi, E., Hager, C., & Pfister, H. D. (2018). Decoding Reed-Muller Codes Using Minimum- Weight Parity Checks. IEEE International Symposium on Information Theory - Proceedings, 2018-June, 1296–1300. https://doi.org/10.1109/ISIT.2018.8437637
Santi, E., C. Hager, and H. D. Pfister. “Decoding Reed-Muller Codes Using Minimum- Weight Parity Checks.” IEEE International Symposium on Information Theory - Proceedings 2018-June (August 15, 2018): 1296–1300. https://doi.org/10.1109/ISIT.2018.8437637.
Santi E, Hager C, Pfister HD. Decoding Reed-Muller Codes Using Minimum- Weight Parity Checks. IEEE International Symposium on Information Theory - Proceedings. 2018 Aug 15;2018-June:1296–300.
Santi, E., et al. “Decoding Reed-Muller Codes Using Minimum- Weight Parity Checks.” IEEE International Symposium on Information Theory - Proceedings, vol. 2018-June, Aug. 2018, pp. 1296–300. Scopus, doi:10.1109/ISIT.2018.8437637.
Santi E, Hager C, Pfister HD. Decoding Reed-Muller Codes Using Minimum- Weight Parity Checks. IEEE International Symposium on Information Theory - Proceedings. 2018 Aug 15;2018-June:1296–1300.

Published In

IEEE International Symposium on Information Theory - Proceedings

DOI

ISSN

2157-8095

Publication Date

August 15, 2018

Volume

2018-June

Start / End Page

1296 / 1300