We present a novel iterative decoding algorithm for Reed-Muller (RM) codes, which takes advantage of a graph representation of the code. Vertices of the considered graph correspond to codewords, with two vertices being connected by an edge if and only if the Hamming distance between the corresponding codewords equals the minimum distance of the code. The algorithm uses a greedy local search to find a node optimizing a metric, e.g. the correlation between the received vector and the corresponding codeword. In addition, the cyclic redundancy check can be used to terminate the search as soon as a valid codeword is found, leading to an improvement in the average computational complexity of the algorithm. Simulation results for both binary symmetric channel and additive white Gaussian noise channel show that the presented decoder approaches the performance of maximum likelihood decoding for RM codes of length less than 1024 and for the second-order RM codes of length less than 4096. Moreover, it is demonstrated that the considered decoding approach outperforms state-of-the-art decoding algorithms of RM codes with similar computational complexity for a wide range of block lengths and rates.
翻译:我们为 Reed- Muller (RM) 代码提出了一个新颖的迭代解码算法,它利用了该代码的图形表示法。 被考虑的图形的空格与代码对应的代码对应, 有两个顶端由边缘连接, 如果并且只有在相应的代码字词之间的含膜距离等于代码的最小距离时才如此。 该算法使用贪婪的本地搜索来寻找一个节点, 优化一个测量标准, 例如, 接收的矢量和相应的代码之间的关联。 此外, 循环冗余检查可以用来在找到有效的编码词后立即终止搜索, 从而导致算法的平均计算复杂性的改善。 二元对称频道和添加的白高山噪音频道的模拟结果显示, 所提出的解码将接近于长度小于1024 的 RM码最大可能的解码操作, 和长度小于4096 的第二顺序 RM 代码。 此外, 还可以证明, 所考虑的解码方法可以在找到有效编码后立即终止搜索, 导致算算算法的平均计算复杂性。