基于原模圖的歐氏幾何準循環LDPC碼

劉原華, 何 華

(西安郵電大學 通信與信息工程學院， 陜西 西安 710121)

低密度奇偶校驗(low-density parity-check， LDPC)碼是一種具有稀疏校驗矩陣的線性分組碼，能夠利用低復雜度迭代譯碼算法達到接近香農限的糾錯性能。LDPC碼可分為隨機LDPC碼和結構化LDPC碼。隨機LDPC碼圍長較大，性能優異，但由于缺乏一定的結構特性，編碼復雜度高，不利于硬件實現，且校驗矩陣的存儲復雜度也較高。結構化LDPC碼具有循環或準循環的結構，可實現線性復雜度的編譯碼，中短碼長時性能可與隨機碼相比擬，正逐步進入各種通信領域，在中國數字電視地面廣播傳輸標準、歐洲第二代數字電視地面廣播標準、無線局域網IEEE 802.16n中均已采納準循環LDPC(quasi-cyclic LDPC，QC-LDPC)碼作糾錯編碼方式。

絕大多數歐氏幾何LDPC碼都是結構化的循環碼或準循環碼，可以通過移位寄存器實現線性復雜度編碼,同時可利用多種譯碼算法實現復雜度、速度以及糾錯性能之間的良好折衷。利用歐氏幾何的結構特性,可構造出不包含4環的性能優異的LDPC碼[1-7]。基于歐氏幾何的QC-LDPC碼[6]雖然不包含4環，但在校驗矩陣的行重和列重給定的情況下，其譯碼門限就確定了，無法進一步有效改善QC-LDPC碼的糾錯性能。

原模圖QC-LDPC碼可以由一個很小的原模圖通過復制和循環矩陣擴展得到，其糾錯性能由原模圖、復制次數以及循環矩陣的移位數共同決定。原模圖QC-LDPC碼與一般的QC-LDPC碼的不同之處在于，其基矩陣中的元素不僅僅局限于0和1，可以是任意小于其復制次數的非負整數，即原模圖具有允許多邊存在的特點，有利于降低碼的譯碼門限，進一步優化QC-LDPC碼的性能。基于Sidon序列的QC-LDPC碼[8]屬于一種原模圖QC-LDPC碼，其基矩陣中的元素均為2。對于給定的原模圖，為避免短環的出現，在設計循環矩陣的移位次數時需考慮原模圖中的環分布情況[9-12]。例如,在利用PEG算法構造原模圖QC-LDPC碼時，通常先要基于PEG算法構造原模圖，再借助附加的環檢測算法來設計循環矩陣的移位次數[13-15]。這種方法可有效地構造短碼長的性能優異碼，但當碼長增加時，該方法的復雜度將很高。

為簡化構造算法的復雜度，同時改善歐氏幾何QC-LDPC碼的糾錯性能，本文擬給出一種基于原模圖的歐氏幾何QC-LDPC碼構造方法。利用歐氏幾何的結構特性設計循環矩陣的移位次數，有效避免短環的出現，簡化實現復雜度；同時將原模圖多邊的特點引入歐氏幾何碼的基矩陣，降低譯碼門限，進一步優化其糾錯性能。

1 原模圖QC-LDPC碼

原模圖是節點相對較少的Tanner圖，記為

Gp=(V，C，E)。

其中V是變量節點集和，C是校驗節點集和，E是邊集和。原模圖對應的基矩陣為

B=(bij)m×n。

其中m為校驗節點的個數，n為變量節點的個數，bij為第i個校驗節點和第j個變量節點之間連接邊的條數，當bij>1時，原模圖中有并行邊的存在。對原模圖進行T次復制，然后把T條相同類型的變量節點和校驗節點之間的邊置換，可以擴展成不同大小的圖，這種圖稱為導出圖G，對應的LDPC碼稱為原模圖LDPC碼。若邊置換為循環置換，則對應的LDPC碼為原模圖QC-LDPC碼。

原模圖QC-LDPC碼可由其基矩陣經循環矩陣擴展得到：將基矩陣中的非零元素，用bij個不重疊的循環置換矩陣的和替換，零元素用全零矩陣替換，即可得到原模圖QC-LDPC碼的校驗矩陣H，該操作稱為循環矩陣擴展。

2 原模圖歐氏幾何QC-LDPC碼

LDPC碼的性能可由譯碼門限值來衡量，門限值是LDPC碼成功譯碼所能容忍的最小信噪比，當信道的信噪比高于門限值時，碼集中的幾乎任何一種碼的誤比特率都將隨著迭代次數或碼長的增加而趨于零，否則碼集中的碼的誤比特率將始終大于某個常數。因此，這個門限值是評價LDPC碼性能的重要參數。外信息轉移(extrinsic information transfer，EXIT)圖技術是分析LDPC碼迭代譯碼性能的有效方法之一，可根據LDPC碼的度分布，計算其譯碼門限。具有相同度分布的QC-LDPC碼可以具有不同的基矩陣，從而具有不同的譯碼收斂性能，而傳統的EXIT圖無法區分這些QC-LDPC碼譯碼性能的不同，故需引入基于原模圖的EXIT(protograph EXIT，PEXIT)圖技術[16]，用以分析相同度分布不同基矩陣的原模圖QC-LDPC碼的譯碼門限。

基于原模圖構造歐氏幾何QC-LDPC碼，需先構造具有低譯碼門限的多邊原模圖的基矩陣，再利用歐氏幾何的結構特性設計循環矩陣的移位次數，并通過循環矩陣擴展獲得不包含4環的歐氏幾何原模圖QC-LDPC碼。

2.1 歐氏幾何

令伽羅華域FG(pms)為域FG(ps)的擴域，可以看作是FG(ps)上的所有m維向量構成的向量空間，FG(pms)上的任意元素可表示成為FG(ps)上的m維向量，域FG(pms)上的pms個元素與歐氏幾何GE(m,ps)中的pms個點一一對應，因此,伽羅華域FG(pms)等價于GE(m,ps)[6]。FG(pms)中的每個元素可由其本原元α的冪次表示，歐氏幾何中的每個點也可由α的冪次來表示，其中α∞表示原點。

將有限域FG(pms)中的一個本原元記為α，令

ai=αi-1(i=1,2,…,n)

v(ai)=(v1,v2,…,vn)，

vL=(v1,v2,…,vps)，

該向量包含ps個子向量，每個子向量為n維二進制向量，其中第i個子向量vi是直線L上第i個點的關聯向量。

任一循環類中任一直線均可作為此循環類的代表元，將代表元的關聯向量進行分段循環移位n次即可得到該循環類中的其他直線的關聯向量。

2.2 改進歐氏幾何碼設計

對于第i個循環類(i=1,2,…,K)，將該類中n條直線的關聯向量作為列，可構造出nps×n階矩陣Hi。由直線的循環特性可知，Hi可設計成一個由n×n的循環置換矩陣組成的ps×1矩陣陣列，Hi的每行包含1個非零元素1，每列包含ps個非零元素1，其余元素皆為0，即Hi的行重為1，列重為ps。將這K個矩陣H1，H2,…，HK作為子矩陣構造矩陣

選擇H的任意γ×ρ子陣列，即可得到(γ，ρ)規則歐氏幾何QC-LDPC碼[6]，其中γ和ρ為碼校驗矩陣的行重和列重。該碼的基矩陣為一個γ行ρ列全1矩陣，其譯碼門限可由PEXIT算法計算得到。因此，無論如何選擇H的子陣列，只要參數γ和ρ確定了，其譯碼門限就固定不變了，無法進一步有效改善QC-LDPC碼的糾錯性能。為解決這一問題，考慮利用原模圖碼的特點，將大于1的元素引入到基矩陣中，從而優化QC-LDPC碼的糾錯性能。

原模圖QC-LDPC碼中存在不可避免短環的問題[9]，若QC-LDPC碼的基矩陣包含元素3，則無論如何設計循環矩陣的維數(即復制次數)和循環矩陣的移位次數，必定存在長度為6的不可避免短環；若基矩陣的某行或某列包含兩個2，則必定存在長度為8的不可避免短環。基于以上結論，在設計基矩陣時，除了元素0和1，只引入元素2，不考慮元素3，且每行每列最多包含一個2。由于LDPC碼校驗矩陣的行重大于列重，即基矩陣的列數ρ大于行數γ，不失一般性，將元素2設計在基矩陣的前γ列，且處在基矩陣左邊γ行γ列子矩陣的對角線位置。為保證LDPC碼的列重不變，基矩陣的前γ列每列需設置一個元素0，為保證LDPC碼的行重不變，這γ個0需處在不同行且不同列。

例如，當γ=4，ρ=8時，基矩陣可設計為

(1)

其譯碼門限可由PEXIT算法計算得到，與4行8列的全1基矩陣相比，式(1)的譯碼門限獲得了0.247 5的改進，其對應原模圖QC-LDPC碼的性能可得到有效提高。

利用歐氏幾何的結構特性可設計循環矩陣的移位次數，再通過循環矩陣擴展，即可獲得不包含4環的歐氏幾何原模圖QC-LDPC碼。

假設原歐氏幾何QC-LDPC碼的校驗矩陣是由n×n的循環置換矩陣組成的γ×ρ的矩陣陣列，具有形式

(2)

其中Iaij為n×n的循環置換矩陣，可由單位陣I每行向右循環移位aij位得到，而aij為該循環置換矩陣的循環移位次數，其值由歐氏幾何中直線的關聯向量確定。

矩陣(2)的基矩陣為一個γ行ρ列全1矩陣，為獲得形如式(1)的基矩陣，將矩陣H前γ列陣列的每列選擇一個子矩陣移入到左半邊陣列的對角線對應的子矩陣Iaii(1≤i≤γ)中，基矩陣中的元素2對應的循環子矩陣為2個不重疊的循環置換矩陣的疊加。以式(1)的基矩陣為例，改進后的校驗矩陣

H′=[h1,h2,h3,h4,h5,h6,h7,h8],

(3)

h1=[Ia11+Ia21,0,Ia31,Ia41]T,
h2=[0,Ia22+Ia12,Ia32,Ia42]T,
h3=[Ia13,Ia23,Ia33+Ia43,0]T,
h4=[Ia14,Ia24,0,Ia44+Ia34]T,
h5=[Ia15,Ia25,Ia35,Ia45]T,
h6=[Ia16,Ia26,Ia36,Ia46]T,
h7=[Ia17,Ia27,Ia37,Ia47]T,
h8=[Ia18,Ia28,Ia38,Ia48]T,。

其中0為零矩陣，其零空間即為所設計的原模圖QC-LDPC碼。

2.3 碼結構分析

3 仿真結果

對改進方法構造的原模圖QC-LDPC碼和已有歐氏幾何碼[6]的譯碼門限進行比較，同時采用二進制相移鍵控調制下的加性高斯白噪聲信道，仿真比較改進方法和已有方法構造的QC-LDPC碼在置信傳播迭代譯碼算法下的誤比特率(bit error rate，BER)和誤幀率(frame error rate，FER)，譯碼的最大迭代次數設置為100次。

兩種方法構造的三組(6,9)，(4,8)和(4,10)規則QC-LDPC碼的譯碼門限如表1所示。由其可見，與原歐氏幾何碼相比，改進方法構造的QC-LDPC碼譯碼門限更低，三組碼的門限改進值均大于0.2。

表1 譯碼門限對比

圖1 兩種方法構造QC-LDPC碼的糾錯性能

4 結論

為降低碼的譯碼門限,首先構造了基于多邊的原模圖的基矩陣，然后利用歐氏幾何的結構特性設計基矩陣對應的循環矩陣的移位次數，獲得了不包含4環的歐氏幾何原模圖QC-LDPC碼。仿真結果表明，與已有歐氏幾何碼相比，改進方法構造的QC-LDPC碼通過降低譯碼門限獲得了更優的糾錯性能。同時，所構造的碼具有準循環的結構，具有編譯碼實現簡單的特點。