Decoding Reed-Muller Codes Using Minimum- Weight Parity Checks
Decoding Reed-Muller Codes Using Minimum- Weight Parity Checks
复制标题
DOI：
10.1109/isit.2018.8437637
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Elia Santi;Christian Häger;H. Pfister
中科院分区：
文献类型：
--
作者：
Elia Santi;Christian Häger;H. Pfister
Reed-Muller（RM）码由于其高度对称的结构，在最大似然（ML）译码下表现出良好的性能。在本文中，我们探讨的问题，是否也可以利用RM码的代码对称性，以实现近ML性能在实践中。其主要思想是对仅包含最小权重双重码字作为行的高度冗余奇偶校验（PC）矩阵应用迭代解码。作为例子，我们考虑剥离解码器的二进制擦除信道，线性规划和置信传播（BP）解码的二进制输入加性白色高斯噪声信道，位翻转和BP解码的二进制对称信道。对于短块长度，它表明，近ML性能确实可以在许多情况下实现。我们还提出了一种方法来定制的PC矩阵接收到的观察，通过只选择一小部分有用的最小重量PC解码开始之前。与使用全套最小重量PC相比，这使人们能够提高性能并显着降低复杂性。
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.