Channel polarization, originally proposed for binary-input channels, is generalized to arbitrary discrete memoryless channels. Specifically, it is shown that when the input alphabet size is a prime number, a similar construction to that for the binary case leads to polarization. This method can be extended to channels of composite input alphabet sizes by decomposing such channels into a set of channels with prime input alphabet sizes. It is also shown that all discrete memoryless channels can be polarized by randomized constructions. The introduction of randomness does not change the order of complexity of polar code construction, encoding, and decoding. A previous result on the error probability behavior of polar codes is also extended to the case of arbitrary discrete memoryless channels. The generalization of polarization to channels with arbitrary finite input alphabet sizes leads to polar-coding methods for approaching the true (as opposed to symmetric) channel capacity of arbitrary channels with discrete or continuous input alphabets. Index Terms Capacity-achieving codes, channel polarization, polar codes. I. POLARIZATION Channel polarization was introduced in [1] for binary input discrete memoryless channels as a coding technique to construct codes — called polar codes — for data transmission. Polar codes are capable of achieving the ‘symmetric capacity’ of any binary input channel, using low-complexity encoding and decoding algorithms. In terms of the block-length N, polar codes can be encoded and decoded in complexity O(N log N ) and achieve a block error probability that decays roughly like 2-√N . The latter result was shown in [2]. The aim of this note is to extend these results of [1], [2] to DMCs with q-ary inputs for any finite integer q ≥ 2. To that end, we recall the polarization construction and outline how the results above were shown. Given a binary input channel W : X → Y with X = {0, 1} define its symmetric capacity as 􏰘􏰘1 W(y|x) I(W)= 2W(y|x)log2􏰖 1 ′ . (1) x∈X y∈Y I(W) is nothing but the mutual information developed between the input and the output of the channel when the input is uniformly distributed. In [1], two independent copies of W are first combined and then split so as to obtain two unequal binary input channels W- and W+. The channel W2 : X2 → Y2 describes two uses of the channel W, W2(y1,y2|x1,x2) = W(y1|x1)W(y2|x2). The input (x1, x2) to the channel W 2 are put in one-to-one correspondence with (u1, u2) ∈ X 2 via x1 = (u1 + u2) mod 2, x2 = u2, thus obtaining the combined channel W2 : X2 → Y2 described by W2(y1,y1|u1,u2)=W2(y1,y2|u1 +u2,u2)=W(y1|u1 +u2)W(y2|u2). The split is inspired by the chain rule of mutual information: Let U1,U2,X1,X2,Y1,Y2 be random variables corresponding to their lowercase versions above. If U1,U2 are independent and uniformly distributed, then so are X1,X2 and consequently, on the one hand, I (U1 , U2 ; Y1 , Y2 ) = I (X1 , X2 ; Y1 , Y2 ) = I (X1 ; Y1 ) + I (X2 ; Y2 ) = 2I (W ), and on the other I(U1, U2; Y1, Y2) = I(U1; Y1, Y2) + I(U2; Y1, Y2, U1). The split channels W- and W+ describe those that occur on the right-hand side of the equation above: W-(y1,y2|u1)= 􏰘 1W(y1|u1 +u2)W(y2|u2), 2 x′∈X 2W(y|x) u2 ∈X W+(y1,y2,u1|u2)= 1W(y1|u1 +u2)W(y2|u2), 2 so that I(U1;Y1,Y2) = I(W-) and I(U2;Y1,Y2,U1) = I(W+). arXiv:0908.0302v1 [cs.IT] 3 Aug 2009 Thepolarizationconstructiongivenin[1]isobtainedbyarepeatedapplicationofW→􏰣 (W-,W+).SincebothW-and W+ are binary input channels, one can obtain W– := (W-)-, W-+ := (W-)+, W+- := (W+)-, and W++ := (W+)+. After n levels of application, one obtains 2n channels W - ··· -, . . . , W + ··· +. The main observation in [1] is that these channels polarize in the following sense: Proposition 1 ([1]). For any δ > 0, lim #􏰆s∈{+,-}n:I(Ws)∈(δ,1-δ)􏰇=0. (2) n→∞ 2n In other words, except for a vanishing fraction, all the channels obtained at level n are either almost perfect, I(Ws) ≥ 1-δ, or almost pure noise, I(Ws) ≤ δ. 􏰖 As the equality I(W -) + I(W +) = 2I(W ) leads by induction to s∈{+,-}n I(W s) = 2nI(W ), one then concludes that the fraction of almost perfect channels approaches the symmetric capacity. This last observation is the basis of what lets [1] conclude that polar codes achieve the symmetric capacity. We give here a new proof of this proposition because it will readily generalize to the q-ary input case we will discuss later. Before we embark on this proof, we introduce the Bhattacharyya parameter for a binary input channel W : X → Y, defined by Z(W ) = 􏰘 􏰥W (y|0)W (y|1). (3) y The relationship between Z(W), Z(W-), Z(W+) and I(W) is already discussed in [1], where the following is shown: Lemma 1 ([1]). (i) Z(W+)=Z(W)2, (ii) Z(W-) ≤ 2Z(W) - Z(W)2, (iii) I(W)+Z(W)≥1, (iv) I(W)2+Z(W)2≤1. Proposition 1 was proved in [1] for the binary case (q = 2) using Lemma 1.

Polarization for arbitrary discrete memoryless channels Eren S ̧as ̧og ̆lu, Emre Telatar, Erdal Arıkan