Channel polarization: A method for constructing capacity ...

1 [ ] 20 Jul 20091 Channel polarization: A method for constructingcapacity-achieving codes for symmetric binary-inputmemoryless channelsErdal Ar kan,Senior Member, IEEEA bstract A method is proposed, called Channel polarization,to construct code sequences that achieve the symmetric capacityI(W)of any given binary- input discrete memoryless Channel (B-DMC)W. The symmetric capacity is the highest rate achievablesubject to using the input letters of the Channel with equalprobability. Channel polarization refers to the fact that it ispossible to synthesize, out ofNindependent copies of a givenB-DMCW, a second set ofNbinary- input channels{W(i)N:1 i N}such that, asNbecomes large, the fraction ofindicesifor whichI(W(i)N)is near 1 approachesI(W)andthe fraction for whichI(W(i)N)is near 0 approaches1 I(W).

2 The polarized channels{W(i)N}are well-conditioned for channelcoding: one need only send data at rate 1 through those withcapacity near1and at rate 0 through the remaining. Codesconstructed on the basis of this idea are called polar proves that, given any B-DMCW withI(W)>0and anytarget rateR < I(W), there exists a sequence of polar codes{Cn;n 1}such thatCnhas block-lengthN= 2n, rate R, andprobability of block error under successive cancellation decodingbounded asPe(N, R) O(N 14)independently of the code performance is achievable by encoders and decoders withcomplexityO(NlogN)for Terms capacity -achieving codes, Channel capacity , Channel polarization, Plotkin construction, polar codes,Reed-Muller codes, successive cancellation INTRODUCTION AND OVERVIEWA fascinating aspect of Shannon s proof of the noisy channelcoding theorem is the random-coding method that he usedto show the existence of capacity -achieving code sequenceswithout exhibiting any specific such sequence [1].

3 Explicitconstruction of provably capacity -achieving code sequenceswith low encoding and decoding complexities has since thenbeen an elusive goal. This paper is an attempt to meet thisgoal for the class of will give a description of the main ideas and results ofthe paper in this section. First, we give some definitions andstate some basic facts that are used throughout the PreliminariesWe writeW:X Yto denote a generic B-DMCwith input alphabetX, output alphabetY, and transitionE. Ar kan is with the Department of Electrical-ElectronicsEngineering,Bilken t University, Ankara, 06800, Turkey (e-mail: work was supported in part by The Scientific and TechnologicalResearch Council of Turkey (T UBITAK) under Project 107E216and in partby the European Commission FP7 Network of Excellence NEWCOM++ undercontract (y|x),x X,y Y.)

4 The input alphabetXwill always be{0,1}, the output alphabet and the transitionprobabilities may be arbitrary. We writeWNto denote thechannel corresponding toNuses ofW; thus,WN:XN YNwithWN(yN1|xN1) =QNi=1W(yi|xi).Given a B-DMCW, there are two Channel parameters ofprimary interest in this paper: the symmetric capacityI(W) =Xy YXx X12W(y|x) logW(y|x)12W(y|0) +12W(y|1)and the Bhattacharyya parameterZ(W) =Xy YpW(y|0)W(y|1).These parameters are used as measures ofrateandreliability, (W)is the highest rate at which reliable com-munication is possible acrossWusing the inputs ofWwithequal (W)is an upper bound on the probabilityof maximum-likelihood (ML) decision error when W is usedonly once to transmit a 0 or is easy to see thatZ(W)takes values in[0,1]. Through-out, we will use base-2 logarithms; hence,I(W)will also takevalues in[0,1].

5 The unit for code rates and Channel capacitieswill , one would expect thatI(W) 1iffZ(W) 0,andI(W) 0iffZ(W) 1. The following bounds, provedin the Appendix, make this 1:For any B-DMCW, we haveI(W) log21 +Z(W),(1)I(W) p1 Z(W)2.(2)The symmetric capacityI(W)equals the Shannon capacitywhenWis asymmetricchannel, , a Channel for whichthere exists a permutation of the output alphabetYsuchthat (i) 1= and (ii)W(y|1) =W( (y)|0)for ally binary symmetric Channel (BSC) and the binary erasurechannel (BEC) are examples of symmetric channels. A BSCis a B-DMCW withY={0,1},W(0|0) =W(1|1), andW(1|0) =W(0|1). A B-DMCWis called a BEC if for eachy Y, eitherW(y|0)W(y|1) = 0orW(y|0) =W(y|1). Inthe latter case,yis said to be anerasuresymbol. The sumofW(y|0)over all erasure symbolsyis called the erasureprobability of the denote random variables (RVs) by upper-case letters,such asX,Y, and their realizations (sample values) by thecorresponding lower-case letters, such asx,y.

6 ForXa RV,PXdenotes the probability assignment onX. For a joint ensembleof RVs(X, Y),PX,Ydenotes the joint probability use the standard notationI(X;Y),I(X;Y|Z)to denotethe mutual information and its conditional form, use the notationaN1as shorthand for denoting a rowvector(a1, .. , aN). Given such a vectoraN1, we writeaji,1 i, j N, to denote the subvector(ai, .. , aj); ifj < i,ajiisregarded as void. GivenaN1andA {1, .. , N}, we writeaAto denote the subvector(ai:i A). We writeaj1,oto denotethe subvector with odd indices(ak: 1 k j;kodd). Wewriteaj1,eto denote the subvector with even indices(ak: 1 k j;keven). For example, fora51= (5,4,6,2,1), we havea42= (4,6,2),a51,e= (4,2),a41,o= (5,6). The notation0N1isused to denote the all-zero constructions in this paper will be carried out in vectorspaces over the binary field GF(2).

7 Unless specified otherwise,all vectors, matrices, and operations on them will be overGF(2). In particular, foraN1,bN1vectors over GF(2), we writeaN1 bN1to denote their componentwise mod-2 sum. TheKronecker product of anm-by-nmatrixA= [Aij]and anr-by-smatrixB= [Bij]is defined asA B= A11B AmnB ,which is anmr-by-nsmatrix. The Kronecker powerA nisdefined asA A (n 1)for alln 1. We will follow theconvention thatA 0 = [1].We write|A|to denote the number of elements in a write1 Ato denote the indicator function of a setA; thus,1A(x)equals1ifx Aand 0 use the standard Landau notationO(N),o(N), (N)to denote the asymptotic behavior of Channel polarizationChannel polarization is an operation by which one manu-factures out ofNindependent copies of a given B-DMCWa second set ofNchannels{W(i)N: 1 i N}that showa polarization effect in the sense that, asNbecomes large,the symmetric capacity terms{I(W(i)N)}tend towards 0 or 1for all but a vanishing fraction of indicesi.

8 This operationconsists of a Channel combining phase and a Channel ) Channel combining:This phase combines copies of agiven B-DMCWin a recursive manner to produce a vectorchannelWN:XN YN, whereNcan be any power of two,N= 2n,n 0. The recursion begins at the 0-th level (n= 0)with only one copy ofWand we setW1 =W. The first level(n= 1) of the recursion combines two independent copies ofW1as shown in Fig. 1 and obtains the channelW2:X2 Y2with the transition probabilitiesW2(y1, y2|u1, u2) =W(y1|u1 u2)W(y2|u2).(3)+WWu2u1x2x1y2y1W2 Fig. next level of the recursion is shown in Fig. 2 where twoindependent copies ofW2are combined to create the channelW4:X4 Y4with transition probabilitiesW4(y41|u41) =W2(y21|u1 u2, u3 u4)W2(y43|u2, u4).+WWx4x3y4y3W2+WWx2x1y2y1W2++W4v2v1v4 v3u1u2u3u4R4 Fig. channelW4and its relation Fig.

9 2,R4is the permutation operation that maps an input (s1, s2, s3, s4)tov41= (s1, s3, s2, s4). The mappingu417 x41from the input ofW4to the input ofW4can be writtenasx41=u41G4withG4= 1 0 0 01 0 1 01 1 0 01 1 1 1 .Thus, we have therelationW4(y41|u41) =W4(y41|u41G4)between the transitionprobabilities ofW4and those general form of the recursion is shown in Fig. 3 wheretwo independent copies ofWN/2are combined to produce thechannelWN. The input vectoruN1toWNis first transformedintosN1so thats2i 1=u2i 1 u2iands2i=u2ifor1 i N/2. The operatorRNin the figure is a permutation,known as thereverse shuffleoperation, and acts on its inputsN1to producevN1= (s1, s3, .. , sN 1, s2, s4, .. , sN), whichbecomes the input to the two copies ofWN/2as shown in observe that the mappinguN17 vN1is linear overGF(2).

10 It follows by induction that the overall mappinguN17 xN1, from the input of the synthesized channelWNto the inputof the underlying raw channelsWN, is also linear and may berepresented by a matrixGNso thatxN1=uN1GN. We callGN3 WNRNWN/2WN/2u1s1+v1y1u2s2v2y2uN/2 1sN/2 1+vN/2 1yN/2 1uN/2sN/2vN/2yN/2uN/2+1sN/2+1+vN/2+1yN/2 +1uN/2+2sN/2+2vN/2+2yN/2+2uN 1sN 1+vN 1yN construction ofWNfrom two copies matrixof sizeN. The transition probabilities ofthe two channelsWNandWNare related byWN(yN1|uN1) =WN(yN1|uN1GN)(4)for allyN1 YN,uN1 XN. We will show in Sect. VII thatGNequalsBNF nfor anyN= 2n,n 0, whereBNis apermutation matrix known asbit-reversalandF = [1 01 1]. Notethat the Channel combining operation is fully specified by thematrixF. Also note thatGNandF nhave the same set ofrows, but in a different (bit-reversed) order; we will discussthis topic more fully in Sect.