無線通信報告ldpc碼的線性規(guī)劃譯碼算法-wenkub
2023-05-25 09:45:30 本頁面
【正文】 劃問題中的約束式的數量是隨著校驗節(jié)點度數的增加而呈指數增加，因此研究大規(guī)模的線性規(guī)劃問題的求解問題具有重要的意義。 所以 ， LP 譯碼 可以避免短環(huán)對譯碼性能的影響，提高性能 ，在誤碼性能與復雜上的保持平衡。 LDPC 碼的校驗矩陣是 m 行n 列的， 一般 LDPC 碼的碼字 c 就是與其對應的校驗矩陣 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 的 二進制 LDPC 碼校驗矩陣 圖 ２ 1 顯示 的是一個碼長為 10 的 LDPC 碼校驗矩陣。=Hp1H=[Imm PTmk] () Hp1是 一個 mm 維 的變換矩陣， 假設 不存在矩陣 Hp， 則表明 H 矩陣非滿秩 ，這時 我們只需保留矩陣中最大數目的線性相關行即可得到 H39。 c0c1c2c3v0v1v2v3v4v51 1 0 1 0 00 0 1 1 0 11 0 1 0 1 00 1 0 0 1 1H ????????? 圖 22 校驗矩陣 H和 對應的 Tanner 圖 圖 22 展現(xiàn) 了一個校驗矩陣和所對應的 Tanner 圖。 周珍珠 13212895 信息與通信工程專業(yè)（電 A） 3 三 LDPC 碼的譯碼 LDPC 碼的譯碼算法可分為硬判決譯碼算法和軟判決譯碼算法。推廣和積 (SumProduct, SP)算法和變異算法，如最小和 (Minimum Sum, MS)譯碼算法 。也就是說對于迭代譯碼算法來講，盡管在大多數情況下都能收斂到最大似然碼字，依然缺乏理論根據，因此采用迭代譯碼時，譯碼性能難以分析。 四 線性規(guī)劃譯碼算法 （一） 線性規(guī)劃以及線性規(guī)劃松弛 線性規(guī)劃是指在一個線性目標函數下，求解一系列線性約束式集合的問題，即在由一系列線性約束式形成的可行域中尋找線性目標函數的最優(yōu)值，是較簡單的一種凸優(yōu)化問題。這樣的優(yōu)化問題為整數線性規(guī)劃 (Integer Linear Programming, ILP)問題，其可行域由離散的整數點組成。在很多問題中，只需簡單的對每個值進行舍入處理，使其變成整數，就可以得到 ILP 的最優(yōu)解。 對 ML 譯碼的目標函數進行如下變換 使得代價函數符合 ILP 中最小值優(yōu)化的特點。如果 i? 0，說明信道輸入端發(fā)送 1 的可能性大于發(fā)送 0 的可能性 。 令 1 2 1 2( , , .. ., ) , ( , , .. ., ) ,TTnny y y y? ? ? ???可得 ML 譯碼的等價 ILP 問題如下式（ ）所示。 對于一個給定的碼 C，定義其碼字多面體為碼 C 中所有有效碼字的凸包，記為 Poly(C)，即 ( ) { : 0 , 1 }y y yy C y CP oly C y? ? ???? ? ? ? ? （ ） 從式 ()知 碼字多面體中每一點都是碼字的凸組合，且碼字多面體的頂點與碼字一一對應。 minimize:1n iii f??? subject to: f ? Poly(C) 當碼長 n 較大時，根據式 （ )對碼字多面體進行描述是十分復雜的，對式 ()所示 LP 問題的求解難度也隨之增大。為了使約束條件更容易被表達，引入輔助LP 變量，這些輔助變量對代價函數均不 產生影響。 用變量 f=(f1,f2,...,fn)表示碼比特序列，通過松弛使碼比特變量 fi滿足以下約束 , 0 1ii I f? ? ? ? （ ） 通過該約束，將變量 f 限制在一個 n 維的單位立方體中，因此式 ()稱為箱限制。 39。對 Ej 中的每個 S 定義一個輔助 LP 變量wjs，變量 wjs 可以看成碼字 以此 S 結構滿足校驗節(jié)點 j 的標識 :當 wjs 為 1 時，表示碼字以此 S 結構滿足校驗節(jié)點 j:當 wjs 為 0 時，表示碼字不以此 S 結構滿足校驗節(jié)點 j。令 Q=∩ jQj,那么 Q 在變量 f 定義的子空間上的投影 Pr ( ) Pr ( ) Pr ( ) ( )j j j j j jo j Q o j Q o Q Q? ? ? ? ? ? ? ? （ ）就是本地碼字多面體的交集Ω。給定一個二進制碼比特序列 39。12( , ,..., )nf f f f? ，將式()中的 S 換成 V,Ej 換成 Dj，如果碼比特值滿足更換后的等式，就稱該序列具有校驗節(jié)點 j 的 V 結構。那么對任意校驗節(jié)點 j ? J，應該滿足式( )所示不等式，即保證 f 遠離于壞結構。保持目標函數不變，以碼字多面體的交集 Q 作為可行多面體，得到簡潔形式的不等式約束的 LP 譯碼模型如下 minimize:1n iii f??? subject to: 0 1,if i I? ? ? ?
研究報告相關推薦
鄂ICP備17016276號-1