趙 明, 劉志鵬, 趙 嶺

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

0 引 言

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

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

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

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

1 QC-LDPC-C碼的主要構(gòu)造框架

為降低譯碼設(shè)計實現(xiàn)的復(fù)雜度, 所構(gòu)造的QC-LDPC-C碼對應(yīng)的校驗矩陣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碼。

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

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

2.1 QC-LDPC-C碼對應(yīng)校驗矩陣的可快速編碼結(jié)構(gòu)

為利用迭代計算的方式實現(xiàn)快速編碼, 需對QC-LDPC-C碼對應(yīng)基矩陣Hb的每行進行設(shè)計。這里要求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∈)的校驗部分子矩陣中各行非負值的位置集合是其所有可能行位置的排列組合, 即所有行不存在重復(fù)的非負值行位置。

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

2.2 基于偏移量周期性填充的QC-LDPC-C碼構(gòu)造

2.2.1 無4環(huán)的擴展矩陣結(jié)構(gòu)

圖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)結(jié)構(gòu)中Fig.2 The positions of non-zero sub-matrices M1,M2,M3,M4 in H are in an length-4 cycle

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

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

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

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

(3)

假定已經(jīng)構(gòu)建了n(n≥0)列的校驗矩陣HB滿足所有的約束條件, 即對k=1,2,…,N, 第k列的列重正好為ak； 并且相應(yīng)二分圖的girth滿足g≥6。現(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), 應(yīng)該避免這個校驗節(jié)點在U2中出現(xiàn)。因此, 為滿足girth限制, 應(yīng)盡量避免將集合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碼的構(gòu)造方法如算法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) 設(shè)置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中。如果失敗, 整個算法將停止。

這里為降低計算復(fù)雜度, 對搜索的次數(shù)進行了簡化。由于構(gòu)造的基校驗矩陣僅考慮不存在4環(huán), 因此將循環(huán)搜索的次數(shù)設(shè)置為2, 由此可令構(gòu)造矩陣的圍長至少為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中, 然后設(shè)U1={c}, 并且計算

(8)

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

(9)

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

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

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

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

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

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

2.2.3 計算復(fù)雜度分析

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

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

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

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

利用算法構(gòu)造QC-LDPC-C碼對應(yīng)基校驗矩陣時, 算法的總體計算復(fù)雜度如表1所示。

表1 構(gòu)造算法總體的計算復(fù)雜度

3 實驗結(jié)果與討論

為驗證構(gòu)造算法的譯碼性能, 使用具有不同碼率和碼長的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]。構(gòu)造的QC-LDPC-C碼CC-1和CC-2分別與碼Ref-CC12-1901和Ref-CC23-1901具有相同的碼率和行列重分布, 且兩個碼的周期均為3。其中碼CC-1對應(yīng)基矩陣的每個元素包含2列, 子矩陣擴展因子為2, 記憶塊長度為108； 碼CC-2對應(yīng)基矩陣的每個元素包含3列, 子矩陣擴展因子為3, 記憶塊長度為76。

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

圖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碼構(gòu)造的碼率為2/3, 約束長度為2520的LDPC-C碼[8]。構(gòu)造的QC-LDPC-C碼CC-3具有相同的碼率和約束長度, 其對應(yīng)基矩陣的每個元素包含4列, 子矩陣擴展因子為64, 碼的周期為10。圖5表明構(gòu)造碼CC-3比碼Ref-CC2有更好的性能, 同時碼CC-3具有較低的編譯碼復(fù)雜度。

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

4 結(jié) 語

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