Fast polarization for non-stationary channels
Hessam Mahdavifar · 2017
We consider the problem of polar coding for transmission overa non-stationary sequence of independent binary-input memoryless symmetric (BMS) channels {Wi}∞i=1where the i-th encoded bit is transmitted over Wi. We show, for the first time, a polar coding scheme that achieves the average symmetric capacity I̅({Wi}∞i=1) def= limN→∞1/NNΣi=1I(Wi) assuming that the limit exists. The polar coding scheme is constructed using Arikan's channel polarization transformation in combination with certain permutations at each polarization level and certain skipped operations. This guarantees a fast polarization process that results in polar coding schemes with block lengths upper bounded by a polynomial of 1/e, where e is the gap to the average capacity. More specifically, given an arbitrary sequence of BMS channels {Wi}Ni=1and Pe, where 0i}Ni=1such that N ≤ κ/(I̅N- R)μwhere μ is a constant, κ is a constant depending on Pe and μ, and INis the average of the symmetric capacities I (Wi), for i = 1, 2, ...,N. We further show a numerical upper bound on μ that is: μ ≤ 10.78. The encoding and decoding complexities of the constructed polar code preserves O(N log N) complexity of Arikan's polar codes.