Polar Codes for the Deletion Channel: Weak and Strong Polarization
Polar Codes for the Deletion Channel: Weak and Strong Polarization
复制标题
DOI：
10.1109/isit.2019.8849705
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
I. Tal;H. Pfister;Arman Fazeli;A. Vardy
中科院分区：
文献类型：
--
作者：
I. Tal;H. Pfister;Arman Fazeli;A. Vardy
本文首次证明了具有恒定删失率和规则隐马尔可夫输入分布的删除信道的极化。这项工作的一个关键部分涉及使用格子表示删除信道，并描述在该格子上的正负极解码操作。具体地说，加和减运算可以被视为组合相邻的格子级，以产生具有一半数量的级的新格子。利用这一观点，我们证明了删除信道上标准极性码的一个弱极化定理。为了实现强极化，我们对该方案进行了改进，在码字的各个部分之间增加了重复零的保护带。利用这种方法，我们得到了一种方案，它的速率接近于互信息，其差错概率在分组长度的立方根上指数衰减。
This paper presents the first proof of polarization for the deletion channel with a constant deletion rate and a regular hidden-Markov input distribution. A key part of this work involves representing the deletion channel using a trellis and describing the plus and minus polar-decoding operations on this trellis. In particular, the plus and minus operations can be seen as combining adjacent trellis stages to yield a new trellis with half as many stages. Using this viewpoint, we prove a weak polarization theorem for standard polar codes on the deletion channel. To achieve strong polarization, we modify this scheme by adding guard bands of repeated zeros between various parts of the codeword. Using this approach, we obtain a scheme whose rate approaches the mutual information and whose probability of error decays exponentially in the cube-root of the block length.