Fast Polarization and Finite-Length Scaling for Non-Stationary Channels.
Hessam Mahdavifar · arXiv (Cornell University) · 2016
We consider the problem of polar coding for transmission over a non-stationary sequence of independent binary-input memoryless symmetric (BMS) channels $\left\{W_i\right\}_{i=1}^{\infty}$, where the $i$-th encoded bit is transmitted over $W_i$. We show, for the first time, a polar coding scheme that achieves the effective average symmetric capacity $$ \overline{I}(\left\{W_i\right\}_{i=1}^{\infty}) := \lim_{N\rightarrow \infty} \frac{1}{N}\sum_{i=1}^N I(W_i), $$ 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/\epsilon$, where $\epsilon$ is the gap to the average capacity. More specifically, given an arbitrary sequence of BMS channels $\left\{W_i\right\}_{i=1}^{N}$ and $P_e$, where $0 < P_e <1$, we construct a polar code of length $N$ and rate $R$ guaranteeing a block error probability of at most $P_e$ for transmission over $\left\{W_i\right\}_{i=1}^{N}$ such that $$ N \leq \frac{\kappa}{(\overline{I}_N - R)^{\mu}} $$ where $\mu$ is a constant, $\kappa$ is a constant depending on $P_e$ and $\mu$, and $\overline{I}_N$ is the average of the symmetric capacities $I(W_i)$, for $i=1,2,,\dots,N$. We further show a numerical upper bound on $\mu$ that is: $\mu \leq 10.78$. The encoding and decoding complexities of the constructed polar code preserves $O(N \log N)$ complexity of Arikan's polar codes.