《無線通信報(bào)告LDPC碼的線性規(guī)劃譯碼算法.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《無線通信報(bào)告LDPC碼的線性規(guī)劃譯碼算法.doc（11頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

組合最優(yōu)化課程論文 論文題目：LDPC碼的線性規(guī)劃 譯碼算法 班 級(jí)： 13級(jí)電子A班 姓 名： 周珍珠 學(xué) 號(hào)： 13212895 任課老師： 婁定俊 一 背景 低密度奇偶校驗(yàn)（Low Density Parity Check, LDPC）碼一類具有稀疏校驗(yàn)矩陣的線性分組碼，也是一種性能非常接近Shannon極限的信道編碼方案，具有很強(qiáng)的糾錯(cuò)抗干擾能力。LDPC碼的線性規(guī)劃（Linear Programming，LP）譯碼算法是將最大似然譯碼松馳成線性規(guī)劃問題，譯碼碼字具有最大似然特性。對(duì)于LDPC碼，線性規(guī)劃問題中的約束式的數(shù)量是隨著校驗(yàn)節(jié)點(diǎn)度數(shù)的增加而呈指數(shù)增加，因此研究大規(guī)模的線性規(guī)劃問題的求解問題具有重要的意義。本文對(duì)LDPC碼的最大似然(Maximum Likehood, ML)譯碼進(jìn)行近似求解，建立了二進(jìn)制分組碼的松弛規(guī)劃譯碼模型，從而提出了LP譯碼算法。作為ML譯碼的估計(jì)，理論證明該算法具有最大似然保持特性，也就是，一旦最優(yōu)解為整數(shù)解，那么該解一定為最大似然碼字。同時(shí)，當(dāng)Tanner圖中存在環(huán)時(shí)，可以通過添加限制條件，改進(jìn)LP譯碼的性能。所以，LP譯碼可以避免短環(huán)對(duì)譯碼性能的影響，提高性能，在誤碼性能與復(fù)雜上的保持平衡。特別是對(duì)中短碼長的LDPC碼，利用線性規(guī)劃譯碼算法性能更突出。 二 LDPC碼簡介 （一）LDPC碼的H矩陣表示法 LDPC碼是一種線性分組碼，它是把長度為k的信息序列作為一個(gè)分組，然后按照一定規(guī)則將該信息序列映射為碼長為n的碼字，可表示為(n,k)線性分組碼。對(duì)于LDPC碼，可以由它的校驗(yàn)矩陣H確定。LDPC碼的校驗(yàn)矩陣是m行n列的，一般 LDPC碼的碼字c就是與其對(duì)應(yīng)的校驗(yàn)矩陣H的零空間，滿足如下方程： cHT=0 (2.1) 圖2-1 n=10的二進(jìn)制LDPC碼校驗(yàn)矩陣 圖２-1顯示的是一個(gè)碼長為10的LDPC碼校驗(yàn)矩陣。對(duì)于LDPC碼的碼率的計(jì)算則為: R≥k/n=(n-m)/n (2.2) 當(dāng)且僅當(dāng)校驗(yàn)矩陣H滿秩的時(shí)候，等號(hào)成立。 對(duì)于線性分組通常給出的是k行n列的生成矩陣G，生成矩陣G和校驗(yàn)矩陣H存在著正交的關(guān)系，即GHT=0或HGT=0。對(duì)于長度為k的信息序列u就可以使用生成矩陣G生成長度為n的碼字c，用公式表示如下： c=uG (2.3) 而對(duì)于LDPC碼，我們首先得到是它的校驗(yàn)矩陣H，要想完成編碼過程必須得進(jìn)行一些矩陣變換從校驗(yàn)矩陣H得到生成矩陣G，通常所用的方法為高斯消元法，現(xiàn)將校驗(yàn)矩陣H進(jìn)行格式變化： H=Hp-1H=[Imm PTmk] (2.4) Hp-1是一個(gè)mm維的變換矩陣，假設(shè)不存在矩陣Hp，則表明H矩陣非滿秩，這時(shí)我們只需保留矩陣中最大數(shù)目的線性相關(guān)行即可得到H矩陣，繼而得到生成矩陣G： G=[Pkm Ikk] (2.5) （二）LDPC碼的Tanner圖表示 LDPC碼除了可以使用校驗(yàn)矩陣H進(jìn)行表示之外，還可以用雙向圖模型進(jìn)行表示,而且Tanner圖與校驗(yàn)矩陣是一一對(duì)應(yīng)的。Tanner圖包含三類元素：變量節(jié)點(diǎn)(variable node)、校驗(yàn)節(jié)點(diǎn)(check node)和連接變量節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)的邊(edge). 在Tanner圖中，還有一個(gè)環(huán)(cycle)的概念：從某個(gè)節(jié)點(diǎn)出發(fā)經(jīng)過一定的路徑又回到了該節(jié)點(diǎn)，除了此節(jié)點(diǎn)外，其余節(jié)點(diǎn)均只出現(xiàn)一次。在這個(gè)過程中經(jīng)過的邊數(shù)被稱為環(huán)長，最短的環(huán)的環(huán)長又被稱為圍長(girth)。 圖2-2 校驗(yàn)矩陣H和對(duì)應(yīng)的Tanner圖 圖2-2展現(xiàn)了一個(gè)校驗(yàn)矩陣和所對(duì)應(yīng)的Tanner圖。從圖2-2可以看到，校驗(yàn)節(jié)點(diǎn)的度數(shù)為3，變量節(jié)點(diǎn)的度數(shù)為2，虛線所示的就是Tanner圖中的一個(gè)環(huán)，由六條邊組成，故環(huán)長為6。注意到，因子圖和校驗(yàn)矩陣的形式是一一對(duì)應(yīng)的，對(duì)于一個(gè)給定的碼，其可能的校驗(yàn)矩陣有很多個(gè)，相應(yīng)地，可能的因子圖也有很多個(gè)。很多譯碼算法都依賴于因子圖的結(jié)構(gòu)特性，采用這些譯碼算法時(shí)，因子圖的多樣性就顯得尤為重要。 三 LDPC碼的譯碼 LDPC碼的譯碼算法可分為硬判決譯碼算法和軟判決譯碼算法。硬判決算法操作簡單，易于硬件實(shí)現(xiàn)，但是性能較差;軟判決算法性能較好，但實(shí)現(xiàn)復(fù)雜度太高。在軟判決算法方面，以Gallager提出的消息傳遞算法(Message Passing Algorithm, MPA)為主，在因子圖上進(jìn)行消息迭代地傳播算法，也稱置信傳播(Belief Propagation, BP)算法。推廣和積(Sum-Product, SP)算法和變異算法，如最小和(Minimum Sum, MS)譯碼算法。軟判決迭代譯碼算法均具有譯碼速度快，譯碼性能優(yōu)良，復(fù)雜度較低的優(yōu)點(diǎn)。然而，迭代算法在許多情況下，比如當(dāng)Tanner圖中存在環(huán)時(shí)，并不能保證算法收斂;并且，如果算法收斂，收斂點(diǎn)也不一定全是有意義的。也就是說對(duì)于迭代譯碼算法來講，盡管在大多數(shù)情況下都能收斂到最大似然碼字，依然缺乏理論根據(jù)，因此采用迭代譯碼時(shí)，譯碼性能難以分析。 2005年，J.Feldman等人,利用線性規(guī)劃(Linear Programming, LP)松弛，對(duì)LDPC碼的最大似然(Maximum Likehood, ML)譯碼進(jìn)行近似求解，建立了二進(jìn)制分組碼的松弛規(guī)劃譯碼模型，從而提出了LP譯碼算法。作為ML譯碼的估計(jì)，理論證明該算法具有最大似然保持特性，也就是，一旦最優(yōu)解為整數(shù)解，那么該解一定為最大似然碼字。同時(shí)，當(dāng)Tanner圖中存在環(huán)時(shí)，可以通過添加限制條件，改進(jìn)LP譯碼的性能。 四 線性規(guī)劃譯碼算法 （一） 線性規(guī)劃以及線性規(guī)劃松弛 線性規(guī)劃是指在一個(gè)線性目標(biāo)函數(shù)下，求解一系列線性約束式集合的問題，即在由一系列線性約束式形成的可行域中尋找線性目標(biāo)函數(shù)的最優(yōu)值，是較簡單的一種凸優(yōu)化問題。許多簡單的優(yōu)化問題都可以利用線性規(guī)劃求解。 如果一個(gè)優(yōu)化問題的目標(biāo)函數(shù)是線性的，但當(dāng)且僅當(dāng)變量取整數(shù)時(shí)才有意義(比如變量代表候車廳的座椅數(shù)目)，那么采用線性規(guī)劃對(duì)此問題無法直接求解。這是因?yàn)榫€性規(guī)劃的可行域是連續(xù)的，求解LP問題所得最優(yōu)解可能不是整數(shù)，從而可能導(dǎo)致解無意義。這樣的優(yōu)化問題為整數(shù)線性規(guī)劃(Integer Linear Programming, ILP)問題，其可行域由離散的整數(shù)點(diǎn)組成。 LP問題可以通過優(yōu)化算法高效地求解，ILP卻通常是一個(gè)NP-hard問題。如果我們對(duì)ILP問題中限制變量為整數(shù)的條件進(jìn)行修改，使可行域變?yōu)榘锌尚姓麛?shù)點(diǎn)在內(nèi)的連續(xù)域，那么這個(gè)ILP問題便被松弛成一個(gè)LP問題，可以通過高效的優(yōu)化算法來求解。此時(shí)LP問題的解可能是ILP問題的最優(yōu)解，也可能不是，如果不是，可以采用現(xiàn)有方法修正結(jié)果使其有意義。在很多問題中，只需簡單的對(duì)每個(gè)值進(jìn)行舍入處理，使其變成整數(shù)，就可以得到ILP的最優(yōu)解。 這種通過轉(zhuǎn)化成LP問題來求解ILP問題的方法被稱為線性規(guī)劃松弛。線性規(guī)劃松弛廣泛應(yīng)用在計(jì)算科學(xué)和組合優(yōu)化上的近似求解算法中，用以解決各種難以求解的凸優(yōu)化問題。 （二）等價(jià)ILP問題 ILP問題是指在有限個(gè)整數(shù)離散點(diǎn)組成的可行域中，找到使線性代價(jià)函數(shù)最小的可行點(diǎn)的問題，常見形式如下： （4.1） minimize: aTx subject to: x?Zn 其中x表示一個(gè)n維的變量,a表示系數(shù)向量, aTx稱為代價(jià)函數(shù)，minimize:aTx 稱為目標(biāo)函數(shù)，Zn表示n維整數(shù)域。 （4.2） 對(duì)ML譯碼的目標(biāo)函數(shù)進(jìn)行如下變換 使得代價(jià)函數(shù)符合ILP中最小值優(yōu)化的特點(diǎn)。假設(shè)信道具有離散無記憶的特性， 那么，式（4.2）可等價(jià)為 （4.3） 此時(shí)ML譯碼已變?yōu)樽钚』瘑栴}，但仍然是非線性的。對(duì)代價(jià)函數(shù)整體進(jìn)行整數(shù)的加減乘除運(yùn)算并不會(huì)改變最優(yōu)解的值，在信道特性已知的情況下，為常數(shù)，將其加入到式（4.3）的代價(jià)函數(shù)中，有 （4.4） 稱為發(fā)送符號(hào)yi的最大似然比。取值的正負(fù)決定了信道輸入端符號(hào)取值的可能性。如果< 0，說明信道輸入端發(fā)送1的可能性大于發(fā)送0的可能性;反之，如果 > 0，則說明信道輸入端發(fā)送0的可能性大于發(fā)送1的可能性。用表示發(fā)送端碼字為y = (y1,y2,......, yk)的代價(jià)，而最大似然碼字就是碼C中具有最小代價(jià)的碼字。發(fā)送符號(hào)的最大似然比依賴于信道特性，在不同信道傳輸下，最大似然比是不一樣的。 令可得ML譯碼的等價(jià)ILP問題如下式（4.5）所示。這樣，就可通過求解ILP問題來獲取ML碼字。 （4.5） minimize: γTy subject to: y?C （三）等價(jià)LP松弛問題 ML譯碼雖然可等價(jià)為式(4.5)所示ILP譯碼形式，但求解算法依然具有較高的計(jì)算復(fù)雜度。通過LP松弛技術(shù)對(duì)式(4.5)進(jìn)行初級(jí)松弛處理，可以得到一個(gè)等價(jià)的LP松弛問題，從而可以利用有效的優(yōu)化算法進(jìn)行求解。 對(duì)于一個(gè)給定的碼C，定義其碼字多面體為碼C中所有有效碼字的凸包，記為Poly(C)，即 （4.6） 從式(4.6)知碼字多面體中每一點(diǎn)都是碼字的凸組合，且碼字多面體的頂點(diǎn)與碼字一一對(duì)應(yīng)。事實(shí)上，LP問題的最優(yōu)解總是在其可行多面體的頂點(diǎn)處取得。如果將碼C的碼字多面體Poly(C)作為線性規(guī)劃松弛后的可行域，那么在Poly(C)中求解使得代價(jià)函數(shù)最小的點(diǎn)等價(jià)于求解式(4.5)所示整數(shù)規(guī)劃問題。因此ML譯碼可等價(jià)為如下式(4.7)所示的LP問題。 （4.7） minimize: subject to: f ? Poly(C) 當(dāng)碼長n較大時(shí)，根據(jù)式（4.6)對(duì)碼字多面體進(jìn)行描述是十分復(fù)雜的，對(duì)式 (4.7)所示LP問題的求解難度也隨之增大。因此，希望找到碼字多面體的松弛或近似多面體，使其不僅包含所有的碼字，而且具有確切的易于表達(dá)的可實(shí)現(xiàn)的描述形式。 五 LP譯碼 （一）等式約束LP譯碼模型 基于線性碼的因子圖結(jié)構(gòu)，首先給出一個(gè)含輔助變量的LP松弛譯碼模型，對(duì)LP問題(4.7)做進(jìn)一步松弛。建模時(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)生影響。為了使約束條件更容易被表達(dá)，引入輔助LP變量，這些輔助變量對(duì)代價(jià)函數(shù)均不產(chǎn)生影響。 定義校驗(yàn)節(jié)點(diǎn)j的本地碼字為滿足該校驗(yàn)節(jié)點(diǎn)的任意二進(jìn)制向量，并稱校驗(yàn)節(jié)點(diǎn)j本地碼字的集合為校驗(yàn)節(jié)點(diǎn)j的本地碼，記為Cj。在因子圖中，每個(gè)校驗(yàn)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)本地碼，碼C是所有本地碼的交集即C=∩jCj.每個(gè)本地碼對(duì)應(yīng)一個(gè)本地碼字的凸包Poly(Cj),稱為本地碼字多面體。取所有碼字多面體的交集，記為Ω，即Ω= ∩jPoly(Cj)。用變量f=(f1,f2,...,fn)表示碼比特序列，通過松弛使碼比特變量fi滿足以下約束 （5.1） 通過該約束，將變量f限制在一個(gè)n維的單位立方體中，因此式(5.1)稱為箱限制。 其次，考慮任意校驗(yàn)節(jié)點(diǎn)j?J，將校驗(yàn)節(jié)點(diǎn)j鄰域N(j)中勢(shì)為偶數(shù)的子集(包括空集?)記為S，所有S的集合記為Ej。給定一個(gè)二進(jìn)制碼比特序列， 那么該二進(jìn)制序列f’就是校驗(yàn)節(jié)點(diǎn)j的本地碼字。Ej中的每個(gè)S對(duì)應(yīng)校驗(yàn)節(jié)點(diǎn)j的一個(gè)本地碼字。對(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。由于wjs為輔助LP變量，將其松弛后應(yīng)同碼比特變量一樣，滿足約束 （5.2）此外，對(duì)給定的校驗(yàn)節(jié)點(diǎn)j，Ej中的元素S與j的本地碼字按一一對(duì)應(yīng)的關(guān)系滿足式(5.2)，因此對(duì)校驗(yàn)節(jié)點(diǎn)j的輔助變量應(yīng)滿足以下約束條件： （5.3） 使得校驗(yàn)節(jié)點(diǎn)j的本地碼字以某個(gè)特定的S結(jié)構(gòu)滿足該校驗(yàn)節(jié)點(diǎn)。相應(yīng)的，變量節(jié)點(diǎn)i的碼比特變量fi的值必須同由輔助變量決定的本地碼字的S結(jié)構(gòu)相一致,因此，對(duì)校驗(yàn)節(jié)點(diǎn)j的鄰域變量節(jié)點(diǎn)的碼比特變量，以下約束條件成立 （5.4） 對(duì)任意一個(gè)校驗(yàn)節(jié)點(diǎn)j?J，定義多面體Qj如下式（5.5）： 其中w為由校驗(yàn)節(jié)點(diǎn)j所有輔助變量wjs組成的向量。 記多面體Qj在變量f所定義的空間上的投影為Proj(Qj),且Proj(Qj),就是校驗(yàn)節(jié)點(diǎn)j的本地碼字多面體Poly(Cj)記為Ωj。令Q=∩jQj,那么Q在變量f定義的子空間上的投影 （5.6）就是本地碼字多面體的交集Ω。目標(biāo)函數(shù)中不包含輔助變量，因此用Q=∩jQj代替本地碼字多面體的交集Ω作為可行多面體并不會(huì)改變求解結(jié)果。 那么含有輔助變量的LP松弛譯碼模型如式（5.7）所示： minimize:（5.7） subject to: (f，w) ? Q （二）不等式約束LP譯碼模型 如果能略去輔助變量，找到能直接描述多面體Ω的約束條件，可以得到一個(gè)更為簡潔的LP問題模型。對(duì)任意校驗(yàn)節(jié)點(diǎn)j?J，記其鄰域N(j)中勢(shì)為奇數(shù)的子集為V，所有V的集合為Dj。給定一個(gè)二進(jìn)制碼比特序列，將式(4.2)中的S換成V,Ej換成Dj，如果碼比特值滿足更換后的等式，就稱該序列具有校驗(yàn)節(jié)點(diǎn)j的V結(jié)構(gòu)。顯然，具有V結(jié)構(gòu)的碼比特序列都不能滿足相應(yīng)的校驗(yàn)節(jié)點(diǎn)。因此，稱V結(jié)構(gòu)為壞結(jié)構(gòu)。 圖5.1 給定校驗(yàn)節(jié)點(diǎn)j，當(dāng)|N(j)|=3時(shí)，鄰域變量節(jié)點(diǎn)對(duì)應(yīng)的二進(jìn)制序列分布圖 首先使碼比特變量fi滿足式(5.8)所示箱限制條件 (5.8) 其次，對(duì)一個(gè)碼字而言，必以某個(gè)特定的S結(jié)構(gòu)滿足給定校驗(yàn)節(jié)點(diǎn)j，但就N(j)中的變量節(jié)點(diǎn)對(duì)應(yīng)的二進(jìn)制序列部分而言，碼字與校驗(yàn)節(jié)點(diǎn)j的任意一個(gè)具有壞結(jié)構(gòu)的二進(jìn)制序列的L1距離至少為1。那么對(duì)任意校驗(yàn)節(jié)點(diǎn)j ? J，應(yīng)該滿足式(5.9 )所示不等式，即保證f遠(yuǎn)離于壞結(jié)構(gòu)。 （5.9）稱不等式(5.9 )為奇偶校驗(yàn)不等式。在|N(j)|= 3即三維情況下，從圖5.1可以看出，對(duì)給定校驗(yàn)節(jié)點(diǎn)j，同時(shí)滿足約束(5.8 )和(5.9 )的點(diǎn)的集合恰好對(duì)應(yīng)于校驗(yàn)節(jié)點(diǎn)j的碼字多面體Ωj。令所有校驗(yàn)節(jié)點(diǎn)j ? J都滿足約束(5.9 )，便可得到所有碼字多面體的交集Ω=∩jΩj。保持目標(biāo)函數(shù)不變，以碼字多面體的交集Q作為可行多面體，得到簡潔形式的不等式約束的LP譯碼模型如下 minimize:（5.10） subject to: 從上節(jié)中可知，多面體Ω與多面體Q在變量f空間上的投影是等價(jià)的，且目標(biāo)函數(shù)只跟變量f有關(guān)，因此，求解(5.10)式得到的最優(yōu)解f與求解(5.7)式得到的最優(yōu)解(f*，w*)在變量f空間上的投影是等價(jià)的。 定義5.1 :給定一個(gè)n維多面體P且P ? [0,1]n，如果多面體P的整數(shù)頂點(diǎn)恰與碼C中的碼字一一對(duì)應(yīng)，即P∩[0,1]n =C，就稱多面體P為一個(gè)合適多面體。 引理5.1 多面體Ω是一個(gè)合適多面體，即Ω∩[0,1]n =C。 LP譯碼的最優(yōu)解總是在可行多面體的頂點(diǎn)處取得，因此采用合適多面體進(jìn)行線性規(guī)劃譯碼問題求解時(shí)，一旦最優(yōu)解在整數(shù)頂點(diǎn)處取得，該整數(shù)頂點(diǎn)就是最大似然碼字。LP譯碼步驟如下:求解LP問題，得最優(yōu)解(f*,w*)或f*;如果f* ?[0,1]n ,輸出f*為最大似然碼字，否則，如果f*是分?jǐn)?shù)解，輸出譯碼錯(cuò)誤。因此，采用LP譯碼時(shí)，如果譯碼器輸出為一個(gè)碼字，那么保證為最大似然碼字。LP譯碼算法的這個(gè)特性稱為最大似然保證特性。所以采用LP譯碼比迭代譯碼更容易分析譯碼性能。盡管迭代譯碼性能優(yōu)良，但沒有任何一種迭代譯碼算法能從理論上證明其收斂值為ML碼字。不過，隨著碼長n的增長，LP問題的規(guī)模將會(huì)隨n呈指數(shù)增長。 六 LP譯碼性能分析 （一）抽象可行多面體及誤碼率分析 如圖6.1所示為一個(gè)抽象的合適松弛多面體P，雖然該多面體顯示為二維，但其頂點(diǎn)均可見。其中相連的虛線及其內(nèi)部表示該合適多面體P，圓點(diǎn)表示多面體頂點(diǎn)，其中實(shí)心點(diǎn)表示整數(shù)頂點(diǎn)(與碼字一一對(duì)應(yīng))，空心點(diǎn)表示分?jǐn)?shù)頂點(diǎn)，相連的實(shí)線及其內(nèi)部表示碼字多面體。內(nèi)部的箭頭表示信道接收端接收到的符號(hào)序列方向，均與信道噪聲有關(guān)，其中灰色箭頭表示無信道噪聲時(shí)接收到的符號(hào)序列方向，也是發(fā)送碼字(y1)的方向，黑色箭頭a, b, c, d分別表示四種不同噪聲情況下的接收到的符號(hào)序列的方向。內(nèi)部垂直于實(shí)心點(diǎn)之間的實(shí)連線的直線表示按經(jīng)典碼距譯碼的判決閉值，垂直于實(shí)心點(diǎn)與空心點(diǎn)之間的虛連線的直線表示按分?jǐn)?shù)距離譯碼的判決閉值。 圖6.1 給定碼C的一個(gè)合適多面體P的抽象表示 根據(jù)圖6.1所示抽象多面體，對(duì)LP譯碼進(jìn)行分析。 (a)噪聲很小時(shí)，信道輸出端接收符號(hào)序列指向?yàn)閍，無論按分?jǐn)?shù)距離判決還是經(jīng)典碼距判決，此時(shí)都應(yīng)將譯為發(fā)送碼字y1，LP譯碼輸出為ML碼字，且采用ML譯碼和LP譯碼都成功。 (b)噪聲變大一些時(shí)，信道輸出端接收符號(hào)序列指向?yàn)閎，如果采用ML譯碼，按最小距離判決，譯為發(fā)送碼字y1，而采用LP譯碼，按最小分?jǐn)?shù)距離判決，譯為f，則LP譯碼輸出為分?jǐn)?shù)解f，此時(shí)ML譯碼成功，LP譯碼失敗。 (c)噪聲繼續(xù)增大，信道輸出端接收符號(hào)序列指向?yàn)?。，如果采用ML譯碼，按最小距離判決，譯為碼字y2，如果采用LP譯碼，按最小分?jǐn)?shù)距離判決，依然譯為f , LP譯碼輸出為分?jǐn)?shù)解f，此時(shí)ML譯碼和LP譯碼均失敗。不過由于LP譯碼結(jié)果為分?jǐn)?shù)，譯碼錯(cuò)誤是可檢測(cè)，而采用ML譯碼輸出依然是最大似然譯碼，雖然譯碼錯(cuò)誤，但不可檢測(cè)。 (d)噪聲很大，信道輸出端接收符號(hào)序列指向?yàn)閐，如果采用ML譯碼，按最小距離判決，譯為碼字y2，如果采用LP譯碼，按最小分?jǐn)?shù)距離判決，也譯為y2，LP譯碼輸出為整數(shù)解，為最大似然碼字，此時(shí)ML譯碼和LP譯碼都出現(xiàn)譯碼錯(cuò)誤，并且錯(cuò)誤均不可檢測(cè)。 假設(shè)信道輸入端的發(fā)送碼字為y*?C，那么LP譯碼輸出可總結(jié)為以下四種情況: 1)LP問題有一個(gè)最優(yōu)解f* ,，此時(shí)LP譯碼輸出譯碼錯(cuò)誤，譯碼失敗。 2) LP問題有一個(gè)最優(yōu)解f*,但f*≠y*，此時(shí)LP譯碼輸出為ML碼字，但不是發(fā)送碼字，譯碼失敗。 3 ) LP問題有一個(gè)最優(yōu)解f*,但f*=y*，此時(shí)LP譯碼輸出為ML碼字，也是發(fā)送碼字，譯碼成功。 4 ) LP問題有多個(gè)最優(yōu)解，此時(shí)，LP譯碼輸出可能正確也可能不正確，我們保守地將這種情況視為譯碼失敗。 用Pr[err|y*]表示LP譯碼出錯(cuò)的概率，那么有 （二）仿真分析 在Bi-AWGN信道下，采用LDPC碼為信道編碼，對(duì)編碼后的碼字進(jìn)行BPSK調(diào)制，研究LDPC碼采用三種不同譯碼算法時(shí)的性能，其中BP譯碼的最大迭代次數(shù)為100。碼長為96的LDPC碼在MS、BP、LP三種譯碼算法下的誤碼率曲線如圖6.2。 圖6.2 碼長為96的LDPC碼在MS、BP、LP三種譯碼算法下的誤碼率曲線 從圖6.2中可以看出，對(duì)具有中長碼長的LDPC碼，無論高信噪比還是低信噪比時(shí)，LP譯碼的性能都明顯好過MS譯碼。當(dāng)BER=10-2時(shí)，這兩種方法的信道增益相差大約0.5dB。同BP譯碼相比，在低信噪比下，LP譯碼同BP譯碼具有相似的性能，隨著信噪比增大，BP譯碼的性能只略好于LP譯碼。當(dāng)BER=10-2時(shí)，這兩種方法的信道增益只相差大約0.05dB，且隨著信噪比的繼續(xù)增大，LP譯碼和BP譯碼有相交的趨勢(shì)。產(chǎn)生這種現(xiàn)象的原因之一是，中短碼長的LDPC碼的因子圖中常有環(huán)的存在，因而對(duì)其采用BP譯碼時(shí)可能不收斂，從而導(dǎo)致譯碼性能的下降，而采用LP譯碼卻可以避免這種情況的發(fā)生。 因此對(duì)碼長較長的LDPC碼，適合采用BP譯碼算法進(jìn)行譯碼，而對(duì)中短碼長的LDPC碼，采用線性規(guī)劃譯碼算法可以避免短環(huán)對(duì)譯碼性能的影響。