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

1、vol. 18no. 372航 天 器 工 程spacecraften gin eerin g第18卷 第3期 2009年5月applicationof ldpccodes in satellitenavigationsystemsh e shanbao l iu chonghua l in yiming(beijinginstit ute of spacecraft system engineering , beijing 100094 , china)abstract : low density parity check (ldpc ) codes are being accepted i

2、n many applicationsas a type of advanced channel codes approachingshannon limit.for example , ldpc codes havebeen used in dvb2s2 and willbe adopted in telemetry channel coding standard of ccsds.thispaper discusses an application of ldpc codes in satellite navigation systems , includingencodingon spa

3、cecraft and decoding in user receivers.gpsjointprogram office has presented ldpc codes of l1 message struct ure ininterfacespecification(draftis2gps2800 , navstargps space segment/ user segment l1c interfaces , 19april 2006) . subframe2 and 3 shall utilize 242bit cyclic redundancy check ( crc) algor

4、it hm wit ha separate crc for each subframe.eachof the two subframes shall bef urt her encoded using ld 2pc codes wit h lengt h 1 200/ 548 and rate 1/ 2.this paper gives a different kind of ldpc codes from above fec codes wit h the same lengt hand rate.they exhibitexcellent decoding performance , si

5、mple encoding struct ure and low deco2ding complexity.anot her advantage is that the parity check matrix can be denoted wit hout a se2ries of redundant tables.finally , this const ructionmethod of ldpc codes can be extended toot her satellite navigationsystems , such as galileo systemof europe and c

6、ompasssystemof china.key words :satellite navigation ; gps; ldpc codes; quasi2cyclic codes收稿日期:2008211215 ;修回日期:2009203210基金项目:国家重大科技专项工程作者简介:何善宝(1976 - ) ,男,博士,高工,从事卫星测控、 卫星通信与卫星导航等研究工作,目前研究方向为ldpc码 、星间通信与宽带多媒体通信。ldpc码在卫星导航系统中的应用何善宝 刘崇华 林益明(北京空间飞行器总体设计部,北京 100094)摘 要 作为一种接近香农极限的信道编码,近年来ldpc 码被广泛采用,

7、例如欧洲第二代数字视频广播卫星标准dvb 2s2和空间数据咨询委员会(ccsds)遥测信道编码标准就分别采用了 ldpc 码 。文章将讨论ldpc 码在卫星导航系统中的应用,内容涵盖星上编码与接收机解码。gps联合项目办公室在接口规范(draftis2gps2800 , navstar gps space segment/ u ser seg2ment l1c interfaces , 19 april2006) 中展现了l1 电文结构中的ldpc 码 。子帧 2 和子帧 3 将分别用一个独立的24bit 循环冗余检验(crc) 算法 。加入 crc 比特之后每一子帧将进一步被长度为 1 20

8、0/ 548 码率为 1/ 2 的 ldpc 码编码 。文章将给出同等长度同等码率的不同类型的ldpc 码 。它们表现出了优异的译码性能、 简单的编码结构和较低的译码复杂度。另外一个优点是其校验矩阵无需用一系列的冗余表格来表示。这种 ldpc 码的构造方法可以被扩展到其它卫星导航系统,比如欧洲的伽俐略( galileo) 系统和中国的北斗 (compass) 系统 。关键词 卫星导航gps ldpc 码 准循环码中图分类号: tn911122 文献标志码:a文章编号 :167328748(2009) 03200722051int roductionldpc codeswerefirst pre

9、sentedby g allager122in1960s. several years ago , ldpc codes were redis2covered by mac kay and neal 3, sipser and spiel2man 4and wiberg 5 . since then , intensivere2search has been dedicated to the study ofthesecodes. in recent years , various design schemes ofldpc codes have been accepted in many a

10、pplica2tions as a type of advanced channel codes approac2hingshannon limit.for example , ldpccodeshave being used in dvb 2s2 6and willbe adoptedin telemet ry channel coding standard of ccsds 7.this paper discusses an application of ldpc codesin satellite navigationsystems.l1c ldpc codes and their ap

11、plication in navi2gation data are described in section 2 , which maybe adopted in fut ure gps 8. ldpc codes based onsparse sequences 9and practical examples in gpsnavigation message are int roduced in detail in sec2tion 3.performance comparisons of differentclas2sesof ldpc codes are given in section

12、 4. section 5suggests an implementingmethod of encoding anddecoding of ldpc codes. and section 6 concludesthis paper and extends ldpc codes to other navi2gation systems.2l1c ldpccodesgps jointprogram officehas presented ld 2pc codes of l1 message struct ure in interface spec2ification 8 . subf rame

13、2 and subframe 3 are sepa2rately encoded using rate 1/ 2 ldpccodes.sub2frame 2 has a total of 600 bit s consisting of 576 bit sforclock and ephemeris and 24 bit s forcrc.subframe 3 has a total of 274 bit s consisting of 250bit s for variabledata and 24 bit s forcrc.as aresult of rate 1/ 2 ldpc encod

14、ing , there are 1 200symbols(coded bit s)for subframe 2 and 548 sym2bols for subframe 3 as described in figure 1.the ldpcencoder struct ure is based onaparity 2check matrixh (m, n)ofmrows and n col2umns.for subframe 2 ,m= 600 ,n= 1 200 and forsubf rame 3 ,m= 274 ,n= 548.h ( m, n)is furt herdecompose

15、d into 6 submat ricesa , b ,t,c,d ,and e as shown in figure 2. each element of ma2trixh ( m, n)is either a value of“0”or“1” .twelve tables , which occupy 27 pages , definet he coordinates of element s wit h value“1”in eachof the submatricesa , b, c, d , e,andt, respec2tively , for subframe 2 and sub

16、frame 3.the enco2ded symbols for broadcast are compo sed of( s; p1;p2)where s is the systematic portion of the code2word , and p1, p2comprises the combined paritybit s.fig. 1l1cmessage structurefig. 2parity check matrixhfor ldpccodes3sparse sequence ldpccodes311 construction methodsparse binary sequ

17、ences contain a small fixed37第3期 h e shanbao , et al : applicationof ldpccodes in satellitenavigationsystemsnumber of 1 while the ot her terms are all 0. com2puter generates several sparse sequences, whosecyclic cro ss correlationfunctionsare constrained.these sequences and their leftshift s by spec

18、ifiedpositions form the paritycheck matrix of an ldpccode so that each sequencecorresponds to a row inthis matrix.we user12(k)=n -1i =0 xiyi+ k(k =0,1,n -1)to denote the cyclic cro ss correlationfunctionbetween two sparse binary sequencess1= x0, x1, xn - 1ands2= y0, y1, yn- 1.the additionof those su

19、bscript sin the function is modulo n ad2dition.the const ructionof(3 ,p)ldpc codeswit h code rate (1 - 3/p) , or slightlyhigher than(1 - 3/p) , is illust rated as follows.three randomsparse sequencescontaining p1 s wit h sizen=m p,wheremis a natural number , can be representedbys1= x0, x1, xn- 1 , s

20、2= y0, y1, yn - 1ands3= z0, z1,zn -1.every termin a se2quence is labeled wit h a number ranging fro m 0 top - 1 , which is equivalent to it s subscript modulop. it is required t hat only one nonzero element ineach sequence lies in those places having the samelabel.the algorit hm forthe generationof

21、threesparse sequencesis described as follows.generate random sparse sequences1;s2befound =false ;while (s2befound = false)begingenerate random sparse sequences2;s2befound = true ;for (k= 0; k1 )s2befound =false ;ends3befound =false ;while (s3befound =false)begingenerate random sparse sequences3;s3be

22、found = true ;for (k= 0; k1 orr23(k)1)s3befound = false ;if(s3befound = true)for (i= 0; in ; i=i+p)for (j= 0; j1( ij). a 62cycle can also bedetected if the followingconditionsare satisfied :1) there is an 1 in common betweens1and a shiftedsequences2ofs2; 2) there is an 1 in commo n be2tweens1and a s

23、hifted sequences3ofs3; 3)thereis also a 1 in common betweens2ands3; 4) thepositions of the above three 1s are different.thennew codes wit h girt h 8 can be searched out fast.the parity 2check matrixh can be transformedinto the followingform through interchangingthecolumns :h =a01a02a0p-1a11a12a1p-1a

24、21a22a2p-1,whereaij( i =0,1,2; j =0,1, p -1)is a circu2lant matrix.therefore , quasi2cyclic codes, whichcan be made linear2timeencodable , can be ob2tained.312 navigation ldpc codes47航 天 器 工 程 18卷 312 11 separate codesthe similar separate encoding schedule as gpsjpo can be designed according to abov

25、e sparse se2quences constructionmethod.because ofredun2dancy of rows inhmatrix , ldpc codes ( 1 200 ,602) and (552 ,278) willbe const ricted forsub2frame 2 and subframe 3.for subframe 2 , 576 bit sclock & ephemeris and 24 bit s crc willbe enco2ded wit h 2 bit s zeros into 1 200 bit s. for subfra

26、me3 , 274 bit s willbe encoded wit h 4 bit s zeros into552 bit s , then 548 bit s willbe attained after punc2turing 4 bit s.312 12 compositive codeswe can encode a codeword for two subframes.the source 874 bit s (600 forsubframe 2 and 274for subframe 3)willbe encoded wit h 4 bit s zerosinto 1 752 bi

27、t s, then 1 748 bit s willbe attained af2ter puncturing 4 bit s.4simulationresult sthe belief propagation algorit hm or sum2prod 2uct algorit hm isused to decode sparse sequeces( ss )2ldpc codes. in the simulation , bpsk mod2ulated aw gn channel is adopted and the maxi2mum number of iterationis set

28、to 50.figure3showsbit2error 2rate( ber )andframe2error 2rate ( fer) of three ss 2ldpc codes ,(1 200 ,602 ) , ( 552 ,278) and ( 1 752 ,878) .it isseen that ldpc ( 1 752 ,878) only needs 215db atber 10- 5.separate ldpc ( 1 200 , 602)needs2165dbandseparateldpc( 552 , 278)needs3128db at ber 10- 5. it is

29、 also shown that ldpc(1 752 ,878)only needs 2158db at fer 10- 4. sep2arate ldpc( 1 200 ,602)needs 2178db and sepa2rate ldpc(552 ,278) needs 315db at fer 10- 4.figure 4 compares the ber of three ss 2ldpccodes and uncoded ber of bpsk modulation.it isseen that performanceimprovementofaboutatleast 712db

30、 , 710db and 6135db at ber 10- 5for akind of compositive ldpc codes and two kinds ofseparate ldpc codes.fig13b er and fer of ldpccodesfig14comparingss2ldpccodes withuncoded bpskmodulation5encoding and decodinginsatellitenavigationsystem ,theparitycheck matrices we design are quasi2cyclic.thent he ge

31、nerator matrices can also be transformed intoquasi2cyclic matrices.encoding of quasi2cyclic ld 2pc codes wit hout redundantrows in paritycheckmatrices can be implementedwit h shiftedregis2ters.quasi2cyclicldpccodeswit hredundantrows can also be encoded wit h several shifted regis2ters 10 . so ss 2ld

32、pc codes can be encoded easilyaccording to reference 10.in navigationsatellite , power and mass of anencoder are limited.on eart h , power and mass ofa decoder are limitedfor average handheld receiv257第3期 h e shanbao , et al : applicationof ldpccodes in satellitenavigationsystemsers. an area efficie

33、ntdecoding method of quasi2cy2clicldpccodes has been presented 11.themethod could reduce the logic core size by approxi 2mately 21 % wit hout any performance degradatio n.ss 2ldpc codes can be decoded by using this ap2proach.6conclusionsparse sequenceldpc codes are presented forgps navigationsignals

34、 , which performwellandhave low encoding complexityand good decodingstruct ure.the const ructionmethod can also beused to attained ldpc codes forgalileo navigationsystem and compass navigation system. for exam2ple , sparse sequenceldpc codes can replace con2volutionalcode wit h rate 1/ 2 in galileo

35、navigationsignals.references 1gallagerr g. low2density parity2check codesj .iretransinformtheory , 1962 ,8 :21228 2gallagerrg.low2densityparity2checkcodes m .cambridge , ma : mitpress , 1963 3mac kay d j c , neal r m.near shannon limitperform2ance of lowdensityparitycheck codes j .electronicsletters, 1996 ,32 (18) :164521646 4sipser m ,spielmand.expandercoders j .ieeetrans informtheory , 1996 ,42 :1710217225 wibergn.codes and decoding on generalgraphs d .linkoping, sweden : linkopinguniv., 1996 6