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

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