Technical Program

Paper Detail

Paper Title Polar Codes for the Deletion Channel: Weak and Strong Polarization
Paper IdentifierTU4.R8.2
Authors Ido Tal, Technion - Israel Institute of Technology, Israel; Henry D. Pfister, Duke University, United States; Arman Fazeli, Alexander Vardy, University of California, San Diego, United States
Session Insertion-Deletion Correcting Codes I
Location Conseil, Level 5
Session Time Tuesday, 09 July, 16:40 - 18:00
Presentation Time Tuesday, 09 July, 17:00 - 17:20
Manuscript  Click here to download the manuscript
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 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.