2010年第4期大眾科技No.4,2010(總第128期)DA ZHONG KE」I( Cumulatively No 128)LDPG碼的應(yīng)用尹芳滕舟〔桂林電子科技大學(xué)信息與通信學(xué)院,廣西桂林541004)【摘要】LDPC碼是迄今為止實驗中最接近 Shannon極限的信道編碼,也是下一代寬帶移動通信系統(tǒng)中糾錯碼的主要備選方案。文章介紹了LDPC碼的特點和優(yōu)勢,綜述了LDPC碼的編碼結(jié)構(gòu)及其優(yōu)化、譯碼及其優(yōu)仳、性能分析、碼的工程實現(xiàn)和實際應(yīng)用,分析了LDPC碼的應(yīng)用前景【關(guān)鍵詞】LDPC碼;二分圖;校驗矩陣;BP算法;EX∏圖【中圖分類號】TN9112【文獻標(biāo)識碼】A【文章編號】1008-1151(2010)04005002Gallager在1962年提出的低密度奇偶校驗碼Tanner圖中最短循環(huán)的長度稱為圖的 girth。LDPC碼的( Low-Density Parity- Check Codes,LDPC是一類可以用稀 Tanner圖和校驗矩陣一一對應(yīng)。疏矩陣或二分圖定義的線性分組碼。它具有非常好的特點:2.LDPC碼的優(yōu)化性能逼近香農(nóng)限,描述方便,易于進行理論分析,譯碼簡單碼的結(jié)構(gòu)決定了碼的性能。目前關(guān)于LDPC碼的構(gòu)造方法且可并行操作,適合硬件實現(xiàn)。近年來LDPC碼以其優(yōu)異的性能、簡潔的形式以及良好的應(yīng)用前景,非常適合在未來的移有很多。對于長碼、中長碼,短碼具有不同的構(gòu)造方法,其中主要可以分為兩大類:其一,隨機構(gòu)造和偽隨機構(gòu)造;其動通信系統(tǒng)中使用,因此吸引了廣大研究人員進行了深入研結(jié)構(gòu)化構(gòu)造方法。碼的隨機性越好碼的性能越好,但是隨機究?，F(xiàn)在許多正在擬定的通信標(biāo)準(zhǔn)都更多的關(guān)注了LDPC礦例如寬帶無線接入?yún)f(xié)議E802.16、中國國家地面數(shù)字電視性碼的編解碼和硬件實現(xiàn)比較困難,一般只用于理論仿真和標(biāo)準(zhǔn)以及衛(wèi)星通信標(biāo)準(zhǔn)DVB-S2已經(jīng)采納LDPC碼比較。結(jié)構(gòu)化構(gòu)造方法可以分為代數(shù)構(gòu)造方法和組合方法一)LDPC碼的結(jié)構(gòu)和優(yōu)化代數(shù)方法中包括基于有限幾何的構(gòu)造方法和基于循環(huán)置換矩1.LDPC碼的表示陣的方法。LDPC碼是一種線性分組碼,它的名字來源于其校驗矩陣LDC的譯碼主要分為硬判決譯碼和軟判決譯碼。軟判決的稀疏性,即校驗矩陣中只有數(shù)量很少的元素為“1”’大部譯碼主要采用迭代譯碼。如置信傳播(B)算法和對數(shù)域置分都為“0”。正是由于校驗矩陣是低密度矩陣,才能構(gòu)造出信傳播(LR)算法。BP譯碼的每次迭代包括兩步:校驗節(jié)點具有低復(fù)雜度、高性能的LDPC碼。 Gallager最早給出了正則的處理和變量節(jié)點的處理。在每次迭代中,所有校驗節(jié)點從LDPC碼的定義,具體來講正則(規(guī)則)LDPC碼的校驗矩陣H滿相鄰變量節(jié)點處接受信息,處理后再傳回到相鄰的變量節(jié)點足下面三個條件:(1)H的每行有p個“1”;(2)H的每列有λ個“1”,A≥3;(3)與碼長n和H的行數(shù)相比,p和λ都然后所有的變量節(jié)點進行同樣的過程;最后變量節(jié)點收集所有可以利用的消息進行判決。LLR算法將BP算法中大量的乘很小l1110000000。。00000。0法運算變成了加法運算,大大降低了譯碼算法的復(fù)雜度00。1111000000001碼的優(yōu)化包括編碼的優(yōu)化和譯碼的優(yōu)化。要消除校驗矩00000 00 0陣中的短環(huán),特別是四環(huán)?？梢圆捎媒Y(jié)構(gòu)化編碼避免環(huán),如準(zhǔn)循環(huán)方法構(gòu)造的QC-LDPC碼、基于均衡不完全區(qū)組0010設(shè)計構(gòu)造的BIBD-LDC碼、光正交00C-LDPC碼、 Turbo碼結(jié)010。構(gòu)的LDPC碼(TS-LDPC碼)等。如果采用隨機化編碼,如Gallager碼、 Mackay碼、PEG碼,可以采用一定的編碼方法。。。00。0。消除其中存在的短環(huán),如四環(huán)、六環(huán)圖1(20,3,4)LDC碼的校驗矩陣(二)性能分析DPC碼除了用校驗矩陣描述外,也可以由其二分圖即LDPC碼的性能分析方法主要分為三類:密度進化Tanner圖表示。( Density Evolution)理論、高斯近似( GaussianApproximation)和EXIT圖( ExtrinsicTransform Chart)。1.密度進化在LDPC碼的譯碼過程中,存在一種閥值現(xiàn)象,或者成為門限效應(yīng),即在信道噪聲水平低于某個閥值時,隨著碼長趨于無窮大,碼的錯誤概率可以任意逼近零,否則錯誤概率將大于一個正的常數(shù)。 Richardson等人通過分析傳遞信息的概率密度的進化情況,發(fā)現(xiàn)在和積譯碼算法的每次迭代信息傳圖2(20,3,4)矩陣的 Tanner圖中國煤化工【收稿日期】201001-20CNMHG【作者簡介】尹芳(1985-),女,湖北咸寧人,桂林電子科技大學(xué)信息與通仁子九土,九月向為無線通信。遞中出現(xiàn)錯誤信息的部分可以遞歸地表示成LDPC碼的度分布和概念上不再有什么秘密,因此在知識產(chǎn)權(quán)和專利商不再有序列和信道參數(shù)的函數(shù)。迭代計算節(jié)點間傳遞信息的概率密什么麻煩。這些優(yōu)點使得LDPC碼在信道條件較差的無線移動度函數(shù)的方法就成為密度進化。他們通過研究遞歸函數(shù)證明通信中展現(xiàn)出了巨大的應(yīng)用前景,非常適合于在未來的移動了閥值現(xiàn)象的存在性并給出了一種搜索好的節(jié)點度分布對的通信系統(tǒng)中實現(xiàn)?，F(xiàn)在許多正在擬定的通信標(biāo)準(zhǔn)都更多的關(guān)數(shù)值優(yōu)化技術(shù)。密度進化不僅應(yīng)用于BEC信道,還可以擴展注了LDPC碼到ISI信道,并由分析二進制LDPC碼擴展到多進制LDPC碼,近年來,LDC碼的很多研究成果表明LDPC碼時一類性能但是密度進化運算復(fù)雜度很高。優(yōu)異的好碼。LDPC碼比 Turbo碼在技術(shù)上更具有優(yōu)勢,更能2.高斯近似適應(yīng)未來無線通信系統(tǒng)的要求。由于對LDPC碼深入研究較晚晩,利用密度進化理論來計算閥值和尋找好的度數(shù)分布的算3G標(biāo)準(zhǔn)未采用,但基于LDPC碼極有可能成為4G通信系統(tǒng)的法復(fù)雜度是相當(dāng)大的,特別對于信息概率密度函數(shù)是多維的應(yīng)用方案,日前已經(jīng)有很多系統(tǒng)采用LDPC碼。如802.1la、信道來說,密度進化算法就過于復(fù)雜而難以處理。為提高密802.11n、802.3an、802.16e、DVB-S2等標(biāo)準(zhǔn)都采用了LDPC度進化算法的計算速度, Chung等人采用高斯近似的方法,即碼根據(jù)中心極限定理可以近似認(rèn)為節(jié)點間迭代的信息的概率密(四)結(jié)語度函數(shù)是符合高斯分布的,這樣講迭代計算的多為問題轉(zhuǎn)化除了優(yōu)化編解碼方法外,LDPC碼還可以與調(diào)制、級聯(lián)為跟新高斯密度均值的一維問題,極大簡化了分析和計算信分集合并、鏈路自適應(yīng)、跨層優(yōu)化等技術(shù)結(jié)合以達到更優(yōu)的道參數(shù)閥值的復(fù)雜度,而且可以快速的搜索和優(yōu)化非規(guī)則性能。LDPC碼由于LDPC碼不僅有逼近香農(nóng)限的良好性能,而且編譯碼3.EXIT圖復(fù)雜度較低,結(jié)構(gòu)靈活,因此成為第四代通信系統(tǒng)強有力的譯碼收斂性是指接收到的碼字是嗎能夠通過迭代方法漸竟?fàn)幷?具有巨大的應(yīng)用潛力,將在深空通信、光纖通信近正確碼字,如果能夠接近則說明收斂,ⅨXI?曲線( Extrinsic衛(wèi)星數(shù)字視頻和聲頻廣播、磁/光/全息存儲、移動和固定無Information transfer Chart)是從互信息角度分析譯碼器線通信、電纜調(diào)制解調(diào)器和數(shù)字用戶線(DSL)中得到廣泛的的收斂性?；バ畔? mutual information)可以充分反映譯應(yīng)用。碼器輸入輸出的相關(guān)性,它的特性:(1)互信息是最準(zhǔn)確的【參考文獻】統(tǒng)計變量;(2)互信息也幾乎是魯棒性最好的統(tǒng)計變量們袁東風(fēng),張海剛LDPC碼理論與應(yīng)用[M].人民郵電出版就是說互信息不會隨著信道、調(diào)制解調(diào)器等變化而有很大變社,2008.化。因此,采用互信息來觀察密度進化過程,比采用其他參[2]文紅符初生LDPC碼原理與應(yīng)用M]電子科技大學(xué)出版數(shù)跟蹤密度進化過程要簡單而且有效。EXIT圖比密度進化方社,2006.法計算量要小得多[]袁東風(fēng)張海霞寬帶移動通信中的先進信道編碼技術(shù)[M]J(三)LDP碼的應(yīng)用北京郵電大學(xué)出版社,2004LDPC碼的應(yīng)用有4個明顯優(yōu)勢:首先,LDPC碼具有一套[4] Nicholas Bonello, Sheng Chen, Lajos hanzo. Construction of較為系統(tǒng)的優(yōu)化設(shè)計方法、更強大的糾錯能力和更低的地板Regular Quasi-Cyclic Protograph LDPC Codes Based on效應(yīng)。其次,由于LDPC碼譯碼不基于網(wǎng)絡(luò),迭代譯碼算法為Vandermonde Matrices].IEEE Transactions on vehicular并行算法,可以實行完全并行的操作,便于硬件實現(xiàn),延時technology July 2008遠遠小于 turbo碼的串行迭代譯碼算法。第三,LDPC碼本身[5] Eran Sharon, Analysis of Low- Densty Parity-Check Codes即有抗突發(fā)差錯的特性,不需要引入交織器,避免了可能帶Based on EXIT Functions[] IEEE Transactions on來的延時。第四,LDPC碼是上世紀(jì)60年代發(fā)明的,現(xiàn)在理論ommunicationsAugust 2006一一一一一一一一一一一一一二二二二一上接第64頁)理.在通過隨機方法產(chǎn)生光線后,因為隨機的效果性而會有噪聲存在,在光照部分可以細分,而反射面到隨機使用蒙特卡羅的隨機光能匯集可以使計算量減少來滿足光線未到達部分則不用再細分。其中,分層思想涉及到波形實時情況下渲染幀數(shù)的提高,但由于隨機性使其從顯示上來因素細分和塊面細分兩方面內(nèi)容看,還有噪聲的存在;分層概念的引入則是為了彌補噪聲的(1)波形因素F。需要投射面的波形因素F到足夠存在,在有噪聲部分使分層面塊變大,計算精度降低,模糊,小否則就再分F下一步的工作是讓隨機光能匯集產(chǎn)生的噪聲結(jié)合新的方法來滿足實時光照要求。足m=()(-()2+(+…),r為塊的面積,R是點到塊中心的距離,并且r遠遠小于R【參考文獻】(2)面塊規(guī)則。面塊可以借用二叉樹型結(jié)構(gòu),如圖2。[1 GoralC M, T orance K E et a Modeling the interaction of light通過規(guī)則:一個塊只能訪問其同層但不直接相鄰的塊,并且between diffuse surfaces]. Computer Graphics 1984, 18(3)只能訪問其父塊直接相鄰的節(jié)點中的那些子塊.通過這兩條2 Cohen F, donald P. reenberg; Hemi-cube a radiosity規(guī)則,可以看到如塊b在圖2中能訪問的塊就是塊f:同理塊a能訪問的塊就是塊d。[3] KaiyaJ T, et al. T he R endering Equation[]. ACM Sig GraphComp Graph, 1986.(四)結(jié)語[4]Cohen M F,通過對物體表面分層化照射渲染和使用蒙特卡羅隨機光to fast radios中國煤化工rh,19824源匯集的方法可以實時的實現(xiàn)全局光照效果,在節(jié)約渲染時5] Gregary),FraCNMHGatang solution to間和圖形處理器時間和性能的條件下,達到了比較令人滿意dffureintereiedu