非規(guī)則LDPC碼的局部消環(huán)

1、非規(guī)則非規(guī)則 LDPCLDPC 碼的局部消環(huán)碼的局部消環(huán)論文導讀：再保證整個 LDPC 碼的環(huán)最大化。個圖的圍長定義為。該度分布下變量節(jié)點的度數(shù)為 2、3 和 9。為了討論方便將上述方法稱之為局部消環(huán)。圍長，非規(guī)則 LDPC 碼的局部消環(huán)。關(guān)鍵詞：LDPC 碼，圍長，度分布，局部消環(huán)1 引言1962 年，Gallager 在他的博士論文1中提出了低密度奇偶校驗碼（LDPC）。近年來，LDPC 碼由于其接近香農(nóng)極限的高性能而被廣泛的研究2-4。一個 LDPC 碼可由一個二進制的校驗矩陣 H 來描述。矩陣 H 的每一行與每一列中 1 的個數(shù)是固定的，且其相比于矩陣中 0 的個數(shù)是很少的。矩陣 H

2、的每一列對應(yīng)著所接收到的碼字 x 的每一位，每一行對應(yīng)這些信息位的一個約束校驗。因此，一個正確的碼字必須滿足如下等式：(1)矩陣 H 同樣可以方便地用一個 Tanner 圖來描述。H 的每一行，每一列都代表著 tanner 圖中的一個節(jié)點。列對應(yīng)的節(jié)點稱其為變量節(jié)點，行對應(yīng)的節(jié)點稱其為校驗節(jié)點。H 中的 1 代表這個 1 所在行對應(yīng)的節(jié)點和所在列對應(yīng)的節(jié)點之間有一條邊。顯然，矩陣 H 所對應(yīng)的 Tanner 圖是一個二部圖。因為按定義只有變量節(jié)點和校驗節(jié)點之間存在邊，變量節(jié)點與變量節(jié)點之間，校驗節(jié)點與校驗節(jié)點之間不存在邊。在二部圖中，偶數(shù)長的路徑的起點和終點必定同時為變量節(jié)點或校驗節(jié)點，奇數(shù)長

3、的路徑的起點和終點必定一個屬于變量節(jié)點，另一個屬于校驗節(jié)點。環(huán)定義為一個沒有重復(fù)節(jié)點的封閉路徑，其必為偶數(shù)長。任意兩個節(jié)點之間至多有一條邊。因此，最短環(huán)的長度為 4。環(huán)長度為 4的環(huán)稱其為 4-環(huán)，長度為 n 的環(huán)稱其為 n-環(huán)。一個圖的圍長定義為該圖中最小環(huán)的長度。下圖為一個碼長為 4.的 LDPC 碼的校驗矩陣及其對應(yīng)的 tanner 圖。圖 1 校驗矩陣及其對應(yīng)的 Tanner 圖普遍認為，度數(shù)高的節(jié)點由于其有更多的路徑來更新信息，因此其抵抗信道中的錯誤的能力相比于度數(shù)低的節(jié)點要強。因此首先保證度數(shù)低的節(jié)點之間的環(huán)最大化，再保證整個 LDPC 碼的環(huán)最大化。通過這個步驟構(gòu)造出的 LDPC

4、 碼相比于只保證整個 LDPC 碼的環(huán)最大化所得到的 LDPC 碼性能方面更優(yōu)。本文研究了一種通過交換邊首先保證度數(shù)低的節(jié)點之間的環(huán)的長度最大化，然后同樣也是通過交換邊，在不改變度數(shù)低的節(jié)點之間分布情況的前提下使整個 LDPC 碼的環(huán)的長度最大化。仿真結(jié)果表明該過程能改善 LDPC 碼的性能。為了討論方便將上述方法稱之為局部消環(huán)。本文安排如下：第二節(jié)介紹了 LDPC 碼與其對應(yīng)的鄰接矩陣，并且闡述了如何通過鄰接矩陣找到給定長度的環(huán)。第三節(jié)基于鄰接矩陣，討論了局部消環(huán)的具體實現(xiàn)方法。第四節(jié)給出了仿真結(jié)果，并比較了僅僅保證整個 LDPC 碼的環(huán)長的最大化和局部消環(huán)得到的 LDPC 碼的性能比較。結(jié)

5、論在第五節(jié)，同時包含了實現(xiàn)局部消環(huán)的算法。2 環(huán)的檢測對于一個給定的圖，將其節(jié)點標示為。定義該圖的鄰接矩陣 A如下：通過上面的定義，對于一個 LDPC 碼自然排序其節(jié)點所對應(yīng)的鄰接矩陣 A 如下：（2）其中 H 正好為該 LDPC 碼對應(yīng)的校驗矩陣?？紤] A 的平方：（3）的元素可由如下公式計算：（4）該式子正好是節(jié)點和之間長度為 2 的路徑的個數(shù)。因為當時，則有兩條邊連接,和。定理 1：中(i,j)項的值等于節(jié)點到節(jié)點長度為 n 的路徑個數(shù)。定理 2：在一個給定的圍長為 n 的圖中，節(jié)點和位于某個 n 環(huán)上正好相對的位置（到的距離為 n/2）當且僅當：(5)（6）3 環(huán)的消去及局部消環(huán)如果某

6、一 LDPC 碼對應(yīng)的 Tanner 圖需要消去的環(huán)被檢測到，接下來要做的就是從該圖中消去此環(huán)。通過交換節(jié)點之間的邊可以消去檢測到的環(huán)，但同時必須保證沒有新的同等長度或更小長度的環(huán)產(chǎn)生。通過交換節(jié)點之間的邊消去環(huán)的另一個好處是并沒有改變圖中節(jié)點的度分布。首先，需要一條在環(huán)上的邊。定理 2 中檢測環(huán)的方法給出了環(huán)中相對的兩個節(jié)點 vi 和 vj。免費論文，圍長。免費論文，圍長。如果節(jié)點 vk 為環(huán)上與 vj相鄰的節(jié)點，則其與 vi 的距離必為 n/2-1。免費論文，圍長。免費論文，圍長。因此，有如下式子可以得到 vk：（7）這樣就得到環(huán)上的一條邊 e=vjvk。免費論文，圍長。接下來需要尋找圖中的一條邊與該邊交換，交換后破壞了此環(huán)的同時，沒有生成同等長度的和更小長度的環(huán)。定義 Ce 為所有與邊 e 長度大于等于 n-1 長的節(jié)點的集合。則該集合包含的節(jié)點是滿足式子（8）的節(jié)點的集合。隨機取一條兩個節(jié)點都在 Ce 中的圖中的一條邊 e。如果不存在這樣的邊，則邊 e 不能通過交換節(jié)點之間