可快速編碼的大圍長QC-LDPC碼構造方法

, ,,2

(1.重慶郵電大學 通信與信息工程學院 重慶高校市級光通信與網絡重點實驗室,重慶 400065;2.中國電子科技集團第四十四研究所,重慶 400065)

0 概述

由于具有逼近Shannon限的糾錯性能[1],且譯碼復雜度較低,低密度奇偶校驗(Low Density Parity Check,LDPC)碼一直是近年來編碼領域的研究熱點,并被廣泛應用在各類現代通信系統中。根據構造方法的不同,LDPC碼[2]可分為隨機碼[3]和結構化碼。隨機LDPC碼的編碼復雜度與碼長的平方成正比,且校驗矩陣的硬件存儲復雜度高,尤其在碼長較長時不利于實際應用。因此,需要設計性能優越、校驗矩陣具有一定結構特性的LDPC碼。作為一種結構化的LDPC碼,基于循環置換矩陣(Circulant Permutation Matrix,CPM)構造的準循環(Quasi Cyclic,QC)LDPC碼[4-5]由于其簡單靈活的設計方法引起了編碼領域的廣泛關注和研究。

雖然QC-LDPC碼具有存儲復雜度低、構造靈活簡單等優點,然而傳統QC-LDPC碼的編碼仍然需要通過校驗矩陣轉化成生成矩陣來實現,由于生成矩陣中子矩陣不一定具備稀疏的特性,因此在硬件編碼實現時仍會占用大量存儲空間。為了降低QC-LDPC碼的編碼復雜度,文獻[6]提出了一種將校驗矩陣的校驗部分設計成近似下三角結構的構造方法,在編碼過程中可直接通過校驗矩陣進行迭代編碼,從而有效地降低了編碼復雜度。其中,IEEE 802.16e標準所采用的就是一種典型的采用準雙對角線近似下三角結構的QC-LDPC碼[7-8]。然而,其校驗矩陣右半部分雙對角線上的子矩陣均是單位陣,這些確定性單位陣的存在不僅破壞了這類QC-LDPC碼的隨機性,使得碼字性能有一定的損失,而且導致一些基于組合設計、代數設計等確定性方法構造大圍長QC-LDPC碼存在局限性。

針對上述問題,本文提出一種基于獨立行列映射序列(Independent Row-column Mapping Sequence,IRCMS)算法以及通過CPM的行列循環移位和掩碼技術來構造圍長為8、可快速編碼的QC-LDPC碼的方法。該方法采用IRCMS算法構造圍長為8的全局校驗矩陣,然后通過CPM的行列循環移位使得校驗部分的矩陣具有一定的半隨機結構特性,最后利用掩碼技術得到一種改進型的半隨機準雙對角線結構及可快速編碼的大圍長QC-LDPC碼。

1 大圍長QC-LDPC碼

基于CPM構造的規則(J,L)QC-LDPC碼,列重為J,行重為L,其校驗矩陣可表示如下[9]:

(1)

其中,1≤j≤J,1≤l≤L,0≤Pj,l

(2)

根據IRCMS算法[10],Pr,c=f(r,c)=g(r)h(c),其中,g(r)(r=1,2,…,J)和h(c)(c=1,2,…,L)分別為互異的非負整數序列。當預先設定的序列h(c)已知時,只需要根據IRCMS算法搜索序列g(r),并且確定P的取值范圍,即可使得所構造校驗矩陣對應Tanner圖[11]的圍長至少為8。

IRCMS算法的步驟如下:

輸入列重J和序列h={h1,h2,…,hL}

輸出序列g={g1,g2,…,gJ}

初始化g初始化為{0,1},令j=0。

步驟1如果j<(J-2),則轉至步驟2;否則結束,搜索完成。

步驟2令Y=t+1(t等于當前g中最后一個元素的值)。

步驟3在當前集合g中遍歷地選取任意2個不相同數g(i)和g(j),如果對于當前h中任意3個{hl,hm,hn}∈h都滿足:

(Y-g(i))(hn-hl)=(g(j)-g(i))(hm-hl)

(3)

那么設置flag=1;否則,設置flag=0。

步驟4如果flag=1,令Y=Y+1,返回至步驟3;如果flag=0,令g=g∪Y,j=j+1,返回至步驟1。

由上可知,指數矩陣E可以由IRCMS算法所確定,根據文獻[12]中的定理1可知,當循環置換矩陣的維數P滿足:P>gmaxhmax時,所構造的QC-LDPC碼對應Tanner圖的圍長至少為8。

2 可快速編碼的大圍長QC-LDPC碼設計

2.1 校驗矩陣的構造方法

本節給出一種可快速編碼的大圍長QC-LDPC碼構造方法。該方法首先基于IRCMS算法構造圍長為8的全局校驗矩陣,然后采用CPM的行列循環移位使得校驗部分的子矩陣排列滿足一定的結構特性,最后對所得矩陣進行掩碼處理得到具有改進型準雙對角線結構的校驗矩陣。

1)基于IRCMS算法構造圍長為8的初始校驗矩陣,并且將全局校驗矩陣分成如下部分:

(4)

其中,Hk由P×P維CPM的行列循環移位構成的M×(N-M)矩陣陣列,對應于校驗矩陣H的信息位部分,Hp是由P×P的CPM構成M×M的矩陣陣列,對應于校驗矩陣H的校驗位部分。

本文所提出的改進型雙對角結構Hp矩陣如下:

(5)

其中,hi,j表示校驗部分矩陣Hp的第i行、第j列的子矩陣,當0

2)對H矩陣的最后三行的CPM向右循環移位。其中,Sr(i)表示對第i行的CPM同時向右循環移位Sr(i)位,i=M-2,M-1,M:

(6)

然后,對Hp矩陣第2列至第M-2列的CPM分別同時向左循環移位。其中,Sc(i)表示對Hp矩陣的第i列CPM同時向左循環移Sc(i)位,i=2,3,…,M-2:

Sc(i)=Ep(i-1,i)

(7)

定理1基矩陣E中存在序列(p1,p2,…,p2l),其中任意兩相鄰元素pi和pi+1(包括p1和p2l)位于同一行或者同一列,不相鄰元素位于不同行且不同列,則該序列構成長度為2l的環的充分必要條件為[12]:

(8)

引理1如果基于CPM構造的QC-LDPC碼沒有四環、六環存在,則對其校驗矩陣的若干行或列的CPM分別同時循環移位,若同行或者同列的CPM移位位數相同,該矩陣無四環、六環產生。

證明:

1) 若基于CPM構造的QC-LDPC碼的校驗矩陣無四環,根據定理1,對如圖1(a)所示的任意的兩行(i,j)、兩列(m,n),有:

Pi,m-Pi,n+Pj,n-Pj,m≠0(modP)

(9)

對其校驗矩陣的若干行或列的CPM分別同時向左或向右循環移位。首先,對如圖1(a)所示的兩行CPM分別同時進行循環移S1、S2位,則如圖1(b)所示的四環存在充要條件為:

(Pi,m+S1)-(Pi,n+S1)+(Pj,n+S2)-

(Pj,m+S2)=0(modP)

(10)

即:

Pi,m-Pi,n+Pj,m-Pj,n=0(modP)

(11)

但上式與式(9)矛盾,故四環存在條件不滿足,即該校驗矩陣沒有四環的存在。同理,對如圖1(a)所示的兩列CPM分別同時進行循環移S1、S2位,則圖1(c)所示的四環存在條件亦不滿足。故對校驗矩陣的若干行或列CPM同時進行循環移位,若同行或者同列的CPM移位位數相同,不會產生四環。

圖1 四環的不存在性示意圖

2) 若基于CPM構造的QC-LDPC碼的校驗矩陣無六環,則根據定理1,對圖2(a)所示的任意的三行(i,j,k)、兩列(m,n,l),有:

Pi,m-Pi,n+Pj,n-Pj,l+Pk,l-Pk,m≠0(modP)

(12)

對校驗矩陣若干行或列的CPM分別同時進行循環移位,對如圖2(a)所示的三行CPM同時循環移S1、S2、S3位后,如圖2(b)所示的六環存在充要條件為:

(Pi,m+S1)-(Pi,n+S1)+(Pj,n+S2)-

(Pj,l+S2)+(Pk,l+S3)-(Pk,m+S3)=

0(modP)

(13)

即:

Pi,m-Pi,n+Pj,n-Pj,l+Pk,l-Pk,m=0(modP)

(14)

但上式與式(12)矛盾,故六環存在條件不滿足,則校驗矩陣沒有六環。同理,對如圖2(a)所示的三列CPM分別同時進行循環移S1、S2、S3位,則如圖2(c)所示的六環存在條件亦不滿足。故校驗矩陣的若干行或列的CPM分別同時進行循環移位后,若同行或者同列的CPM移位位數相同,無六環產生。引理1證畢。

圖2 六環的不存在性示意圖

由引理1可知,上述行列循環移位操作不會使得校驗矩陣產生四環、六環,即不改變所構造的全局校驗矩陣的四環、六環特性。

3)對經過行列循環移位后的H矩陣進行掩碼處理。掩碼技術通常被簡單地用來采用一些全零矩陣替換相應位置P×P的CPM。對于一個由P×P的CPM所構成的M×N矩陣陣列H而言,設M(M,N)=(mj,l)0≤j

M?H=(mj,l·Hj,l)0≤j

(15)

如果mj,l=1,則mi,j·Hi,j=I(Pi,j);否則mj,l·Hj,l為P×P的I(-1)矩陣,即P×P的零矩陣。

為了使得最終所構造的校驗矩陣右半部分滿足式(5)所示結構,則M矩陣對應于Hp部分的Mp如下:

(16)

QC-LDPC碼校驗矩陣的較優行重分布為近似相等的二三個連續行重值[13]。由于Mp的行重為近似相等的2個值,因此為了在得到一個稀疏矩陣H的同時,優化碼字的度分布,則掩碼矩陣M的左半部分Mk的行重也需近似相等,從而使得所構造校驗矩陣H的行重為近似相等的二三個數值。

由于基于IRCMS算法構造圍長為8的H矩陣沒有四環、六環,因此經過掩碼處理后的H亦不會有四環、六環[14]。所以,本文基于IRCMS算法、行列循環置換和掩碼技術構造的可快速編碼QC-LDPC碼字保持了大圍長特性。

2.2 快速編碼算法與編碼復雜度分析

C=[S,P]

(17)

由于編碼向量C為校驗矩陣H的零空間,則在GF(2)域中可得:

(18)

根據式(5)的前M-3行結構,首先依次迭代至式(18)的第1行到第M-3行:

(19)

則可得校驗位向量Pi(i=2,3,…,M-2):

(20)

然后,迭代至式(18)的第M-2行至第M行:

(21)

將式(21)中3個等式相加,可得:

(22)

將式(22)代入到式(21)中,即可得:

(23)

編碼復雜度主要關注編碼過程的運算量、運算復雜度和編碼所需存儲的參數,運算量即乘法和加法次數,運算復雜度即運算量與碼長的變化關系。QC-LDPC碼的各個子矩陣都是稀疏矩陣,因此按照稀疏矩陣的運算方式可大大減小運算量。計算式(22)、式(23)中Pi的運算量如表1所示。

表1 編碼算法的運算量

在表1中,R表示碼率,N表示擴展之后的碼長,N=n×p,P表示校驗矩陣中CPM的維數。

從表 1 可明顯地看到,計算各個校驗分向量Pi的運算復雜度為O(N),即運算復雜度與碼長呈線性關系。因此,本節基于改進型準雙對角結構構造的可快速編碼QC-LDPC碼具有完全線性的編碼復雜度,編碼效率很高。

3 性能仿真與分析

本節通過仿真將本文構造的圍長為8、可快速編碼的QC-LDPC碼,與采用IRCMS算法構造圍長為8的規則QC-LDPC碼、基于PEG算法構造的QC-LDPC碼[15-16]和基于改進型DVB-S2碼[17]的性能分別做比較。仿真是在加性高斯白噪聲(Additive White GaussNoise,AWGN)信道下進行,采用二進制相移鍵控(Binary Phase Shift Keying,BPSK)方式進行調制,采用置信傳播(Belief Propagation,BP)算法進行譯碼,設置最大迭代次等于100。

首先,設置h={0,1,2,3,4,6,7,8,9,10},J=5。根據IRCMS算法,產生序列g={0,1,11,12,25}。由P>gmaxhmax取P=300。然后,根據式(6)和式(7)對所構造的H矩陣進行CPM的行列循環移位。最后,對CPM行列循環移位后的矩陣進行掩碼處理。所采用的掩碼矩陣如下:

(24)

1)當設置P=300時,由上述指數矩陣E=[Ek,Ep]可構造圍長為8、可快速編碼的(3 000,1 500)QC-LDPC碼。本文構造的不規則(3 000,1 500)QC-LDPC碼與文獻[15]中基于IRCMS算法構造圍長為8的(3 000,1 500)規則QC-LDPC碼的誤碼率(Bit Error Rate,BER)和誤幀率(Frame Error Rate,FER)性能對比如圖3所示。

圖3本文所構造的碼字與采用IRCMS算法構造的規則QC-LDPC碼的BER和FER性能對比

由圖3可知,本文構造的可快速編碼QC-LDPC碼譯碼的性能明顯優于基于IRCMS算法構造的圍長為8的規則QC-LDPC碼,在BER為10-5時,在編碼復雜度更低的基礎上,有0.15 dB左右的編碼增益。

將本文所構造的不規則(3 000,1 500)QC-LDPC碼與基于PEG算法構造的相同碼長、碼率、度分布的不規則QC-LDPC碼和圍長為6的隨機QC-LDPC碼進行比較。由圖4可知,本文所構造的碼字與基于PEG算法構造的不規則QC-LDPC碼性能相當,且本文所構造的碼字具有完全線性的編碼復雜度,編碼復雜度更低。與圍長為6的隨機QC-LDPC碼相比,本文所構造的碼字具有更加優越的性能,在誤碼率達到10-5時,碼字性能有0.2 dB的提升。

圖4本文所構造的碼字與基于PEG算法構造的QC-LDPC碼和隨機QC-LDPC碼的BER性能對比

2)當設置P=540時,可構造圍長為8、可快速編碼的(5 400,2 700)QC-LDPC碼,將這種碼字與文獻[17]中改進型DVB-S2碼相比,其仿真結果如圖5所示。

圖5本文所構造的碼字與改進型DVB-S2碼字的BER性能對比

由圖5可知,與文獻[17]中改進型的DVB-S2碼相比,本文所構造的可快速編碼的QC-LDPC碼不僅同樣具有可快速編碼特性,而且性能有了一定的提升,在誤碼率達到10-5時,其碼字性能提高了0.1 dB左右。

4 結束語

本文基于IRCMS算法、CPM的行列循環移位以及掩碼技術提出一種圍長為8、可快速編碼的QC-LDPC碼構造方法。該方法所構造的QC-LDPC碼不僅保持了圍長至少為8的特性,而且還可以利用該改進型準雙對角線結構的校驗矩陣直接進行簡單快速的編碼,在保證優異性能的同時,降低了QC-LDPC碼的編碼復雜度。仿真結果表明,本文所構造的碼字不僅具有線性的編碼復雜度,而且性能較優。與已有的確定性構造方法相比,該方法是一種基于計算機搜索的構造方法,雖然比較靈活,但為滿足各種約束條件,沒有解決碼的存在性問題,存在構造失敗的可能性,下一步將針對上述問題進行改進。

[1] MACKAY D J C,NEAL R M.Near Shannon Limit Performance of Low Density Parity Check Codes[J].Electronics Letters,1996,32(18):1645-1646.

[2] GALLAGER R G.Low-density Parity-check Codes[J].IRE Transactions on Information Theory,1962,8(1):21-28.

[3] MACKAY D J C.Good Error-correcting Codes Based on Very Sparse Matrices[J].IEEE Transactions on Information Theory,1999,45(2):399-431.

[4] FOSSORIER M P C.Quasi-cyclic Low-density Parity-check Codes from Circulant Permutation Matrices[J].IEEE Transactions on Information Theory,2004,50(8):1788-1793.

[5] 焦新泉,陳建軍,單彥虎.基于 BIBD 和循環置換矩陣的 LDPC碼[J].計算機工程,2012,38(2):282-283.

[6] MYUNG S,YANG K,KIM J.Quasi-cyclic LDPC Codes for Fast Encoding[J].IEEE Transactions on Information Theory,2005,51(8):2894-2901.

[7] WANG H,CHEN S,ZHU C,et al.A Novel QC-LDPC Code with Flexible Construction and Low Error Floor[C]//Proceedings of the 16th International Conference on Advanced Communication Technology.Washington D.C.,USA:IEEE Press,2014:431-436.

[8] IEEE.Part 16:Air Interface for Fixed and Mobile Broadband Wireless Access Systems[S].New York,USA:Institute of Electrical and Electronics Engineering,2006.

[9] WANG R,LI Y,ZHAO H,et al.Construction of Girth-eight Quasi-cyclic Low-density Parity-check Codes with Low Encoding Complexity[J].IET Communications,2016,10(2):148-153.

[10] WANG L,ZHANG X,YU F,et al.QC-LDPC Codes with Girth Eight Based on Independent Row-column Mapping Sequence[J].IEEE Communications Letters,2013,17(11):2140-2143.

[11] TANNER R M.A Recursive Approach to Low Complexity Codes[J].IEEE Transactions on Information Theory,1981,27(5):533-547.

[12] 彭 立,朱光喜.QC-LDPC 碼的置換矩陣循環移位次數設計[J].電子學報,2010,38(4):786-790.

[13] KANG J,HUANG Q,ZHANG L,et al.Quasi-cyclic LDPC Codes:An Algebraic Construction[J].IEEE Transactions on Communications,2010,58(5):1383-1396.

[14] KAMIYA N.Efficiently Encodable Irregular QC-LDPC Codes Constructed from Self-reciprocal Generator Polynomials of MDS Codes[J].IEEE Communications Letters,2010,14(9):1-3.

[15] LI Z,KUMAR K V.A Class of Good Quasi-cyclic Low-density Parity Checks Code Based on Progressive Edge Growth Graph [C]//Proceedings of Conference on Signals,Systems & Computers.Washington D.C.,USA:IEEE Press,2004:1990-1994.

[16] JIANG X,XIA X G,LEE M H.Efficient Progressive Edge-growth Algorithm Based on Chinese Remainder Theorem[J].IEEE Transactions on Communications,2014,62(2):442-451.

[17] 肖 揚,范 俊,黃 希.DVB-S2標準的LDPC碼改進[J].鐵道學報,2011,33(2):52-59.