基于完備循環(huán)差集的type-Ⅱ QC-LDPC碼的構(gòu)造

黃 勝, 宋 靜, 袁建國

(重慶郵電大學(xué)光通信及網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室, 重慶 400065)

0 引 言

低密度奇偶校驗(yàn)(low-density parity-check, LDPC)碼[1]是線性分組碼的一種,因其性能良好,廣泛應(yīng)用在許多領(lǐng)域。2016年,LDPC碼作為5G的標(biāo)準(zhǔn)碼重新引起世人的關(guān)注,對(duì)于準(zhǔn)循環(huán)(quasi-cyclic)低密度奇偶校驗(yàn)(quasi-cyclic low-density parity check,QC-LDPC)碼[2]來講,若校驗(yàn)矩陣H僅由單位循環(huán)置換矩陣(circulant permutation matrices, CPM)或零矩陣(zero matrices, ZM)構(gòu)成,其對(duì)應(yīng)的碼字為type-I QC-LDPC碼[3],多數(shù)文獻(xiàn)中構(gòu)造的碼都屬于type-I QC-LDPC碼[4-7]。若校驗(yàn)矩陣中不僅包含ZM、CPM,還含有權(quán)重為2的循環(huán)置換矩陣(weight-2 circulant permutation matrices, W2-CPM),其對(duì)應(yīng)碼字為type-Ⅱ QC-LDPC碼,其最小距離的上界值比type-I QC-LDPC碼的更大(任意(J,L)規(guī)則type-I QC-LDPC碼最小距離上界值為dmin≤(J+1)![8],而type-Ⅱ QC-LDPC碼的最小距離上界值為dmin≤(J+1)!2J[9])。最小距離又與碼的檢、糾錯(cuò)能力息息相關(guān),最小距離值越大,碼的檢錯(cuò)、糾錯(cuò)能力越強(qiáng)。由于type-Ⅱ QC-LDPC碼中僅含權(quán)重為2的循環(huán)矩陣W2-CPM,導(dǎo)致Tanner圖中更易出現(xiàn)短環(huán),影響譯碼性能,出現(xiàn)錯(cuò)誤平層。文獻(xiàn)[10]主要分析了type-Ⅱ QC-LDPC碼中的W2-CPM對(duì)最小距離上界值以及譯碼性能的影響。文獻(xiàn)[11]基于sidon序列構(gòu)造的type-Ⅱ QC-LDPC碼,其校驗(yàn)矩陣H中僅包含W2-CPM,Tanner圖中含有大量的6環(huán)導(dǎo)致譯碼性能下降。文獻(xiàn)[12]基于完備循環(huán)差集構(gòu)造的type-Ⅱ QC-LDPC碼,其校驗(yàn)矩陣是滿秩的且包含ZM、CPM和W2-CPM的3種形式的子矩陣,校驗(yàn)矩陣具有中心對(duì)稱結(jié)構(gòu),圍長至少為8,但由于8環(huán)的數(shù)量過多影響了譯碼性能。文獻(xiàn)[13]基于有限域構(gòu)造的type-Ⅱ QC-LDPC碼的校驗(yàn)矩陣同樣包含ZM、CPM和W2-CPM子矩陣,但文中并未給出具體的仿真實(shí)驗(yàn)結(jié)果,而僅有理論分析。文獻(xiàn)[14]基于完備循環(huán)差集,構(gòu)造了一種新穎的可快速編碼的非規(guī)則type-Ⅱ QC-LDPC碼,但因其含有短環(huán),影響了迭代譯碼收斂速度,導(dǎo)致迭代譯碼性能下降。

基于此,本文構(gòu)造一種type-Ⅱ QC-LDPC碼,其圍長至少為8,且8環(huán)的數(shù)量較少,迭代譯碼性能優(yōu)異。首先構(gòu)造校驗(yàn)矩陣H,校驗(yàn)矩陣具有近似雙對(duì)角的結(jié)構(gòu),再由完備循環(huán)差集填充,用CPM、ZM和W2-CPM的矩陣擴(kuò)展校驗(yàn)矩陣H,通過推理證明校驗(yàn)矩陣中不含4、6環(huán)。由仿真實(shí)驗(yàn)結(jié)果可知,在迭代譯碼時(shí),本文構(gòu)造的type-Ⅱ QC-LDPC碼無明顯的錯(cuò)誤平層。

1 完備循環(huán)差集

定義1設(shè)v為正整數(shù),取加法群Zv={0,1,2…,v-1}中的t個(gè)子集,每個(gè)子集包含k個(gè)元素,即Di={d1,d2,…,dk},i=1,2…t,m≠n,m,n=1,2…k,滿足Zv中每個(gè)非零元素在(dm-dn)modv運(yùn)算時(shí),其值恰好出現(xiàn)λ次,則集合Di被定義為一組t-(v,k,λ)循環(huán)差集(cyclic difference families, CDF)[15]。當(dāng)循環(huán)差集參數(shù)為t=1,λ=1,v=k2-k+1時(shí),稱為完備循環(huán)差集[14],完備循環(huán)差集的特性,即Di中的任意兩個(gè)元素dm、dn,作(dm-dn)modv運(yùn)算其值各不相同。對(duì)于(7,3,1)-完備循環(huán)差集,D={0,1,3}的差集表如表1所示[16]。在差集表中,除0元素外,其余元素具有相異性。

表1 完備循環(huán)差集{0,1,3}mod7的差集表

Table 1 Difference table of mod 7 pefect cycle difference family {0,1,3}

2 Type-Ⅱ QC-LDPC碼

設(shè)J,L,p為正整數(shù),則碼長為N=Lp,Type-Ⅱ QC-LDPC碼校驗(yàn)矩陣H的結(jié)構(gòu)如式(1)所示[17]。

(2)

3 基于完備循環(huán)差集的Type-Ⅱ QC-LDPC碼

3.1 構(gòu)造方法:

基矩陣的構(gòu)造過程如下所示:

圖1 構(gòu)造的基矩陣E的結(jié)構(gòu)Fig.1 Structure of constructed base matrix E

步驟2令擴(kuò)展因子為p,大小等于差集的模p=v,將基矩陣E中元素對(duì)分別替換為p×p大小的矩陣,權(quán)重為2的循環(huán)矩陣I(dm)+I(dn),用大小為p×p的單位矩陣替換基矩陣的0元素,用p×p的零矩陣0替換∞元素,從而獲得校驗(yàn)矩陣。

通過以上步驟構(gòu)造出基矩陣,既保留了Type-Ⅱ QC-LDPC碼最小距離上界值大的優(yōu)點(diǎn),同時(shí)利用構(gòu)造的近似雙對(duì)角結(jié)構(gòu)與完備循環(huán)差集的特性結(jié)合,避免了短環(huán)的出現(xiàn),而且構(gòu)造出的碼字具有良好的檢、糾錯(cuò)性能。

3.2 圍長分析

(3)

滿足jn=j0,ln=l0,t2n=t0,當(dāng)jk=jk+1時(shí),t2k≠t2k+1;當(dāng)lk=lk+1時(shí),t2k≠t2k+2。

3.2.1 無四環(huán)證明

引理1對(duì)于所有j0、j1,0≤j0≠j1≤J,所有l(wèi)0、l1,0≤l0≠l1≤L-1,以及所有ti∈{1,2},0≤i≤3,當(dāng)以下不等式全部都不成立時(shí),本文構(gòu)造的校驗(yàn)矩陣H所對(duì)應(yīng)的Tanner圖中不存在4環(huán)。

其中,0≤j0,j1≤J, 0≤l0,l1≤L-1,而當(dāng)l0=l1且j0=j1時(shí),t1≠t0。由完備循環(huán)差集的特性可知,基矩陣E中的任意兩元素之差作模p運(yùn)算,值各不相同,因此本文構(gòu)造的基矩陣不存在4環(huán)。

3.2.2 無六環(huán)證明

由環(huán)長存在定理可知,當(dāng)n=3時(shí),可將式(3)寫為式(4)形式。

(4)

結(jié)合基矩陣的結(jié)構(gòu),可能存在6環(huán)的情況如下:

(1) 當(dāng)j0≠j1≠j2,l0≠l1≠l2時(shí),只有橫跨三行三列,才可能出現(xiàn)6環(huán),如圖2(a)～圖2(f)所示,即如同Type-I QC-LDPC碼六環(huán)的證明情況一樣。由于本文構(gòu)造的基矩陣有類似雙對(duì)角結(jié)構(gòu),結(jié)合完備循環(huán)差集的特性,基矩陣中的任意兩元素之差作模p運(yùn)算值各不相同,故上述6環(huán)情況不會(huì)出現(xiàn)。

圖2 基矩陣E(H)中6環(huán)的存在形式Fig.2 Form of six cycles in E(H)

(2) 當(dāng)j0=j1,l0=l1時(shí),其他變量保持不變,則式(4)變?yōu)槭?5)。

(5)

由環(huán)長的構(gòu)成可知,一個(gè)環(huán)內(nèi)只有首,尾位置的坐標(biāo)相同,其余位置不同,而式(5)與之矛盾,故無6環(huán)。同理,j0=j1,l2=l1和j0=j1,l2=l0的證明與上述相同。

(3)當(dāng)j0=j1時(shí),其他變量保持不變,橫跨兩行三列的形式,則式(4)變?yōu)槭?6),若6環(huán)存在,則如圖2(g)所示。

(6)

由圖1可知,本文構(gòu)造的基矩陣中并不存在此結(jié)構(gòu),故無6環(huán)。同理,j2=j1,j2=j0時(shí)的證明與上述相同。

(4)當(dāng)l0=l1時(shí),其他變量保持不變,橫跨三行兩列的形式,則式(4)變?yōu)槭?7),若6環(huán)存在,則如圖2(h)所示。

(7)

由圖1可知,本文構(gòu)造的基矩陣中并不存在此結(jié)構(gòu),故無6環(huán)。同理,l2=l1,l2=l0時(shí)的證明與上述相同。

(5)當(dāng)l0=l1=l2時(shí),其他變量保持不變,三行一列的形式,則式(4)變?yōu)槭?8),若6環(huán)存在,則如圖2(i)所示。

(8)

由圖1可知,本文構(gòu)造的基矩陣中并不存在此結(jié)構(gòu)。故無6環(huán),等式(8)不成立。

(6)當(dāng)j0=j1=j2時(shí),其他變量保持不變,一行三列的形式,則式(4)變?yōu)槭?9),若6環(huán)存在,則如圖2(j)所示。

(9)

由圖1可知,本文構(gòu)造的基矩陣含有此結(jié)構(gòu),又因?yàn)橥陚溲h(huán)差集中任意兩元素之差作模p運(yùn)算值各不相同,故等式(9)不成立。綜上所述,本文構(gòu)造的基矩陣中不含6環(huán)。

4 仿真與性能分析

在構(gòu)造QC-LDPC碼時(shí),需要考慮碼的結(jié)構(gòu)、碼長、碼率等影響性能的因素。一般來講,當(dāng)其他參數(shù)相同的情況下,碼長較長時(shí),性能普遍好。但碼長過長會(huì)導(dǎo)致時(shí)延增加。碼率越小,糾錯(cuò)性能越好,但會(huì)導(dǎo)致監(jiān)督位的過度冗余。本文構(gòu)造中短碼長,碼率為0.5的碼字。采用加性高斯白噪聲(additive white Gaussian noise, AWGN)信道,和積(sum-product algorithm, SPA)譯碼,BPSK調(diào)制,選擇迭代50次。

首先選取完備循環(huán)差集為{1,2,23,34,84, 123,136,142,146,160,176,201,226,230,232,239},將完備循環(huán)差集的元素分為h={1,2,23,34,84,123,136,142},g={160,176,201, 226,230,232,239}兩個(gè)子集,令δ=5,μ=3,h*={123,136,142,1,2,23,34,84},g*={201,226,230,232,239,146,160,176},令p=241,碼率為R=0.5,碼長N=3 856。

圖3 碼率為0.5的Type-Ⅱ P-CDF-QC-LDPC (3 856,1 928)碼與其他碼型的糾錯(cuò)性能對(duì)比圖 Fig.3 Contrast figure of error correction performance of Type-Ⅱ P-CDF-QC-LDPC (2 680,1 340) code at code-rate of 0.5

本文構(gòu)造的基于完備循環(huán)差集的圍長至少為8的type-Ⅱ P-CDF-QC-LDPC(3 856,1 928)碼,與文獻(xiàn)[14]基于完備循環(huán)差集構(gòu)造的非規(guī)則且可實(shí)現(xiàn)快速編碼的type-Ⅱ CDS-QC-LDPC(4 788,2 394)碼比較,同時(shí)與文獻(xiàn)[17]基于完備循環(huán)差集構(gòu)造的列重為4的規(guī)則type-Ⅱ P-CDS-QC-LDPC (3 906,1 953)碼的性能進(jìn)行比較,在誤碼率為(bit error ratio, BER)為10-6時(shí),其凈編碼增益分別提高0.42 dB和0.15 dB。

為進(jìn)一步展現(xiàn)構(gòu)造碼字的優(yōu)越性能,構(gòu)造碼率為0.5,碼長為6 096的type-Ⅱ P-CDF- QC-LDPC(6 096,3 048)碼,選擇完備循環(huán)差集{1,2,20,29,97,119,152,154,177,203,241,255,291,297,301,308,338,362,367,370},令δ=5,μ=3,p=381,將構(gòu)造的碼字分別與基于sidon序列構(gòu)造的type-Ⅱ QC-LDPC碼,基于斐波那契數(shù)列構(gòu)造的type-I QC-LDPC碼對(duì)比,如圖4所示。

圖4 碼率為0.5的Type-Ⅱ P-CDF-QC-LDPC(6 096,3 048)碼與其他碼型的糾錯(cuò)性能對(duì)比圖 Fig.4 Contrast figure of error correction performance of Type-Ⅱ P-CDF-QC-LDPC (6096,3048) code at code-rate of 0.5

在BER為10-6時(shí),與文獻(xiàn)[11]基于sidon序列構(gòu)造的type-Ⅱ SD-QC-LDPC(6 096,3 048)碼和文獻(xiàn)[19]基于斐波那契數(shù)列構(gòu)造的type-I FS-QC-LDPC(6 200,3 100)碼相比,本文構(gòu)造的type-Ⅱ P-CDF-QC-LDPC(6 096,3 048)碼的凈編碼增益分別提升0.3 dB和0.4 dB。

綜合上述分析,與其他具有優(yōu)異性能的QC-LDPC碼相比,本文type-Ⅱ P-CDF-QC-LDPC碼的碼率為0.5,圍長至少為8,并且具有較為明顯的凈編碼增益。

5 結(jié) 論

本文提出了基于完備循環(huán)差集構(gòu)造具有近似雙對(duì)角結(jié)構(gòu)的type-Ⅱ P-CDF- QC-LDPC碼的設(shè)計(jì)方法,使其對(duì)應(yīng)的Tanner圖中的圍長至少為8,且8環(huán)的數(shù)量較少?；仃囍械脑赜赏陚溲h(huán)差集中的元素構(gòu)成,節(jié)省了存儲(chǔ)空間,該方法構(gòu)造簡(jiǎn)單,在高信噪比區(qū)域收斂速度快速,無明顯的錯(cuò)誤平層,其糾錯(cuò)性能優(yōu)異。