無線通信報(bào)告ldpc碼的線性規(guī)劃譯碼算法(存儲版)
【正文】 3212895 信息與通信工程專業(yè)（電 A） 9 根據(jù)圖 所示抽象多面體，對 LP 譯碼進(jìn)行分析。 LP譯碼算法的這個(gè)特性稱為最大似然保證特性 。保持目標(biāo)函數(shù)不變，以碼字多面體的交集 Q 作為可行多面體，得到簡潔形式的不等式約束的 LP 譯碼模型如下 minimize:1n iii f??? subject to: 0 1,if i I? ? ? ? ( ( ) \ ) ( 1 ) 1 , ,i i ji N j V i Vf f V D j J??? ? ? ? ? ? ? ? ? 從上節(jié)中可知，多面體 Ω 與多面體 Q 在變量 f 空間上的投影是等價(jià)的，且目標(biāo)函數(shù)只跟變量 f 有關(guān)，因此，求解 ()式得到的最優(yōu)解 f39。12( , ,..., )nf f f f? ，將式()中的 S 換成 V,Ej 換成 Dj，如果碼比特值滿足更換后的等式，就稱該序列具有校驗(yàn)節(jié)點(diǎn) j 的 V 結(jié)構(gòu)。令 Q=∩ jQj,那么 Q 在變量 f 定義的子空間上的投影 Pr ( ) Pr ( ) Pr ( ) ( )j j j j j jo j Q o j Q o Q Q? ? ? ? ? ? ? ? （ ）就是本地碼字多面體的交集Ω。 39。為了使約束條件更容易被表達(dá)，引入輔助LP 變量，這些輔助變量對代價(jià)函數(shù)均不 產(chǎn)生影響。 對于一個(gè)給定的碼 C，定義其碼字多面體為碼 C 中所有有效碼字的凸包，記為 Poly(C)，即 ( ) { : 0 , 1 }y y yy C y CP oly C y? ? ???? ? ? ? ? （ ） 從式 ()知 碼字多面體中每一點(diǎn)都是碼字的凸組合，且碼字多面體的頂點(diǎn)與碼字一一對應(yīng)。如果 i? 0，說明信道輸入端發(fā)送 1 的可能性大于發(fā)送 0 的可能性 。在很多問題中，只需簡單的對每個(gè)值進(jìn)行舍入處理，使其變成整數(shù)，就可以得到 ILP 的最優(yōu)解。 四 線性規(guī)劃譯碼算法 （一） 線性規(guī)劃以及線性規(guī)劃松弛 線性規(guī)劃是指在一個(gè)線性目標(biāo)函數(shù)下，求解一系列線性約束式集合的問題，即在由一系列線性約束式形成的可行域中尋找線性目標(biāo)函數(shù)的最優(yōu)值，是較簡單的一種凸優(yōu)化問題。推廣和積 (SumProduct, SP)算法和變異算法，如最小和 (Minimum Sum, MS)譯碼算法 。 c0c1c2c3v0v1v2v3v4v51 1 0 1 0 00 0 1 1 0 11 0 1 0 1 00 1 0 0 1 1H ????????? 圖 22 校驗(yàn)矩陣 H和 對應(yīng)的 Tanner 圖 圖 22 展現(xiàn) 了一個(gè)校驗(yàn)矩陣和所對應(yīng)的 Tanner 圖。 LDPC 碼的校驗(yàn)矩陣是 m 行n 列的， 一般 LDPC 碼的碼字 c 就是與其對應(yīng)的校驗(yàn)矩陣 H 的零空間，滿足如下方程： cHT=0 () 1 1 1 0 0 0 0 0 0 00 0 0 0 1 1 1 0 0 01 0 0 0 0 0 0 1 1 00 0 1 1 0 0 0 0 0 10 1 0 0 0 1 0 0 1 0H????????? 圖 21 n=10 的 二進(jìn)制 LDPC 碼校驗(yàn)矩陣 圖 ２ 1 顯示 的是一個(gè)碼長為 10 的 LDPC 碼校驗(yàn)矩陣。對于LDPC 碼，線性規(guī)劃問題中的約束式的數(shù)量是隨著校驗(yàn)節(jié)點(diǎn)度數(shù)的增加而呈指數(shù)增加，因此研究大規(guī)模的線性規(guī)劃問題的求解問題具有重要的意義。同時(shí)，當(dāng) Tanner 圖中存在環(huán)時(shí)，可以通過添加限制條件，改進(jìn) LP 譯碼的性能。 對于 長度為 k 的信息序列 u 就可以使用生成矩陣 G生成長度為 n 的碼字 c，用公式表示如下： c=uG () 而對于 LDPC 碼 ， 我們首先得到是 它 的校驗(yàn)矩陣 H， 要想完成編碼過程必須得進(jìn)行一些矩陣變換從校驗(yàn)矩陣 H 得到生成矩陣 G，通常 所用的 方法為高斯消元法 ， 現(xiàn)將 校驗(yàn) 矩陣 H 進(jìn)行格式變化： H39。很多譯碼算法都依賴于因子圖的結(jié)構(gòu)特性，采用這些譯碼算法時(shí)，因子圖的多樣性就顯得 尤為重要。并且，如果算法收斂，收斂點(diǎn)也不一定全是有意義的。這是因?yàn)榫€性規(guī)劃的可行域是連續(xù)的，求解 LP 問題所得最優(yōu)解可能不是整數(shù)，從而可能導(dǎo)致解無意義。 （二） 等價(jià) ILP 問題 ILP 問題是指在有限個(gè)整數(shù)離散點(diǎn)組成的可行域中，找到使線性代價(jià)函 數(shù)最小的可行點(diǎn)的問題，常見形式如下： minimize: aTx subject to: x?Zn 其中 x 表示一個(gè) n 維的變量 ,a 表示系數(shù)向量 , aTx 稱為代價(jià)函數(shù)， minimize:aTx 稱為目標(biāo)函數(shù)， Zn 表示 n 維整數(shù)域。發(fā)送符號的最大似然比 依賴于信道特性，在不同信道傳輸下，最（ ） （ ） （ ） 周珍珠 13212895 信息與通信工程專業(yè)（電 A） 5 大似然比是不一樣的。因此 ML 譯碼可等價(jià)為如下式 ()所示的 LP 問題。取所有碼字多面體的交集，記（ ） （ ） 周珍珠 13212895 信息與通信工程專業(yè)（電 A） 6 為Ω，即Ω = ∩ jPoly(Cj)。 Ej中的每
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號-1