학술논문
Polar Codes for the Deletion Channel: Weak and Strong Polarization
Document Type
Periodical
Author
Source
IEEE Transactions on Information Theory IEEE Trans. Inform. Theory Information Theory, IEEE Transactions on. 68(4):2239-2265 Apr, 2022
Subject
Language
ISSN
0018-9448
1557-9654
1557-9654
Abstract
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 that 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. This gives a scheme whose rate approaches the mutual information and whose probability of error decays exponentially in the cube-root of the block length. We conclude by showing that this scheme can achieve capacity on the deletion channel by proving that the capacity of the deletion channel can be achieved by a sequence of regular hidden-Markov input distributions.