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 代码。 此外, 还可以证明, 所考虑的解码方法可以在找到有效编码后立即终止搜索, 导致算算算法的平均计算复杂性。

0
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37
【KDD2021】图神经网络,NUS- Xavier Bresson教授
专知会员服务
62+阅读 · 2021年8月20日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
将门创投
5+阅读 · 2018年10月16日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
Arxiv
4+阅读 · 2021年11月29日
Arxiv
0+阅读 · 2021年11月23日
VIP会员
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
将门创投
5+阅读 · 2018年10月16日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
Top
微信扫码咨询专知VIP会员