LDPC码在卫星导航系统中的应用_英文_

Vol.18No.372t?SPACECRAFTENGINEERING1832009M5ApplicationofLDPCCodesinSatelliteNavigationSystemsHEShanbaoLIUChonghuaLINYiming(BeijingInstituteofSpacecraftSystemEngineering,Beijing100094,China)Abstract:LowDensityParityCheck(LDPC)codesarebeingacceptedinmanyapplicationsasatypeofadvancedchannelcodesapproachingShannonlimit.Forexample,LDPCcodeshavebeenusedinDVB-S2andwillbeadoptedintelemetrychannelcodingstandardofCCSDS.ThispaperdiscussesanapplicationofLDPCcodesinsatellitenavigationsystems,includingencodingonspacecraftanddecodinginuserreceivers.GPSJointProgramOfficehaspresentedLDPCcodesofL1messagestructureinInterfacespecification(DraftIS-GPS-800,NavstarGPSSpaceSegment/UserSegmentL1CInterfaces,19April2006).Subframe2and3shallutilize24-bitCyclicRedundancyCheck(CRC)algorithmwithaseparateCRCforeachsubframe.EachofthetwosubframesshallbefurtherencodedusingLD-PCcodeswithlength1200/548andrate1/2.ThispapergivesadifferentkindofLDPCcodesfromaboveFECcodeswiththesamelengthandrate.Theyexhibitexcellentdecodingperformance,simpleencodingstructureandlowdeco-dingcomplexity.Anotheradvantageisthattheparitycheckmatrixcanbedenotedwithoutase-riesofredundanttables.Finally,thisconstructionmethodofLDPCcodescanbeextendedtoothersatellitenavigationsystems,suchasGalileosystemofEuropeandCompasssystemofChina.Keywords:satellitenavigation;GPS;LDPCcodes;quas-icycliccodesl:2008-11-15;:2009-03-10:国家重大科技专项工程Te:何善宝(1976-),男,博士,高工,从事卫星测控a卫星通信与卫星导航等研究工作,目前研究方向为LDPC码a星间通信与宽带多媒体通信bLDPCtd何善宝刘崇华林益明(bWf98!9,100094)K1作为一种接近香农极限的信道编码,近年来LDPC码被广泛采用,例如欧洲第二代数字视频广播卫星标准DVB-S2和空间数据咨询委员会(CCSDS)遥测信道编码标准就分别采用了LDPC码b文章将讨论LDPC码在卫星导航系统中的应用,内容涵盖星上编码与接收机解码bGPS联合项目办公室在接口规范(DraftIS-GPS-800,NavstarGPSSpaceSegment/UserSeg-mentL1CInterfaces,19April2006)中展现了L1电文结构中的LDPC码b子帧2和子帧3将分别用一个独立的24bit循环冗余检验(CRC)算法b加入CRC比特之后每一子帧将进一步被长度为1200/548码率为1/2的LDPC码编码b文章将给出同等长度同等码率的不同类型的LDPC码b它们表现出了优异的译码性能a简单的编码结构和较低的译码复杂度b另外一个优点是其校验矩阵无需用一系列的冗余表格来表示b这种LDPC码的构造方法可以被扩展到其它卫星导航系统,比如欧洲的伽俐略(Galileo)系统和中国的北斗(Compass)系统b1oM卫星导航GPSLDPC码准循环码ms|:TN911122DS:AcI|:1673-8748(2009)03-0072-051IntroductionLDPCcodeswerefirstpresentedbyGallager1-2in1960s.Severalyearsago,LDPCcodeswereredis-coveredbyMacKayandNeal3,SipserandSpie-lman4andWiberg5.Sincethen,intensivere-searchhasbeendedicatedtothestudyofthesecodes.Inrecentyears,variousdesignschemesofLDPCcodeshavebeenacceptedinmanyapplica-tionsasatypeofadvancedchannelcodesapproac-hingShannonlimit.Forexample,LDPCcodeshavebeingusedinDVB-S26andwillbeadoptedintelemetrychannelcodingstandardofCCSDS7.ThispaperdiscussesanapplicationofLDPCcodesinsatellitenavigationsystems.L1CLDPCcodesandtheirapplicationinnav-igationdataaredescribedinSection2,whichmaybeadoptedinfutureGPS8.LDPCcodesbasedonsparsesequences9andpracticalexamplesinGPSnavigationmessageareintroducedindetailinSec-tion3.Performancecomparisonsofdifferentclas-sesofLDPCcodesaregiveninSection4.Section5suggestsanimplementingmethodofencodinganddecodingofLDPCcodes.AndSection6concludesthispaperandextendsLDPCcodestoothernav-igationsystems.2L1CLDPCCodesGPSJointProgramOfficehaspresentedLD-PCcodesofL1messagestructureinInterfacespec-ification8.Subframe2andsubframe3aresepa-ratelyencodedusingrate1/2LDPCcodes.Sub-frame2hasatotalof600bitsconsistingof576bitsforClockandEphemerisand24bitsforCRC.Subframe3hasatotalof274bitsconsistingof250bitsforVariableDataand24bitsforCRC.Asaresultofrate1/2LDPCencoding,thereare1200symbols(codedbits)forSubframe2and548sym-bolsforSubframe3asdescribedinFigure1.TheLDPCencoderstructureisbasedonaparity-checkmatrixH(m,n)ofmrowsandnco-lumns.ForSubframe2,m=600,n=1200andforSubframe3,m=274,n=548.H(m,n)isfurtherdecomposedinto6submatricesA,B,T,C,D,andEasshowninFigure2.Eachelementofma-trixH(m,n)iseitheravalueof/00or/10.Twelvetables,whichoccupy27pages,definethecoordinatesofelementswithvalue/10ineachofthesubmatricesA,B,C,D,E,andT,respec-tively,forSubframe2andSubframe3.Theenco-dedsymbolsforbroadcastarecomposedof(s;p1;p2)wheresisthesystematicportionofthecode-word,andp1,p2comprisesthecombinedparitybits.Fig.1L1CMessageStructureFig.2ParitycheckmatrixHforLDPCcodes3SparseSequenceLDPCCodes311ConstructionMethodSparsebinarysequencescontainasmallfixed733HEShanbao,etal:ApplicationofLDPCCodesinSatelliteNavigationSystemsnumberof1whiletheothertermsareall0.Com-putergeneratesseveralsparsesequences,whosecycliccrosscorrelationfunctionsareconstrained.ThesesequencesandtheirleftshiftsbyspecifiedpositionsformtheparitycheckmatrixofanLDPCcodesothateachsequencecorrespondstoarowinthismatrix.WeuseR12(k)=EN-1i=0xiyi+k(k=0,1,N-1)todenotethecycliccrosscorrelationfunctionbetweentwosparsebinarysequencesS1=x0,x1,xN-1andS2=y0,y1,yN-1.TheadditionofthosesubscriptsinthefunctionismoduloNad-dition.Theconstructionof(3,p)LDPCcodeswithcoderate(1-3/p),orslightlyhigherthan(1-3/p),isillustratedasfollows.Threerandomsparsesequencescontainingp1swithsizeN=Mp,whereMisanaturalnumber,canberepresentedbyS1=x0,x1,xN-1,S2=y0,y1,yN-1andS3=z0,z1,zN-1.Everyterminase-quenceislabeledwithanumberrangingfrom0top-1,whichisequivalenttoitssubscriptmodulop.Itisrequiredthatonlyonenonzeroelementineachsequenceliesinthoseplaceshavingthesamelabel.Thealgorithmforthegenerationofthreesparsesequencesisdescribedasfollows.generaterandomsparsesequenceS1;S2befound=false;while(S2befound=false)begingeneraterandomsparsesequenceS2;S2befound=true;for(k=0;k1)S2befound=false;endS3befound=false;while(S3befound=false)begingeneraterandomsparsesequenceS3;S3befound=true;for(k=0;k1orR23(k)1)S3befound=false;if(S3befound=true)for(i=0;i1(iXj).A6-cyclecanalsobedetectedifthefollowingconditionsaresatisfied:1)thereisan1incommonbetweenS1andashiftedsequenceSc2ofS2;2)thereisan1incommonbe-tweenS1andashiftedsequenceSc3ofS3;3)thereisalsoa1incommonbetweenSc2andSc3;4)thepositionsoftheabovethree1saredifferent.Thennewcodeswithgirth8canbesearchedoutfast.Theparity-checkmatrixHcanbetransformedintothefollowingformthroughinterchangingthecolumns:H=A01A02,A0p-1A11A12,A1p-1A21A22,A2p-1,whereAij(i=0,1,2;j=0,1,p-1)isacircu-lantmatrix.Therefore,quas-icycliccodes,whichcanbemadelinear-timeencodable,canbeob-tained.312NavigationLDPCCodes74t?1831211SeparateCodesThesimilarseparateencodingscheduleasGPSJPOcanbedesignedaccordingtoabovesparsese-quencesconstructionmethod.Becauseofredun-dancyofrowsinHmatrix,LDPCcodes(1200,602)and(552,278)willbeconstrictedforsub-frame2andsubframe3.Forsubframe2,576bitsclock&ephemerisand24bitsCRCwillbeenco-dedwith2bitszerosinto1200bits.Forsubframe3,274bitswillbeencodedwith4bitszerosinto552bits,then548bitswillbeattainedafterpunc-turing4bits.31212CompositiveCodesWecanencodeacodewordfortwosubframes.Thesource874bits(600forsubframe2and274forsubframe3)willbeencodedwith4bitszerosinto1752bits,then1748bitswillbeattainedaf-terpuncturing4bits.4SimulationResultsThebeliefpropagationalgorithmorsum-prod-uctalgorithmisusedtodecodesparsesequeces(SS)-LDPCcodes.Inthesimulation,BPSKmod-ulatedAWGNchannelisadoptedandthemax-imumnumberofiterationissetto50.Figure3showsbit-error-rate(BER)andframe-error-rate(FER)ofthreeSS-LDPCcodes,(1200,602),(552,278)and(1752,878).ItisseenthatLDPC(1752,878)onlyneeds215dBatBER10-5.SeparateLDPC(1200,602)needs2165dBandseparateLDPC(552,278)needs3128dBatBER10-5.ItisalsoshownthatLDPC(1752,878)onlyneeds2158dBatFER10-4.Sep-arateLDPC(1200,602)needs2178dBandsepa-rateLDPC(552,278)needs315dBatFER10-4.Figure4comparestheBERofthreeSS-LDPCcodesanduncodedBERofBPSKmodulation.Itisseenthatperformanceimprovementofaboutatleast712dB,710dBand6135dBatBER10-5forakindofcompositiveLDPCcodesandtwokindsofseparateLDPCcodes.Fig13BERandFERofLDPCcodesFig14ComparingSS-LDPCcodeswithuncodedBPSKmodulation5EncodingandDecodingInsatellitenavigationsystem,theparitycheckmatriceswedesignarequas-icyclic.Thenthegeneratormatricescanalsobetransformedintoquas-icyclicmatrices.Encodingofquas-icyclicLD-PCcodeswithoutredundantrowsinparitycheckmatricescanbeimplementedwithshiftedregis-ters.Quas-icyclicLDPCcodeswithredundantrowscanalsobeencodedwithseveralshiftedregis-ters10.SoSS-LDPCcodescanbeencodedeasilyaccordingtoreference10.Innavigationsatellite,powerandmassofanencoderarelimited.Onearth,powerandmassofadecoderarelimitedforaveragehandheldreceiv-753HEShanbao,etal:ApplicationofLDPCCodesinSatelliteNavigationSystemsers.Anareaefficientdecodingmethodofquas-icy-clicLDPCcodeshasbeenpresented11.Themethodcouldreducethelogiccoresizebyapprox-imately21%withoutanyperformancedegradation.SS-LDPCcodescanbedecodedbyusingthisap-proach.6ConclusionSparsesequenceLDPCcodesarepresentedforGPSnavigationsignals,whichperformwellandhavelowencodingcomplexityandgooddecodingstructure.TheconstructionmethodcanalsobeusedtoattainedLDPCcodesforGalileonavigationsystemandCompassnavigationsystem.Forexam-ple,sparsesequenceLDPCcodescanreplaceCon-volutionalcodewithrate1/2inGalileonavigationsignals.References1GallagerRG.Low-densityparity-checkcodesJ.IRETransInformTheory,1962,8:21-282GallagerRG.Low-densityparity-checkcodesM.Cambridge,MA:MITPress,19633MacKayDJC,NealRM.Nearshannonlimitperform-anceoflowdensityparitycheckcodesJ.ElectronicsLetters,1996,32(18):1645-16464SipserM,SpielmanD.ExpandercodersJ.IEEETransInformTheory,1996,42