LDPC碼的優(yōu)化設計

LDPC碼的優(yōu)化設計[朱艷]搞要I通過(guò)碼結構優(yōu)化設計，可以得到性能接近香農限的LDPC好碼，其關(guān)鍵是尋找好的次數分布對。本文闡述了幾種有效分析LDPC碼性能的方法:密度演進(jìn)分析，高斯近似分析及基于EXIT圖的方法， 在此基礎上給出了LDPC碼優(yōu)化設計的過(guò)程。LDPC碼結構設計的研究對提高碼的性能和進(jìn)一步 推動(dòng)LDPC碼的實(shí)際應用有著(zhù)重要的意義?！逢P(guān)鍵詞: LDPC碼; 密度演進(jìn);高斯近似技術(shù)朱艷南京郵電大學(xué)通信與信息工程學(xué)院團1引言2 LDPC碼基礎LDPC (Low Density Parity Check)碼，最初是由LDPC碼是一種具有稀疏校驗矩陣H的線(xiàn)性分組碼,Gallager'l于1962年提出的。其后沉寂幾十年，1993年性舉例來(lái)說(shuō)，一個(gè)碼長(cháng)N=8,碼率R=1/2的LDPC碼可 以用能可逼近香農限的Turbo碼的出現，帶來(lái)了糾錯編碼理論下面的校驗矩陣來(lái)確定。任- -個(gè) 二進(jìn)制的線(xiàn)性分組碼，都上的突破，D.J.C.MacKay和M.Neal等人”對LDPC碼重新可以用“二分圖(Bipartite Graph)”描述。上面例子中進(jìn)行了研究，發(fā)現它同樣具有逼近香農限的性能?，F在它的LDPC碼二分圖表示如圖1所示。已成為通信技術(shù)中的新的研究熱點(diǎn)，其技術(shù)也日趨成熟。實(shí)驗上的結果表明LDPC性能極為優(yōu)異,文獻"中優(yōu)化設計的非正則LDPC碼在A(yíng)WGN信道上的理論極限性能[1 0011001]m0 110101 0|m.若"僅僅比香農限高0.0045 dB.>m中國煤化工，LDPC碼結構的優(yōu)化是要找到具有更好性能，離香農限更近的次數分布對。本文介紹了幾種碼結構優(yōu)化的分析1YHCNMHG4方法、密度演進(jìn)、高斯近似、EXIT圖等。n,圖1 LDPC碼的二分圖66LDPC碼的優(yōu)化設計二分圖由變量節點(diǎn)(Variable Nodes)、校驗節點(diǎn)LLR(r,)=0(Check Nodes)以及連接它們的邊(Edge)組成。左側的節點(diǎn)為變量節點(diǎn),代表了編碼后的比特位，對應校驗(2)計算變量節點(diǎn)i到校驗節點(diǎn)j的消息，矩陣中相應的列;右側的節點(diǎn)為校驗節點(diǎn)，代表了編碼比LLR(q,)= 2 LLR(ry)+ LLR(p,)特組成的校驗方程，對應校驗矩陣中相應的行;圖中的邊(3)計算校驗節點(diǎn)到變量節點(diǎn)i的消息，則表示左側的某個(gè)比特出現在右側的某個(gè)校驗方程中，對應了校驗矩陣中的非0元素。校驗方程表明，對一有效的LL()=(-1)40N2tanh-(. I tanh(; L(,))碼字，與各個(gè)校驗節點(diǎn)相連的變量節點(diǎn)其模2加的和應為0。在二分圖中，d. d分別表示與變量節點(diǎn)和校驗節點(diǎn)相(4)每個(gè)變量節點(diǎn)計算后驗LLR,連的邊數，稱(chēng)為該節點(diǎn)的次數(degree)。當d、 d。為 常數LLR(q,)= 2 LLR(y,)+ LLR(p,),1eM()時(shí)，這樣的LDPC碼稱(chēng)為正則(regular)碼，如上例所示。而當二分圖中的變量節點(diǎn)的次數各不相同(校驗節點(diǎn)的次(5)進(jìn)行硬判決LLR(q;)>=0判為1,否則判為0,數也有相應的變動(dòng))時(shí)，稱(chēng)為非正則irregular)碼。非正得x_ hat,如果mode(x_ _hat'H' ,2)=0則譯 碼成功。則碼通常用次數分布對(degree distribution pair)(1,p)來(lái)(6)否則重復步驟2~5,直到最大迭代次數，譯碼失描述:敗。硬判決譯碼，復雜度最低，性能也最差，BP算法譯技A(x)=金1p(p(x)=p;.x-分別碼復雜度在MP算法類(lèi)中最高，性能也最好。1=2從二分圖中看，對于變量節點(diǎn)，與之相連的邊越多為變量節點(diǎn)和校驗節點(diǎn)的次數分布多項式; A(p,)表示越好，如果邊越多，那么它可以從更多的相鄰校驗節點(diǎn)得與次數為i的比特(校驗)節點(diǎn)相連的邊數在總邊數中所到更多的邊信息，這樣就可更準確的判斷出它的正確值;占的比例; d,px (dgx) 表示比特(校驗)節點(diǎn)中的但對校驗節點(diǎn)來(lái)說(shuō)，恰好相反，與之相連的邊越少越好。如果與校驗節點(diǎn)相連的邊越少，那么它就可以給相鄰的信最大次數。息節點(diǎn)發(fā)送更有效的校驗信息。對于兩種相矛盾的要求,LDPC碼的性能與采用的譯碼算法密切相關(guān)，非正則碼顯然能較正則碼可更好的實(shí)現兩者的均衡。Gallager在提出LDPC碼"時(shí)給出了兩種迭代譯碼算法:但是并非所有的非正則碼性能都優(yōu)于正則碼，優(yōu)化硬判決和概率譯碼。后者雖有好的性能，但太復雜。選擇節點(diǎn)的次數分布(.p),可以提高LDPC碼的性能。Message Passing算法是一種工I作在圖論基礎上的譯碼算法，由于在算法的運行過(guò)程中，可靠性信息在二分圖的變3次數分布對的優(yōu)化設計量節點(diǎn)和校驗節點(diǎn)之間來(lái)回的傳遞，因此稱(chēng)為MessageGallager在最初的文獻"中，在BSC(二進(jìn)制對稱(chēng)信Passing算法。它是-一個(gè)算法類(lèi)，如果相互間傳送的是硬道)上分析了(3,k)正則碼進(jìn)行硬判決譯碼的性能;判決信息，算法即成為Gallager提出的硬判決譯碼，如Richardson等人在文獻[4]中分析了非正則碼(3,2)在BEC果傳遞的消息是連續的軟判決信息，就等價(jià)于BP(Belief(二元刪除信道)上用MP (Message Passing)算法譯Propagation)算法。碼時(shí)的性能，發(fā)現LDPC碼存在一種“門(mén)限BP譯碼算法過(guò)程如下所示:(Th中國煤化工于某一門(mén)限值時(shí)，2或信MHCNMHG,在碼長(cháng)足夠大的(1)初始化: LLR(p;)==y; (AWGN信道).情況下，碼集中的幾乎任何一種碼的誤碼率都能隨著(zhù)迭代σ2009.8廣東通信技術(shù)》技術(shù)交流譯碼次數的增加而遞減趨近于0;反之，誤碼率將始終大P= P 8 a[r"([(P_))(2)于某一正的常數。對應某一碼集的門(mén)限值也可看成碼容量其中，r. r-I 分別表示定義在兩種消息域上的概(Capacity)。具有良好特征的二分圖，其對應的LDPC率密度函數域之間的變換和反變換。碼集有高譯碼噪聲門(mén)限，也具有較大的碼容量。(2)近似Density Evolution相關(guān)研究表明這個(gè)信噪比門(mén)限取決于LDPC碼的次數分布。這方面研究往往結合次數分布優(yōu)化技術(shù)和密度演進(jìn)用密度演進(jìn)(DE)計算門(mén)限，優(yōu)化次數分布是困難(Density Evolution)技術(shù)來(lái)搜索具有高譯碼噪聲門(mén)限的的，復雜度很高，相應的就有了近似DE算法。近似算法的基本思路是將PDF迭代的多維計算問(wèn)題轉化為僅僅次數分布對。計算一個(gè)參數(通常是高斯函數)迭代的-維計算問(wèn)(1)基于BP算法的密度演進(jìn)密度演進(jìn)(DE: Density Evolution)分 析的思想是由題。幾種常見(jiàn)的近似DE方案:高斯近似(GA-GaussianRichardson等'在研究MP(Message Passing)譯碼算法時(shí)Approximation),基于EXIT圖的方法，Semi高斯近似。Sae-Young Chung等間提出對概率密度函數進(jìn)行高提出的:通過(guò)考察譯碼消息的概率密度函數(PDF一Probability Density Function)在譯碼迭代中的演進(jìn)情斯近似的方法，根據譯碼消息的獨立性條件和大數定理,況，分析譯碼算法的收斂情況。變量節點(diǎn)次數d,較大時(shí)，從變量節點(diǎn)發(fā)往校驗節點(diǎn)的譯在DE分析中，通常需要滿(mǎn)足對稱(chēng)性(symmetry)的條碼消息v近似呈高斯分布;從校驗節點(diǎn)發(fā)往變量節點(diǎn)的譯件。Richardson等人“已證明，在對稱(chēng)性條件下， 譯碼差碼消息u則不像高斯分布，尤其是當它的均值靠近0的時(shí)錯概率具有條件獨立性(Conditional Independence)，候。但是研究發(fā)現，假設譯碼消息V. u為高斯分布的隨即，譯碼差錯率與發(fā)送的碼字無(wú)關(guān)。這樣，就可以假設發(fā)機變量不僅不影響對BP算法的密度演進(jìn)分析，還可以簡(jiǎn)送的是全1碼字來(lái)計算DE.化密度演進(jìn)的分析過(guò)程。而由對稱(chēng)性條件，消息的均值與在譯碼算法的消息獨立性條件下，譯碼中的消息求方差之間存在著(zhù)聯(lián)系: σ°=2m° 因此，在GA分析中，和運算，其密度演進(jìn)對應譯碼消息的PDF的卷積運算。因對應的密度演進(jìn)就進(jìn)-步簡(jiǎn)化為一個(gè)參數(均值)的運此，為簡(jiǎn)化DE分析，Richardson等'45)引入另一種消息形算。迭代公式如下所示:式，并定義了兩種消息域上的映射Y:[-∞,+∞]→GF(2)x[0,+∞],使得BP算法的譯碼(4)迭代都為消息求和運算:其中，l為迭代次數，m。if(1=0)(u-x)戶(hù)m"={mo+ 2 m") if(l≥1)qx)={-底' [uanh exp(-4-)du (x>0)c'eCct(x=0)m")=y"[ Er(m!=")](1)中(x)函數的直接計算很復雜，可以作如下近似計v'e叫算:其中，l為迭代次數，m(為從變量節點(diǎn)v發(fā)往校驗對較小的x，如x <10，中(x)~e*+B, 其中節點(diǎn)C的譯碼消息，m"表示從校驗節點(diǎn)發(fā)往變量節點(diǎn)的a=-0.4527，β=0.0218， Y= 0.86;中國煤化工)取上.下界的平均譯碼消息，mg為初始消息。 若令P. Q、P分別表MHCNMHG值，示它們的PDF.則話(huà)e(-元)LDPC碼的優(yōu)化設計這一簡(jiǎn)化不但使得求取LDPC碼的門(mén)限值的計算變得似，EXIT圖等方法得其門(mén)限值。簡(jiǎn)單，而且可以更直觀(guān)地理解譯碼器的工作原理。另外,若采用GA算法計算門(mén)限值，則評價(jià)次數分布對高斯近似還方便了在A(yíng)WGN信道上設計非正則碼的次數分(h,p)時(shí)。先給定- -個(gè)較小的信道參數(高斯信道的σ參布對。數)，再將對應的初始消息的均值一代入式(4)中，EXIT ( Extrinsic Information Transfer)圖是由S. tenBrink提出的一種用迭代譯碼器之間傳輸的外信息來(lái)表征進(jìn)行迭代。若在給定的最大迭代譯碼次數內，譯碼的錯誤迭代譯碼中收斂行為的分析工具。s. ten Brink等人”將消息概率小于之前設定的目標值E(足夠小，接近于0),則EXIT圖技術(shù)引入到LDPC碼譯碼分析中，即把LDPC碼認為該信道參數小于門(mén)限值，并按某步長(cháng)增大信道參數σ的譯碼過(guò)程可以看作是變量節點(diǎn)譯碼器和校驗節點(diǎn)譯碼器重新代入計算;若新的信道參數使得迭代始終無(wú)法收之間外信息的迭代，用EXIT圖跟蹤譯碼器之間的互信息斂，即譯碼的錯誤消息概率不能達到目標值，則認為超出傳遞來(lái)估計LDPC碼和積譯碼算法的收斂性?；贓XIT了門(mén)限值，并取增大前的信道參數σ作為該次數分布對圖的方法可以看作是DE方法的一種簡(jiǎn)化方案，它的優(yōu)點(diǎn)(.ρ)的門(mén)限值σ°。在于:在迭代的過(guò)程中跟蹤的是互信息的值，與DE方法③優(yōu)化算法中的概率密度函數. GA方法中的均值等相比較，具有更搜索具有高譯碼噪聲門(mén)限的次數分布對是一種復雜好的魯棒性。其對碼的性能分析和估計比高斯近似方法更的非線(xiàn)性?xún)?yōu)化技術(shù)。主要有局部?jì)?yōu)化和全局優(yōu)化的兩種不準確，與密度演進(jìn)方法相比計算復雜度也小得多。同的方法。局部?jì)?yōu)化的方法利用局部?jì)?yōu)化的結果進(jìn)行試探技(3)優(yōu)化設計過(guò)程術(shù)性的搜索.以減小搜索空間。全局優(yōu)化的方法從整體上進(jìn)LDPC碼的門(mén)限是使得所有譯碼迭代收斂或譯碼消息行優(yōu)化。的密度演進(jìn)收斂的信道參數的上限。它表明了正則或非正采用DE. GA可以得出具體次數分布對下LDPC碼的則LDPC碼能夠達到的碼容量的上界，反映了LDPC碼能門(mén)限值，結合優(yōu)化算法可以?xún)?yōu)化設計次數分布對。優(yōu)化算夠容忍的信道環(huán)境的惡劣程度.因而是評價(jià)LDPC碼的重法可以采用差分進(jìn)化，PSO算法及各種改進(jìn)算法等。要標準。④目前次數分布對尋找的成果而優(yōu)化設計LDPC碼，就是在次數分布的解空間中,對于二元輸入的BI-AWGN信道，已經(jīng)找到了門(mén)限值搜索具有高門(mén)限值的LDPC碼。與香農限僅僅相差0.0045dB的次數分布對，而仿真表明.①解空間在碼長(cháng)為10'. R= 1/2時(shí)，它的性能曲線(xiàn)距離香農限只差次數分布多項式中的系數是待優(yōu)化變量，相互之間0.04 dB*。J.Hou等鬥研究了平坦瑞利衰落信道中LDPC碼存在碼率約束Zp,/i=(1-R)22/j.歸一化約束的優(yōu)化和性能分析，證明優(yōu)化了的非正則碼(碼長(cháng)為3072)性能優(yōu)于相應的Turbo碼。h=1--三不. p:=1-Ep同時(shí)校驗節點(diǎn)的次數4結束語(yǔ)分布具有集中形式: p(x)=ρ.x*-'+(1-ρ)x。 去除通過(guò)LDPC碼的碼結構優(yōu)化設計，可以獲得性能盡可次數分布對中的冗余變量后得到待優(yōu)化的目標向量能好的LDPC碼。LDPC碼結構設計的研究對提高碼的性能和進(jìn)(...).其中獨立變量數為L(cháng)=d, -2.中國煤化工要的意義。本文介②計算LDPC碼的門(mén)限值紹了密TYCHCNMHG點(diǎn)及LDPC碼優(yōu)化設給定次數分布對時(shí)，可以通過(guò)密度演進(jìn)，高斯近計的過(guò)程，后面可將其他的優(yōu)化技不與LDPC碼性能分析方法相結合.如PSO算法及各種改進(jìn)算法和DE技術(shù)或者EXIT692009.8廣東通信技術(shù)》技術(shù)交流圍方法進(jìn)行結合，尋找一種兼顧性能和復雜度的有效搜索3 T.J.Richardson, M.A.Shokrollahi and R.L.Urbanke. Design方法，是碼結構優(yōu)化設計的一-個(gè)可行的研究方向。of Capacity-Approaching Iregular Low Density Parity-Check Codes. IEEE Trans. on Inform. Theory, 47(2):619-637, 2001參考文獻1 R.G.Gallager. Low-Density Parity-Check Codes. IRE3 Sae-Young Chung, TJ.Richardson and R.L.Urbanke.Transactions on Information Theory, IT-8:21-28, 1962Analysis of Sum-Product Decoding of Low-Density Parity-2 David J.C.MacKay and R.M.Neal. Near Shannon LimitCheck Codes Using a Gaussian Appoximatin. IEEEPertormance of Low-Density Party-Check Codes.Transactions on Information Theory, 47(2): 657-670, 2001Electronics Ltters, 32(18): 1645-1646, 19963 Stephan ten Brink, Gerthard Kramer and Alexei Ashikhmin.3 S.Y. Chung, G. D. Fomey, Jr, T. J. Richardson, andDesign of Low-Density Parity Check Codes for Multi-R. Urbanke. On the design of low density parity-checkAntenna Modulation and Detection. IEEE Transactions oncodes within 0.0045 dB of the Shannon limit. IEEEcommunications,52(4):670-678.2004Communication Letters, 5(2): 58-60. 20013 J. Hou, P. H. Siegel and L. B. Milstein, Perormance3 T.J.Richardson and RL.Urbanke. The Capacity of Low-analysis and code optimization of low density parity checkDensity Parity-Check Codes under Message-Passingcodes on rayleigh fading channels, IEEE J.S.A in Commun.decoding. IEEE Trans. on Inform. Theory, 47(2);599-618,19(5):924-934. 20012001(收稿日期:2009-07-15)技:=:=:=:=i=:=:=i=:=:=:=:=:=:=:=:=: =:3 =:=: = =:=:=:=:=i=: = =:=(上接第58頁(yè))Wireless Networks, IEEE Jourmal on Selected Areas inConference, 2007, Globecom' 07. November 2007.Communications, January 2008.41 Niyato.D, Hossain.E. Equilibrum and Disequilibrum39 Dusit Niyato, Ekram Hossain. Competitive Pricing forPricing for Spectrum Trading in Cognitive Radio: A Control-Spectrum Sharing in Cognitive Radio Networks: DynamicTheoretic Approach. IEEE Global TelecommunicationsGame, Iefficiency of Nash Equlibrium, and Collusion.Conference, 2007, Giobecom' 07. November 2007.IEEE Joumal on Selected Areas in Communications,42 Kyasanur Pradeep and Valaya Nitin H. Protocol designVOL26, NO.1 January 2006.chanlenges for multi-hop dynamic spectrum access40 Niyato.D. Hossain.E. Optimal Price Compettion fornetworks. In Proe IEEE DySPAN' 05. Baltimore,Spectrum Sharing in Cognitive Radio: A Dynamic Game-November 2005:645-648(收稿日期:2009-07-10)歡迎訂閱《廣 東通信技術(shù)》《曠東通信技術(shù)》創(chuàng )刊于1981年，是中國電信股份有元，國內外公開(kāi)發(fā)行。國際標準刊號: ISSN 1006- 6403;限公司廣東分公司主管，廣東省通信學(xué)會(huì )和廣東省電信情報國內統-刊號: CN44- -1221/TN.中心站聯(lián)合主辦的廣東省唯- -的綜合性通信技術(shù)刊物。全國各地郵局均可訂閱。國內郵發(fā)代號: 46-245.《廣東通信技術(shù)》主要反映廣東通信建設的最新成就中國煤化工里訂閱，具體事宜與和交流引進(jìn)、吸收國內外先進(jìn)通信技術(shù)的經(jīng)驗，介紹國內外最新通信技術(shù)的發(fā)展及趨勢等。MYHCNMHG《廣東通信技術(shù)》月刊，大16開(kāi)，全年定價(jià)120.00聯(lián)系人:方小姐70|