搜索
IEEETRANSACTIONSONINFORMATIONTHEORY,VOL.55,NO.7,JULY20093051ChannelPolarization:AMethodforConstructingCapacity-AchievingCodesforSymmetricBinary-InputMemorylessChannelsErdalArıkan,SeniorMember,IEEEAbstract—Amethodisproposed,calledchannelpolarization,toconstructcodesequencesthatachievethesymmetriccapacity ofanygivenbinary-inputdiscretememorylesschannel(B-DMC) .Thesymmetriccapacityisthehighestrateachiev-ablesubjecttousingtheinputlettersofthechannelwithequalprobability.Channelpolarizationreferstothefactthatitispos-sibletosynthesize,outof independentcopiesofagivenB-DMC ,asecondsetof binary-inputchannels suchthat,as becomeslarge,thefractionofindices forwhich isnear approaches andthefractionforwhich isnear approaches .Thepolarizedchannels arewell-conditionedforchannelcoding:oneneedonlysenddataatrate throughthosewithcapacitynear andatrate throughtheremaining.Codesconstructedonthebasisofthisideaarecalledpolarcodes.Thepaperprovesthat,givenanyB-DMC with andanytargetrate ,thereexistsasequenceofpolarcodes suchthat hasblock-length ,rate ,andprobabilityofblockerrorundersuc-cessivecancellationdecodingboundedas independentlyofthecoderate.Thisperformanceisachievablebyencodersanddecoderswithcomplexity foreach.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:arikan@ee.bilkent.edu.tr).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