a method for constructing capacity achieving codes

IEEETRANSACTIONSONINFORMATIONTHEORY,VOL.55,NO.7,JULY20093051ChannelPolarization:AMethodforConstructingCapacity-AchievingCodesforSymmetricBinary-InputMemorylessChannelsErdalArıkan,SeniorMember,IEEEAbstract—Amethodisproposed,calledchannelpolarization,toconstructcodesequencesthatachievethesymmetriccapacityofanygivenbinary-inputdiscretememorylesschannel(B-DMC).Thesymmetriccapacityisthehighestrateachiev-ablesubjecttousingtheinputlettersofthechannelwithequalprobability.Channelpolarizationreferstothefactthatitispos-sibletosynthesize,outofindependentcopiesofagivenB-DMC,asecondsetofbinary-inputchannelssuchthat,asbecomeslarge,thefractionofindicesforwhichisnearapproachesandthefractionforwhichisnearapproaches.Thepolarizedchannelsarewell-conditionedforchannelcoding:oneneedonlysenddataatratethroughthosewithcapacitynearandatratethroughtheremaining.Codesconstructedonthebasisofthisideaarecalledpolarcodes.Thepaperprovesthat,givenanyB-DMCwithandanytargetrate,thereexistsasequenceofpolarcodessuchthathasblock-length,rate,andprobabilityofblockerrorundersuc-cessivecancellationdecodingboundedasindependentlyofthecoderate.Thisperformanceisachievablebyencodersanddecoderswithcomplexityforeach.IndexTerms—Capacity-achievingcodes,channelcapacity,channelpolarization,Plotkinconstruction,polarcodes,Reed–Muller(RM)codes,successivecancellationdecoding.I.INTRODUCTIONANDOVERVIEWAFASCINATINGaspectofShannon’sproofofthenoisychannelcodingtheoremistherandom-codingmethodthatheusedtoshowtheexistenceofcapacity-achievingcodesequenceswithoutexhibitinganyspecificsuchsequence[1].Explicitconstructionofprovablycapacity-achievingcodesequenceswithlowencodinganddecodingcomplexitieshassincethenbeenanelusivegoal.Thispaperisanattempttomeetthisgoalfortheclassofbinary-inputdiscretememorylesschannels(B-DMCs).Wewillgiveadescriptionofthemainideasandresultsofthepaperinthissection.First,wegivesomedefinitionsandstatesomebasicfactsthatareusedthroughoutthepaper.ManuscriptreceivedOctober14,2007;revisedAugust13,2008.Currentver-sionpublishedJune24,2009.ThisworkwassupportedinpartbyTheScien-tificandTechnologicalResearchCouncilofTurkey(TÜB˙ITAK)underProject107E216andinpartbytheEuropeanCommissionFP7NetworkofExcellenceNEWCOM++underContract216715.ThematerialinthispaperwaspresentedinpartattheIEEEInternationalSymposiumonInformationTheory(ISIT),Toronto,ON,Canada,July2008.TheauthoriswiththeDepartmentofElectrical-ElectronicsEngineering,BilkentUniversity,Ankara,06800,Turkey(e-mail:[e-mail]).CommunicatedbyY.Steinberg,AssociateEditorforShannonTheory.ColorversionsofFigures4and7inthispaperareavailableonlineat:thesymmetriccapacityandtheBhattacharyyaparameterTheseparametersareusedasmeasuresofrateandreliability,respectively.isthehighestrateatwhichreliablecommu-nicationispossibleacrossusingtheinputsofwithequalfrequency.isanupperboundontheprobabilityofmax-imum-likelihood(ML)decisionerrorwhenisusedonlyoncetotransmitaor.Itiseasytoseethattakesvaluesin.Throughout,wewillusebase-logarithms;hence,willalsotakevaluesin.Theunitforcoderatesandchannelcapacitieswillbebits.Intuitively,onewouldexpectthatiff,andiff.Thefollowingbounds,provedintheAppendix,makethisprecise.Proposition1:ForanyB-DMC,wehave(1)(2)ThesymmetriccapacityequalstheShannoncapacitywhenisasymmetricchannel,i.e.,achannelforwhichthereexistsapermutationoftheoutputalphabetsuchthati)andii)forall.Thebi-narysymmetricchannel(BSC)andthebinaryerasurechannel(BEC)areexamplesofsymmetricchannels.ABSCisaB-DMCwithand.AB-DMCiscalledaBECifforeach,eitheror.Inthelattercase,0018-9448/$25.00©2009IEEE3052IEEETRANSACTIONSONINFORMATIONTHEORY,VOL.55,NO.7,JULY2009Fig.1.Thechannel.issaidtobeanerasuresymbol.ThesumofoverallerasuresymbolsiscalledtheerasureprobabilityoftheBEC.Wedenoterandomvariables(RVs)byuppercaseletters,suchas,andtheirrealizations(samplevalues)bythecorre-spondinglowercaseletters,suchas.ForanRV,denotestheprobabilityassignmenton.ForajointensembleofRVsdenotesthejointprobabilityassignment.Weusethestandardnotationtodenotethemutualinformationanditsconditionalform,respectively.Weusethenotationasshorthandfordenotingarowvector.Givensuchavector,wewrite,,todenotethesubvector;ifisregardedasvoid.Givenand,wewritetodenotethesubvector.Wewritetodenotethesubvectorwithoddindicesodd.Wewritetode-notethesubvectorwithevenindiceseven.Forexample,for,wehave.Thenotationisusedtodenotetheall-zerovector.CodeconstructionsinthispaperwillbecarriedoutinvectorspacesoverthebinaryfieldGF.Unlessspecifiedotherwise,allvectors,matrices,andoperationsonthemwillbeoverGF.Inparticular,forvectorsoverGFwe