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

1、非規(guī)那么LDPC碼的局部消環(huán)論文導讀：再保證整個LDPC碼的環(huán)最大化。個圖的圍長定義為。該度分布下變量節(jié)點的度數(shù)為2、3和9。為了討論方便將上述方法稱之為局部消環(huán)。圍長，非規(guī)那么LDPC碼的局部消環(huán)。關鍵詞：LDPC碼，圍長，度分布，局部消環(huán)1 引言1962年，Gallager在他的博士論文【1】中提出了低密度奇偶校驗碼其中H正好為該LDPC碼對應的校驗矩陣?？紤]A的平方： 的元素可由如下公式計算： 該式子正好是節(jié)點和之間長度為2的路徑的個數(shù)。因為當時，那么有兩條邊連接,和。定理1：中(i,j)項的值等于節(jié)點到節(jié)點長度為n的路徑個數(shù)。定理2：在一個給定的圍長為n的圖中，節(jié)點和位于某個n環(huán)上正好

2、相對的位置3環(huán)的消去及局部消環(huán)如果某一LDPC碼對應的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： 這樣就得到環(huán)上的一條邊e=vjvk。免費論文，圍長。接下來需要尋找圖中

3、的一條邊與該邊交換，交換后破壞了此環(huán)的同時，沒有生成同等長度的和更小長度的環(huán)。定義Ce為所有與邊e長度大于等于n-1長的節(jié)點的集合。那么該集合包含的節(jié)點是滿足式子的節(jié)點的集合。隨機取一條兩個節(jié)點都在Ce中的圖中的一條邊e。如果不存在這樣的邊，那么邊e不能通過交換節(jié)點之間的邊從該環(huán)中去除而不產(chǎn)生新的長度相等或更小的環(huán)，那么需要選擇環(huán)中另外一條邊。假設e的兩個端點為vl和vm。圖2表示刪掉邊e和e，生成邊。 圖2 節(jié)點vj,vk,vl和vm之間邊的交換 定理 3：用邊e2和e2取代邊e和e將消去邊e和e所在的n環(huán)，并且同時沒有生成新的小于n或等于n的新環(huán)。(定理1、2和3在文獻【6】中有詳細證明過

4、程)以上為如何通過交換節(jié)點之間的邊來消去檢測到的需要消去的環(huán)。接下來要解決的問題就是如何通過該方法首先保證度數(shù)低的節(jié)點之間的環(huán)的長度最大化，再保證整個LDPC碼的環(huán)的最大化。我們可以通過如下兩個方案完成局部消環(huán)。方案一：令H=,其中Hh由校驗矩陣H中度數(shù)高的節(jié)點組成。Hl由校驗矩陣H中度數(shù)高的節(jié)點組成。 因為最正確度分布中校驗節(jié)點的度數(shù)根本不變，所以這里指的度數(shù)上下只針對于變量節(jié)點。首先根據(jù)(7)式尋找一條邊e，然后按(8)式尋找集合Ce，在Ce中隨機選取一條邊，再按圖1所示交換這兩條邊所在節(jié)點之間的邊，使Hl局部中短環(huán)盡量的消去。然后消去H中的短環(huán)，在這個過程中通過(10)式選取的環(huán)上的一條

5、邊和Ce中節(jié)點的選擇都限制在Hh中，這樣我們就沒有改變Hl中的邊，從而使H中的短環(huán)消去的同時保證Hl沒有改變。免費論文，圍長。方案二：如方案一，同樣先盡可能大的消去Hl中的短環(huán)。假設經(jīng)過消環(huán)后，Hl中的最小環(huán)長為m。從四環(huán)開始，根據(jù)(10)式選取環(huán)上的一條邊e。接下來選取Ce，將(11)式修改為，在Ce中隨機取一條邊e。然后按圖2交換e和e節(jié)點之間的邊。由定理3可知交換后不會產(chǎn)生小于或等于m的環(huán)。通過這個步驟就消去了4環(huán)，同時沒有產(chǎn)生小于或等于m的環(huán)。重復上述步驟，消去6、8,直到m-2環(huán)。方案一和方案二都可以完成局部消環(huán)。實際運行中，方案一的可行性遠遠高于方案二，效果也比方案二好。4 仿真結(jié)

6、果及討論為了驗證局部消環(huán)相比于只簡單的整體消環(huán)方法的更優(yōu)性能，本文給出了局部消環(huán)和整體消環(huán)在相同碼長、AWGN信道條件下，用BP算法迭代譯碼的誤碼率、誤幀率仿真結(jié)果圖。圖3 分別通過局部消環(huán)和整體消環(huán)構造的碼長為1000、碼率1/2的LDPC碼性能比擬圖3中的碼碼率都為1/2，碼長為1000。LR-part和LR-whole的度分布為文獻【3】中給出的最大變量節(jié)點為9時的最正確度分布。該度分布下變量節(jié)點的度數(shù)為2、3和9。我們將2和3看成低度數(shù)，9看成高度數(shù)。LR-part碼為方案一局部消環(huán)后的碼，其中度2和3之間的最小環(huán)長為12，整體環(huán)長為6。LR-whole為只整體消環(huán)的碼，其中整體環(huán)長為

7、8。圖3的碼最大迭代次數(shù)都為80。仿真結(jié)果說明，我們通過局部消環(huán)的矩陣由于優(yōu)先保證了度數(shù)小的節(jié)點之間環(huán)的最大化，而比直接整體消環(huán)所構造出的LDPC碼譯碼性能要高。5 結(jié)論直接構造出不包含短環(huán)的LDPC碼是困難的。本文討論了一種首先隨機生成一給定度分布下的LDPC碼，然后通過交換節(jié)點之間的邊的方法，先最大可能地消去度數(shù)低的節(jié)點之間的短環(huán)，然后在保證度數(shù)低的節(jié)點之間最小環(huán)不變的情況下最大可能地消去整個LDPC碼中短環(huán)的方案。由于該方法在消去LDPC碼短環(huán)的同時并沒有改變該LDPC碼對應的Tanner圖中節(jié)點的度分布，從而得到一個不包含短環(huán)而度分布確定的LDPC碼。該方法盡最大可能降低了環(huán)對降低LD

8、PC碼譯碼性能的影響。仿真結(jié)果說明，該方法相比于只簡單的從整體上消去短環(huán)構造的LDPC碼更好地改善了LDPC碼的性能。算法1： 校驗矩陣H的局部消環(huán)。1 B=H中度數(shù)低的節(jié)點構成的局部2 C=H中度數(shù)高的節(jié)點構成的局部3 B1=對B消環(huán)4 H1=5 A=6 n=47 由(7)選取一條邊e，并且該邊在H1中度數(shù)高的節(jié)點之間8 由(8)式選取集合Ce9 Ee=所有Ce中節(jié)點組成的H1的邊，并且這些邊的變量節(jié)點屬于度數(shù)高的局部10 如果Ee不空，交換e和e，更新H1和A11 n=n+212 重復7-11，直到?jīng)]有可以交換的邊參考文獻：【1】R. G. Gallager, Low-Density Pa

9、rity-Check Codes. Cambridge, MA:MIT Press, 1963.【2】D. J. C. MacKay and R. M. Neal, Near-Shannon-limitperformance of low density parity check codes ; Electron. Lett., vol. 32,Aug. 1996: 1645-1646.【4】趙嶺,張曉林,朱曼潔,一種用于規(guī)那么QC-LDPC碼的高效譯碼方法2007 33(09):64-65【5】J. Pearl, ProbabilisticReasoning in Intelligent Systems: Networks of Plausible Inference. San Francisco, CA: Morgan