LDPC碼的優(yōu)化設(shè)計[朱艷]搞要I通過碼結(jié)構(gòu)優(yōu)化設(shè)計，可以得到性能接近香農(nóng)限的LDPC好碼，其關(guān)鍵是尋找好的次數(shù)分布對。本文闡述了幾種有效分析LDPC碼性能的方法:密度演進分析，高斯近似分析及基于EXIT圖的方法， 在此基礎(chǔ)上給出了LDPC碼優(yōu)化設(shè)計的過程。LDPC碼結(jié)構(gòu)設(shè)計的研究對提高碼的性能和進一步 推動LDPC碼的實際應(yīng)用有著重要的意義?！逢P(guān)鍵詞: LDPC碼; 密度演進;高斯近似技術(shù)朱艷南京郵電大學(xué)通信與信息工程學(xué)院團1引言2 LDPC碼基礎(chǔ)LDPC (Low Density Parity Check)碼，最初是由LDPC碼是一種具有稀疏校驗矩陣H的線性分組碼,Gallager'l于1962年提出的。其后沉寂幾十年，1993年性舉例來說，一個碼長N=8,碼率R=1/2的LDPC碼可 以用能可逼近香農(nóng)限的Turbo碼的出現(xiàn)，帶來了糾錯編碼理論下面的校驗矩陣來確定。任- -個 二進制的線性分組碼，都上的突破，D.J.C.MacKay和M.Neal等人”對LDPC碼重新可以用“二分圖(Bipartite Graph)”描述。上面例子中進行了研究，發(fā)現(xiàn)它同樣具有逼近香農(nóng)限的性能?，F(xiàn)在它的LDPC碼二分圖表示如圖1所示。已成為通信技術(shù)中的新的研究熱點，其技術(shù)也日趨成熟。實驗上的結(jié)果表明LDPC性能極為優(yōu)異,文獻"中優(yōu)化設(shè)計的非正則LDPC碼在AWGN信道上的理論極限性能[1 0011001]m0 110101 0|m.若"僅僅比香農(nóng)限高0.0045 dB.>m中國煤化工，LDPC碼結(jié)構(gòu)的優(yōu)化是要找到具有更好性能，離香農(nóng)限更近的次數(shù)分布對。本文介紹了幾種碼結(jié)構(gòu)優(yōu)化的分析1YHCNMHG4方法、密度演進、高斯近似、EXIT圖等。n,圖1 LDPC碼的二分圖66LDPC碼的優(yōu)化設(shè)計二分圖由變量節(jié)點(Variable Nodes)、校驗節(jié)點LLR(r,)=0(Check Nodes)以及連接它們的邊(Edge)組成。左側(cè)的節(jié)點為變量節(jié)點,代表了編碼后的比特位，對應(yīng)校驗(2)計算變量節(jié)點i到校驗節(jié)點j的消息，矩陣中相應(yīng)的列;右側(cè)的節(jié)點為校驗節(jié)點，代表了編碼比LLR(q,)= 2 LLR(ry)+ LLR(p,)特組成的校驗方程，對應(yīng)校驗矩陣中相應(yīng)的行;圖中的邊(3)計算校驗節(jié)點到變量節(jié)點i的消息，則表示左側(cè)的某個比特出現(xiàn)在右側(cè)的某個校驗方程中，對應(yīng)了校驗矩陣中的非0元素。校驗方程表明，對一有效的LL()=(-1)40N2tanh-(. I tanh(; L(,))碼字，與各個校驗節(jié)點相連的變量節(jié)點其模2加的和應(yīng)為0。在二分圖中，d. d分別表示與變量節(jié)點和校驗節(jié)點相(4)每個變量節(jié)點計算后驗LLR,連的邊數(shù)，稱為該節(jié)點的次數(shù)(degree)。當(dāng)d、 d。為 常數(shù)LLR(q,)= 2 LLR(y,)+ LLR(p,),1eM()時，這樣的LDPC碼稱為正則(regular)碼，如上例所示。而當(dāng)二分圖中的變量節(jié)點的次數(shù)各不相同(校驗節(jié)點的次(5)進行硬判決LLR(q;)>=0判為1,否則判為0,數(shù)也有相應(yīng)的變動)時，稱為非正則irregular)碼。非正得x_ hat,如果mode(x_ _hat'H' ,2)=0則譯 碼成功。則碼通常用次數(shù)分布對(degree distribution pair)(1,p)來(6)否則重復(fù)步驟2~5,直到最大迭代次數(shù)，譯碼失描述:敗。硬判決譯碼，復(fù)雜度最低，性能也最差，BP算法譯技A(x)=金1p(p(x)=p;.x-分別碼復(fù)雜度在MP算法類中最高，性能也最好。1=2從二分圖中看，對于變量節(jié)點，與之相連的邊越多為變量節(jié)點和校驗節(jié)點的次數(shù)分布多項式; A(p,)表示越好，如果邊越多，那么它可以從更多的相鄰校驗節(jié)點得與次數(shù)為i的比特(校驗)節(jié)點相連的邊數(shù)在總邊數(shù)中所到更多的邊信息，這樣就可更準確的判斷出它的正確值;占的比例; d,px (dgx) 表示比特(校驗)節(jié)點中的但對校驗節(jié)點來說，恰好相反，與之相連的邊越少越好。如果與校驗節(jié)點相連的邊越少，那么它就可以給相鄰的信最大次數(shù)。息節(jié)點發(fā)送更有效的校驗信息。對于兩種相矛盾的要求,LDPC碼的性能與采用的譯碼算法密切相關(guān)，非正則碼顯然能較正則碼可更好的實現(xiàn)兩者的均衡。Gallager在提出LDPC碼"時給出了兩種迭代譯碼算法:但是并非所有的非正則碼性能都優(yōu)于正則碼，優(yōu)化硬判決和概率譯碼。后者雖有好的性能，但太復(fù)雜。選擇節(jié)點的次數(shù)分布(.p),可以提高LDPC碼的性能。Message Passing算法是一種工I作在圖論基礎(chǔ)上的譯碼算法，由于在算法的運行過程中，可靠性信息在二分圖的變3次數(shù)分布對的優(yōu)化設(shè)計量節(jié)點和校驗節(jié)點之間來回的傳遞，因此稱為MessageGallager在最初的文獻"中，在BSC(二進制對稱信Passing算法。它是-一個算法類，如果相互間傳送的是硬道)上分析了(3,k)正則碼進行硬判決譯碼的性能;判決信息，算法即成為Gallager提出的硬判決譯碼，如Richardson等人在文獻[4]中分析了非正則碼(3,2)在BEC果傳遞的消息是連續(xù)的軟判決信息，就等價于BP(Belief(二元刪除信道)上用MP (Message Passing)算法譯Propagation)算法。碼時的性能，發(fā)現(xiàn)LDPC碼存在一種“門限BP譯碼算法過程如下所示:(Th中國煤化工于某一門限值時，2或信MHCNMHG,在碼長足夠大的(1)初始化: LLR(p;)==y; (AWGN信道).情況下，碼集中的幾乎任何一種碼的誤碼率都能隨著迭代σ2009.8廣東通信技術(shù)》技術(shù)交流譯碼次數(shù)的增加而遞減趨近于0;反之，誤碼率將始終大P= P 8 a[r"([(P_))(2)于某一正的常數(shù)。對應(yīng)某一碼集的門限值也可看成碼容量其中，r. r-I 分別表示定義在兩種消息域上的概(Capacity)。具有良好特征的二分圖，其對應(yīng)的LDPC率密度函數(shù)域之間的變換和反變換。碼集有高譯碼噪聲門限，也具有較大的碼容量。(2)近似Density Evolution相關(guān)研究表明這個信噪比門限取決于LDPC碼的次數(shù)分布。這方面研究往往結(jié)合次數(shù)分布優(yōu)化技術(shù)和密度演進用密度演進(DE)計算門限，優(yōu)化次數(shù)分布是困難(Density Evolution)技術(shù)來搜索具有高譯碼噪聲門限的的，復(fù)雜度很高，相應(yīng)的就有了近似DE算法。近似算法的基本思路是將PDF迭代的多維計算問題轉(zhuǎn)化為僅僅次數(shù)分布對。計算一個參數(shù)(通常是高斯函數(shù))迭代的-維計算問(1)基于BP算法的密度演進密度演進(DE: Density Evolution)分 析的思想是由題。幾種常見的近似DE方案:高斯近似(GA-GaussianRichardson等'在研究MP(Message Passing)譯碼算法時Approximation),基于EXIT圖的方法，Semi高斯近似。Sae-Young Chung等間提出對概率密度函數(shù)進行高提出的:通過考察譯碼消息的概率密度函數(shù)(PDF一Probability Density Function)在譯碼迭代中的演進情斯近似的方法，根據(jù)譯碼消息的獨立性條件和大數(shù)定理,況，分析譯碼算法的收斂情況。變量節(jié)點次數(shù)d,較大時，從變量節(jié)點發(fā)往校驗節(jié)點的譯在DE分析中，通常需要滿足對稱性(symmetry)的條碼消息v近似呈高斯分布;從校驗節(jié)點發(fā)往變量節(jié)點的譯件。Richardson等人“已證明，在對稱性條件下， 譯碼差碼消息u則不像高斯分布，尤其是當(dāng)它的均值靠近0的時錯概率具有條件獨立性(Conditional Independence)，候。但是研究發(fā)現(xiàn)，假設(shè)譯碼消息V. u為高斯分布的隨即，譯碼差錯率與發(fā)送的碼字無關(guān)。這樣，就可以假設(shè)發(fā)機變量不僅不影響對BP算法的密度演進分析，還可以簡送的是全1碼字來計算DE.化密度演進的分析過程。而由對稱性條件，消息的均值與在譯碼算法的消息獨立性條件下，譯碼中的消息求方差之間存在著聯(lián)系: σ°=2m° 因此，在GA分析中，和運算，其密度演進對應(yīng)譯碼消息的PDF的卷積運算。因?qū)?yīng)的密度演進就進-步簡化為一個參數(shù)(均值)的運此，為簡化DE分析，Richardson等'45)引入另一種消息形算。迭代公式如下所示:式，并定義了兩種消息域上的映射Y:[-∞,+∞]→GF(2)x[0,+∞],使得BP算法的譯碼(4)迭代都為消息求和運算:其中，l為迭代次數(shù)，m。if(1=0)(u-x)戶m"={mo+ 2 m") if(l≥1)qx)={-底' [uanh exp(-4-)du (x>0)c'eCct(x=0)m")=y"[ Er(m!=")](1)中(x)函數(shù)的直接計算很復(fù)雜，可以作如下近似計v'e叫算:其中，l為迭代次數(shù)，m(為從變量節(jié)點v發(fā)往校驗對較小的x，如x <10，中(x)~e*+B, 其中節(jié)點C的譯碼消息，m"表示從校驗節(jié)點發(fā)往變量節(jié)點的a=-0.4527，β=0.0218， Y= 0.86;中國煤化工)取上.下界的平均譯碼消息，mg為初始消息。 若令P. Q、P分別表MHCNMHG值，示它們的PDF.則話e(-元)LDPC碼的優(yōu)化設(shè)計這一簡化不但使得求取LDPC碼的門限值的計算變得似，EXIT圖等方法得其門限值。簡單，而且可以更直觀地理解譯碼器的工作原理。另外,若采用GA算法計算門限值，則評價次數(shù)分布對高斯近似還方便了在AWGN信道上設(shè)計非正則碼的次數(shù)分(h,p)時。先給定- -個較小的信道參數(shù)(高斯信道的σ參布對。數(shù))，再將對應(yīng)的初始消息的均值一代入式(4)中，EXIT ( Extrinsic Information Transfer)圖是由S. tenBrink提出的一種用迭代譯碼器之間傳輸?shù)耐庑畔肀碚鬟M行迭代。若在給定的最大迭代譯碼次數(shù)內(nèi)，譯碼的錯誤迭代譯碼中收斂行為的分析工具。s. ten Brink等人”將消息概率小于之前設(shè)定的目標值E(足夠小，接近于0),則EXIT圖技術(shù)引入到LDPC碼譯碼分析中，即把LDPC碼認為該信道參數(shù)小于門限值，并按某步長增大信道參數(shù)σ的譯碼過程可以看作是變量節(jié)點譯碼器和校驗節(jié)點譯碼器重新代入計算;若新的信道參數(shù)使得迭代始終無法收之間外信息的迭代，用EXIT圖跟蹤譯碼器之間的互信息斂，即譯碼的錯誤消息概率不能達到目標值，則認為超出傳遞來估計LDPC碼和積譯碼算法的收斂性?；贓XIT了門限值，并取增大前的信道參數(shù)σ作為該次數(shù)分布對圖的方法可以看作是DE方法的一種簡化方案，它的優(yōu)點(.ρ)的門限值σ°。在于:在迭代的過程中跟蹤的是互信息的值，與DE方法③優(yōu)化算法中的概率密度函數(shù). GA方法中的均值等相比較，具有更搜索具有高譯碼噪聲門限的次數(shù)分布對是一種復(fù)雜好的魯棒性。其對碼的性能分析和估計比高斯近似方法更的非線性優(yōu)化技術(shù)。主要有局部優(yōu)化和全局優(yōu)化的兩種不準確，與密度演進方法相比計算復(fù)雜度也小得多。同的方法。局部優(yōu)化的方法利用局部優(yōu)化的結(jié)果進行試探技(3)優(yōu)化設(shè)計過程術(shù)性的搜索.以減小搜索空間。全局優(yōu)化的方法從整體上進LDPC碼的門限是使得所有譯碼迭代收斂或譯碼消息行優(yōu)化。的密度演進收斂的信道參數(shù)的上限。它表明了正則或非正采用DE. GA可以得出具體次數(shù)分布對下LDPC碼的則LDPC碼能夠達到的碼容量的上界，反映了LDPC碼能門限值，結(jié)合優(yōu)化算法可以優(yōu)化設(shè)計次數(shù)分布對。優(yōu)化算夠容忍的信道環(huán)境的惡劣程度.因而是評價LDPC碼的重法可以采用差分進化，PSO算法及各種改進算法等。要標準。④目前次數(shù)分布對尋找的成果而優(yōu)化設(shè)計LDPC碼，就是在次數(shù)分布的解空間中,對于二元輸入的BI-AWGN信道，已經(jīng)找到了門限值搜索具有高門限值的LDPC碼。與香農(nóng)限僅僅相差0.0045dB的次數(shù)分布對，而仿真表明.①解空間在碼長為10'. R= 1/2時，它的性能曲線距離香農(nóng)限只差次數(shù)分布多項式中的系數(shù)是待優(yōu)化變量，相互之間0.04 dB*。J.Hou等鬥研究了平坦瑞利衰落信道中LDPC碼存在碼率約束Zp,/i=(1-R)22/j.歸一化約束的優(yōu)化和性能分析，證明優(yōu)化了的非正則碼(碼長為3072)性能優(yōu)于相應(yīng)的Turbo碼。h=1--三不. p:=1-Ep同時校驗節(jié)點的次數(shù)4結(jié)束語分布具有集中形式: p(x)=ρ.x*-'+(1-ρ)x。 去除通過LDPC碼的碼結(jié)構(gòu)優(yōu)化設(shè)計，可以獲得性能盡可次數(shù)分布對中的冗余變量后得到待優(yōu)化的目標向量能好的LDPC碼。LDPC碼結(jié)構(gòu)設(shè)計的研究對提高碼的性能和進(...).其中獨立變量數(shù)為L=d, -2.中國煤化工要的意義。本文介②計算LDPC碼的門限值紹了密TYCHCNMHG點及LDPC碼優(yōu)化設(shè)給定次數(shù)分布對時，可以通過密度演進，高斯近計的過程，后面可將其他的優(yōu)化技不與LDPC碼性能分析方法相結(jié)合.如PSO算法及各種改進算法和DE技術(shù)或者EXIT692009.8廣東通信技術(shù)》技術(shù)交流圍方法進行結(jié)合，尋找一種兼顧性能和復(fù)雜度的有效搜索3 T.J.Richardson, M.A.Shokrollahi and R.L.Urbanke. Design方法，是碼結(jié)構(gòu)優(yōu)化設(shè)計的一-個可行的研究方向。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頁)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年，是中國電信股份有元，國內(nèi)外公開發(fā)行。國際標準刊號: ISSN 1006- 6403;限公司廣東分公司主管，廣東省通信學(xué)會和廣東省電信情報國內(nèi)統(tǒng)-刊號: CN44- -1221/TN.中心站聯(lián)合主辦的廣東省唯- -的綜合性通信技術(shù)刊物。全國各地郵局均可訂閱。國內(nèi)郵發(fā)代號: 46-245.《廣東通信技術(shù)》主要反映廣東通信建設(shè)的最新成就中國煤化工里訂閱，具體事宜與和交流引進、吸收國內(nèi)外先進通信技術(shù)的經(jīng)驗，介紹國內(nèi)外最新通信技術(shù)的發(fā)展及趨勢等。MYHCNMHG《廣東通信技術(shù)》月刊，大16開，全年定價120.00聯(lián)系人:方小姐70|