The recently introduced polar codes constitute a breakthrough in coding theory due to their capacityachieving property. This goes hand in hand with a quasilinear construction, encoding, and successive cancellation list decoding procedures based on the Plotkin construction. The decoding algorithm can be applied with slight modifications to Reed-Muller or eBCH codes, that both achieve the capacity of erasure channels, although the list size needed for good performance grows too fast to make the decoding practical even for moderate block lengths. The key ingredient for proving the capacity-achieving property of Reed-Muller and eBCH codes is their group of symmetries. It can be plugged into the concept of Plotkin decomposition to design various permutation decoding algorithms. Although such techniques allow to outperform the straightforward polar-like decoding, the complexity stays impractical. In this paper, we show that although invariance under a large automorphism group is valuable in a theoretical sense, it also ensures that the list size needed for good performance grows exponentially. We further establish the bounds that arise if we sacrifice some of the symmetries. Although the theoretical analysis of the list decoding algorithm remains an open problem, our result provides an insight into the factors that impact the decoding complexity.


翻译:最近引入的极地代码因其能力化属性而构成了编码理论的突破。 这与基于 Plotkin 构造的准线性构建、编码和连续取消列表解码程序相关联。 解码算法可以略微修改Reed- Muller 或 eBCH 代码来应用, 这两种代码都能达到删除渠道的能力, 尽管良好性能所需的列表大小增长过快, 以至于即使对中等区块长度也无法使解码实用。 证明Reed- Muller 和 eBCH 代码能力化属性的关键要素是它们的对称组合。 它可以插进 Plotkin 解码概念中, 用于设计各种整变解码算法。 虽然这些技术可以超越直接的极化解码功能, 但复杂性仍然不切实际。 在本文中, 尽管大型的自动化组下的不一致性在理论意义上是有价值的, 但它也确保了良好性能所需的列表大小成指数化。 我们进一步确定了如果我们牺牲了某种精确性分析的结果, 我们就会产生某种精确性分析的结果。

0
下载
关闭预览

相关内容

强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
186+阅读 · 2019年10月10日
已删除
将门创投
4+阅读 · 2018年11月20日
Arxiv
0+阅读 · 2021年12月13日
Arxiv
0+阅读 · 2021年12月10日
Arxiv
0+阅读 · 2021年12月10日
Efficient and Effective $L_0$ Feature Selection
Arxiv
5+阅读 · 2018年8月7日
Arxiv
5+阅读 · 2018年5月31日
VIP会员
相关资讯
已删除
将门创投
4+阅读 · 2018年11月20日
相关论文
Arxiv
0+阅读 · 2021年12月13日
Arxiv
0+阅读 · 2021年12月10日
Arxiv
0+阅读 · 2021年12月10日
Efficient and Effective $L_0$ Feature Selection
Arxiv
5+阅读 · 2018年8月7日
Arxiv
5+阅读 · 2018年5月31日
Top
微信扫码咨询专知VIP会员