吳思遠(yuǎn)，陳 成，姜 明，徐安來

(東南大學(xué) 信息科學(xué)與工程學(xué)院，江蘇 南京 214135)

0 引言

隨著第五代移動(dòng)通信技術(shù)(5th Generation Mobile Communication Technology, 5G)的商業(yè)化,基于5G應(yīng)用[1-2]和學(xué)術(shù)研究的需求日益增加。低密度奇偶校驗(yàn)(Low-Density Parity-Check,LDPC)碼是5G[3-4]采用的信道編碼技術(shù)之一,是一種具有稀疏校驗(yàn)矩陣的分組糾錯(cuò)碼,幾乎適用于所有信道,可以應(yīng)用于有線通信、深空通信、光通信[5-6]以及磁盤存儲(chǔ)[7-8]工業(yè)等對誤碼率要求更加苛刻的場合,因此成為編碼界近30年來的研究熱點(diǎn)。LDPC碼的性能逼近香農(nóng)極限,具有優(yōu)良的抗干擾性能,但是編譯碼過程過于復(fù)雜,因此如何設(shè)計(jì)性能優(yōu)良、便于硬件實(shí)現(xiàn)的編譯碼器成為LDPC碼編譯碼技術(shù)研究中的一個(gè)關(guān)鍵問題。

目前,LDPC碼編譯碼的硬件實(shí)現(xiàn)研究主要分為3個(gè)方向,分別是可編程邏輯門陣列(Field Programmable Gate Array, FPGA)[9-10]、中央處理器(Central Processing Unit, CPU)和數(shù)字信號(hào)處理器(Digital Signal Processing, DSP)[11-13]。隨著國內(nèi)外在硬件平臺(tái)研究的不斷深入、計(jì)算機(jī)處理能力不斷提高,編譯碼器的硬件實(shí)現(xiàn)成為LDPC碼編譯碼技術(shù)研究中的一個(gè)重要問題[14]。LDPC碼編譯碼器的優(yōu)化設(shè)計(jì)是LDPC 碼工程應(yīng)用的前提,但是在以往的研究中,編碼器硬件平臺(tái)具體實(shí)現(xiàn)方面的文獻(xiàn)較少,且吞吐率并不高[15]。因?yàn)镈SP具有運(yùn)算能力強(qiáng)、速度快、體積小、采用軟件編程靈活度高等優(yōu)點(diǎn),提出了基于CEVA-XC4500 DSP的5G-LDPC碼編碼[16]。

5G-LDPC碼編碼需要高密度數(shù)據(jù)處理,使用普通的嵌入式系統(tǒng)處理將面臨硬件資源不足和運(yùn)算效率低的問題。針對這一情況,本文采用極低功耗、高密度計(jì)算的CEVA-XC4500 DSP作為計(jì)算單元,結(jié)合該DSP集成了超長指令字(Very Long Instruction Word, VLIW)和單指令多數(shù)據(jù)(Single Instruction Multiple Data, SIMD)矢量功能的完全可編程架構(gòu)特點(diǎn),利用SIMD的矢量化、內(nèi)聯(lián)指令集優(yōu)化和編譯器優(yōu)化選項(xiàng)合理設(shè)置等多種優(yōu)化技巧,在CEVA-XC Toolbox平臺(tái)上實(shí)現(xiàn)5G-LDPC碼編碼。本文的研究工作是針對CEVA-CX4500 DSP芯片的特定指令結(jié)構(gòu)和5G-LDPC碼的準(zhǔn)循環(huán)校驗(yàn)矩陣,實(shí)現(xiàn)支持5G業(yè)務(wù)信道的高速LDPC碼編碼。采用芯片內(nèi)聯(lián)指令集優(yōu)化后的5G-LDPC碼編碼,平均吞吐率顯著提高,與C語言版本比較,吞吐率提高超過6倍。通過矢量化操作和使用內(nèi)聯(lián)指令集,針對5G的基圖2(BG2)低碼率應(yīng)用場景,優(yōu)化的5G-LDPC碼編碼最大吞吐率可達(dá)到250 Mb/s,若只考慮核心矩陣,最大吞吐率可達(dá)到1.6 Gb/s。

1 5G-LDPC碼編碼原理

1.1 準(zhǔn)循環(huán)5G-LDPC碼的“a-0-a”雙對角結(jié)構(gòu)介紹

圖1為5G LDPC碼校驗(yàn)矩陣示意,A、B為校驗(yàn)矩陣的核心部分,其中B對應(yīng)核心部分的校驗(yàn)比特。C、D、E為拓展部分,其中E為單對角矩陣[17]。K為信息比特長度,M1為核心部分校驗(yàn)比特長度,M2為拓展部分校驗(yàn)比特長度。

圖1 5G-LDPC碼校驗(yàn)矩陣示意Fig.1 Schematic diagram of 5G-LDPC code verification matrix

準(zhǔn)循環(huán)性質(zhì)是指校驗(yàn)矩陣H由多個(gè)大小為Z的子矩陣構(gòu)成,Z為拓展因子,每個(gè)子矩陣為全零方陣或?qū)挝痪仃囇h(huán)右移得到的置換矩陣。每一個(gè)子矩陣都可以用I(Pi,j)表示,其中I表示大小為Z的單位陣,Pi,j表示在第i行第j列處單位陣的循環(huán)右移值。Pi,j取值為-1時(shí)對應(yīng)大小為Z的全零方陣,取值為非負(fù)時(shí)對應(yīng)大小為Z的單位陣循環(huán)右移Pi,j位[18]。

“a-0-a”雙對角結(jié)構(gòu)是指核心矩陣校驗(yàn)位的子矩陣B第1列的第1個(gè)元素和最后1個(gè)元素的Pi,j為同1個(gè)非負(fù)值,中間元素的Pi,j也為非負(fù)值(如果行數(shù)是奇數(shù)則取中間行為中間元素,如果行數(shù)是偶數(shù)則取2個(gè)中間行中的一個(gè)為中間元素),其余元素的Pi,j都為-1,該子矩陣B其余列為雙對角結(jié)構(gòu)[19]。

圖2為iLS=0的BG2的核心部分基矩陣示意。核心部分的行數(shù)和列數(shù)分別用M1和N1表示,則圖2的M1=4,N1=14。第N1-M1列為“a-0-a”結(jié)構(gòu)[20],即對應(yīng)核心矩陣校驗(yàn)位的子矩陣B第1列為“a-0-a”結(jié)構(gòu),該子矩陣B其余列為雙對角結(jié)構(gòu)[21]。

圖2 BG2核心部分示意Fig.2 Schematic diagram of BG2 core part

1.2 5G-LDPC碼分塊累加編碼介紹

因?yàn)?G-LDPC碼的校驗(yàn)矩陣同時(shí)具有準(zhǔn)循環(huán)性質(zhì)和雙對角結(jié)構(gòu),所以使用編碼高效的分塊累加編碼。將長為K的信息比特分為Kb個(gè)子向量mi,i=0,1,…,Kb-1,每個(gè)子向量的長度為Z。5G協(xié)議制定了BG1和BG2兩組矩陣,BG1的Kb=22,BG2的Kb=10,在本例中以BG2為研究對象,Kb=10。記向量形式的信息比特為m=[m0,m1,…,mKb-1]。將核心部分長度為M1的校驗(yàn)比特分為Mb1=4個(gè)長度為Z的子向量pi,i=0, 1, 2, 3。記向量形式的校驗(yàn)比特為p=[p0,p1,p2,p3]。則整個(gè)核心部分的編碼結(jié)果可以表示為c=[mp],圖2的校驗(yàn)矩陣可以表示為:

(1)

使用分塊累加編碼,根據(jù)H·cT=0可得下面4個(gè)公式(本文編碼涉及的乘加運(yùn)算皆為二進(jìn)制編碼中的模二運(yùn)算):

(2)

(3)

(4)

(5)

將式(2)～式(5)模二加得到下式:

(6)

因?yàn)槭悄６?所以式(6)可以變化為:

(7)

(8)

(9)

(10)

至此,已經(jīng)解出核心部分的全部校驗(yàn)比特向量。

將拓展部分長度為M2的校驗(yàn)比特分為Mb2個(gè)長度為Z的子向量pi,i=Mb1,Mb1+1,…,Mb1+Mb2-1。記向量形式的拓展部分校驗(yàn)比特為p=[pMb1,pMb1+1,…,pMb1+Mb2-1]。因?yàn)橥卣共糠諧、D、E的E為單對角矩陣,所以可以十分簡單地得到拓展部分的校驗(yàn)比特向量:

(11)

至此,完成了整個(gè)校驗(yàn)矩陣的編碼。

定義信息比特?cái)?shù)為K,DSP的主頻為f,總指令周期(cycle)數(shù)為Ctotal,核心矩陣指令周期數(shù)為Ccore,總吞吐率為ηtotal,核心矩陣吞吐率為ηcore,在CEVA-XC4500 DSP內(nèi)核上的總吞吐率和核心矩陣吞吐率的計(jì)算如下:

(12)

(13)

2 5G-LDPC碼編碼CEVA-XC4500 DSP實(shí)現(xiàn)

2.1 CEVA-XC4500 DSP介紹

CEVA-XC4500是第八代可獲許可的DSP核心,基于CEVA-X16xx DSP核心的架構(gòu)進(jìn)行設(shè)計(jì)。CEVA-XC4500是一個(gè)功能強(qiáng)大、低功耗的DSP處理器系列,專為高級(jí)無線通信而設(shè)計(jì)和優(yōu)化。這種完全可編程的體系結(jié)構(gòu)支持軟件中多個(gè)空中接口的完整收發(fā)器處理。單個(gè)CEVA-XC4500內(nèi)核就能夠處理發(fā)送和接收,因此它對算術(shù)運(yùn)算和比特操作都有廣泛的支持。

本文主要研究CEVA-XC4500 DSP核心在LDPC碼編碼中的應(yīng)用。通常稱C語言編程使用的基本數(shù)據(jù)類型如整形(char、short、int等)和浮點(diǎn)類型(float、double)為標(biāo)量類型,CEVA-XC4500 DSP核心的指令集所使用的數(shù)據(jù)類型為矢量類型。CEVA-XC4500 DSP核心的指令集所使用的矢量類型用vec_t表示,矢量類型vec_t由2個(gè)矢量計(jì)算單元(VCU)組成,每個(gè)VCU的結(jié)構(gòu)相同,每個(gè)VCU由一組相同的標(biāo)量數(shù)據(jù)類型組合而成,CEVA-XC4500 DSP核心支持的元素標(biāo)量數(shù)據(jù)類型分別為char、short、long、long long,占用數(shù)據(jù)位寬分別為8、16、32、64 bit,被矢量類型vec_t包含的數(shù)目分別為32、16、8、4。每個(gè)VCU占用數(shù)據(jù)位寬256 bit,而每個(gè)矢量類型vec_t包含2個(gè)VCU,則每個(gè)矢量類型vec_t占用數(shù)據(jù)位寬512 bit。

2.2 5G-LDPC碼編碼在CEVA-XC4500 DSP上的C語言實(shí)現(xiàn)

在DSP上用C語言實(shí)現(xiàn)5G-LDPC碼編碼。第一步是根據(jù)輸入的信息比特長度K和碼率R確定Z。第二步根據(jù)K和R讀入基圖并確定基矩陣。第三步根據(jù)K和R計(jì)算實(shí)際參與編碼的基矩陣的行數(shù)和列數(shù),再計(jì)算出shorten數(shù)和打孔數(shù)。第四步計(jì)算核心部分的校驗(yàn)比特。第五步計(jì)算拓展部分的校驗(yàn)比特。

本文采用分塊累加的方法對信息比特進(jìn)行5G-LDPC碼編碼。首先將信息比特按順序每Zbit分成一組,之后將分組的信息比特依次存儲(chǔ)于數(shù)據(jù)類型為unsigned long long的數(shù)組中,其中數(shù)據(jù)類型unsigned long long占用位寬64 bit,即一個(gè)數(shù)組元素可以存放64個(gè)信息比特。

因?yàn)閿?shù)據(jù)類型為unsigned long long的數(shù)組的每一個(gè)數(shù)組元素都存放著信息比特,所以分塊累加編碼方法的循環(huán)移位操作就相當(dāng)于對數(shù)組元素按位進(jìn)行循環(huán)移位。因?yàn)镃語言中沒有按位進(jìn)行循環(huán)移位的指令,所以要靠按位進(jìn)行邏輯移位指令和按位或指令來達(dá)到循環(huán)移位的效果:邏輯左移x位按位或邏輯右移(Z-x)位就相當(dāng)于循環(huán)左移x位。其實(shí)現(xiàn)源代碼如下:

*temp2 = (*(sourcebit+0) <>(Z-Baset[0]));

t2[0] = t2[0] ^ *temp2;

循環(huán)左移Baset[0]位可以用將數(shù)組元素sourcebit按位邏輯左移Baset[0]位按位或按位邏輯右移(Z-Baset[0])位實(shí)現(xiàn)。

然后再根據(jù)基矩陣中的非-1元素所在位置對存儲(chǔ)信息比特的數(shù)組進(jìn)行循環(huán)移位和異或累加就能完成對應(yīng)于5G-LDPC碼編碼原理中式(2)～式(5)的編碼。之后再根據(jù)5G-LDPC碼編碼原理中式(7)～式(11)進(jìn)行相應(yīng)的循環(huán)移位和按位異或操作就能計(jì)算出核心部分和拓展部分的校驗(yàn)比特。

指令周期數(shù)是計(jì)算機(jī)處理器執(zhí)行代碼指令所需的周期數(shù)。一個(gè)指令周期包括若干個(gè)時(shí)鐘周期,且不同的指令會(huì)有不同的指令周期數(shù)。指令周期數(shù)越少,表示該代碼的執(zhí)行效率越高。指令周期數(shù)也可以根據(jù)式(12)和式(13)轉(zhuǎn)換成吞吐率,LDPC碼編碼程序吞吐率越高,意味針對該處理器的LDPC碼編碼的代碼執(zhí)行效率越高。

定義核心部分指令周期數(shù)(式(2)～式(5)和式(7)～式(10)周期數(shù)的總和)為Ccore,拓展部分周期數(shù)(式(11)周期數(shù)的總和)為Cext。圖3給出了C語言實(shí)現(xiàn)時(shí)Z為64、256核心部分和拓展部分編碼的指令周期數(shù)的柱狀圖。從圖3可以看出,用C語言實(shí)現(xiàn)5G-LDPC碼編碼時(shí),隨著Z的增大,指令周期數(shù)會(huì)極大增加,導(dǎo)致吞吐率急劇下降,根本無法滿足5G-LDPC碼編碼工程應(yīng)用指標(biāo)要求。為了解決這一問題,本文采用了矢量化和使用內(nèi)聯(lián)指令集等操作進(jìn)行優(yōu)化。

圖3 C語言實(shí)現(xiàn)時(shí)核心部分和拓展部分指令周期數(shù)Fig.3 Number of instruction cycles for the core and extension parts in C language implementation

2.3 5G-LDPC碼編碼在CEVA-XC4500 DSP上的內(nèi)聯(lián)指令集實(shí)現(xiàn)

在CEVA-XC4500 DSP上進(jìn)行5G-LDPC碼編碼優(yōu)化時(shí),要合理利用CEVA-XC4500 DSP內(nèi)聯(lián)指令集,能夠極大節(jié)省運(yùn)算時(shí)間;盡量多使用單指令多數(shù)據(jù)SIMD,一條指令處理多個(gè)數(shù)據(jù),提高運(yùn)算效率。

5G-LDPC碼編碼的優(yōu)化主要面臨以下問題:第一,5G-LDPC碼編碼涉及大量循環(huán)移位操作。因?yàn)閿?shù)據(jù)位寬最大為64 bit,當(dāng)Z>64時(shí),循環(huán)移位操作的次數(shù)急劇增加;第二,5G-LDPC碼編碼涉及大量按位異或操作,按位異或操作未優(yōu)化前在CEVA-XC4500 DSP上運(yùn)算效率低。

針對以上問題,本文主要從以下幾個(gè)方面做了優(yōu)化:

(1)矢量化。CEVA-XC4500 DSP的內(nèi)聯(lián)指令集特有的就是它的矢量類型vec_t型變量,vec_t型變量由2個(gè)VCU組成,VCU的結(jié)構(gòu)如圖4所示。

圖4 vec_t型變量的VCU的結(jié)構(gòu)Fig.4 Structure of vec_t type variable

從圖4可以看出,一個(gè)VCU有8個(gè)單元,每一個(gè)單元占數(shù)據(jù)位寬32 bit,而每一個(gè)vec_t型變量有2個(gè)VCU,分別是VCU0和VCU1,因此一個(gè)vec_t型變量含有16個(gè)單元,可以操作16×32=512 bit。優(yōu)化時(shí)應(yīng)盡可能使用CEVA-XC4500 DSP內(nèi)聯(lián)指令對5G-LDPC碼編碼進(jìn)行矢量化并行處理。

(2)內(nèi)聯(lián)指令集優(yōu)化。利用內(nèi)聯(lián)指令集對5G-LDPC碼編碼代碼進(jìn)行優(yōu)化。5G-LDPC碼編碼代碼使用CEVA-XC4500 DSP的內(nèi)聯(lián)指令vlddw_v32和vstdw_v32_vuX來替代數(shù)據(jù)的加載和存儲(chǔ)以加快代碼效率。利用vxor_v32_v32_v32指令加快異或運(yùn)算。使用vshift_v32_c32_v32_lg內(nèi)聯(lián)指令替代編碼代碼中的大量邏輯移位操作,提高代碼的執(zhí)行效率。

(3)5G-LDPC碼編碼循環(huán)移位算法優(yōu)化。因?yàn)閮?nèi)聯(lián)指令集中沒有循環(huán)移位指令,所以循環(huán)移位操作要通過內(nèi)聯(lián)指令集中的按位邏輯移位指令、向量置換指令和按位或指令來達(dá)到循環(huán)移位的效果。CEVA的內(nèi)聯(lián)指令中的邏輯移位指令是分別將每一個(gè)單元進(jìn)行邏輯移位,而不是將整個(gè)VCU看作整體進(jìn)行邏輯移位,例如邏輯左移x位指令是分別將vec_t型變量的16個(gè)單元進(jìn)行左移而不是將這512 bit看作整體進(jìn)行左移。

以Z=192,循環(huán)左移33 bit為例介紹內(nèi)聯(lián)指令的循環(huán)移位方法。下圖中的k0～k5分別各自代表32個(gè)信息比特向量。首先vec_t型變量vt讀入192個(gè)信息比特,變量vt的內(nèi)存空間如圖5(a)所示。因?yàn)镃EVA的內(nèi)聯(lián)指令中的移位指令是分別將每一個(gè)單元進(jìn)行邏輯移位,所以如果直接用內(nèi)聯(lián)指令進(jìn)行左移33 bit就會(huì)導(dǎo)致每一個(gè)k中的信息比特都為0。所以先將33對32取商得到1,這個(gè)取商得到的1意味著要將k0、k1、k2、k3、k4、k5的排列順序用向量置換內(nèi)聯(lián)指令循環(huán)左移1位得到k1、k2、k3、k4、k5、k0的排列順序并存儲(chǔ)在vec_t型變量x1中,變量x1的內(nèi)存空間如圖5(b)所示,這相當(dāng)于將信息比特循環(huán)左移了32位。之后再在圖5(b)的基礎(chǔ)上將k的排列順序用向量置換內(nèi)聯(lián)指令再循環(huán)左移1位并存儲(chǔ)在vec_t型變量x2中 ,變量x2的內(nèi)存空間如圖5(c)所示,這相當(dāng)于將原始的信息比特循環(huán)左移了64位。之后再將33對32取余得到1,取余得到的1意味著對vec_t型變量x1使用邏輯左移1位的內(nèi)聯(lián)指令,對vec_t型變量x2使用邏輯右移32-1 bit的內(nèi)聯(lián)指令,之后對x1和x2使用異或的內(nèi)聯(lián)指令就實(shí)現(xiàn)了將v1循環(huán)左移33 bit。

(a)變量vt

該循環(huán)移位算法優(yōu)化可以實(shí)現(xiàn)的關(guān)鍵是內(nèi)聯(lián)指令中的向量置換指令vpermutew可以花費(fèi)極少的指令周期數(shù)就對k0、k1、k2、k3、k4、k5的順序進(jìn)行重新排列。

(4)合理的編譯器選項(xiàng)設(shè)置。編譯可執(zhí)行代碼前,在CEVA-XC Toolbox編譯環(huán)境選取-O3(速度優(yōu)化)和-Os0(最大的代碼尺寸),以獲取高效的可執(zhí)行代碼。

圖6給出了指令集實(shí)現(xiàn)時(shí)Z為64、256核心部分和拓展部分編碼的指令周期數(shù)的柱狀圖。從圖6可以看出,雖然內(nèi)聯(lián)指令實(shí)現(xiàn)5G-LDPC碼編碼時(shí)隨著Z的增大,指令周期數(shù)會(huì)增加。對比圖3,內(nèi)聯(lián)指令實(shí)現(xiàn)的指令周期數(shù)平均僅有C語言實(shí)現(xiàn)的1/6,指令周期數(shù)所對應(yīng)的吞吐率滿足5G-LDPC碼編碼工程應(yīng)用指標(biāo)要求。

圖6 內(nèi)聯(lián)指令實(shí)現(xiàn)時(shí)核心部分和拓展部分指令周期數(shù)Fig.6 Number of instruction cycles for the core and extension parts during the implementation of inline instructions

C語言5G-LDPC碼編碼、優(yōu)化后內(nèi)聯(lián)指令集5G-LDPC碼編碼和核心矩陣編碼吞吐率曲線如圖7所示。圖7中的不同曲線表示不同代碼下5G-LDPC碼編碼器的實(shí)現(xiàn)性能,從圖中可以看出,內(nèi)聯(lián)指令集編碼的吞吐率全面優(yōu)于C語言編碼,在Z=80處吞吐率都有大幅下降是因?yàn)閿?shù)據(jù)位寬最大為64 bit,當(dāng)Z>64時(shí),要使用更多的指令來實(shí)現(xiàn)循環(huán)移位操作,導(dǎo)致指令周期數(shù)增加、吞吐率降低。內(nèi)聯(lián)指令集編碼的中長塊編碼吞吐率大于100 Mb/s,核心矩陣吞吐率超過1 Gb/s,最大吞吐率可達(dá)到250 Mb/s,最大核心矩陣吞吐率達(dá)到1.6 Gb/s,滿足5G-LDPC碼編碼工程應(yīng)用指標(biāo)要求。

圖7 吞吐率曲線Fig.7 Throughput curve

3 結(jié)束語

本文在理解5G-LDPC碼編碼原理的基礎(chǔ)上,利用CEVA-XC4500 DSP的極低功耗、高密度計(jì)算的架構(gòu)和內(nèi)聯(lián)指令集的特點(diǎn)實(shí)現(xiàn)了5G-LDPC碼編碼在CEVA-XC4500 DSP上的優(yōu)化,通過矢量化策略、使用內(nèi)聯(lián)指令集、算法優(yōu)化和合理的編譯器選項(xiàng)設(shè)置等優(yōu)化手段,提高代碼效率。仿真結(jié)果表明,經(jīng)過優(yōu)化的5G-LDPC碼編碼中長塊編碼吞吐率大于100 Mb/s,核心矩陣吞吐率超過1 Gb/s,最大吞吐率達(dá)到250 Mb/s,只考慮核心矩陣,最大吞吐率達(dá)到1.6 Gb/s,滿足5G-LDPC碼編碼工程應(yīng)用指標(biāo)要求。此外,該5G-LDPC碼編碼優(yōu)化的思想具有通用性,為信道編碼領(lǐng)域內(nèi)的此類編碼在相似嵌入式平臺(tái)上實(shí)現(xiàn)提供了參考。