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