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

薛宇叢，周 華，鐵 鑫

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

0 引 言

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

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

1 LDPC碼

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

(1)

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

圖1 校驗(yàn)矩陣H的Tanner圖表示

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

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

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

(2)

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

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

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

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

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

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

(3)

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

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

(4)

其中

(5)

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

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

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

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

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

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

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

(6)

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

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

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

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

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

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

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

4 性能仿真及分析

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

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

(7)

(8)

(9)

譯碼方式選擇傳統(tǒng)BP譯碼算法，BP算法的主要思路是將接收到的信息在校驗(yàn)節(jié)點(diǎn)與變量節(jié)點(diǎn)之間迭代[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所示，其中實(shí)線表示BER，虛線表示FER。矩陣H1的數(shù)值點(diǎn)用圓形表示，矩陣H2的數(shù)值點(diǎn)用星形表示，矩陣H3的數(shù)值點(diǎn)用方形表示。

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

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

為驗(yàn)證算法的適用性，構(gòu)造4行8列的矩陣H，矩陣H由32個(gè)經(jīng)過(guò)左循環(huán)移位的單位矩陣I(pn,l)組成，其中單位矩陣的大小為64×64?；诃h(huán)路檢測(cè)算法得到一組大小相同、最小環(huán)路長(zhǎng)度不同的校驗(yàn)矩陣H4、H5、H6， 且H4，H5，H6的最小環(huán)路圍長(zhǎng)依次為4、6、8，構(gòu)造方法同校驗(yàn)矩陣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所示，其中實(shí)線表示BER，虛線表示FER。矩陣H4的數(shù)值點(diǎn)用圓形表示，矩陣H5的數(shù)值點(diǎn)用星形表示，矩陣H6的數(shù)值點(diǎn)用方形表示。

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

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

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

5 結(jié)束語(yǔ)

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