張曉芳,黎 勇,2

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2. 重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044)

0 引 言

基于量子力學(xué)的物理基礎(chǔ)即測不準(zhǔn)原理和量子不可克隆原理，量子密鑰分發(fā)(quantum key distribution, QKD)系統(tǒng)給合法的通信雙方提供了絕對安全可靠的“一次一密”通信[1]。量子密鑰分發(fā)系統(tǒng)是量子信息在實(shí)際生活中的第一個應(yīng)用。在離散變量量子密鑰分發(fā)(discrete variable QKD, DV-QKD)中，由于單光子檢測器的速度和效率的限制，使其實(shí)現(xiàn)成本很高；而連續(xù)變量量子密鑰分發(fā)(continuous variable QKD, CV-QKD)系統(tǒng)可以采用現(xiàn)有的標(biāo)準(zhǔn)電信技術(shù)，因而被認(rèn)為更有前景。連續(xù)變量量子密鑰分發(fā)系統(tǒng)利用連續(xù)變量例如相干態(tài)的正交基編碼密鑰信息。量子密鑰分發(fā)系統(tǒng)一般主要有2個階段：①量子比特的傳輸過程；②量子后處理過程。后處理過程分為2個步驟：密鑰協(xié)商和隱私放大。其中，通過提升譯碼糾錯速度實(shí)現(xiàn)高效地密鑰協(xié)商尤為重要。在較遠(yuǎn)距離，較低信噪比的情況下，通信雙方只有傳輸碼率較低、碼長較長的碼字才能獲得高效的密鑰協(xié)商。

R. Gallager[2]博士于1962年提出了一種帶有稀疏奇偶校驗(yàn)矩陣的線性糾錯碼——低密度奇偶校驗(yàn)(low density parity check, LDPC)碼。Tanner于1981年將LDPC碼用Tanner圖表示：一類節(jié)點(diǎn)是校驗(yàn)節(jié)點(diǎn)，代表碼字的一組校驗(yàn)方程；另一類是表示碼字元素的變量節(jié)點(diǎn)，變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)通過邊連接。D. Mackay和R. M. Neal等[3]于1999年發(fā)現(xiàn)采用迭代置信傳播譯碼算法，LDPC碼糾錯性能接近香農(nóng)極限。LDPC碼主要有2類：隨機(jī)LDPC碼和結(jié)構(gòu)化LDPC碼，隨機(jī)LDPC碼性能較好，但是沒有結(jié)構(gòu)的校驗(yàn)矩陣增加了編碼復(fù)雜度。因此，在實(shí)際系統(tǒng)中通常采用結(jié)構(gòu)化LDPC碼，比如準(zhǔn)循環(huán)低密度奇偶校驗(yàn)(quasi-cyclic LDPC, QC-LDPC)碼[4]。

Paul Jouguet[5]提出利用圖形處理器(graphics processing unit,GPU)實(shí)現(xiàn)LDPC譯碼器，在0.161的信噪比下，碼率為0.1的隨機(jī)多邊型低密度奇偶校驗(yàn)(multi-edge type LDPC, MET-LDPC)碼的譯碼速度達(dá)到了7.10 Mbit/s。Mario Milicevic等[6]針對碼率為0.1，擴(kuò)展因子為512的準(zhǔn)循環(huán)多邊型低密度奇偶校驗(yàn)(quasi-cyclic MET-LDPC, QC-MET-LDPC)碼，在信噪比為0.161，具有提前終止的條件下，達(dá)到了9.17 Mbits/s的速度。XIANGYU WANG等[7]提出只在最后一次迭代時才更新度為一的變量結(jié)點(diǎn)，大大減少了計(jì)算量，在碼率為0.1，信噪比為0.161的條件下，獲得了30.39 Mbits/s的速度。以上方法都是基于GPU實(shí)現(xiàn)的傳統(tǒng)置信傳播(belief propagation, BP)譯碼器，在每次迭代過程中，首先更新所有的變量節(jié)點(diǎn)的對數(shù)似然值(log likelihood ratio, LLR)，再更新所有校驗(yàn)節(jié)點(diǎn)的對數(shù)似然值。GPU譯碼器的譯碼速度由拷貝耗時、單次迭代譯碼耗時和總的迭代次數(shù)等因素決定。傳統(tǒng)的BP譯碼算法收斂速度較慢，需要更多的迭代次數(shù)才能達(dá)到較好的譯碼性能，降低了譯碼速率[8]。本文設(shè)計(jì)了一種基于分層置信傳播譯碼(layered BP, LBP)算法的GPU譯碼器，在碼率為0.1，碼長為106，循環(huán)50次的條件下，該譯碼器速率達(dá)到了41.50 Mbits/s。

1 分層譯碼算法

LDPC碼通過節(jié)點(diǎn)之間消息可信度的傳播進(jìn)行譯碼，即BP譯碼算法。最初的BP算法含有大量的乘法和指數(shù)運(yùn)算，為了降低運(yùn)算的復(fù)雜度，進(jìn)而提出了對數(shù)域的BP算法[9]。分層BP譯碼算法不同于傳統(tǒng)的BP算法，分層BP譯碼算法可以將整個校驗(yàn)矩陣按行劃分為不同的層，每層的列重小于等于1，層內(nèi)依然使用的是傳統(tǒng)的BP譯碼算法，層與層之間，下一層利用上一層獲得的數(shù)據(jù)依次進(jìn)行運(yùn)算。分層BP譯碼算法收斂速度更快，只需要傳統(tǒng)BP譯碼算法約一半的迭代次數(shù)就可以達(dá)到同等的糾錯效果[10]。

本文采用的譯碼算法為分層BP譯碼算法[11]，其流程如下。

1)初始化。

(1)

2)校驗(yàn)節(jié)點(diǎn)更新。

(2)

(3)

(4)

(5)

3)變量節(jié)點(diǎn)更新。

(6)

(7)

4)更新下一層。

l=l-1

(8)

5)譯碼判決。

(9)

(9)式中，Cv表示根據(jù)第v個變量節(jié)點(diǎn)判決出的碼字。如果滿足C·HT=spc或者達(dá)到最大迭代次數(shù)則停止迭代，反之返回1.2節(jié)中進(jìn)行迭代。

2 譯碼器實(shí)現(xiàn)和優(yōu)化

2.1 譯碼器整體結(jié)構(gòu)

分層譯碼器整體結(jié)構(gòu)可分為數(shù)據(jù)處理模塊、數(shù)據(jù)拷貝模塊、糾錯譯碼模塊和誤碼統(tǒng)計(jì)模塊，整體結(jié)構(gòu)框圖如圖1。

圖1 譯碼器結(jié)構(gòu)框圖Fig.1 Structure diagram of decoder

數(shù)據(jù)處理模塊通過讀取基矩陣獲取基矩陣非‘-1’元素的總數(shù)、移位量、基矩陣非‘-1’元素對應(yīng)的列的位置和基矩陣的行重等信息，并將糾錯譯碼模塊所需的基矩陣信息處理合并。數(shù)據(jù)拷貝模塊將糾錯譯碼模塊所需信息從主機(jī)端拷貝至GPU端，如：基矩陣信息和碼字信息。糾錯譯碼模塊結(jié)構(gòu)框圖如圖2。

圖2 糾錯譯碼模塊結(jié)構(gòu)框圖Fig.2 Structure diagram of error correction decoding module

糾錯譯碼模塊利用分層BP譯碼算法迭代更新變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的信息值進(jìn)行糾錯譯碼。初始化部分計(jì)算了校正子和信道傳輸?shù)阶兞抗?jié)點(diǎn)的信息的LLR值。子矩陣信息值更新部分利用一個核函數(shù)，找到對應(yīng)的索引號，更新變量節(jié)點(diǎn)傳給校驗(yàn)節(jié)點(diǎn)的LLR值，再更新校驗(yàn)節(jié)點(diǎn)傳給變量節(jié)點(diǎn)的LLR值，最后更新變量節(jié)點(diǎn)的LLR值。一個子矩陣的信息值更新完畢，則換到下一個子矩陣進(jìn)行更新。遍歷所有的子矩陣完成一次完整的信息值更新。當(dāng)循環(huán)到下一次迭代時，又從第一個子矩陣開始遍歷，直至更新完所有的子矩陣，跳到下一次迭代，達(dá)到最大迭代次數(shù)時結(jié)束循環(huán)。碼字判決部分通過變量節(jié)點(diǎn)的LLR值是否大于等于零進(jìn)行判決，若LLR值大于等于零則判決碼字為0，否則為1。接下來再次利用數(shù)據(jù)拷貝模塊將GPU上的數(shù)據(jù)拷貝回主機(jī)端。最后，誤碼統(tǒng)計(jì)模塊在主機(jī)端統(tǒng)計(jì)錯誤幀數(shù)。

2.2 節(jié)點(diǎn)并行方案

由分層BP譯碼算法可以看出，節(jié)點(diǎn)與節(jié)點(diǎn)之間在更新LLR值時互不影響，因此，可以利用GPU線程的并行處理方式，將Tanner圖中的每一個變量節(jié)點(diǎn)的計(jì)算量對應(yīng)于一條線程，因?yàn)榉謱雍竺總€子矩陣的變量節(jié)點(diǎn)度小于等于1，亦即每條邊上傳遞的信息對應(yīng)于一條線程，使變量節(jié)點(diǎn)可以同步并行更新，獲得更快的譯碼速度。

在節(jié)點(diǎn)并行譯碼方案中，根據(jù)以上線程的映射方式，節(jié)點(diǎn)的計(jì)算分2步進(jìn)行：①校驗(yàn)節(jié)點(diǎn)的計(jì)算。線程先映射于每條邊上傳遞的信息，計(jì)算出變量節(jié)點(diǎn)與該校驗(yàn)節(jié)點(diǎn)相連的邊傳遞的LLR值，再更新一組子矩陣的所有校驗(yàn)節(jié)點(diǎn)；②變量節(jié)點(diǎn)的計(jì)算。線程先映射于每條邊上傳遞的信息，根據(jù)子矩陣校驗(yàn)節(jié)點(diǎn)的信息，并行計(jì)算與該校驗(yàn)節(jié)點(diǎn)相連的每條邊所傳遞的信息，然后線程映射于變量節(jié)點(diǎn)的信息，更新該子矩陣的所有變量節(jié)點(diǎn)。在同次迭代中，該子矩陣更新的值傳遞到下一子矩陣，下一子矩陣采用和該子矩陣相同的處理方式，重復(fù)利用線程資源更新子矩陣對應(yīng)的校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)的LLR值，直至所有子矩陣更新完畢，完成一次迭代。

為方便理解，采用圖3舉例說明節(jié)點(diǎn)并行LLR值更新方式。其中，thv表示線程，Qvc表示由變量節(jié)點(diǎn)傳遞給校驗(yàn)節(jié)點(diǎn)的LLR值，Rc表示校驗(yàn)節(jié)點(diǎn)的LLR值，Rcv表示由校驗(yàn)節(jié)點(diǎn)傳遞給變量節(jié)點(diǎn)的LLR值，Qv表示變量節(jié)點(diǎn)的LLR值，對應(yīng)圖3代入了具體的數(shù)據(jù)。

圖3 節(jié)點(diǎn)并行譯碼方案Fig.3 Node parallel decoding scheme

Begin

映射th0、th1、th2→Q00、Q10、Q20

更新Q00、Q10、Q20

映射th0、th1、th2→R0

更新R0

映射th0、th1、th2→R00、R01、R02

更新R00、R01、R02

映射th0、th1、th2→Q0、Q1、Q2

更新Q0、Q1、Q2

End

2.3 核函數(shù)數(shù)據(jù)流

圖4是本文提出的分層BP譯碼器核函數(shù)數(shù)據(jù)流的圖示。

圖4 核函數(shù)數(shù)據(jù)流Fig.4 Data flow of kernel

圖4中，在一次迭代譯碼一個子矩陣時，進(jìn)行糾錯譯碼的核函數(shù)需要v個線程。v為該子矩陣的變量節(jié)點(diǎn)的個數(shù)，所有的數(shù)據(jù)處理都用了v個線程。所利用的線程對應(yīng)變量節(jié)點(diǎn)個數(shù)，也對應(yīng)由變量節(jié)點(diǎn)傳遞給校驗(yàn)節(jié)點(diǎn)或由校驗(yàn)節(jié)點(diǎn)傳遞給變量節(jié)點(diǎn)的消息個數(shù)，即2類節(jié)點(diǎn)的連接邊的數(shù)量。因?yàn)榫€程對應(yīng)變量節(jié)點(diǎn)而不是校驗(yàn)節(jié)點(diǎn)，碼字的校驗(yàn)節(jié)點(diǎn)的度大于等于1，即子矩陣的變量節(jié)點(diǎn)數(shù)量大于等于校驗(yàn)節(jié)點(diǎn)的數(shù)量，所以增加了利用的線程的數(shù)量。在計(jì)算校驗(yàn)節(jié)點(diǎn)的信息時，v個線程也對應(yīng)的計(jì)算出v個與變量節(jié)點(diǎn)對應(yīng)的校驗(yàn)節(jié)點(diǎn)的LLR值，雖然這部分重復(fù)計(jì)算出校驗(yàn)節(jié)點(diǎn)的值，過多的存儲校驗(yàn)節(jié)點(diǎn)的數(shù)據(jù)，但是在下一步需要找到對應(yīng)的校驗(yàn)節(jié)點(diǎn)的值、計(jì)算由校驗(yàn)節(jié)點(diǎn)傳遞給變量節(jié)點(diǎn)的信息值時，不用再次索引。此外，線程不會進(jìn)入不同的分支，不產(chǎn)生線程阻塞的情況。當(dāng)在該次迭代譯碼至下一個子矩陣時，可以重復(fù)利用線程資源。

譯碼器初始化時，利用同變量節(jié)點(diǎn)數(shù)量相同的線程初始化變量節(jié)點(diǎn)的信息值。譯碼完所有子矩陣而且達(dá)到最大迭代次數(shù)后，也利用同變量節(jié)點(diǎn)數(shù)量相同的線程判決碼字。這2部分沒有在圖4中畫出。

2.4 優(yōu)化

QC-LDPC碼的奇偶校驗(yàn)矩陣是通過基矩陣擴(kuò)展而來的[12]，基矩陣包含了所有的矩陣信息。如圖5，為了減少基矩陣存儲占用的空間，將基矩陣內(nèi)非‘-1’元素的移位量信息、非‘-1’元素對應(yīng)的列的位置信息和基矩陣每一行的行重信息3個數(shù)據(jù)存放在同一變量內(nèi)，減少變量內(nèi)未利用的空位帶來的存儲空間消耗。

圖5 基矩陣信息存儲結(jié)構(gòu)Fig.5 Structure of base matrix information storage

移位量的數(shù)值表示單位矩陣循環(huán)向右移的位數(shù)。元素‘-1’則表示該元素是一個全零矩陣。如果最大移位量為x，則用該變量從最高位開始的「lbx?位表示移位量，「x?表示大于等于x的最小整數(shù)；基矩陣若具有y列，即變量節(jié)點(diǎn)的個數(shù)為y，則用該變量內(nèi)表示前一信息后的「lby?位表示基矩陣的列信息；基矩陣的最大校驗(yàn)節(jié)點(diǎn)的度若為z，則用該變量內(nèi)表示前兩類信息后的「lbz?位表示基矩陣對應(yīng)行的行重。存儲3個數(shù)據(jù)信息總共需要sum=「lbx?+「lby?+「lbz?位，所以存儲數(shù)據(jù)的變量的位數(shù)需要大于等于sum。該變量通過位運(yùn)算存儲和讀取矩陣信息，減少了基矩陣信息所占用的GPU存儲空間，同樣減少了數(shù)據(jù)拷貝模塊需要拷貝的數(shù)據(jù)量，從而減少了譯碼總耗時。

Hbase=

(10)

(10)式是一個行數(shù)為4，列數(shù)為8的基矩陣，其擴(kuò)展因子為100，即基矩陣中的每個元素可擴(kuò)展為100×100的矩陣，該擴(kuò)展后的奇偶校驗(yàn)矩陣行數(shù)為400，列數(shù)為800。基矩陣中的非‘-1’元素表示移位量，移位量的數(shù)值表示單位矩陣循環(huán)向右移動的位數(shù)，因?yàn)閿U(kuò)展因子為100，移位量的取值為0～99，最大移位量為99，26<99<27，所以至少用7位存儲移位量信息的值。元素‘-1’則表示該元素是一個全零矩陣，不存儲元素為‘-1’的基矩陣信息?；仃嚵袛?shù)為8，列號由0至7，最大列號為7，22<7<23，所以用3位存儲基矩陣中的非‘-1’元素所在的列號。基矩陣從第0行至第3行的行重分別為3、2、4、3，則最大行重為4，22=4<23，則需要3位存儲基矩陣非‘-1’元素所在行的行重。存儲這3個關(guān)鍵信息共需要：7+3+3=13位，一個short int型變量共16位，則一個short int型變量可以存下所有信息。通過對該變量進(jìn)行位運(yùn)算就可以存儲和讀取所需的基矩陣信息。此方法很大程度減少了GPU存儲空間的開銷，加快了主機(jī)端到GPU端的拷貝速度，而且簡便的位運(yùn)算不會增加運(yùn)算的復(fù)雜度。

3 仿 真

本文以NVIDIA公司的TITAN Xp GPU為硬件平臺，以CUDA 9.0 + Visual Studio 2017為編譯器。表1為NVIDIA TITAN Xp GPU資源。寄存器/線程表示每條線程所分配到的寄存器個數(shù)。FLOPS為floating-point operations per second的縮寫，表示每秒GPU所能夠進(jìn)行的浮點(diǎn)運(yùn)算數(shù)目(每秒浮點(diǎn)運(yùn)算量)，T為tera的縮寫，表示一萬億(=1012)，TFLOPS則表示每秒一萬億次的浮點(diǎn)運(yùn)算。

表1 GPU資源Tab.1 Resource of GPU

本文利用該GPU，同時譯碼糾錯多個碼字，實(shí)現(xiàn)了高速糾錯譯碼，碼字個數(shù)與譯碼速率對比如圖6。由圖6可以看出，譯碼器譯碼率為0.1，碼長為106的碼字，循環(huán)迭代50次時，不同碼字?jǐn)?shù)量對應(yīng)的譯碼速率。從1個碼字至16個碼字，隨著碼字?jǐn)?shù)量的增加，譯碼速度逐步增加。在同時譯碼16個碼字時，內(nèi)存讀寫的等待時間與更新消息的等待時間相同，譯碼器達(dá)到最大的譯碼速度。碼字?jǐn)?shù)量增加后，線程所需的寄存器資源短缺，數(shù)據(jù)存入全局內(nèi)存，增加了內(nèi)存讀寫的時間，所以在32個碼字至64個碼字時，譯碼器速度降低。隨著碼字?jǐn)?shù)量的繼續(xù)增加，降低了內(nèi)存讀取等待時間的影響，所以譯碼器在同時譯碼128個碼字時，譯碼速度稍有增加。當(dāng)超出128個碼字時，數(shù)據(jù)量超出GPU的存儲空間大小，譯碼器無法實(shí)現(xiàn)譯碼。

圖6 碼字個數(shù)與譯碼速率對比Fig.6 Comparison of the number of codewords and decoding speed

表2展示了本文提出的分層譯碼器譯相同碼長不同數(shù)量的連接邊的碼字的譯碼情況。碼字連接邊的數(shù)量越大，譯碼需要計(jì)算的信息值就越多。由表2中數(shù)據(jù)可看出：3個不同的碼字，連接邊的數(shù)量從上至下逐漸增加，計(jì)算的邊的信息值的數(shù)量對應(yīng)有所增加，即校驗(yàn)節(jié)點(diǎn)傳遞給變量節(jié)點(diǎn)的信息值的數(shù)量和變量節(jié)點(diǎn)傳遞給校驗(yàn)節(jié)點(diǎn)的信息值的數(shù)量有所增加。在相同碼長相同擴(kuò)展因子相同碼字個數(shù)的條件下，碼字連接的邊的數(shù)量越大，消耗的譯碼時長越長，吞吐量越小。

表2 分層譯碼器譯同碼長不同數(shù)量的連接邊的碼字的譯碼速率Tab.2 Decoding speed of a layered decoder for decoding codewords with different numbers of connectededges of the same code length

圖7展示了具有和不具有提前終止功能的分層譯碼器的性能。由圖7可知，當(dāng)該譯碼器譯碼率為0.1，碼長為106，擴(kuò)展因子為2 500的碼字，且同時譯16個碼字時，不具有提前終止功能的分層譯碼器固定循環(huán)次數(shù)為50次，不論信噪比為多少，吞吐量都約為41.50 Mbit/s。而具有提前終止功能的分層譯碼器在不同的信噪比條件下需要的譯碼迭代次數(shù)不同，相應(yīng)的吞吐量也不同。當(dāng)信噪比小于0.161時，具有提前終止功能的分層譯碼器不僅需要執(zhí)行50次譯碼迭代，判別是否譯碼成功還需要額外的消耗時間，所以具有提前終止功能的分層譯碼器速率略小于不具有提前終止功能的分層譯碼器，信噪比大于0.161后，前者需要的迭代次數(shù)逐漸減少，吞吐量逐漸增大，在信噪比為0.191時，譯碼速率達(dá)到了90.047 Mbit/s。因此，在傳輸環(huán)境較好，信噪比較大時，偏向于選擇具有提前終止功能的譯碼器。

圖7 具有/不具有提前終止功能的分層譯碼器譯相同碼字的譯碼速率Fig.7 Layered decoder with/without early termination decoding speed for the same codeword

表3為本文與文獻(xiàn)[5-7]中實(shí)現(xiàn)的譯碼器性能對比。可以看出，文獻(xiàn)[5]利用AMD Tahiti Graphics Processor實(shí)現(xiàn)的GPU譯碼器，在碼長為220，碼率為0.1時，吞吐量為7.10 Mbit/s，而文獻(xiàn)[6]在同樣的碼長同樣的碼率下，引入提前終止條件，利用NVIDIA GeForce GTX 1080實(shí)現(xiàn)的GPU譯碼器達(dá)到了9.17 Mbit/s的譯碼速率；文獻(xiàn)[7]利用NVIDIA TITAN Xp實(shí)現(xiàn)的GPU譯碼器通過減少迭代過程中度為1的變量節(jié)點(diǎn)的更新，譯碼速率達(dá)到了30.39 Mbit/s。本文采用與文獻(xiàn)[7]同樣的GPU硬件，采用分層BP譯碼算法，在碼長為106，碼率為0.1時，實(shí)現(xiàn)了41.50 Mbit/s的譯碼速率。

表3 譯碼器性能對比Tab.3 Decoder performance comparison

4 結(jié) 論

本文針對CV-QKD系統(tǒng)中低信噪比下傳輸超長碼的特點(diǎn)，設(shè)計(jì)出一種基于分層置信傳播譯碼(layered BP, LBP)算法的GPU譯碼器，該譯碼器譯碼具有較長碼長的QC-LDPC碼。本文采用收斂速度更快的分層置信傳播譯碼算法，并且優(yōu)化了核函數(shù)內(nèi)線程的分配方式及QC-LDPC碼基矩陣的存儲方式，提升了譯碼速率。在碼長為106，碼率為0.1，循環(huán)50次，同時譯16個碼字的條件下，該譯碼器的速率達(dá)到了41.50 Mbit/s。該譯碼器的糾錯譯碼速率比之前的文獻(xiàn)所提到的速率提升10 Mbit/s左右，實(shí)現(xiàn)了更高效的密鑰協(xié)商過程。雖然該譯碼器速率有提升，但是也存在缺點(diǎn)，例如，存儲了多份同一個校驗(yàn)節(jié)點(diǎn)的LLR信息，同時譯碼的碼字個數(shù)只有16個等等。通過Nsight還觀察到該譯碼器受限于寄存器和warps。今后的工作將集中于減少不必要的信息存儲，增加同時譯碼的碼字個數(shù)和消除譯碼器受限因素。