基于偏移量周期填充的QC-LDPC碼構造方法

趙 明, 劉志鵬, 趙 嶺

(1. 中國電子科技集團公司 電子科學研究院, 北京 100041； 2. 北京航空航天大學 電子信息工程學院, 北京 100191)

0 引 言

低密度奇偶校驗卷積(LDPC-C: Low Density Parity-Check Convolutional)碼是定義在稀疏奇偶校驗矩陣上的一類卷積碼[1-2], 其可對任意長度的數(shù)據(jù)進行連續(xù)編碼和譯碼, 因此可以很好地應用于可變幀長的通信(如無線局域網(wǎng))或連續(xù)模式的通信(如視頻通信、 中繼衛(wèi)星高速數(shù)傳)系統(tǒng)中[3]。LDPC-C碼具有接近香農(nóng)(Shannon)極限的譯碼性能和較低的編碼復雜度[1-2,4]。其中準循環(huán)低密度奇偶校驗卷積(QC-LDPC-C: Quasi-Cyclic LDPC-C)碼對應的半無窮校驗矩陣由一組循環(huán)移位矩陣(CPMs: Circulant Permutation Matrices)構成, 從而易于高效編碼和譯碼, 且便于硬件實現(xiàn)[5-6]。

目前, 構造LDPC-C碼需通過對LDPC分組碼進行校驗矩陣拆解。文獻[1]提出基于LDPC分組碼的校驗矩陣并利用剪切、交換和重復的方法構造LDPC-C碼。利用QC-LDPC分組碼的循環(huán)移位子矩陣構造LDPC-C碼對應的校驗矩陣[5], 可簡化矩陣構造的復雜度。文獻[7]提出在LDPC-C碼的構造中, 采用LDPC分組碼的漸進邊增長(PEG: Progressive Edge-Growth)構造方法。文獻[8]提出利用LDPC碼, 并采用基于圖覆蓋的方法構造LDPC-C碼, 所構造的LDPC-C碼性能優(yōu)于相應的LDPC分組碼, 同時分析了其中的卷積增益。文獻[9]提出利用有限域的乘群, 并采用相關的修正方法獲得可實現(xiàn)快速編碼的LDPC-C碼。此外, 還有其他構造LDPC-C碼對應校驗矩陣的方法[10-12]。

LDPC-C譯碼算法利用基于校驗矩陣行的置信度傳播(BP: Belief Propagation)迭代計算完成, 因此LDPC-C碼, 特別是QC-LDPC-C碼對應校驗矩陣需考慮短環(huán)問題[13-14]。雖然LDPC-C碼可利用對應的LDPC分組碼進行構造, 但需對LDPC分組碼對應的校驗矩陣進行剪切、 交換和復制等操作, 而此時會改變矩陣的結構, 特別當LDPC-C碼的碼長、 記憶長度和周期為隨機的正整數(shù)時, 無法確保得到的LDPC-C碼對應校驗矩陣不存在4環(huán)。并且, 若不考慮LDPC-C碼對應校驗矩陣的結構特點, 直接構造校驗矩陣, 將會使構造算法的計算復雜度呈指數(shù)增長[15-22]。

為獲得較好的譯碼性能, 盡可能提高所構造碼的圍長(girth)并避免短環(huán), 特別是4環(huán)的存在, 筆者提出基于子矩陣偏移量周期性填充的QC-LDPC-C碼構造方法。同時, 考慮到可實現(xiàn)快速編碼, 在QC-LDPC-C碼對應校驗矩陣的構造中, 令每個校驗行塊中最右端子矩陣的校驗部分子矩陣滿足行和列的非負值個數(shù)均為1。所提構造方法基于QC-LDPC-C碼對應的基矩陣構造, 利用基矩陣的周期性, 首先填充確定的校驗行塊中校驗部分子矩陣的位置；而后利用基于子矩陣偏移量周期性擴展填充的方法, 周期性擴展所填充的對應位置, 并在周期性擴展每個對應位置時, 使由周期性確定的位置與即將填充的位置構成的矩陣可滿足無4環(huán)的擴展矩陣結構。因此, 所構造的由基矩陣擴展的校驗矩陣不存在4環(huán), 即校驗矩陣的圍長至少為6。利用所提方法構造的QC-LDPC-C碼可實現(xiàn)快速編碼, 降低編碼復雜度, 同時可獲得較好的譯碼性能。

1 QC-LDPC-C碼的主要構造框架

為降低譯碼設計實現(xiàn)的復雜度, 所構造的QC-LDPC-C碼對應的校驗矩陣H由基矩陣Hb擴展得到, 其中子矩陣擴展因子為b。對于碼率為R=k0/n0的(n0b0,k0b0,M)QC-LDPC-C碼, 其基矩陣

(1)

其中Bi(t)(i=0,1,…,M,t∈)是mb×nb=(m0b0/b)×(n0b0/b)階矩陣。Hb中元素的取值范圍為{-1,0,1,…,b-1}, 若元素為-1, 則擴展得到的子矩陣即為全零矩陣； 若元素為其他值, 則擴展為循環(huán)移位單位矩陣(CPIM: Circulant Permutation Identity Matrix), 元素值即為子矩陣的循環(huán)移位偏移量。

k0,n0的最大公約數(shù)是1, 且任意Bi(t)(i=0,1,…,M,t∈)是m0b0×n0b0=(n0-k0)b0×n0b0階二元矩陣。其中M為碼組的記憶塊長度, 而ns=(M+1)n0b0為碼的約束長度。若式(1)滿足Bi(t+T)=Bi(t)(i=0,1,…,M,t∈), 則該碼為周期性時變QC-LDPC-C碼； 當T=1時, 該碼為時不變QC-LDPC-C碼。

為簡化校驗矩陣設計的復雜度, 同時考慮到校驗矩陣的行重和列重分布, 在校驗矩陣的構造中不能直接利用b0進行矩陣框架的構造, 否則可能無法滿足所設計的行重和列重。因此, 提出利用子矩陣擴展因子b構造校驗矩陣, 其中b0是b的整數(shù)倍。

2 基于偏移量周期性填充高效構造QC-LDPC-C碼

2.1 QC-LDPC-C碼對應校驗矩陣的可快速編碼結構

為利用迭代計算的方式實現(xiàn)快速編碼, 需對QC-LDPC-C碼對應基矩陣Hb的每行進行設計。這里要求Hb中B0(t)(t∈)的校驗部分子矩陣滿足行和列的非負數(shù)個數(shù)均為1(見圖1)。

圖1 B0(t)(t∈)的校驗部分子矩陣的行和列非負數(shù)個數(shù)分布Fig.1 The numbers of non-negative values in each row and column of parity-check portion in B0(t)(t∈)

由圖1可知,B0(t)(t∈)的校驗部分子矩陣中各行非負值的位置集合是其所有可能行位置的排列組合, 即所有行不存在重復的非負值行位置。

同時, 為實現(xiàn)正確的基于迭代計算的快速編碼, 需基矩陣Hb的每行中非負數(shù)的個數(shù)至少為2, 即要求每行除B0(t)(t∈)對應的校驗部分外, 其余位置的非負數(shù)的個數(shù)至少為1。

2.2 基于偏移量周期性填充的QC-LDPC-C碼構造

2.2.1 無4環(huán)的擴展矩陣結構

圖2所示的基校驗矩陣中存在4環(huán), 其中Mi(1≤i≤4)為H中的非零子矩陣。此時若要求擴展后的矩陣不存在4環(huán), 則

mod(q(M1)-q(M2),b)≠mod(q(M3)-q(M4),b)

(2)

其中q(Mi)表示非零子矩陣Mi的循環(huán)右移數(shù)值, mod(a,b)表示a對b整除后求余。

圖2 非零子矩陣M1,M2,M3,M4在H中的位置處于4環(huán)結構中Fig.2 The positions of non-zero sub-matrices M1,M2,M3,M4 in H are in an length-4 cycle

2.2.2 基于偏移量周期性填充方法

在構造QC-LDPC-C碼對應的基校驗矩陣時, 可首先利用行位置的排列組合方法確定B0(t)中校驗部分子矩陣非負數(shù)的位置。

將式(1)中QC-LDPC-C碼對應基校驗矩陣Hb的周期假定為T, 則在確定其余非負數(shù)的位置上, 比特填充的周期也為T, 同時在周期為T的對應位置上填充相同的值。因此, 只需完成周期T內(nèi)的列構成的子矩陣的構造即可。同時為降低設計和計算的復雜度, 將校驗矩陣H的圍長設置為6, 即不存在4環(huán)。所以, 只需檢驗矩陣Hb中(T+2M)個包含完整約束長度的行構成的子矩陣的短環(huán)即可。于是, 筆者提出基于偏移量周期性填充的QC-LDPC-C碼構造方法。

由于所考慮的基校驗矩陣Hb的周期為T, 所以若Hb中存在4環(huán), 則4環(huán)的一條豎邊必在周期為T的校驗列內(nèi), 因此4環(huán)的結構必在周期為T的校驗列所包含的檢驗行中。同時, 所構造的部分基校驗矩陣需使前Mmb行的行重至少為2, 因此所考慮的部分基校驗矩陣為

(3)

假定已經(jīng)構建了n(n≥0)列的校驗矩陣HB滿足所有的約束條件, 即對k=1,2,…,N, 第k列的列重正好為ak； 并且相應二分圖的girth滿足g≥6?，F(xiàn)在考慮增加第(n+1)列到校驗矩陣HB中, 新增的列用包含元素的個數(shù)至多為an+1的校驗節(jié)點集合U1表示, 初始化為空。進一步假定, 已經(jīng)在U1中加入了i(0≤i≤an+1)個校驗節(jié)點。

對任一個校驗節(jié)點1≤c≤M,Nc是指與c共享變量節(jié)點的所有校驗節(jié)點的集合。對j≥2, 定義

(4)

顯然U2中每個校驗節(jié)點肯定與U1中某個校驗節(jié)點存在長度為2的路徑。增加一個校驗節(jié)點c′到U1中, 則c′和U1的每個校驗節(jié)點間都存在一條長度為2的路徑, 所以如果c′也出現(xiàn)在U2中, 就可確定長度為4的環(huán)的存在。因此為避免長度為4的環(huán), 應該避免這個校驗節(jié)點在U2中出現(xiàn)。因此, 為滿足girth限制, 應盡量避免將集合U中的校驗節(jié)點加到U1中。集合

U=U1∪U2

(5)

令D(c)為校驗節(jié)點c的度數(shù), 同時令

A= {c∈{1,2,…,M}|D(c)

(6)

其中A是還沒有達到最大重量的校驗節(jié)點集, 則沒有違反girth約束的可加到U1的校驗節(jié)點集合即為A集合與U集合的差值, 可表示為

F0=AU

(7)

如果F0為空, 當前girth將減少2； 如果g′降到小于4, 則算法停止。

于是, 提出的QC-LDPC-C碼的構造方法如算法1所示。

算法1

輸入?yún)?shù)：mb,nb,M,T,smax,{a1,a2,…,anbT}, {br1,br2,…,br(M+T)mb}, {P1,P2,…,PT}

填充確定的子矩陣部分：

1) Fori=0;i≤T-1;i=i+1

2) Forj=1;j≤mb;j=j+1

3) 確定B0(i)(Pi(j),nb-mb+1)的值

4) End For

5) End For

6) Fori=T;i≤T+2M-1;i=i+1

7) If mod(i,T)=0

8)B0(i)=B0(T)

9) Else

10)B0(i)=B0(mod(i,T))

11) End If

12) End For

13) Forc=1;c≤mb(T+2M);c=c+1

14)D(c)=1;Nc={c}

15) End For

填充隨機子矩陣部分：

17) Fort=0;t

18) Forn=0;n

19) Ifn≥nb-mb+1

20)A={mb(t+1)+1,mb(t+1)+2,…,mb(t+M+1)}

21)anT=anT-1

22) Else

23)A={mbt+1,mbt+2,…,mb(t+M+1)}

24) End If

26) Fors=0; (t+sT+i<=T+2M-1);s=s+1

27) 設置Bi(t+sT+i)(j,n)的數(shù)值

28) End For

30) Fori=0;i

31) sel_flag=0;

32) Forg′=g_max; (g′>=4sel_flag=0);g′=g′-2

33) 計算F0=AU0

34) If(g′≥6&&F0≠φ)‖g′=4

35) Ifg′=4

36) 依據(jù)算法2中的算法從F1中選擇c*

37) Else

38) 依據(jù)文獻[16]中的算法從F0中選擇c*

39) End If

40) sel_flag=1,F1=F1c*

41)ii=?c*/mb」

42) Fors=0; (t+sT+ii<=T+2M-1);s=s+1

49)b=br-counter,A=A∩{?d|D(d)

50) End If

51) End For

52) Else

54) End If

55) End For

56) End For

57) End For

58) End For

輸出參數(shù)：HB,g′

最后, 更新U=U∪V2(c)。只有當girth降低2時, 才需重新計算U。算法1的目的即加入第(i+1)個校驗節(jié)點到U1中。如果失敗, 整個算法將停止。

這里為降低計算復雜度, 對搜索的次數(shù)進行了簡化。由于構造的基校驗矩陣僅考慮不存在4環(huán), 因此將循環(huán)搜索的次數(shù)設置為2, 由此可令構造矩陣的圍長至少為6。

在算法1中, 從F1中選擇c*的算法如下。

算法2

1) ?c∈F1, 令U1(c)={c}；

2) ?c∈F1, 計算U2(c), 并計算T0(c)=U2(c)∩U0；

3) ?c∈F1, 計算S1(c)=|T0(c)|, 計算T1={c1∈F1: ?c2∈F1,S1(c1)≤S1(c2)}；

4) ?c∈T1, 計算S2(c)=D(c), 計算T2={c1∈T1: ?c2∈T1,S2(c1)≤S2(c2)}；

5) 從T2中選擇c*。

注意到算法1中, 如果已經(jīng)添加了一個校驗節(jié)點c到U1中, 然后設U1={c}, 并且計算

(8)

V2(c)=U1(c)∪U2(c)

(9)

算法1中的構造流程示意圖如圖3所示。假定構造的基矩陣Hb的列重均為3, 且Hb的周期為T。若矩陣Hb的參數(shù)設置為其他數(shù)值, 則可采用類似的方法進行構造。

圖3 所提構造方法的流程示意圖Fig.3 The flow diagram of proposed construction method

由于矩陣Hb的周期為T, 因此只要完成前Tnb列的構造, 即可依據(jù)矩陣的周期性得到Hb。在算法1中, 首先根據(jù)每個行塊中B0(t),t∈[0,T-1]的校驗部分子矩陣滿足行和列的非負數(shù)個數(shù)均為1, 確定一個周期內(nèi)B0(t)的校驗部分子矩陣中非負值的位置, 而后進行周期性擴展, 即填充確定的子矩陣部分(圖3中標記X的方格)。

在矩陣Hb的隨機子矩陣部分的構造中, 只需得到前Tnb列的非負值位置即可, 而所要完成周期性填充的部分基校驗矩陣HB的總列數(shù)為(T+2M)nb。因此, 在確定前Tnb列的每個非負值位置后, 需依據(jù)矩陣HB的周期, 填充以T為周期的對應位置(即完成第26～28行, 也即圖3中周期T內(nèi)未標記X的位置)。

由于需確定非負值位置的矩陣HB的總列數(shù)為(T+2M)nb, 因此在針對矩陣Hb的前Tnb列的構造中, 每個即將填充的非負值位置及其周期擴展后填充的位置都要與已填充的位置及其周期擴展后填充的位置構成聯(lián)合矩陣, 并依據(jù)式(2)對此聯(lián)合矩陣進行擴展矩陣結構4環(huán)檢驗。

于是, 利用所提的基于子矩陣偏移量周期性擴展填充的方法, 即可得到部分基校驗矩陣HB的非負值位置, 而后依據(jù)矩陣的周期性, 得到基校驗矩陣Hb的非負值位置。并且在構造過程中使Hb滿足無4環(huán)的擴展矩陣結構的要求, 于是可確保由矩陣Hb擴展后得到的檢驗矩陣的圍長至少為6, 即不存在4環(huán)。

2.2.3 計算復雜度分析

依據(jù)式(3)給出的部分基校驗矩陣HB和算法1, 算法1中填充確定子矩陣部分可在O((T+M)mb)(即線性復雜度)內(nèi)完成。

對算法1中的填充隨機子矩陣部分, 假定構造的部分基校驗矩陣HB的行、 列重平均值分別為a和b, 第33行計算A和U0的差集, 可在O((T+M)mb)內(nèi)完成。針對聯(lián)合矩陣中存在無4環(huán)結構的情形, 執(zhí)行第36行從F1中選擇c*(即算法2), 在最復雜的情形下需O(((T+M)mb)2)次運算。而針對聯(lián)合矩陣中存在4環(huán)的情形, 執(zhí)行第38行從F0中選擇c*[16], 在最復雜的情形下也需要O(((T+M)mb)2)次運算。

于是, 每執(zhí)行一次第30～56行的“For…End For”內(nèi)循環(huán), 復雜度為O(((T+M)mb)2)。這個循環(huán)最多執(zhí)行a次, 復雜度為O(a((T+M)mb)2)。最后, 第 17～58行的兩層外循環(huán)“For…End For”最多執(zhí)行bT(T+M)mb/a次, 所以算法總體復雜度為

O(a((T+M)mb)2bT(T+M)mb/a)=O(bT((T+M)mb)3)

利用算法構造QC-LDPC-C碼對應基校驗矩陣時, 算法的總體計算復雜度如表1所示。

表1 構造算法總體的計算復雜度

3 實驗結果與討論

為驗證構造算法的譯碼性能, 使用具有不同碼率和碼長的LDPC-C碼的校驗矩陣進行仿真實驗。實驗是在二進制移相鍵控(BPSK： Binary Phase Shift Keying)調(diào)制和加性高斯白噪聲(AWGN： Additive White Gaussian Noise)信道條件下, 使用不同的迭代次數(shù)及信噪比(SNRs： Signal to Noise Ratios)條件, 其中最大迭代次數(shù)為30次。針對IEEE 1901標準中LDPC-C碼[3], 利用LBP譯碼算法所得的誤碼率(BER： Bit Error Rate,RBER)性能如圖4所示。

在圖4中, 碼Ref-CC12-1901和Ref-CC23-1901分別是IEEE 1901標準中碼率為1/2和2/3的LDPC-C碼[3]。構造的QC-LDPC-C碼CC-1和CC-2分別與碼Ref-CC12-1901和Ref-CC23-1901具有相同的碼率和行列重分布, 且兩個碼的周期均為3。其中碼CC-1對應基矩陣的每個元素包含2列, 子矩陣擴展因子為2, 記憶塊長度為108； 碼CC-2對應基矩陣的每個元素包含3列, 子矩陣擴展因子為3, 記憶塊長度為76。

圖4表明, 構造碼CC-1和CC-2的譯碼性能均優(yōu)于標準中對應的碼Ref-CC12-1901和Ref-CC23-1901。在圖4中, CC-1和CC-2可利用構造的基校驗矩陣實現(xiàn)基于迭代計算的快速編碼, 即此時的編碼復雜度只與基校驗矩陣的行數(shù)和列重相關, 并且其譯碼過程可直接采用構造的基校驗矩陣進行迭代計算。而Ref-CC12-1901和Ref-CC23-1901在編碼過程中需要存儲和利用完整的校驗矩陣進行計算, 并且譯碼也需基于較為復雜的校驗矩陣進行迭代計算。因此, CC-1和CC-2具有相對較低的編譯碼復雜度。

圖4 碼Ref-CC12-1901與CC-1, Ref-CC23-1901 圖5 碼Ref-CC2與CC-3在不同的 與CC-2在不同的SNR條件下的BER性能 SNR條件下的BER性能 Fig. 4 BER performance of the codes Ref-CC12-1901, Fig. 5 BER performance of the codes Ref-CC2 CC-1, Ref-CC23-1901 and CC-2 under different SNRs and CC-3 under different SNRs

圖5所使用的碼Ref-CC2為基于LDPC碼構造的碼率為2/3, 約束長度為2520的LDPC-C碼[8]。構造的QC-LDPC-C碼CC-3具有相同的碼率和約束長度, 其對應基矩陣的每個元素包含4列, 子矩陣擴展因子為64, 碼的周期為10。圖5表明構造碼CC-3比碼Ref-CC2有更好的性能, 同時碼CC-3具有較低的編譯碼復雜度。

由圖4和圖5可見, 采用筆者提出的方法構造的QC-LDPC-C碼在相同或相近的條件下, 可獲得更好的譯碼性能。同時, 由于構造碼均為具有可實現(xiàn)快速編碼的準循環(huán)碼, 于是這些碼相對具有較低的編譯碼復雜度, 更易于設計實現(xiàn)。

4 結 語

QC-LDPC-C碼具有較低的編譯碼復雜度, 同時經(jīng)過優(yōu)化設計的碼可獲得逼近Shannon極限的譯碼性能, 并可對任意長度的數(shù)據(jù)進行連續(xù)編譯碼。但QC-LDPC-C碼的構造需避免4環(huán), 并且其校驗矩陣的直接構造方法的計算復雜度較高。于是, 筆者提出基于偏移量周期性填充的QC-LDPC-C碼構造方法。依據(jù)QC-LDPC-C碼對應的基校驗矩陣的周期性, 所提方法首先確定校驗行塊中最右端子矩陣的校驗部分子矩陣的位置；而后在針對每個列中每個變量節(jié)點的選擇時, 使由周期性確定的位置與即將填充的位置構成的矩陣能滿足擴展后的校驗矩陣的圍長至少為6。同時, 所提構造方法的計算復雜度相對較低, 具有校驗行數(shù)的3次方的復雜度。實驗結果表明, 基于所提方法構造的QC-LDPC-C碼對應基校驗矩陣的擴展矩陣無4環(huán), 并可獲得較好的譯碼性能, 同時具有較低的編譯碼復雜度。另外, 所提的周期性比特填充方法也可用于其他卷積碼的構造。