Channel-Polarization：-A-Method-for-Constructing-Ca

ChannelPolarization:AMethodforConstructingCapacity-AchievingCodesErdalArıkanElectrical-ElectronicsEngineeringDepartmentBilkentUniversity,Ankara,TR-06800,TurkeyEmail:[e-mail]—Amethodisproposed,calledchannelpolarization,toconstructcodesequencesthatachievethesymmetriccapacityI(W)ofanygivenbinary-inputdiscretememorylesschannel(B-DMC)W.ThesymmetriccapacityI(W)isthehighestrateachievablesubjecttousingtheinputlettersofthechannelequiprobablyandequalsthecapacityC(W)ifthechannelhascertainsymmetryproperties.Channelpolarizationreferstothefactthatitispossibletosynthesize,outofNindependentcopiesofagivenB-DMCW,adifferentsetofNbinary-inputchannelssuchthatthecapacitiesofthelatterset,exceptforanegligiblefractionofthem,areeithernear1ornear0.ThissecondsetofNchannelsarewell-conditionedforchannelcoding:oneneedonlysenddataatfullratethroughchannelswithcapacitynear1andat0ratethroughtheothers.Themaincodingtheoremaboutpolarcodingstatesthat,givenanyB-DMCWwithI(W)0andanyfixed0δI(W),thereexistfiniteconstantsn1(W,δ)andc(W,δ)suchthatforalln≥n1,thereexistpolarcodeswithblocklengthN=2n,rateRI(W)−δ,andprobabilityofblockdecodingerrorPe≤cN−1/4.ThecodeswiththisperformancecanbeencodedanddecodedwithincomplexityO(NlogN).I.CHANNELPOLARIZATIONLetW:X→YdenoteanarbitraryB-DMCwithinputalphabetX={0,1},outputalphabetY,andtransitionprobabilities[W(y|x)],x∈X,y∈Y.LetWNdenotetheDMCconsistingofNindependentcopiesofW.Channelpolarizationmethodhastwoparts:channelcom-biningandchannelsplitting.ThechannelcombiningpartisarecursivemethodthatcombinesN=2nindependentcopiesofWtoconstructachannelWN:XN→YN.TherecursionbeginsbycombiningtwocopiesofWasshowninFig.1toobtainthechannelW2:X2→Y2withtransitionprobabilitiesW2(y1y2|u1u2)=W(y1|u1⊕u2)W(y2|u2)(1)ThenextlevelofrecursionisshowninFig.2wheretwo+WWu2u1x2x1y2y1W2Fig.1.ThechannelW2.independentcopiesofW2arecombinedtocreatethechannelW4:X4→Y4withtransitionprobabilitiesW4(y41|u41)=W2(y21|u1⊕u2,u3⊕u4)W2(y43|u2,u4).Weusethenotation+WWx4x3y4y3W2+WWx2x1y2y1W2++W4v2v1v4v3u1u2u3u4Π4Fig.2.ThechannelW4anditsrelationtoW2andW.aN1todenoteanarbitraryvector(a1,...,aN),andajitodenotethesubvector(ai,...,aj).InFig.2,Π4isthepermu-tationa41→(a1,a3,a2,a4).Notethatthemappingu41→x41fromtheinputofthechannelW4totheinputofW4canbewrittenasx41=u41G4,whereG4=⎡⎢⎢⎣1000101011001111⎤⎥⎥⎦(2)WecallG4thegeneratormatrixofsize4.Thus,wehavetherelationW4(y41|u41)=W4(y41|u41G4)betweenthetransitionprobabilitiesofthecombinedchannelW4andthoseofthecollectionofunderlyingrawchannelsW4.ThegeneralformoftherecursionisshowninFig.3wheretwoindependentcopiesofWNarecombinedtocreateW2N:X2N→Y2N.Theinputvectoru2N1toW2NisfirstISIT2008,Toronto,Canada,July6-11,20081173978-1-4244-2571-6/08/$25.00©2008IEEEΠ2NWNWNu2Nu2N−1u4u3u2u1+++s2Ns2N−1s4s3s2s1v2NvN+2vN+1...vNv2v1...y2NyN+1...yNy1.........W2NFig.3.TherelationbetweenthechannelsW2NandWN.transformedtoavectors2N1suchthats2i−1=u2i−1⊕u2iands2i=u2ifor1≤i≤N.ThepermutationΠ2Nactsons2N1togeneratev2N1suchthatvi=s2i−1andvN+i=s2ifor1≤i≤N.Thiscompletesthedescriptionofthechannelcombiningpart.Togiveaconcisealgebraicdescriptionofchannelcombin-ing,wedefineGN,thegeneratormatrixofsizeN,asthematrixsuchthatWN(yN1|uN1)=WN(yN1|uN1GN)(3)forallyN1∈YN,uN1∈XN.Proposition1:ThegeneratormatrixisgivenbyGN=F⊗n˜ΠN=˜ΠNF⊗n(4)whereF⊗nisthen-foldtensorproductofFΔ=1011 withitselfand˜ΠNisapermutationmatrixknownasthebit-reversaloperation.Weomitproofsduetospacelimitationsandreferto[1].Todescribethebit-reversaloperation,weneedtoconsideranalternativeindexingforvectors.GivenavectoraN1withlengthN=2nforsomen≥0,wemaydenoteitsithelement,ai,1≤i≤N,alternativelyasabn···b1wherebn···b1isthebinaryexpansionofintegeri−1,i.e.,i−1=nj=1bj2j−1.Now,bit-reversalappliedtoaN1sendsittocN1suchthatcbn···b1=ab1···bn.Forexample,a41=(a00,a01,a10,a11)issenttoc41=(a00,a10,a01,a11).HavingcombinedNindependentcopiesofWintoachannelWN,thenextandfinalstepofchannelpolarizationistosplitWNbackintoasetofNbinary-inputchannelsW(i)N:X→YN×Xi−1,1≤i≤N,definedbythetransitionprobabilitiesW(i)N(yN1,ui−11|ui)=uNi+1∈XN−i12N−1WN(yN1|uN1)(5)where(yN1,ui−11)representstheoutputofW(i)Nanduiitsinput.ThechannelsW(i)NexhibitapolarizationeffectinthesensethatthefractionofindicesiforwhichthesymmetriccapacityI(W(i)N)isinsidetheinterval(δ,1−δ)goestozeroasNgoestoinfinityforanyfixedδ0.ThisisillustratedinFig.4forWabinaryerasurechannel(BEC)witherasureprobability=0.5.00.20.40.60.810510152025SymmetriccapacityinbitsFrequencyFig.4.HistogramofI(W(i)N)forN=26andWaBECwith=0.5.WetakeadvantageofthepolarizationeffecttoconstructcodesthatachieveratesapproachingI(W)byamethodwecallpolarcoding.ThebasicideaofpolarcodingistocreateacodingsystemwhereonecanaccesseachsynthesizedchannelW(i)NindividuallyandsenddataonlythroughthesubsetofthemforwhichI(W(i)N)isnear1.II.POLARCODINGForanysubsetAof{1,...,N},wewillwriteGN(A)todenotethesubmatrixofGNconsistingofrowswithindicesinA.WewillrefertothesetAastheinformationsetanddenoteitscardinalityby|A|.WewilldenotebyActhecomplementofAin{1,...,N}.ForanysuchAandanybinaryvectorf|Ac|1oflengthN−|A|,thepair(A,f|Ac|1)wi