【正文】 r [ | 0 ]l n ( ) , { 1 , 2 , .. ., }?Pr [ | 1 ]iiiiiyy inyy? ???? 稱為發(fā)送符號(hào) yi 的最大似然比。 五 LP 譯碼 （一） 等式約束 LP 譯碼模型 基于線性碼的因子圖結(jié)構(gòu)，首先給出一個(gè)含輔助變量的 LP 松弛譯碼模型，對(duì) LP 問(wèn)題 ()做進(jìn)一步松弛。相應(yīng)的，變量節(jié)點(diǎn) i 的碼比特變量 fi 的值必須同由輔助變量決定的本地碼字的 S 結(jié)構(gòu)相一致 ,因此，對(duì)校驗(yàn)節(jié)點(diǎn) j 的鄰域變量節(jié)點(diǎn)的碼比特變量，以下約束條件成立 ,( ) , ji j si S S Ei N j f w??? ? ? ? （ ） 對(duì)任意一個(gè)校驗(yàn)節(jié)點(diǎn) j?J，定義多面體 Qj如下式（ ）： , , ,{( , ) : , 0 1 , , 0 1 , 1 , ( ) , }jjj i j j s j s i j sS E i S S EQ f w i I f S E w w i N j f w? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 2 |, , , |( , , ..., )Fjj S j S Sw w w w? 其中 w 為由校驗(yàn)節(jié)點(diǎn) j 所有輔助變量 wjs 組成的向量 。在 |N(j)|= 3 即三維情況下，從圖 可以看出，對(duì)給定校驗(yàn)節(jié)點(diǎn) j，同時(shí)滿足約束 ( )和 ( )的點(diǎn)的集合恰好對(duì)應(yīng)于校驗(yàn)節(jié)點(diǎn) j的碼字多面體Ω j。內(nèi)部的箭頭表示信道接收端接收 到的符號(hào)序列方向，均與信道噪聲有關(guān)，其中灰色箭頭表示無(wú)信道噪聲時(shí)接收到的符號(hào)序列方向，也是發(fā)送碼字 (y1)的方向，黑色箭頭 a, b, c, d 分別表示四種不同噪聲情況下的接收到的符號(hào)序列的方向。 碼長(zhǎng)為 96 的 LDPC 碼在 MS、 BP、 LP 三種譯碼算法下的誤碼率曲線如圖 。 4 ) LP 問(wèn)題有多個(gè)最優(yōu)解，此時(shí)， LP 譯碼輸出可能正確也可能不正確，我們保守地將這種情況視為譯碼失敗。 六 LP 譯碼性能分析 （一） 抽象可行多面體及誤碼率分析 如圖 所示為一個(gè)抽象的合適松弛多面體 P，雖然該多面體顯示為二維，但其頂點(diǎn)均可見(jiàn)。那么對(duì)任意校驗(yàn)節(jié)點(diǎn) j ? J，應(yīng)該滿足式( )所示不等式，即保證 f 遠(yuǎn)離于壞結(jié)構(gòu)。對(duì) Ej 中的每個(gè) S 定義一個(gè)輔助 LP 變量wjs，變量 wjs 可以看成碼字 以此 S 結(jié)構(gòu)滿足校驗(yàn)節(jié)點(diǎn) j 的標(biāo)識(shí) :當(dāng) wjs 為 1 時(shí)，表示碼字以此 S 結(jié)構(gòu)滿足校驗(yàn)節(jié)點(diǎn) j:當(dāng) wjs 為 0 時(shí)，表示碼字不以此 S 結(jié)構(gòu)滿足校驗(yàn)節(jié)點(diǎn) j。 minimize:1n iii f??? subject to: f ? Poly(C) 當(dāng)碼長(zhǎng) n 較大時(shí)，根據(jù)式 （ )對(duì)碼字多面體進(jìn)行描述是十分復(fù)雜的，對(duì)式 ()所示 LP 問(wèn)題的求解難度也隨之增大。 對(duì) ML 譯碼的目標(biāo)函數(shù)進(jìn)行如下變換 使得代價(jià)函數(shù)符合 ILP 中最小值優(yōu)化的特點(diǎn)。也就是說(shuō)對(duì)于迭代譯碼算法來(lái)講，盡管在大多數(shù)情況下都能收斂到最大似然碼字，依然缺乏理論根據(jù)，因此采用迭代譯碼時(shí)，譯碼性能難以分析。=Hp1H=[Imm PTmk] () Hp1是 一個(gè) mm 維 的變換矩陣， 假設(shè) 不存在矩陣 Hp， 則表明 H 矩陣非滿秩 ，這時(shí) 我們只需保留矩陣中最大數(shù)目的線性相關(guān)行即可得到 H39。 LDPC 碼的線性 規(guī)劃（ Linear Programming， LP）譯碼算法是將最大似然譯碼松馳成線性規(guī)劃問(wèn)題，譯碼碼字具有最大似然特性。在這個(gè)過(guò)程中 經(jīng)過(guò) 的 邊數(shù)被稱為環(huán)長(zhǎng)，最短的環(huán)的環(huán)長(zhǎng) 又被稱為圍長(zhǎng) (girth)。同時(shí)，當(dāng) Tanner 圖中存在環(huán)時(shí)，可以通過(guò)添加限制條件，改進(jìn) LP 譯碼的性能。 i? 取值的正負(fù)決定了信道輸入端符號(hào)取值的可能性。建模時(shí)，每個(gè)變量節(jié)點(diǎn) I ? I 對(duì)應(yīng)一個(gè)一維變量fi，每個(gè)校驗(yàn)節(jié)點(diǎn) j?J 對(duì)應(yīng)一簇線性約束，且這些線性約束只對(duì)該校驗(yàn)節(jié)點(diǎn)鄰域中的變量節(jié)點(diǎn)的碼比特值產(chǎn)生影響。 記多面體 Qj 在變量 f所定義的空間上 的投影為 Proj(Qj),且 Proj(Qj),就是校驗(yàn)節(jié)點(diǎn) j 的本地碼字多面體 Poly(Cj)記為Ω j。令所有校驗(yàn)節(jié)點(diǎn) j ? J 都滿足約束 ( )，便可得到所有碼字多面體的交集Ω =∩ jΩ j。內(nèi)部垂直于實(shí)心點(diǎn)之間的實(shí)連線的直線表示按經(jīng)典碼距譯碼的判決閉值，垂直于實(shí)心點(diǎn)與空心點(diǎn)之間的虛連線的直線表示按分?jǐn)?shù)距離譯碼的判決閉值。 周珍珠 13212895 信息與通信工程專業(yè)（電 A） 10 圖 碼長(zhǎng)為 96 的 LDPC 碼在 MS、 BP、 LP 三種譯碼算法下的誤碼率曲線 從圖 中可以看出，對(duì)具有中長(zhǎng)碼長(zhǎng)的 LDPC 碼，無(wú)論高信噪比還是低 信噪比時(shí)， LP 譯碼的性能都明顯好過(guò) MS 譯碼。*, * {0,1}nf ? 但 f*=y*，此時(shí) LP 譯碼輸出為 ML碼字，也是發(fā)送碼字，譯碼成功 。不過(guò)，隨著碼長(zhǎng) n 的增長(zhǎng)， LP 問(wèn)題的規(guī)模將會(huì)隨 n 呈指數(shù)增長(zhǎng)。 圖 給定校驗(yàn)節(jié)點(diǎn) j，當(dāng) |N(j)|=3時(shí)，鄰域變量節(jié)點(diǎn)對(duì)應(yīng)的二進(jìn)制序列分布圖 首先使碼比特變量 fi滿足式 ()所示箱限制條件 , 0 1ii I f? ? ?