QC-LDPC碼最小環路檢測算法

薛宇叢，周 華，鐵 鑫

(南京信息工程大學 電子與信息工程學院，江蘇 南京 210044)

0 引 言

自從信道編碼理論被提出以來，人們就在尋找一種在性能上能夠無限接近香農極限的編碼。早期的BCH碼、Turbo碼盡管具有結構規整、復雜度較低等優點，但是滿足不了在高信噪比時低誤碼率的要求，LDPC碼的出現則使信道編碼的發展有了新的突破。LDPC(low-density parity-check)碼由Gallager提出[1]，它因性能逼近香農極限而成為近年來的研究熱點，并且被應用到DVB2、4G、5G等標準中。

LDPC碼性能的優越性源于其校驗矩陣的結構，校驗矩陣常用Tanner圖表示。Tanner圖是一種雙向圖，當LDPC碼校驗矩陣對應的雙向圖存在環路時，從某一節點發出的信息經過環路的傳遞，會回到自身，破壞了置信傳播中邊信息的獨立性[2]。所以在LDPC碼的構造上，應該盡量減小環路對于譯碼性能的影響，避免短環結構出現[3]。對于碼長較小的LDPC碼，長度為4的最小環路可以由校驗矩陣直觀地觀察到，對于環路長度大于4的環，就需要用相關的算法檢測。本文提出了一種計算QC-LDPC碼最小環路圍長的方法，基于這種方法，構造最小環路為4、6、8的QC-LDPC碼的校驗矩陣，并通過仿真比較在相同信噪比情況下，最小圍長不同的QC-LDPC碼的誤碼率和誤幀率。

1 LDPC碼

二進制LDPC碼是一種線性分組碼，并由稀疏奇偶校驗矩陣定義。稀疏指奇偶校驗矩陣中“1”的數量相對“0”較少。若各行(列)中包含的“1”的個數相同，則稱為規則LDPC碼，否則稱為非規則LDPC碼[4]。如式(1)所示，以規則LDPC碼為例給出了對應的校驗矩陣H，其中行重為3，列重為2

(1)

LDPC碼的常用表示方法，除了矩陣形式，還有Tanner圖形式。Tanner圖是一種雙向圖，且與校驗矩陣相對應[5]，圖1表示式(1)所給的校驗矩陣H對應的Tanner圖。校驗矩陣中的行對應Tanner圖中的校驗節點(check node)，記為Ci，用方形來表示；列對應Tanner圖中的變量節點(bit node)，記為Vj，用圓形來表示。Tanner圖中的連接特性由校驗矩陣表示，若某行某列的位置上是“1”，則表示對應的校驗節點與變量節點之間存在一條邊相連[6]。由變量節點、邊和校驗節點首尾相連組成的閉合回路稱為環路。構成環路的邊的總數稱為圍長(最小圍長稱為girth)，且圍長是一個大于等于4的偶數。

圖1 校驗矩陣H的Tanner圖表示

圖1中C1→V1→C3→V5→C2→V2→C1就構成了完整的環路，其中路徑長度為6。

2 基于循環置換矩陣的QC-LDPC碼

LDPC碼可以分為兩大類：隨機LDPC碼和QC-LDPC碼[7]。在隨機LDPC碼的校驗矩陣中，“1”的分布沒有規律，存儲時需記錄生成矩陣和校驗矩陣的所有行向量，在實現上比較困難[8]。準循環低密度奇偶校驗(quasi-cyclic low-density parity-check，QC-LDPC)碼是一種高度結構化的LDPC碼，可以由指數矩陣和擴展維數來表示得到的碼字結構，其自身的準循環特性使編碼和解碼的過程更加高效。由單位矩陣經過循環移位后的循環置換矩陣組成QC-LDPC碼的校驗矩陣H，矩陣H形式為

(2)

其中，I(pn,l)表示將一個大小為M×M的單位矩陣向左循環移pn,l位，1≤n≤N，1≤l≤L。每個循環置換矩陣都由其維數M和循環移位次數pn,l唯一確定，因此QC-LDPC碼的H矩陣比較容易在硬件中實現，且方便尋址儲存。

3 QC-LDPC碼最小環路檢測算法

本文以式(1)中的矩陣H為例，提出一種檢測QC-LDPC碼中最小環路圍長的方法。本算法借鑒了比特翻轉(bit-flipping，BF)譯碼算法的思想。比特翻轉譯碼算法是用于LDPC碼的硬判決消息傳遞算法，首先對輸入譯碼器的向量數據做硬判決，將所得的二進制序列帶入全部校驗方程。如果校驗節點所有比特值的模2和為零，則校驗方程成立。如校驗方程不成立，則找出使其不成立數目最多的變量節點，把此變量節點所對應的比特位進行翻轉，此原理請參見文獻[9]。整個BF譯碼過程需要不斷迭代，直至所有奇偶校驗方程均成立，或者達到最大迭代次數自動跳出。BF譯碼算法只進行比特翻轉、模2加等簡單的運算，沒有復雜的算法，而且一旦所有奇偶校驗方程滿足就終止解碼器，可以避免額外的迭代。本算法同樣將二進制序列在變量節點和校驗節點之間迭代交換。不同的是，本算法的硬判決不依靠比特翻轉和模2加運算，只進行簡單的加法運算。下面以式(1)矩陣H為例，檢測最小環路的長度，步驟如下：

(1)參數設定：k=1，初始化長度為e的輸入序列E=[Ek]1×e為全零序列。

(2)設置序列E的第k位為1，即Ek=1，其余位為0。

(3)變量節點Vb將Ek發送到每個與其連接的校驗節點，該消息標記為qji，表示從變量節點Vj到校驗節點Ci的消息。用Ui表示校驗節點Ci接收到的信息之和，即

(3)

式(1)矩陣H中，變量節點V1與校驗節點C1、C3相連，E1從V1被傳遞到C1、C3，序列E中的零元素也沿對應的連線傳遞，得到U1=1,U2=0,U3=1,U4=0。此步驟對應圖2(a)。

(4)校驗節點將消息發送回與之連接的變量節點。該消息標記為rij，表示從校驗節點Ci到變量節點Vj的消息。用Dj表示變量節點Vj接收到的信息之和，即

(4)

其中

(5)

Nj：與變量節點Vj相連的校驗節點的下標集合。

Nj/i：除校驗節點Ci之外，與變量節點Vj相連的校驗節點的下標集合。

由步驟(3)可知，式(1)矩陣H中有U1=1,U2=0,U3=1,U4=0。變量節點V1此刻的信息為之前變量節點V2，V4傳遞到校驗節點C1的信息之和，即D1=0。最初傳遞的E1=1并沒有返回變量節點V1，也就是沒有形成完整環路，需要繼續進行迭代。此步驟對應圖2(b)。

(5)變量節點將不同的消息發送回每個連接的校驗節點，定義以下變量：

Ni：與校驗節點Ci相連的變量節點的下標集合。

Ni/j：除變量節點Vj之外，與校驗節點Ci相連的變量節點的下標集合。

定義校驗節點Cj接收到的信息值qji為其它校驗節點傳遞到與之相連的變量節點的信息之和，即

(6)

以校驗節點C1為例，校驗節點C1接收到的信息來自變量節點V1、V2和V4，根據式(3)和式(6)可知，此時C1的信息值U1=0。此步驟對應圖2(c)。

(6)校驗節點將不同的消息發送回每個與之連接的變量節點。變量節點V1接收到的信息來自校驗節點C1、C3，根據式(6)可知，V1此時的信息值D1=0，最初傳遞的E1=1沒有返回變量節點V1，需要繼續迭代。此步驟對應圖2(d)。

(7)步驟(5)和步驟(6)完成一個迭代過程。重復步驟(5)和步驟(6)，直到最初傳遞的E1=1回到變量節點V1，即D1=1時，迭代結束(如圖2(e)、圖2(f)所示)，環路長度等于2倍的迭代次數。

(8)依次設置全零序列E的第k位為1(k=2,3,…,e)，其余位為0，重復步驟(2)至步驟(7)，并根據Ek的取值更新Ui、Dj取值，得到各序列在上述迭代算法中的環路長度。最終在各環路長度中取最小值，則得到LDPC碼校驗矩陣H所對應的Tanner圖中的最小環路圍長。

圖2 當k=1時，本算法對式(1)中H的環路檢測步驟

為了便于理解，下面給出算法流程如圖3所示。設置循環次數為k，存放數據的集合為g。初始化令k=1，g=?。

圖3 最小環路檢測算法流程

4 性能仿真及分析

校驗矩陣中的環路是影響LDPC碼性能的重要因素之一，本文的算法已經可以準確的檢測出校驗矩陣中的最小環路圍長。為了驗證算法的正確性和合理性，以表明矩陣最小環路圍長對誤碼性能的影響，基于最小環路檢測算法，構造一組QC-LDPC碼，并進行仿真。

定義單位矩陣I(pn,l)的大小M=64。按照式(2)構造由I(pn,l)構成的3行5列的矩陣H，即矩陣H由15個經過循環移位的單位矩陣I(pn,l)組成。利用上述的最小環路圍長檢測算法，在MATLAB R2014a軟件中輸入矩陣H并隨機改變各移位次數pn,l的值，其中0

(7)

(8)

(9)

譯碼方式選擇傳統BP譯碼算法，BP算法的主要思路是將接收到的信息在校驗節點與變量節點之間迭代[10]。設置最大迭代次數為100，信噪比Eb/No為1.5 dB，2.0 dB，2.5 dB，3.0 dB，3.5 dB。

不同信噪比下，矩陣H1，H2，H3誤碼率(BER)及誤幀率(FER)性能曲線如圖4所示，其中實線表示BER，虛線表示FER。矩陣H1的數值點用圓形表示，矩陣H2的數值點用星形表示，矩陣H3的數值點用方形表示。

圖4 不同信噪比下矩陣H1，H2，H3的BER及FER性能曲線

由圖4中可以看出，對于行列數相同的校驗矩陣H1、H2、H3，在信噪比較低的情況下，3個矩陣的誤碼率曲線接近，誤幀率曲線也接近。但是隨著信噪比的增加，在相同信噪比下，最小環路數越大，對應的誤碼率和誤幀率就越小，即誤碼性能更優越。如圖4所示，誤碼率BER=5×10-4時，矩陣H3的信噪比值比矩陣H2的信噪比值小0.06 dB，矩陣H2的信噪比值比矩陣H1的信噪比值小0.2 dB。誤幀率FER=5×10-3時，矩陣H3的信噪比值比矩陣H2的信噪比值小0.06 dB，矩陣H2的信噪比值比矩陣H1的信噪比值小0.25 dB。

為驗證算法的適用性，構造4行8列的矩陣H，矩陣H由32個經過左循環移位的單位矩陣I(pn,l)組成，其中單位矩陣的大小為64×64?；诃h路檢測算法得到一組大小相同、最小環路長度不同的校驗矩陣H4、H5、H6， 且H4，H5，H6的最小環路圍長依次為4、6、8，構造方法同校驗矩陣H1、H2、H3

(10)

(11)

(12)

設置最大迭代次數為100，信噪比Eb/No為1.5 dB，2.0 dB，2.5 dB，3.0 dB，3.5 dB，3.75 dB。不同信噪比下，矩陣H4，H5，H6誤碼率(BER)及誤幀率(FER)性能曲線如圖5所示，其中實線表示BER，虛線表示FER。矩陣H4的數值點用圓形表示，矩陣H5的數值點用星形表示，矩陣H6的數值點用方形表示。

圖5 不同信噪比下矩陣H4，H5，H6的BER及FER性能曲線

類似于H1，H2，H3，兩組仿真的結果均驗證了在相同信噪比下，增加最小環路圍長能夠改進QC-LDPC碼的誤碼率和誤幀率。

對比圖4及圖5可以發現，在相同信噪比下，對于最小環路圍長相同的校驗矩陣，隨著矩陣的增大，誤碼率和誤幀率的值變大，即譯碼性能降低。以最小圍長均為4的校驗矩陣H1和H4為例，當信噪比為2.0 dB時，矩陣H4的誤碼率約為矩陣H1誤碼率的5倍，矩陣H4的誤幀率約為矩陣H1誤幀率的5倍，這會影響QC-LDPC碼在實際中的應用。如何在減少短環和擴大校驗矩陣結構的同時，提高譯碼性能，還需要進一步研究。

5 結束語

本文在比特翻轉譯碼算法的基礎上，提出了一種QC-LDPC碼最小環路圍長的檢測算法，該算法將輸入的二進制序列在變量節點和校驗節點之間迭代交換，把得到的輸出序列做硬判決，計算特定的標識信息回傳至起始節點的迭代數，環路長度為2倍的迭代次數，最小環路圍長即各節點所在環路圍長集合的最小值。利用上述算法構造最小環路圍長遞增的QC-LDPC碼組，借助MATLAB R2014a軟件對碼組進行性能仿真，驗證了最小環路圍長對于QC-LDPC碼譯碼性能的影響：增大最小環路圍長，有利于降低譯碼的誤碼率和誤幀率。