周 創(chuàng)，閻 昊，羅鈺杰，黎 勇,3

(1.重慶郵電大學 通信與信息工程學院，重慶 400065；2.西南通信研究所 保密通信重點實驗室，成都 610041；3.重慶大學 計算機學院，重慶 400044)

0 引 言

連續(xù)變量量子密鑰分發(fā)[1-3]系統(tǒng)由于量子信號本身極其微弱，而且經(jīng)過長距離傳輸后，信噪比還會大大降低，因此，需要采用碼率很低、碼長很長的低密度奇偶校驗(low density parity check, LDPC)碼[4]。性能好的低碼率碼需要同時滿足兩個條件：一是譯碼閾值接近信道容量；二是最小漢明距離較大，保證誤碼殘留很低。這給碼字的設計帶來了很大的挑戰(zhàn)：一方面，為了設計低碼率碼且其譯碼閾值接近香農(nóng)限，在碼字結構中就需要大量度數(shù)為1的變量節(jié)點；另一方面，大量低度數(shù)的變量節(jié)點會阻礙最小漢明距離隨碼字長度的增加而增大。多邊型LDPC碼(multi-edge type LDPC, MET-LDPC)[5]碼引入了多類邊的概念，使其無論在結構上還是碼率的選擇上都更為靈活，因而更容易設計出所需要的LDPC碼。

LDPC碼的度分布體現(xiàn)了各類節(jié)點連接的、由變量節(jié)點度分布多項式和校驗節(jié)點度分布多項式表示的數(shù)量以及碼率等重要信息。度分布在設計校驗矩陣的過程中至關重要，一種好的度分布更容易設計出性能優(yōu)異的LDPC碼。當給出一種度分布時，就給定了一個LDPC碼的集合。密度進化(density evolution, DE)[6]是一種用于分析在置信傳播(belief propagation, BP)譯碼條件下給定LDPC碼集合收斂行為(即譯碼門限值)的方法，其中譯碼門限值被定義為當編碼塊長度達到無窮大時譯碼錯誤概率收斂到零的最大信道噪聲。密度進化的一個明顯缺點就是計算量非常大，因此其近似方法(稱為高斯近似[7])常被用于度分布的優(yōu)化。

為了滿足連續(xù)變量量子密鑰分發(fā)應用場景對LDPC碼的要求，本文提出了一種針對具有3種邊類型且部分變量節(jié)點度為1的MET-LDPC碼的設計方法，這種結構的碼字可以分塊設計且只需設計校驗矩陣的左邊部分。在設計過程中首先進行度分布優(yōu)化[8]，得到滿足該MET-LDPC碼結構要求的度分布，然后再根據(jù)度分布使用基于多路徑外在信息度策略[9]的漸進邊增長(progressive edge growth, PEG)算法[10]去設計該碼字校驗矩陣的左下角以及通過掩模的方式去設計左上角，最后再與校驗矩陣右邊部分合并成整個MET-LDPC碼的校驗矩陣。仿真結果表明，這種設計方法是可行性的。

1 MET-LDPC碼概述

MET-LDPC碼有多種類型的邊，其度分布多項式表示出了各種類型節(jié)點連接的每一類邊數(shù)量以及這種類型節(jié)點所占比例。變量節(jié)點度分布多項式和校驗節(jié)點度分布多項式分別表示為

(1)

(2)

(1)—(2)式中：b,d,r,x都是矢量；nv表示變量節(jié)點的種類數(shù)；nc表示校驗節(jié)點的種類數(shù)。令ne表示MET-LDPC碼邊的類型數(shù)，nr表示可能用于傳輸碼元比特的信道種類數(shù)。每種類型的節(jié)點定義表示為

(3)

(3)式中：x=[x1,x2,…,xne]；d=[d1,d2,…,dne]。每種類型的變量節(jié)點定義為

(4)

(4)式中，bi表示該種類型的變量節(jié)點對應的碼字是否在第i類信道上傳輸。例如，對于二進制輸入的加性高斯白噪聲(binary input additive white Gaussian noise，BI-AWGN)信道，變量節(jié)點對應的碼元比特在信道進行傳輸，即不是刪余變量節(jié)點，則b=[0,1]，否則b=[1,0]。

度分布多項式中vi和ui都是不大于1的正實數(shù)，對應于該類型節(jié)點的比例。無刪余變量節(jié)點的MET-LDPC碼碼率Rate的計算式為

(5)

2 MET-LDPC碼結構

連續(xù)變量量子密鑰分發(fā)(continuous-variable quantum key distribution, CV-QKD)應用場景需要碼率低、碼長長、性能好的MET-LDPC碼，因此，在設計MET-LDPC碼時要引入大量低度數(shù)分布的變量節(jié)點，以保證設計的低碼率LDPC碼性能接近香農(nóng)限；使用邊連接度數(shù)較大的變量節(jié)點，以保證最小漢明距離隨著碼長的增加而增加，從而構造出性能好的低碼率LDPC碼。圖1所示的MET-LDPC碼Tanner圖便符合上述要求。

圖1 MET-LDPC碼Tanner圖

圖1中，Tanner圖可以拆分成2個子Tanner圖T1和T2，E12表示連接T1和T2的邊。E12所連接的變量節(jié)點都在T1中，校驗節(jié)點都在T2中。所有度數(shù)為1的變量節(jié)點都在T2中，且T2的變量節(jié)點的度數(shù)都為1，每個校驗節(jié)點僅僅與一個度數(shù)為1的變量節(jié)點相連接。在T1中除了連接的邊E12，其余結構與一般非規(guī)則LDPC碼相同。從直觀上看，T1與T2通過邊E12串聯(lián)構成。

與圖1所示Tanner圖對應的MET-LDPC碼的校驗矩陣結構如圖2所示。

圖2 MET-LDPC碼校驗矩陣結構

圖1中，T1的校驗節(jié)點與T2的變量節(jié)點之間沒有連線，對應于圖2右上角的全零矩陣。T2中變量節(jié)點的度都為1且通過邊E2與T2中的校驗節(jié)點一一對應相連，邊E2可用圖2右下角的單位陣表示。T1中的變量節(jié)點通過邊E12與T2中的校驗節(jié)點相連，對應圖2左下角的矩陣H2。連接T1中變量節(jié)點與校驗節(jié)點的邊E1則對應圖2左上角的矩陣H1。圖2中MET-LDPC碼校驗矩陣右上角的全零矩陣和右下角的單位陣已經(jīng)確定，所以整個MET-LDPC碼設計就是圖2中矩陣H1與H2的設計。

3 MET-LDPC碼度分布優(yōu)化

MET-LDPC碼的度分布優(yōu)化[11]是一個通過密度進化、高斯近似、差分進化[12]等算法找到滿足譯碼門限值要求的MET-LDPC碼度分布多項式的過程。本文設計的MET-LDPC碼針對BI-AWGN信道，用到的密度進化、高斯近似也是相應地針對BI-AWGN信道的。本文設計的MET-LDPC碼不考慮刪余變量節(jié)點。

優(yōu)化得到的MET-LDPC碼度分布始終要滿足碼率以及變量節(jié)點和校驗節(jié)點連接的各類邊數(shù)量相等這兩個約束條件。令矩陣Ev表示各類變量節(jié)點連接的各類邊數(shù)量，矩陣Ec表示各類校驗節(jié)點連接的各類邊數(shù)量，矢量vT表示變量節(jié)點多項式各項系數(shù)vi，矢量uT表示校驗節(jié)點多項式各項系數(shù)ui，可得

(6)

(7)

vT=[v1,v2,…,vnv]T

(8)

uT=[u1,u2,…，unc]T

(9)

(6)式中，di,j是非負整數(shù)，表示第i類變量節(jié)點連接的第j類邊的數(shù)量；(7)式中，gi,j是非負整數(shù)，表示第i類校驗節(jié)點連接的第j類邊的數(shù)量。于是變量節(jié)點與校驗節(jié)點連接的各類相等邊以及碼率的約束關系便轉換為

Evv=Ecu

(10)

(11)

定義矩陣

(12)

(13)

(12)式中，1nv、1nc分別表示長度為nv、nc的全1矢量。那么(10)—(11)式可以表示為

AX=0

(14)

(14)式中，0是長度為nv+nc的全0矢量。如果Ev、Ec、X可以使(14)式成立，便可以構成一個MET-LDPC碼的度分布多項式。通過(6)—(13)式，度分布優(yōu)化轉換為在給定參數(shù)nv、nc、ne、Rate的條件下，找到使得(14)式成立，同時譯碼門限值value足夠大的Ev、Ec、v、u。Ev和Ec決定了后續(xù)校驗矩陣設計時各子矩陣的列重和行重，v和u決定了各種列重和行重的比例。整個度分布優(yōu)化的過程分為內(nèi)優(yōu)化和外優(yōu)化兩部分，其中內(nèi)優(yōu)化是根據(jù)給出的Ev、Ec、Rate找到使譯碼門限值最大的v和u。算法1為內(nèi)優(yōu)化算法。

算法1 內(nèi)優(yōu)化算法

輸入：Ev，Ec，Rate

輸出：X，value

1.根據(jù)輸入數(shù)據(jù)生成矩陣A；

2.計算滿足(14)式并且元素全是正數(shù)的矢量X的個數(shù)p；

3.p==0，則輸出全零矢量X且value值為0；p==1，則輸出對變量節(jié)點度分布多項式系數(shù)歸一化后的唯一矢量X，以及此時高斯近似計算出的、由A與X構成的、MET-LDPC碼度分布多項式的門限值value;p>1，則對X執(zhí)行差分進化算法，找到并輸出與A構成的MET-LDPC碼度分布多項式高斯近似門限值最大的X以及該最大門限值value。

外優(yōu)化是找到合適的Ev和Ec，使其與經(jīng)過內(nèi)優(yōu)化處理后得到的v和u構成的MET-LDPC碼度分布譯碼門限值足夠大。算法2為外優(yōu)化算法。

算法2 外優(yōu)化算法

輸入：nv，nc，ne

輸出：Ev，Ec，v，u

1.執(zhí)行差分進化算法的初始化步驟，根據(jù)輸入隨機產(chǎn)生Np個Ev和Ec，其中Np為差分進化算法中的種群數(shù)量；

2.對產(chǎn)生的Ev和Ec依次執(zhí)行內(nèi)優(yōu)化，得到對應的X與value，若有value的值超過了設定的門限值，則對該度分布執(zhí)行密度進化算法，得到更準確的門限值并更新value。若更新后的value仍大于設定的門限值，則結束外優(yōu)化，輸出Ev、Ec、v、u。否則繼續(xù)執(zhí)行步驟2，直到所有Ev和Ec均已進行內(nèi)優(yōu)化，執(zhí)行步驟3；

3.執(zhí)行差分進化算法的交叉、變異、選擇3個步驟，產(chǎn)生新的Ev和Ec，執(zhí)行步驟2。若步驟3執(zhí)行次數(shù)達到設定的值，則結束外優(yōu)化，度分布優(yōu)化失敗。

4 MET-LDPC碼設計及譯碼

本文設計的MET-LDPC碼對應的校驗矩陣可以分為4個子矩陣，并且右上角的子矩陣是一個全零矩陣，右下角的子矩陣是一個單位陣，只需要根據(jù)優(yōu)化后的度分布對左上角和左下角的矩陣進行設計，再將4個子矩陣合并便完成了整個MET-LDPC碼的設計。在MET-LDPC碼設計過程中，多路徑外在信息度(extrinsic message degree，EMD)[13]常常被用來作為判斷設計性能的依據(jù)，EMD定義為只與變量節(jié)點集合(或者一個環(huán))中的一個變量節(jié)點相連的校驗節(jié)點的數(shù)量。EMD值越大，這一變量節(jié)點集合(或者環(huán))在信息傳遞過程中獲得的外信息就越多，性能也就越好。

4.1 左上角矩陣設計

左上角矩陣對應于MET-LDPC碼Tanner圖的邊E1，與傳統(tǒng)LDPC碼的結構相同。本文通過在基于平方剩余(quadratic residue, QR)碼構造的具有準循環(huán)結構的低密度奇偶校驗(quasi cyclic LDPC，QC-LDPC)碼[14]的基矩陣上進行掩模的方式，完成左上角矩陣的設計。掩模思路是優(yōu)先掩模掉QC-LDPC碼基矩陣中環(huán)穿數(shù)最多的循環(huán)置換矩陣(circulant permutation matrix, CPM)對應的基矩陣中的元素，當環(huán)穿數(shù)最多的CPM不止一個時，則通過EMD來決定掩模的位置。掩模依據(jù)在于CPM性能的好壞與其環(huán)穿數(shù)多少有關，環(huán)穿數(shù)越多，性能越差，應先被掩模掉。當存在環(huán)穿數(shù)最多的CPM不止一個時，則統(tǒng)計其成環(huán)的EMD值，EMD值越小，性能越差，應先進行掩模。掩模算法具體過程見算法3。

算法3 掩模算法

輸入:Rate,length//需要構造的碼的碼率和碼長

輸出：Hm×n//m行n列矩陣

1.根據(jù)輸入的兩個參數(shù)從已有的基于QR碼構造的QC-LDPC碼的基矩陣中按環(huán)數(shù)最少的原則截取大小為m行n列的矩陣Hm×n

2.l=3//基于QR碼構造的QC-LDPC碼沒有4環(huán)

3.定義矩陣B并初始化為全1的矩陣//記錄掩模的位置并用于判斷掩模后的度分布

4. Loop

5.EMD0=∞

6. 用環(huán)穿數(shù)統(tǒng)計算法得到對應的L以及Nm×n

7. ifNm×n是全零矩陣then

8.l=l+1

9. go to Loop

10. end if

11. ifNm×n有唯一的最大值then

12. 將矩陣B中與最大值對應位置元素置0并根據(jù)B更新Hm×n

13. else

14.EMD0取L里面的最大值

15. whileEMD0不等于L中的最小值do

16. 記錄Nm×n中最大值的位置

17.EMD0取L僅小于它的最大值

18. 用環(huán)穿數(shù)算法重新得到L，Nm×n

19. ifEMD0是L中的最小值且Nm×n中沒有唯一的最大值then

20.l=l+1

21. go to Loop

22. end if

23. ifNm×n里面的元素有唯一個最大值then

24. 矩陣B中與最大值對應位置元素置0并根據(jù)B更新Hm×n

25. end if

26. end while

27. end if

28. ifHm×n滿足度分布要求then

29. go toend Loop

30. end if

31.end Loop

掩模算法從基于QR碼構造的QC-LDPC碼基矩陣中截取矩陣Hm×n進行循環(huán)掩模，如果Hm×n的度分布與經(jīng)過度分布優(yōu)化得到的結果一致，則結束掩模。在掩模過程中，每次確定掩模的位置之前都要統(tǒng)計每個CPM的環(huán)穿數(shù)。

4.2 左下角矩陣設計

算法4 多路徑EMD策略

輸入：vj//當前正在處理的變量節(jié)點

輸出：ci//挑選的校驗節(jié)點

1.fork=1 todvjdo//dvj表示變量節(jié)點vj的度

2. ifk==1 then

3. 從當前度最小的校驗節(jié)點中隨機挑選一個輸出

4. else

8. else

10. 用B表示A中度最小的節(jié)點的集合；

11. 找出從vj到B中各個校驗節(jié)點的路徑數(shù)；

12. 用C表示B中路徑數(shù)最少的節(jié)點的集合；

13.C中元素唯一則輸出該唯一元素，否則計算C中每個元素到vj的路徑的EMD值，并求其平均值，然后選平均值最大的校驗節(jié)點輸出

14. end if

15. end if

16.end for

多路徑EMD策略減少了設計過程中挑選校驗節(jié)點時的隨機性，從而能構造出性能更好的碼。其具體設計過程為執(zhí)行文獻[9]中的構造QC-LDPC碼的PEG算法，當需要挑選與正在處理的變量節(jié)點相連的校驗節(jié)點時，執(zhí)行多路徑EMD策略挑選出與之相連的校驗節(jié)點。圖3是一個從變量節(jié)點vj出發(fā)擴展到深度等于2的例子，其中黑色圓圈表示變量節(jié)點，黑色方框表示校驗節(jié)點。

圖3 變量節(jié)點vj擴展至深度等于2

4.3 MET-LDPC碼譯碼

本文采用LOG-BP校正子譯碼算法進行MET-LDPC碼的譯碼，令yi表示從BI-AWGN信道接收到的對應于第i個變量節(jié)點的信號幅度值，δ表示信道噪聲的均方差，H表示MET-LDPC碼校驗矩陣，Ll(rji)表示第l次迭代時校驗節(jié)點j傳遞給變量節(jié)點i的對數(shù)似然值，Ll(qij)表示第l次迭代時變量節(jié)點i傳遞給校驗節(jié)點j的對數(shù)似然值，Ll(qi)表示變量節(jié)點i第l次迭代時的總信息似然值，Rji表示從與校驗節(jié)點j相連的變量節(jié)點集合中扣除變量節(jié)點i，Cij表示從與變量節(jié)點i相連的校驗節(jié)點集合中扣除校驗節(jié)點j。MET-LDPC碼譯碼算法具體步驟見算法5。

算法5 MET-LDPC碼譯碼算法

1.初始化，對于每個變量節(jié)點i，計算其初始對數(shù)似然值L0(qij)，并利用原始隨機矢量U計算其校正子CB

(15)

CB=HUT

(16)

2.校驗節(jié)點信息更新，計算Ll(rji)

(17)

(18)

(19)

(17)式中，sgn是符號函數(shù)；(18)式中，Φ(x)為

Φ(x)=Φ-1(x)=-ln(tanh(x/2))

(20)

根據(jù)CB的值判斷奇偶校驗類型，是奇校驗則Ll(rji)取相反數(shù)，是偶校驗則Ll(rji)的值不變

3.變量節(jié)點信息更新，計算Ll(qij)

(21)

(22)

4.譯碼判決

(23)

如果判決碼字w滿足CB=HwT或者達到設定的最大迭代次數(shù)，則結束譯碼；否則，回到第2步繼續(xù)迭代。

5 仿真結果

基于前述設計方法，本文設計了兩個基矩陣大小都為42行52列、CPM大小分別為1 000和800的MET-LDPC碼。其碼長分別為52 000和41 600，碼率均為0.192 3。

根據(jù)第2節(jié)MET-LDPC碼結構可知，設計的MET-LDPC碼有3類邊。在做度分布優(yōu)化時設定變量節(jié)點類型數(shù)nv=3，校驗節(jié)點類型數(shù)nc=4，相應的度分布函數(shù)為

(24)

(25)

由(24)—(25)式可知，需設計的MET-LDPC碼基矩陣左側大小為42行14列并且有4列列重為7，10列列重為12。其中左上角矩陣大小為4行14列并且有4列的列重為3，10列的列重為2；左下角矩陣大小為38行14列，其中有4列的列重為4，10列列重為10。

從(98，47)QR碼構造的QC-LDPC碼基矩陣中按環(huán)最少的原則截取一個4行14列的子矩陣用于掩模完成左上角矩陣設計。在整個左側矩陣的度分布條件下，結合已經(jīng)設計完成的左上角矩陣，執(zhí)行基于多路徑EMD策略的PEG算法，完成左下角矩陣設計，最終將各個部分合并以獲得最終的MET-LDPC碼。在相同的參數(shù)條件下，還構造了兩個左上角和左下角都采用PEG算法設計的MET-LDPC碼。所有碼字都采用改進的LOG-BP校正子譯碼算法進行性能仿真，最大迭代次數(shù)為100。CPM大小為1 000的兩個MET-LDPC碼性能仿真曲線如圖4所示，CPM大小為800的兩個MET-LDPC碼性能仿真曲線如圖5所示。

圖4 CPM大小為1 000的MET-LDPC碼性能對比

圖5 CPM大小為800的MET-LDPC碼性能對比

由仿真結果可知，在相同參數(shù)條件下，本文設計的MET-LDPC碼性能優(yōu)于僅用PEG算法設計的碼。

6 結 論

本文針對一類具有3種邊類型且部分變量節(jié)點度為1的MET-LDPC碼，提出了一種掩模加基于多路徑EMD策略的PEG算法的設計方法。掩模不僅去掉了對譯碼性能影響較大的CPM,還減少了影響譯碼性能的短環(huán)，保證了左上角矩陣的性能，為Tanner圖右側部分在譯碼時提供更準確的信息。在整個左側矩陣的度分布條件下，基于已經(jīng)設計完成的左上角矩陣，用帶有多路徑EMD策略的PEG算法設計左下角矩陣，可以更有針對性地挑選校驗節(jié)點，從而保證整個MET-LDPC碼性能。在保證優(yōu)化后度分布的條件下，本文設計出了兩個碼長分別為52 000和41 600、碼率均為0.192 3的MET-LDPC碼。仿真表明，在相同參數(shù)條件下，本文比PEG算法性能更優(yōu)。