一種非規(guī)則QC-LDPC的掩碼矩陣構(gòu)造方法

劉 淵， 李雅慶

（洪都航空集團(tuán)660研究所，江西 南昌3300001）

0 引言

設(shè)計(jì)良好的LDPC 碼在碼長(zhǎng)趨向無限的條件下，可取得接近香農(nóng)限的糾錯(cuò)能力。在實(shí)用的通信系統(tǒng)中，為了平衡復(fù)雜度、編碼增益以及信息吞吐率等方面的指標(biāo)，通常選用的LDPC 長(zhǎng)度較短，且校驗(yàn)矩陣具有某些特殊結(jié)構(gòu)以方便編、譯碼器的設(shè)計(jì)，因而會(huì)在譯碼性能方做出一些犧牲。目前得到廣泛應(yīng)用的LDPC 主要有兩類，即eIRA（Extended Irregular and Repeat Accumulate）LDPC與QC-LDPC［1-3］。前者見于DVB-S2的協(xié)議［4］，這類碼的設(shè)計(jì)著重考慮編碼器的簡(jiǎn)化實(shí)現(xiàn)，通過在校驗(yàn)矩陣對(duì)應(yīng)校驗(yàn)比特的部分采用“雙對(duì)角線”結(jié)構(gòu)，使得校驗(yàn)比特的產(chǎn)生可以采用簡(jiǎn)單的遞推電路；此外，校驗(yàn)矩陣本身的分塊結(jié)構(gòu)也為便于編、譯碼器的并行化設(shè)計(jì)［5］。這種碼的收斂門限較低，但是由于“雙對(duì)角線”結(jié)構(gòu)引入了大量重量為2的變量節(jié)點(diǎn)，它們的誤碼基底通常出現(xiàn)較早。為此，DVB-S2中不得不采用級(jí)聯(lián)BCH 碼的方法作為對(duì)策。

QC-LDPC作為另一類被廣泛應(yīng)用的LDPC，目前已被IEEE 802.16e、IEEE 802.11n等技術(shù)協(xié)議以及美國(guó)國(guó)家航空航天局（NASA）的技術(shù)標(biāo)準(zhǔn)所采用［6］。這類碼的校驗(yàn)矩陣是由尺寸相同的循環(huán)矩陣構(gòu)成的陣列，因而便于編、譯碼器的并行化設(shè)計(jì)。相比eIRA LDPC，這類碼的設(shè)計(jì)方法比較靈活。

例如針對(duì)移動(dòng)通信的IEEE 802.16e 和IEEE 802.11n采用了類似的“雙對(duì)角線”的結(jié)構(gòu)來簡(jiǎn)化編碼器設(shè)計(jì)［7，8］，同時(shí)通過對(duì)校驗(yàn)矩陣的重量分布進(jìn)行優(yōu)化達(dá)到了較低的收斂門限；而在對(duì)誤碼基底要求很高的領(lǐng)域，則通常會(huì)構(gòu)造規(guī)則（regular）的QC-LDPC，例如NASA 技術(shù)標(biāo)準(zhǔn)中給出的7／8碼率的QC-LDPC。雖然這種碼的校驗(yàn)矩陣沒有“雙對(duì)角線”結(jié)構(gòu)，根據(jù)文獻(xiàn)［9］的理論，其編碼器依然可以通過循環(huán)移位寄存器以較低的復(fù)雜度實(shí)現(xiàn)高速編碼。這種碼的一個(gè)缺點(diǎn)是矩陣的密度偏大，增加了譯碼器的硬件復(fù)雜度。

本文提出的構(gòu)造方法是通過在代數(shù)域構(gòu)造的規(guī)則QC-LDPC的校驗(yàn)矩陣上進(jìn)行非規(guī)則掩碼，獲得非規(guī)則QC-LDPC。在構(gòu)造掩碼矩陣的過程中，通過保留原始矩陣中的部分結(jié)構(gòu)，并結(jié)合一種改進(jìn)的PEG（Progressive Edge Growth）算法，降低了收斂門限并延遲了誤碼基底的出現(xiàn)。理論分析和仿真結(jié)果顯示，新方法設(shè)計(jì)的碼字在收斂門限和誤碼基底方面都有良好的表現(xiàn)。

1 技術(shù)背景

1.1 基于有限域構(gòu)造的QC-LDPC碼

令α表示伽羅華域GF（q）上的一個(gè)本原元，其中q 表示某個(gè)質(zhì)數(shù)的冪，則α∞＝0，α，α2，…，αq-2構(gòu)成了GF（q）的所有q 個(gè)元素，且αq-1＝1。令P 表示一個(gè)尺寸為（q-1）×（q-1）的CPM，該矩陣的第一行是一個(gè)GF（2）上的（q-1）維向量（0 1 0 … 0）。如果用0到q-2表示該（q-1）維向量中各個(gè)元素的位置，則唯一的一個(gè)非零元素位于位置1。矩陣P 的其余各行可以由（0 1 0 … 0）進(jìn)行q-2次循環(huán)右移得到。令Pi，1≤i＜q，表示一個(gè)CPM，它的第一行是由（0 1 0 … 0）循環(huán)右移i次得到的（q-1）維向量。當(dāng)i＝q-1時(shí)，Pq-1＝Iq-1是一個(gè)（q-1）×（q-1）單位矩陣。集合P＝｛P0，P，P2，…，Pq-2｝構(gòu)成了一個(gè)基于矩陣乘法的階數(shù)為（q-1）的GF（2）上的循環(huán)群，該群中元素Pi的逆為Pq-1-i，單位元為P0。

對(duì)于GF（q）上的元素αi，1≤i＜q-1，將之?dāng)U展為（q-1）×（q-1）的循環(huán)置換矩陣（CPM）Pi。顯然，GF（q）上的元素和集合P 中的元素是一一對(duì)應(yīng)的關(guān)系，因此GF（q）中的每一個(gè)非零元素在P 中都有一個(gè)唯一與之對(duì)應(yīng)的CPM。對(duì)于GF（q）上的非零元素δ，本文用E（δ）表示這種擴(kuò)展關(guān)系，即當(dāng)δ＝αi時(shí)，E（δ）＝Pi。至于GF（q）上的0元素，它的擴(kuò)展形式是一個(gè)（q-1）×（q-1）的零矩陣（ZM），用P-∞來表示。

在文獻(xiàn)［11］中給出了三種GF（q）上的構(gòu)造方法，本文的后續(xù)部分將以其中的第一種方法構(gòu)造的QC-LDPC 碼為對(duì)象來說明掩碼矩陣的效果。該方法構(gòu)造出的Hb具有如下形式：

該矩陣具有以下特點(diǎn)：

a）每行（列）的各個(gè)元素各不相同；

b）每行（列）都包含一個(gè)零元素（α0-1）；

c）該矩陣是一個(gè)循環(huán)左移矩陣；

d）滿足RD-constraint，即Hb中的任意兩行（兩列）中同一個(gè)元素不出現(xiàn)超過1次。由該矩陣擴(kuò)展得到的二進(jìn)制校驗(yàn)矩陣H 的尺寸為（q-1）2×（q-1）2，且H 對(duì)應(yīng)的Tanner圖上最小圈的尺寸至少為6，即girth≥6；

e）該矩陣對(duì)應(yīng)的碼字空間中，最小碼間距離為（q-1）。

1.2 掩碼技術(shù)介紹

為了降低校驗(yàn)矩陣的密度，或者滿足構(gòu)造碼字在碼長(zhǎng)和碼率方面的要求，通常選擇在Hb的子矩陣Hb（γ，ρ）上進(jìn)行掩碼操作，其中γ 和ρ 分別代表行和列的數(shù)量。

由于掩碼以后的矩陣通常是行滿秩的，因此在目標(biāo)碼長(zhǎng)和碼率確定的情況下，Hb（γ，ρ）尺寸選擇方法如下：如果目標(biāo)碼率為Rd，目標(biāo)碼長(zhǎng)為ρ×（q-1），則γ＝ρ（1-Rd）。

掩碼可以用一種特殊的矩陣乘法表示，令Z表示一個(gè)γ×ρ的GF（2）的掩碼矩陣，則掩碼操作可以用下式子表示為

其中zi，j＝1時(shí)，zi，jAi，j＝Ai，j；zi，j＝0時(shí)，zi，jAi，j＝0。矩 陣Z 和M 分 別 被 稱 為 掩 碼 矩 陣（masking matrix）和 掩 碼 后 矩 陣（masked matrix）。通過將M 用上一節(jié)介紹的方法進(jìn)行擴(kuò)展，可以得到一個(gè)較為稀疏的二進(jìn)制校驗(yàn)矩陣H。

如果Z 的行重和列重分別只有一種，則Z 被稱為規(guī)則掩碼矩陣，否則稱為非規(guī)則掩碼矩陣。相比規(guī)則掩碼，通過優(yōu)化行列的重量分布，利用非規(guī)則掩碼得到的碼字通常可以取得更好的瀑布區(qū)性能，然而它們的誤碼基底出現(xiàn)較早。

2 優(yōu)化的構(gòu)造方法

2.1 掩碼矩陣的構(gòu)造方法

基于有限域構(gòu)造的QC-LDPC碼能夠取得較低的誤碼基底，一個(gè)重要的因素是校驗(yàn)矩陣的行列重量很大。在迭代譯碼過程中，信噪比較高時(shí)，度數(shù)大的變量節(jié)點(diǎn)由于能夠收到較多可靠的外信息，因而收斂較為迅速。當(dāng)它們的輸出信息收斂到一個(gè)穩(wěn)定的值后，可以幫助與它們相連的校驗(yàn)節(jié)點(diǎn)輸出更加可靠的信息。

因此，為了降低掩碼得到的碼字的誤碼基底，在構(gòu)造掩碼矩陣時(shí)，可以將其中少量的列設(shè)為全1向量，以達(dá)到保留原矩陣中一些重量較重的列的目的。這些全1向量通常被設(shè)置在掩碼矩陣的最左端，具體的數(shù)量可以通過仿真來優(yōu)化。它們的數(shù)量很少，一方面是為了保持掩碼后的矩陣行滿秩，從而不影響目標(biāo)碼率；另一方面是為了使得掩碼后的矩陣的平均列重保持在3～4之間，以得到較好的瀑布區(qū)性能。

為了簡(jiǎn)化設(shè)計(jì)，可以假設(shè)對(duì)應(yīng)那些被保留的重量較重的列的變量節(jié)點(diǎn)在迭代譯碼過程中都能夠正確的收斂。令τ表示掩碼矩陣中被設(shè)為全1向量的列的數(shù)量，目標(biāo)碼率為Rd，目標(biāo)碼長(zhǎng)為n＝ρ×（q-1），Hb子矩陣的尺寸為γ×ρ，其中γ＝ρ（1-Rd），則掩碼矩陣剩余的需要優(yōu)化的部分尺寸為γ×（ρ-τ），碼率為R′＝（ρ-τ-γ）／（ρ-τ）。這部分的度數(shù)分布可以通過基于密度演變的優(yōu)化算法獲得。

根據(jù)優(yōu)化的度數(shù)分布，來構(gòu)造掩碼矩陣可以使用PEG 算法及其改進(jìn)算法來構(gòu)造掩碼矩陣［11］。改進(jìn)型PEG 算法目前主要包括應(yīng)用ACE（approximate cycle extrinsic message degree）限制條件的PEG 算法及其各種改進(jìn)。然而這些在考慮了掩碼矩陣本身的結(jié)構(gòu)時(shí)，忽略了原始矩陣的影響。而根據(jù)文獻(xiàn)［10］的證明，這一影響是相當(dāng)顯著的。根據(jù)該文獻(xiàn)的理論，本文給出了一種改進(jìn)的PEG 算法來構(gòu)造掩碼矩陣、

2.2 改進(jìn)的PEG 算法

本文首先簡(jiǎn)要介紹一下傳統(tǒng)的PEG 算法。為了更好的理解PEG 算法，首先需要了解一下變量節(jié)點(diǎn)的局部girth（local girth）。某個(gè)變量節(jié)點(diǎn)的局部girth指的是通過這個(gè)節(jié)點(diǎn)的最短圈的長(zhǎng)度。顯然，一個(gè)Tanner圖的girth是該圖中所有變量節(jié)點(diǎn)的局部girth中尺寸最小的。

PEG 算法由一個(gè)空的Tanner圖開始，變量節(jié)點(diǎn)逐個(gè)加入，每個(gè)變量節(jié)點(diǎn)的邊按照一定的準(zhǔn)則被添加進(jìn)來，即要使得當(dāng)前變量節(jié)點(diǎn)的局部girth最大化。其最終構(gòu)造的碼字，通?？梢跃哂休^大的girth。

為了在給定變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)度數(shù)分布的條件下，構(gòu)造一個(gè)包含n個(gè)變量節(jié)點(diǎn)和m 個(gè)校驗(yàn)節(jié)點(diǎn)的Tanner圖，首先定義如下一些變量。令（v0，v1，…，vn-1）表示n 個(gè)變量節(jié)點(diǎn)的序列，該序列按照各個(gè)節(jié)點(diǎn)的度數(shù)由低到高排列，變量節(jié)點(diǎn)vi，0≤i＜n，的度數(shù)用dvi表示。表示由變量節(jié)點(diǎn)vi為根擴(kuò)展的樹在深度為l 時(shí)所能夠連接的校驗(yàn)節(jié)點(diǎn)集合，它的補(bǔ)集用表示。表示連接vi的第k 條邊。傳統(tǒng)的PEG 算法表述如下：

根據(jù)上面的算法描述，可以看到PEG 算法是逐點(diǎn)逐邊地來構(gòu)造Tanner圖的。它的基本思想是先盡量找到和當(dāng)前變量節(jié)點(diǎn)相連后不會(huì)造成圈的校驗(yàn)節(jié)點(diǎn)；當(dāng)這樣的節(jié)點(diǎn)不存在時(shí)，則尋找能夠使得圈的尺寸盡量大的校驗(yàn)節(jié)點(diǎn)。最后用一條邊將兩者相連，以使得當(dāng)前節(jié)點(diǎn)的局部girth最大化。

本文給出的算法與PEG 算法以及ACE限制條件的PEG 算法的區(qū)別在于從Cl，kvj中選取校驗(yàn)節(jié)點(diǎn)的方法不同。該算法的準(zhǔn)則是使得掩碼后矩陣（而不是使得掩碼矩自身）中新形成的圈的ACE值最大化，因此該算法有可能使得新構(gòu)造的碼字取得更低的誤碼基底。具體的選擇方法如下所示。

3 仿真結(jié)果與分析

本節(jié)通過三個(gè)例子來對(duì)比說明新方法構(gòu)造的碼字相對(duì)于當(dāng)前常見LDPC的性能優(yōu)勢(shì)。在下面的例子中仿真的信道環(huán)境都是高斯白噪聲信道。

首先，以DVB-S2 中短幀格式下的（16 200，13 320）為參照對(duì)象來構(gòu)造碼率為0.82的碼字。在GF（28）上構(gòu)造255×255的矩陣上，從第二行第一列開始割取9×50的子矩陣作為Hb（γ，ρ）。然后構(gòu)造出τ ＝0，1，2，3的四種掩碼矩陣，通過二進(jìn)制擴(kuò)展得到分布如表1 所示的4 個(gè)校驗(yàn)矩陣，這些矩陣對(duì)應(yīng)的碼字長(zhǎng)度為12 750，信息位長(zhǎng)度為10 455。表中變量節(jié)點(diǎn)是將校驗(yàn)矩陣映射為Tanner圖后對(duì)應(yīng)于列的部分，它的分布用γ（x）＝Σγixi-1，i＝2，3，… ，表示，0≤γ ≤1且∑γi＝1， i＝2，3，… ，其中γi表示度數(shù)為i的變量節(jié)點(diǎn)在所有變量節(jié)點(diǎn)中所占的比例；校驗(yàn)節(jié)點(diǎn)則是對(duì)應(yīng)校驗(yàn)矩陣行的部分，它的分布用ρ（x）＝Σρixi-1，i＝2，3，… 表示，0≤ρ≤1且∑iρi ＝1，其中ρi 表示度數(shù)為i的校驗(yàn)節(jié)點(diǎn)在所有校驗(yàn)節(jié)點(diǎn)中所占的比例。

表1 （12750，10455） QC-LDPC碼的度數(shù)分布

圖1顯示了以上四種碼字與DVB-S2中的（16 200，13 320）eIRA LDPC的性能對(duì)比。采用的譯碼算法為bp（belief propagation）算法，迭代次數(shù)的上限設(shè)為100次。由圖可見，（16 200，13 320）eIRA LDPC的誤碼基底非常明顯，在誤比特率（BER）為10-5左右即已出現(xiàn)。新方法構(gòu)造的碼字在誤碼基底方面相比前者要至少低兩個(gè)數(shù)量級(jí)左右。在低信噪比區(qū)域，隨著τ的增大，可以觀察到收斂門限在逐步降低，當(dāng)τ＝3時(shí)，新方法構(gòu)造的碼字相比DVB-S2的碼字在（BER）為10-5左右約有0.1dB的增益。不過τ的增加也帶來了譯碼器中ram 數(shù)量的增加，實(shí)際應(yīng)用中可以根據(jù)需要選擇適當(dāng)?shù)摩右云胶庾g碼能力和運(yùn)算復(fù)雜度之間的關(guān)系。

圖1 幾種（12 750，10 455）QC-LDPC和DVB-S2中的（16 200，13 320）eIRA LDPC的性能對(duì)比

接著，本文以NASA 技術(shù)標(biāo)準(zhǔn)中的（8 176，7 154） QC-LDPC為比較對(duì)象來構(gòu)造碼率為7／8的碼字。該碼字是一種（4，32）的規(guī)則碼，它誤碼基底很低，且收斂門限較低，是一種性能優(yōu)秀的高碼率碼字。在這個(gè)例子中，Hb（γ，ρ）依然是從GF（28）上構(gòu)造255×255的矩陣上割取的，其尺寸為4×32。由于矩陣較“扁”，因而需要較大的τ才能保證較好的保留原始矩陣的優(yōu)良特性。此例中包括了τ＝3，4，5的三種掩碼矩陣，通過二進(jìn)制擴(kuò)展得到分布如表2所示的4個(gè)校驗(yàn)矩陣，這些矩陣對(duì)應(yīng)的碼字長(zhǎng)度為8 160，信息位長(zhǎng)度為7 140。

圖2 顯示了表2 中的碼字與NASA 的（8 176，7 154）QC-LDPC之間的性能對(duì)比。譯碼算法是歸一化的min-sum 算法［13］，最大迭代次數(shù)上限設(shè)為50 次，歸一化系數(shù)設(shè)為0.72。之所以采用歸一化的min-sum 算法，是由于在NASA 的技術(shù)標(biāo)準(zhǔn)中給出了該算法的仿真曲線，并且這種算法在實(shí)際應(yīng)用中應(yīng)用廣泛。由圖可見，得到的碼字性能基本上和NASA 的一致。隨著τ的增加，碼字的性能略有增加，但是不太明顯，這主要是由于校驗(yàn)矩陣比較“扁”，只有4個(gè)行塊構(gòu)成，且平均列重在3左右。不過相對(duì)于NASA 的碼字，新方法構(gòu)造的碼字由于行列重量只有前者的3／4左右，這樣可以在硬件實(shí)現(xiàn)時(shí)節(jié)省約1／4的硬件資源。

最后，本文給出一個(gè)中等碼率，較短碼長(zhǎng)的例子?；仃囀菑腉F（26）上構(gòu)造的31×31的矩陣上割取一個(gè)15×30的子矩陣，進(jìn)行掩碼后，其對(duì)應(yīng)的碼字為一個(gè)碼率為1／2 的（1 890，945）QCLDPC。表3給出了幾種構(gòu)造的校驗(yàn)矩陣的度數(shù)分布。

表2 （8 160，7 140） QC-LDPC碼的度數(shù)分布

圖2 幾種（8 160，7 140）QC-LDPC和NASA的（8 176，7 154）QC-LDPC的性能對(duì)比

圖3 幾種（1 890，945）QC-LDPC和IEEE 802.16e的（1 920，960）QC-LDPC的性能對(duì)比

表3 （1 980，945）QC-LDPC碼的掩碼矩陣的度數(shù)分布

圖3顯示了表3中幾種（1 890，945）QC-LDPC碼的性能。圖中還給出了IEEE 802.16e中的（1 920，960）QC-LDPC碼的性能曲線作為對(duì)比。采用bp譯碼算法，迭代次數(shù)的上限設(shè)為100次。由圖可見，應(yīng)用新的構(gòu)造方法后，誤碼基底的出現(xiàn)相比傳統(tǒng)的PEG 算法有了較為明顯的降低?？梢钥吹剑S著τ的增加，誤碼基底的出現(xiàn)有著下降的趨勢(shì)，但是當(dāng)τ增加到一定數(shù)值以后，雖然明顯降低了誤碼基底，但是瀑布區(qū)的性能有所下降。對(duì)于本例，當(dāng)τ取為2時(shí)，構(gòu)造的碼字在瀑布區(qū)和誤碼基底區(qū)域的性能能夠取得較為良好的平衡。

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

本文結(jié)合掩碼（masking）和基于多元域的代數(shù)構(gòu)造方法，給出了一種高性能QC-LDPC的構(gòu)造方法。仿真結(jié)果顯示，相比現(xiàn)在被廣泛應(yīng)用的LDPC，運(yùn)用本文提出的構(gòu)造方法可以得到在收斂速度和誤碼基底方面表現(xiàn)更加優(yōu)秀的QC-LDPC。

［1］ Mclaughlin，S.，Ramamoorthy，A.，Jaehong Kim.The Design of Efficiently-encodable Rate-compatible LDPC Codes［J］IEEE Trans.Commun.，2009，2（57）：365-375.

［2］ Arabaci，Murat，Djordjevic，Ivan B.，Saunders，Ross，Marcoccia，Roberto M..High-rate Nonbinary Regular Quasi-cyclic LDPC Codes for Optical Communications［J］.Journal of Lightwave Technology，2009，27（23）：5261-5267.

［3］ Lee Moon Ho，Jiang Xue-qin.Design of Irregular Quasi-cyclic LDPC Codes Based on Euclidean geometries［C］.IWSDA，2009.

［4］ ETSI EN302 307 V1.1.1-2005DVB.Second Generation Framing Structure，Channel Coding and Modulation System for Broadcasting，Interactive Service，News Gathering and Other Broadband Satellite Applications［S］.2005.

［5］ 陳兵.基于DVB-S2標(biāo)準(zhǔn)IRA-LDPC編譯碼算法的研究［D］.武漢：武漢理工大學(xué)，2009.

［6］ CCSDS131.1-O-1：Low Density Parity Check Codes for Use in Near-earth and Deep Space Applications［J］.Research and Development for Space Data System Standards，CCSDS，2006，（1）.

［7］ IEEE Standard for Local and Metropolitan Area Networks Part 16：Air Interface for Fixed Broadband Wireless Access Systems［J］.IEEE Std 802：16TM-2005，2006.

［8］ IEEE DraftSTANDARD for Information Technolo-gy-telecommunications an Information Exchange between Systems-Local and Metropolitan Area Networks-Specific Requirements，Part 11： Wireless LAN Medium Access Control（MAC）and Physical Layer（PHY）Specifications［J］.IEEE Standard P802.11nTM／D2.00，2007.

［9］ Zongwang Li，Lei Chen，Lingqi Zeng，Shu Lin，Wai H.Fong.Efficient Encoding of Quasi-cyclic Low-density Parity-check Codes［J］.IEEE Trans.Commun.，2006，54（1）：71-81.

［10］ Lan Lan，Lingqi Zeng，Ying Y.Tai，Lei Chen，Shu Lin and Khaled Abdel-Gha＿ar.Construction of Quasi-cyclic LDPC Codes for AWGN and Binary Erasure Channels：A Finite Field Approach［J］.IEEE Trans.Inf.Theory，2007，53（7）：2429-2458.

［11］ Chen J，F(xiàn)ossorier M P C.Density Evolution for Two Improved BP-based Decoding Algorithms of LDPC Codes［J］.IEEE Commun.Lett.，2002，6（5）：208-210.

［12］ Kang Jingyu.Construction，Decoding and Application of Low-density Parity-check Codes［D］.Electrical Engineering，University of California，Davis，2010.

［13］ Daesun Oh，Keshab K.Parhi.Min-Sum Decoder Architectures with Reduced Word Length for LDPC Codes［J］.IEEE Trans.Circuits and Systems，2010，54（1）：105-115.