薛宇叢，周 華，鐵 鑫

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

0 引 言

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

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

1 LDPC碼

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

(1)

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

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

圖1中C1→V1→C3→V5→C2→V2→C1就構(gòu)成了完整的環(huán)路，其中路徑長度為6。

2 基于循環(huán)置換矩陣的QC-LDPC碼

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

(2)

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

3 QC-LDPC碼最小環(huán)路檢測算法

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

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

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

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

(3)

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

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

(4)

其中

(5)

Nj：與變量節(jié)點Vj相連的校驗節(jié)點的下標(biāo)集合。

Nj/i：除校驗節(jié)點Ci之外，與變量節(jié)點Vj相連的校驗節(jié)點的下標(biāo)集合。

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

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

Ni：與校驗節(jié)點Ci相連的變量節(jié)點的下標(biāo)集合。

Ni/j：除變量節(jié)點Vj之外，與校驗節(jié)點Ci相連的變量節(jié)點的下標(biāo)集合。

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

(6)

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

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

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

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

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

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

圖3 最小環(huán)路檢測算法流程

4 性能仿真及分析

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

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

(7)

(8)

(9)

譯碼方式選擇傳統(tǒng)BP譯碼算法，BP算法的主要思路是將接收到的信息在校驗節(jié)點與變量節(jié)點之間迭代[10]。設(shè)置最大迭代次數(shù)為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的數(shù)值點用圓形表示，矩陣H2的數(shù)值點用星形表示，矩陣H3的數(shù)值點用方形表示。

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

由圖4中可以看出，對于行列數(shù)相同的校驗矩陣H1、H2、H3，在信噪比較低的情況下，3個矩陣的誤碼率曲線接近，誤幀率曲線也接近。但是隨著信噪比的增加，在相同信噪比下，最小環(huán)路數(shù)越大，對應(yīng)的誤碼率和誤幀率就越小，即誤碼性能更優(yōu)越。如圖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。

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

(10)

(11)

(12)

設(shè)置最大迭代次數(shù)為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的數(shù)值點用圓形表示，矩陣H5的數(shù)值點用星形表示，矩陣H6的數(shù)值點用方形表示。

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

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

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

5 結(jié)束語

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