The channel polarization process was introduced by Arikan as an elegant mathematical model for the study of the channel coding problem over binary-input discrete memoryless channels (B-DMCs). By studying the convergence properties of specific information measures associated to the channel polarization process, in particular the symmetric capacity and the Bhattacharyya parameter, Arikan devised the now well established polar coding error correction framework. This paper provides additional results on the convergence properties of the channel polarization process for the class of B-DMCs. In particular, we study the convergence properties of the erasure probabilities of the synthetic channels.

We consider the problem of designing robust and low complexity decoding schemes for polar coding over a given finite class of channels. We propose two schemes based on multiple runs of the polar successive cancellation decoder, where at each run a different metric adapted to a channel in the class is used in the decoder's decision procedure. The first scheme is a modified polar coding scheme which accommodates Cyclic Redundancy Check bits to help the decoder eliminate the estimates that do not pass the test. We show that this scheme achieves the symmetric capacity of the channel with a vanishing rate loss of O(1√N), where N is the blocklength of the code. The second scheme involves a polar decoding algorithm which implements a generalized likelihood ratio test. We show that over classes of channels which satisfy certain mild conditions, this scheme achieves the symmetric capacity of the channel. The analyses reveal that the decay of the error probability of both schemes is exponential in the square root of the blocklength, which is similar to the polar successive cancellation decoder operating with the knowledge of the true channel. Finally, we compare the schemes in terms of their performances and complexity, and discuss the extension to infinite classes of channels.

We give a simple proof of Arıkan's polarization phenomenon that uses only elementary methods. Using the same method, we show that Arıkan's construction also polarizes non-stationary memoryless channels in the same way it polarizes the stationary memoryless channels.

We describe certain extremalities for Gallager's E0function evaluated under the uniform input distribution over the class of binary input discrete memoryless channels; The results characterize the extremality of the E0(ρ) curves of the binary erasure channel and the binary symmetric channel among all the E0(ρ) curves that can be generated by the class of binary discrete memoryless channels whose E0(ρ) curves pass through a given point (ρ0, ε0), for some ρ0> -1.

We study partial orders on the information sets of polar codes designed for binary discrete memoryless channels. We show that the polar transform defined by Arikan preserves `symmetric convex/concave orders'. While for symmetric channels this ordering turns out to be equivalent to the stochastic degradation ordering already known to order the information sets of polar codes, we show that a strictly weaker partial order is obtained when at least one of the channels is asymmetric. We also discuss two tools which can be useful for verifying this ordering: a criterion known as the cut criterion and channel symmetrization.

We give a simple proof of Arikan's polarization phenomenon that uses only elementary methods. Using the same method, we show that Arikan's construction also polarizes non-stationary memoryless channels in the same way it polarizes stationary memoryless channels. This is a new result.

Polar coding over a class of binary input discrete memoryless channels with channel knowledge at the encoder is studied. It is shown that polar codes achieve the symmetric capacity of convex and one-sided sets of channels. This result makes the polar decoder the first low complexity O(N logN) decoder proved to be universal over one sided sets of symmetric channels.

We show that the mismatched capacity of binary discrete memoryless channels can be improved by channel combining and splitting via Arikan's polar transform. We also show that the improvement is possible even if the transformed channels are decoded with a mismatched polar decoder.

We study the extremality of the binary erasure channel and the binary symmetric channel for Gallager's reliability function E0of binary input discrete memoryless channels evaluated under the uniform input distribution from the aspect of channel polarization. In particular, we show that amongst all binary discrete memoryless channels of a given E0(ρ) value, for a fixed ρ ≥ 0, the binary erasure channel and the binary symmetric channel are extremal in the evolution of E0under the one-step polarization transformations.

We prove that channel combining and splitting via Arikan's polarization transformation improves Gallager's reliability function E0for binary input channels. In this sense, polarization creates E0. This observation gives yet another justification as to why the polar transform yields capacity achieving and low complexity codes: the improvement in E0translates to an improvement in complexity-error-probability trade-off. In analyzing polar codes, one examines auxiliary random processes that follow the evolution of information measures as an underlying communication channel undergoes a sequence of transformations. The conclusion of this paper shows that the E0process associated to such an analysis is a submartingale.

We prove that channel combining and splitting via Arikan's polarization transformation improves Gallager's reliability function E0for binary input channels. In this sense polarization `creates' E0. This observation gives yet another justification as to why the polar transform yields capacity achieving and low complexity codes: the improvement in E0translates to an improvement in complexity-error-probability trade-off. In analyzing polar codes, one examines auxiliary random processes that follow the evolution of information measures as an underlying communication channel undergoes a sequence of transformations. The conclusion of this paper shows that the E0process associated to such an analysis is a submartingale.

In this paper we show that mismatched polar codes over symmetric B-DMCs symmetrized under the same permutation can achieve rates of at least I(W, V) bits whenever I(W, V) > 0, where W denotes the communication channel, V the mismatched channel used in the code design including both the encoder and decoder, and I(W, V) × ΣyΣx ϵ {0,1}1/2 W(y|x) log2(V(y|x))/(1/2V(y|0) + 1/2V(y|1)).

We describe certain extremality properties for Gallager's reliability function Eofor binary input symmetric DMCs. In particular, we show that amongst such DMC's whose E0(ρ1) has a given value for a given ρ1, the BEC and BSC have the largest and smallest value of the derivative of Eo(ρ2) for any ρ2≥ ρ1. As the random coding exponent is obtained by tracing the map ρ → (E0'(ρ), E0(ρ) - pE'0(ρ)) this conclusion includes as a special case the results of [1]. Furthermore, we show that amongst channels W with a given value of E0(ρ) for a given ρ the BEC and BSC are the most and least polarizing under Arıkan's polar transformations in the sense that their polar transforms W+and W-has the largest and smallest difference in their Eovalues.