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

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

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

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

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

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

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