無線通信報告ldpc碼的線性規(guī)劃譯碼算法(已修改)
2025-06-07 09:45 本頁面
【正文】 組合最優(yōu)化課程論文 論文 題目 ： LDPC 碼的線性規(guī)劃 譯碼算法 班 級： 13 級電子 A 班 姓 名： 周珍珠 學 號： 13212895 任課老師： 婁定俊 周珍珠 13212895 信息與通信工程專業(yè)（電 A） 1 一 背景 低密度奇偶校驗（ Low Density Parity Check, LDPC） 碼 一類具有稀疏校驗矩陣的線性分組碼 ，也 是一種性能非常接近 Shannon 極限的信道編碼方案，具有很強的糾錯抗干擾能力。 LDPC 碼的線性 規(guī)劃（ Linear Programming， LP）譯碼算法是將最大似然譯碼松馳成線性規(guī)劃問題，譯碼碼字具有最大似然特性。對于LDPC 碼，線性規(guī)劃問題中的約束式的數量是隨著校驗節(jié)點度數的增加而呈指數增加，因此研究大規(guī)模的線性規(guī)劃問題的求解問題具有重要的意義。本文 對LDPC 碼的最大似然 (Maximum Likehood, ML)譯碼進行近似求解，建立了二進制分組碼的松弛規(guī)劃譯碼模型，從而提出了 LP 譯碼算法。作為 ML譯碼的估計，理論證明該算法具有最大似然保持特性，也就是，一旦最優(yōu)解為整數解，那么該解一定為最大似然 碼字。同時，當 Tanner 圖中存在環(huán)時，可以通過添加限制條件，改進 LP 譯碼的性能。 所以 ， LP 譯碼 可以避免短環(huán)對譯碼性能的影響，提高性能 ，在誤碼性能與復雜上的保持平衡。特別是對中短碼長的 LDPC 碼，利用線性規(guī)劃譯碼算法性能更突出。 二 LDPC 碼簡介 （一） LDPC 碼的 H 矩陣表示法 LDPC 碼 是一種 線性分組碼 ，它 是把長度為 k 的信息序列作為一個分組，然后按照一定規(guī)則將該信息序列映射為碼長為 n 的碼字， 可 表示為 (n,k)線性分組碼。對于 LDPC 碼，可以由它的校驗矩陣 H 確定。 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 碼校驗矩陣。 對于 LDPC 碼的碼率的計算則為 : R≥ k/n=(nm)/n () 當且僅當校驗矩陣 H 滿秩的時候，等號成立。 周珍珠 13212895 信息與通信工程專業(yè)（電 A） 2 對于 線性分組 通常給出的是 k 行 n 列的生成矩陣 G， 生成矩陣 G和校驗矩陣H 存在著 正交 的關系 ， 即 GHT=0 或 HGT=0。 對于 長度為 k 的信息序列 u 就可以使用生成矩陣 G生成長度為 n 的碼字 c，用公式表示如下： c=uG () 而對于 LDPC 碼 ， 我們首先得到是 它 的校驗矩陣 H， 要想完成編碼過程必須得進行一些矩陣變換從校驗矩陣 H 得到生成矩陣 G，通常 所用的 方法為高斯消元法 ， 現將 校驗 矩陣 H 進行格式變化： H39。=Hp1H=[Imm PTmk] () Hp1是 一個 mm 維 的變換矩陣， 假設 不存在矩陣 Hp， 則表明 H 矩陣非滿秩 ，這時 我們只需保留矩陣中最大數目的線性相關行即可得到 H39。矩陣 ， 繼而得到生成矩陣 G： G=[Pkm Ikk] () （二） LDPC 碼的 Tanner 圖表示 LDPC 碼除了可以使用校驗矩陣 H 進行 表示 之外 ，還可以 用雙 向圖模型 進行表示 ,而且 Tanner 圖與校驗矩陣是一一對應的。 Tanner 圖 包含三類元素：變量節(jié)點 (variable node)、校驗節(jié)點 (check node)和連接變量節(jié)點 與校驗節(jié)點的邊 (edge). 在 Tanner 圖中，還有一個 環(huán) (cycle)的 概念 ：從 某個節(jié)點出發(fā)經過一定的路徑又回到了該節(jié)點，除了此節(jié)點外，其余節(jié)點均只出現一次。在這個過程中 經過 的 邊數被稱為環(huán)長，最短的環(huán)的環(huán)長 又被稱為圍長 (girth)。 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 展現 了一個校驗矩陣和所對應的 Tanner 圖。 從 圖 22 可以看到 ， 校驗節(jié)點 的度數為 3， 變量節(jié)點的度數為 2， 虛線所示的就是 Tanner 圖中的一個環(huán) ，由六條 邊 組成 ， 故環(huán)長為 6。 注意到，因子圖和校驗矩陣的形式是一一對應的，對于一個給定的碼，其可能的校驗矩陣有很多個，相應地，可能的因子圖也有很多個。很多譯碼算法都依賴于因子圖的結構特性，采用這些譯碼算法時，因子圖的多樣性就顯得 尤為重要。 周珍珠 13212895 信息與通信工程專業(yè)（電 A） 3 三 LDPC
研究報告相關推薦
鄂ICP備17016276號-1