【正文】 使可行域變?yōu)榘锌尚姓麛?shù)點在內(nèi)的連 續(xù)域，那么這個 ILP 問題便被松弛成一個 LP 問題，可以通過高效的優(yōu)化算法來求解。作為 ML譯碼的估計，理論證明該算法具有最大似然保持特性，也就是，一旦最優(yōu)解為整數(shù)解，那么該解一定為最大似然碼字。軟判決算法性能較好，但實現(xiàn)復雜度太高。 Tanner 圖 包含三類元素：變量節(jié)點 (variable node)、校驗節(jié)點 (check node)和連接變量節(jié)點 與校驗節(jié)點的邊 (edge). 在 Tanner 圖中，還有一個 環(huán) (cycle)的 概念 ：從 某個節(jié)點出發(fā)經(jīng)過一定的路徑又回到了該節(jié)點，除了此節(jié)點外，其余節(jié)點均只出現(xiàn)一次。 二 LDPC 碼簡介 （一） LDPC 碼的 H 矩陣表示法 LDPC 碼 是一種 線性分組碼 ，它 是把長度為 k 的信息序列作為一個分組，然后按照一定規(guī)則將該信息序列映射為碼長為 n 的碼字， 可 表示為 (n,k)線性分組碼。 組合最優(yōu)化課程論文 論文 題目 ： LDPC 碼的線性規(guī)劃 譯碼算法 班 級： 13 級電子 A 班 姓 名： 周珍珠 學 號： 13212895 任課老師： 婁定俊 周珍珠 13212895 信息與通信工程專業(yè)（電 A） 1 一 背景 低密度奇偶校驗（ Low Density Parity Check, LDPC） 碼 一類具有稀疏校驗矩陣的線性分組碼 ，也 是一種性能非常接近 Shannon 極限的信道編碼方案，具有很強的糾錯抗干擾能力。特別是對中短碼長的 LDPC 碼，利用線性規(guī)劃譯碼算法性能更突出。矩陣 ， 繼而得到生成矩陣 G： G=[Pkm Ikk] () （二） LDPC 碼的 Tanner 圖表示 LDPC 碼除了可以使用校驗矩陣 H 進行 表示 之外 ，還可以 用雙 向圖模型 進行表示 ,而且 Tanner 圖與校驗矩陣是一一對應的。硬判決算法操作簡單，易于硬件實現(xiàn)，但是性能較差 。 20xx 年， 等人 ,利用線性規(guī)劃 (Linear Programming, LP)松弛，對LDPC 碼的最大似然 (Maximum Likehood, ML)譯碼進行近似求解，建立 了二進制分組碼的松弛規(guī)劃譯碼模型，從而提出了 LP 譯碼算法。 LP 問題可以通過優(yōu)化算法高效地求解， ILP 卻通常是一個 NPhard 問題。假設(shè)信道具有離散無記憶的特性， 那么1? ?Pr [ | ] Pr [ | ]n iiiy y y y???，式（ ）可等價為 *11? ?a r g m in l n ( P r [ | ] ) a r g m in l n ( P r [ | ] )nni i i iy C i y C iy y y y y? ? ? ?? ? ? ? ? ? （ ） 此時 ML譯碼已變?yōu)樽钚』瘑栴}，但仍然是非線性的。這樣，就可通過求解 ILP 問題來獲取 ML 碼字。因此，希望找到碼字多面體的松弛或近似多面體，使其不僅包含所有的碼字，而且具有確切的易于表達的可實現(xiàn)的描述形式。 其次，考慮任意校驗節(jié)點 j?J，將校驗節(jié)點 j 鄰域 N(j)中勢為偶數(shù)的子集 (包括空集 ?)記為 S，所有 S 的集合記為 Ej。由于 wjs 為輔助 LP 變量，將其松弛后應同碼比特變量一樣，滿足約束 , 0 1j j sS E w? ? ? ? （ ） 此外，對給定的校驗節(jié)點 j， Ej中的元素 S 與 j 的本地碼字按一一對 應的關(guān)系滿足式 ()，因此對校驗節(jié)點 j 的輔助變量應滿足以下約束條件 ： , 1j jsSEw??? （ ） 使得校驗節(jié)點 j 的本地碼字以某個特定的 S 結(jié)構(gòu)滿足該校驗節(jié)點。 39。 ( ( ) \ ), ( 1 ) 1j i ii N j V i VV D f f??? ? ? ? ? ? ? （ ）稱不等式 ( )為奇偶校驗不等式。 LP 譯碼步驟如下 :求解 LP 問題，得最優(yōu)解 (f*,w*)或 f*。其中相連的虛線及其內(nèi)部表示該合適多面體 P，圓點表示多面體頂點，其中實心點表示整數(shù)頂點 (與碼字一一對應 )，空心點表示分數(shù)頂點，相連的實線及其內(nèi)部表示碼字多面體。不過由于LP 譯碼結(jié)果為分數(shù)，譯碼錯誤是可檢測，而采用 ML 譯碼輸出依然是最大似然譯碼，雖然譯碼錯誤，但不可檢測 。 用 Pr[err|y*]表示 LP 譯碼出錯的概率，那么有 Pr [ | * ] Pr [ ( , ) , * : * ] Pr [ , * : * ]i i i i i i i ii i i ie r r y f w Q f y f y f f y f y? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（二）仿真分析 在 BiAWGN 信道下，采用 LDPC 碼為信道編碼，對編碼后的碼字進行 BPSK調(diào)制，研究 LDPC 碼采用三種不同譯碼算法時的性能，其中 BP 譯碼的最大迭代次數(shù)為 100。