潘蘇文，葉宇煌，鄭明魁，陳志峰，楊秀芝

(福州大學(xué) 物理與信息工程學(xué)院，福建 福州 350116)

基于脈動(dòng)陣列的HEVC8×8整數(shù)DCT變換的設(shè)計(jì)與實(shí)現(xiàn)*

潘蘇文，葉宇煌，鄭明魁，陳志峰，楊秀芝

(福州大學(xué) 物理與信息工程學(xué)院，福建 福州 350116)

文章基于脈動(dòng)陣列實(shí)現(xiàn)HEVC(High Efficiency Video Coding)中8×8的整數(shù)DCT(Discrete Cosine Transform)變換，改進(jìn)通常使用的蝶型算法。整體架構(gòu)基于脈動(dòng)陣列的思想,并采用中間值數(shù)據(jù)重組的設(shè)計(jì)，使得變換模塊可同時(shí)實(shí)現(xiàn)行列變換操作。只需得到列變換的第一個(gè)值便可開(kāi)始行變換，充分利用了PE單元，減少變換時(shí)間并提高計(jì)算模塊的并行性。文中方法不僅適用于DCT變換，也可用于其他的8×8矩陣相乘，具有通用性。綜合結(jié)果表明，該設(shè)計(jì)最高可工作在203.8 MHz的頻率上，與其他算法相比時(shí)間上只需35個(gè)周期，且資源消耗較少。文中方法非常適合于HEVC視頻編碼對(duì)實(shí)時(shí)性的要求，為HEVC編碼標(biāo)準(zhǔn)的硬件實(shí)現(xiàn)提供了參考。

高效率視頻編碼；離散余弦變換；FPGA；脈動(dòng)陣列

0 引言

離散余弦變換最早是由Ahmed在 1974年提出[1],它具有很好的能量集中特性即所謂的去相關(guān)性，在圖像處理和視頻壓縮領(lǐng)域占有重要地位。在先前的視頻編碼標(biāo)準(zhǔn)中，如MPEG-4、H.264/AVC都使用了DCT變換，并且對(duì)變換矩陣做了一定的改進(jìn)，使其具有一定的規(guī)律性，有更好的快速變換算法，更適合編碼壓縮。一般對(duì)于圖像的處理都不是基于一整幀，而是首先將一幀圖像分解成多個(gè)變換塊(Transform Units,TU)，再對(duì)每塊TU做DCT變換。目前新興的高效率視頻編碼標(biāo)準(zhǔn)HEVC也采用了這種方法，HEVC的TU有4×4到32×32大小塊，除了4×4大小的TU采用離散正弦變換(Discrete Sine Transform)外，其余的TU大小塊都采用整數(shù)DCT變換[2]。HEVC靈活的TU劃分提高了壓縮效率，編碼效率可以提高一倍，但同時(shí)也增加了復(fù)雜度。實(shí)現(xiàn)DCT需要多次進(jìn)行乘法和加法的操作，帶來(lái)了時(shí)間延時(shí)和面積消耗。

為了讓DCT有更好的實(shí)現(xiàn)算法,前人做了很多的努力來(lái)減輕DCT/IDCT(Inverse Discrete Cosine Transform)所帶來(lái)的密集的操作。Budagavi[3]等人利用DCT系數(shù)的奇偶可分解性和硬件共享技術(shù)來(lái)節(jié)約硬件開(kāi)銷(xiāo)，并提出了一個(gè)統(tǒng)一的架構(gòu)實(shí)現(xiàn)正反DCT變換，由此大大減少硬件面積。Meher[4]等人避免使用常規(guī)乘法而是使用更少乘法器的多常數(shù)乘法(Multiple Constant Multiplication,MCM)算法。Ahmed[5]等人將DCT矩陣分解成更小的子矩陣來(lái)減少乘法次數(shù)，它的提升方案中更是可以完全將乘法去除。文獻(xiàn)[6]將蝶型算法分別采用直接乘法器的M模式和使用加法和移位代替乘法操作的AS模式實(shí)現(xiàn)DCT變換。文獻(xiàn)[7]將二維DCT變換轉(zhuǎn)換成兩個(gè)一維變換分別實(shí)現(xiàn)。

在這些方法中幾乎都利用了DCT系數(shù)的對(duì)稱(chēng)性和反對(duì)稱(chēng)性屬性以及蝶型思路去完成DCT變換。然而一旦利用了蝶型，那么整個(gè)算法的并行性就會(huì)有所下降。另外為了增加主頻，還引入了多級(jí)流水處理，這會(huì)進(jìn)一步消耗面積。本文不再基于蝶型算法，而是采用脈動(dòng)陣列設(shè)計(jì)了DCT的硬件實(shí)現(xiàn)，試驗(yàn)結(jié)果顯示，所設(shè)計(jì)的結(jié)構(gòu)只有兩級(jí)流水，具有相對(duì)較低的面積消耗和更高的工作頻率。

1 DCT變換和脈動(dòng)陣列原理分析

1.1 DCT原理分析

假設(shè)輸入為M點(diǎn)的向量n=[n0n1…nM-1]，對(duì)于一維DCT是一個(gè)線(xiàn)性變換，輸出N=[N0N1…NM-1]的值可由式(1)得到[8]：

(1)

這里式(1)也可以寫(xiě)成矩陣運(yùn)算形式

N=Cn

(2)

其中C為M點(diǎn)DCT變換矩陣，且C中對(duì)應(yīng)索引(m,n)的系數(shù)值cmn為：

(3)

作為正交變換，反變換n=CTN。因?yàn)镈CT有內(nèi)核可分解的性質(zhì)，因此可以把2D DCT分解成兩個(gè)一維DCT進(jìn)行運(yùn)算。設(shè)X是一個(gè)N×N維的矩陣，則對(duì)X進(jìn)行2D DCT有式(4):

Y=CXCT

(4)

從式(4)可以看出，其實(shí)二維DCT變換可以分解成串聯(lián)的兩次一維DCT變換，即

Y=ZCT

(5)

Z=CX

(6)

式中，Z為中間值矩陣。因此，在做二維DCT變換時(shí)可以運(yùn)用一維DCT變換來(lái)計(jì)算，流程框圖如圖1所示。

圖1 2D-DCT算法結(jié)構(gòu)

1.2 脈動(dòng)原理分析

脈動(dòng)陣列是由卡內(nèi)基-梅隆大學(xué)的KUNG H.T.教授最早提出。它是由多個(gè)處理單元(PE)按照一定互聯(lián)規(guī)則組成的網(wǎng)絡(luò)，有一維線(xiàn)性、二維矩陣陣列等。每個(gè)PE單元具有相同的功能，并且PE單元只能與自己相鄰的PE進(jìn)行通信，它們的通信是非常規(guī)則的，每個(gè)PE都有自己的內(nèi)部存儲(chǔ)器，用于寄存由鄰近PE傳過(guò)來(lái)的待處理的數(shù)據(jù)。

DCT變換當(dāng)以矩陣相乘的形式表示時(shí)，可以理解為3個(gè)矩陣的相乘。矩陣相乘之所以可以用脈動(dòng)陣列去實(shí)現(xiàn)，原因在于脈動(dòng)陣列適合那些高度規(guī)則的算法實(shí)現(xiàn)，而矩陣相乘本身就是一個(gè)高度規(guī)則的算法形式。可以用DG依賴(lài)圖去判斷一個(gè)算法的規(guī)則性。所謂DG依賴(lài)圖判斷規(guī)則是指如果依賴(lài)圖的任一節(jié)點(diǎn)沿某個(gè)方向的邊都存在，則稱(chēng)DG是規(guī)則的，換句話(huà)說(shuō)DG的所有節(jié)點(diǎn)具有相同形式的邊。由于DCT變換算法最后可以用矩陣相乘的形式表示出來(lái)，用DG依賴(lài)圖的判斷規(guī)則可以判斷得到矩陣相乘是一個(gè)高度規(guī)則的算法，因此矩陣相乘形式的DCT變換非常適合用脈動(dòng)陣列的思想去實(shí)現(xiàn)，滿(mǎn)足脈動(dòng)設(shè)計(jì)的前提條件。

2 脈動(dòng)陣列8×8 DCT的設(shè)計(jì)與實(shí)現(xiàn)

本設(shè)計(jì)基于脈動(dòng)陣列高并行流水?dāng)?shù)據(jù)控制的特點(diǎn)，實(shí)例化多個(gè)PE單元同時(shí)進(jìn)行DCT變換。傳統(tǒng)PE陣列實(shí)現(xiàn)DCT變換要等到列變換做完后，繼續(xù)再做行變換，這樣使得PE單元過(guò)多地被閑置，為了避免在做列變換時(shí)PE的閑置，本文在得到列變換結(jié)果時(shí)即將其輸出到輸入數(shù)據(jù)處理單元，在數(shù)據(jù)處理單元中對(duì)中間值做數(shù)據(jù)重排，經(jīng)過(guò)重排后的數(shù)據(jù)會(huì)被再次送入PE陣列中，這里從輸出中間值到再次輸入到PE單元中做下一次的行變換，中間只需兩個(gè)周期的時(shí)間延遲。另外當(dāng)?shù)玫蕉SDCT第一個(gè)結(jié)果時(shí)，下一個(gè)二維DCT變換也將開(kāi)始，這樣充分提高了PE單元的利用效率，減少了變換周期數(shù)。

2.1 整體架構(gòu)

如圖2所示，脈動(dòng)陣列DCT的整體構(gòu)架由輸入數(shù)據(jù)處理單元、PE陣列(核心單元)、控制單元和結(jié)果轉(zhuǎn)換單元4部分組成。輸入數(shù)據(jù)處理單元對(duì)8×8大小塊的TU殘差數(shù)據(jù)和8x8 DCT系數(shù)的數(shù)據(jù)進(jìn)行重排和延遲，將處理好的數(shù)據(jù)傳給下個(gè)單元做處理。PE陣列單元由64個(gè)獨(dú)立PE單元組成，每個(gè)獨(dú)立的PE單元完成相乘和累加的操作。控制單元負(fù)責(zé)每個(gè)模塊的協(xié)同合作和控制數(shù)據(jù)的輸入輸出。結(jié)果轉(zhuǎn)換單元提取經(jīng)過(guò)PE陣列處理后的最終DCT結(jié)果輸出。

2.2 輸入數(shù)據(jù)處理單元

如果一幅圖像的位深為B，從幀內(nèi)/幀間預(yù)測(cè)得到的殘差值范圍則為-2B+1到2B-1，這同時(shí)也將作為T(mén)U的數(shù)據(jù)。在HEVC中DCT的系數(shù)是由有符號(hào)的整數(shù)組成，這些系數(shù)值是通過(guò)縮放因子為2(6+E/2)放大所得到的矩陣，這里E=log2M,M為T(mén)U的大小。以上所提到的殘差值和DCT系數(shù)以及經(jīng)過(guò)列變換的中間值將作為數(shù)據(jù)處理單元的輸入。

數(shù)據(jù)處理單元主要有兩個(gè)功能：輸入延遲和數(shù)據(jù)重PE陣列，第一象限是殘差值的輸入順序，第三象限是DCT系數(shù)的輸排。輸入延遲如圖3所示，坐標(biāo)的第四象限是入順序，橫縱坐標(biāo)軸所示為周期次序。第1周期X11(殘差矩陣左上角的第一個(gè)值，以此類(lèi)推X12,X18,X81...)和C11(系數(shù)矩陣左上角的第一個(gè)值，以此類(lèi)推C12,C18,C81...)被送入P11單元；第2周期X21,C12被送入P11單元，X12、C11被送入P12單元，X11、C21被送入P21單元；到第8周期時(shí)，X18、C18送入P11單元，這樣P11單元第一次列變換的8個(gè)數(shù)據(jù)全部輸入完成，而P88在第8個(gè)周期則剛好接受X18、C81的最初兩個(gè)數(shù)據(jù)，必須再經(jīng)過(guò)8個(gè)周期才能將數(shù)據(jù)輸入完成。

圖2 系統(tǒng)整體框架

圖3 數(shù)據(jù)輸入順序

在完成列變換之后每個(gè)PE單元都會(huì)存儲(chǔ)一個(gè)結(jié)果值(中間值)，這些值將會(huì)作為下一個(gè)行變換的輸入值，因此需要將重新組織再輸入。本文設(shè)計(jì)中在第9個(gè)周期將會(huì)在P11單元中得到第一個(gè)值Z11,在第10個(gè)周期會(huì)在P12、P21得到Z12、Z21,以此類(lèi)推在第16個(gè)周期會(huì)得到列變換的最后一個(gè)值Z88。這些值一旦在PE生成就會(huì)被輸出到一個(gè)寄存器組中，圖4說(shuō)明了中間值的輸出順序。被存儲(chǔ)在寄存器組中的中間值會(huì)在下個(gè)階段做行變換時(shí)與系數(shù)一起作為輸入進(jìn)入數(shù)據(jù)處理單元，重復(fù)列變換的操作。

圖4 中間值的輸出順序

2.3 PE陣列

PE陣列模塊由64個(gè)獨(dú)立的PE單元構(gòu)成，每個(gè)PE的功能主要有：負(fù)責(zé)接收輸入數(shù)據(jù)、結(jié)果輸出、乘

法/累加操作、相鄰PE之間數(shù)據(jù)通信等。在PE內(nèi)部使用兩個(gè)乘法器和兩個(gè)加法器完成乘法累加核心功能，兩個(gè)選擇器控制數(shù)據(jù)的輸入和結(jié)果的輸出，如圖5所示。圖中所示PE內(nèi)部電路圖上下對(duì)稱(chēng)，上半部分主要完成列變化，下半部分負(fù)責(zé)行變換，上下兩部分功能完全相同，不同的地方在于輸入?yún)?shù)的位深有所改變。In_a、In_b分別對(duì)應(yīng)列變換的系數(shù)和殘差的輸入，2d_in_a、2d_in_b分別對(duì)應(yīng)行變換的系數(shù)和中間值的輸入，前端選擇器在Count信號(hào)的控制下選擇輸入值進(jìn)入乘法器。乘法器的輸出結(jié)果作為加法器的一個(gè)輸入，加法器的一個(gè)輸入由上一個(gè)結(jié)果值作為參數(shù)，最初值初始化為0。最后的輸出結(jié)果由后端選擇器控制。

圖5 PE單元內(nèi)部原理圖

2.4 控制單元

本設(shè)計(jì)的控制單元相對(duì)比較簡(jiǎn)單，由一個(gè)控制器組成，控制殘差數(shù)據(jù)、系數(shù)、中間值，以及何時(shí)輸入到PE陣列中，何時(shí)接收從PE陣列輸出的中間值和最后的結(jié)果并把它們存入相應(yīng)的寄存器組中。

2.5 結(jié)果轉(zhuǎn)換單元

在HEVC標(biāo)準(zhǔn)中，量化是在整數(shù)DCT變換之后，量化的同時(shí)會(huì)把之前由比例因子放大的倍數(shù)給予縮小，因此在變換這一步不做處理。結(jié)果轉(zhuǎn)換單元主要負(fù)責(zé)將最后的DCT變換結(jié)果從PE單元中輸出并配合控制單元得到整個(gè)設(shè)計(jì)的最終結(jié)果。

3 試驗(yàn)結(jié)果與分析

3.1 功能仿真結(jié)果

研究組PTTG、VEGF-C、VEGFR-3陽(yáng)性率及LMVD顯著高于對(duì)照組(P均<0.05)。見(jiàn)表1。

本設(shè)計(jì)采用Verilog語(yǔ)言對(duì)硬件電路進(jìn)行描述，使用ModelSim10.1d進(jìn)行功能仿真,在ISE14.2平臺(tái)上進(jìn)行綜合。本設(shè)計(jì)針對(duì)8×8的殘差值做HEVC的整數(shù)DCT變換，并在MATLAB上先得到精確結(jié)果，表1是原始?xì)埐钪?，?是在MATLAB上得到的DCT變換結(jié)果，圖6是在ModeSim中仿真的最終值，對(duì)比表2和圖6，可以看出兩者結(jié)果一致，從而證明本設(shè)計(jì)實(shí)現(xiàn)DCT變換功能的正確性。

表1 原始?xì)埐钪翟诰仃囍形恢?/p>

表2 MATLAB計(jì)算出的標(biāo)準(zhǔn)結(jié)果

3.2 綜合結(jié)果

在綜合時(shí)，本文設(shè)計(jì)采用Xilinx公司生產(chǎn)virtex-6家族的Xc6vlx550t-2ff1759系列芯片，圖7所示為綜合后的部分RTL圖。圖中PE00、PE01是實(shí)例化出來(lái)的2個(gè)PE單元，以及它們之間的通信連接。

表3 本文與其他算法的比較

另外文獻(xiàn)[6]采用Vivado、LegUp、MATLAB等不同的HLS綜合工具對(duì)HM15中編寫(xiě)的DCT部分進(jìn)行了綜合，并對(duì)每一種尺寸都給出了直接使用乘法器的M模式、使用加法和移位代替乘法操作的AS模式的綜合結(jié)果。表3列出的是與本文配置最相近的一個(gè)對(duì)比結(jié)果，可以看出本文提出的算法在頻率、LUTs、每秒處理幀的數(shù)量上都有一定的優(yōu)勢(shì)。文獻(xiàn)[7]采用無(wú)乘法器架構(gòu)，整個(gè)實(shí)現(xiàn)方

圖6 modesim功能仿真結(jié)果

圖7 ISE綜合結(jié)果

式與本文類(lèi)似，也是先實(shí)現(xiàn)列變換，再把結(jié)果做一次行變換。但是文獻(xiàn)[7]中所用周期數(shù)較多，對(duì)比文獻(xiàn)[7]綜合出的結(jié)果可知，在主頻近似的情況下，本文的周期是它的34%，LUTs是它的62%。

4 結(jié)論

本文基于脈動(dòng)陣列的思想，提出了一個(gè)可快速進(jìn)行DCT變換的框架。算法將DCT變換分解成行列兩個(gè)獨(dú)立的一維變換，并且行列變換模塊共享硬件資源，其中核心部件PE單元的內(nèi)部硬件電路也高度對(duì)稱(chēng)，這些都使得算法更易于FPGA的實(shí)現(xiàn)。在得到列變換的第一個(gè)值時(shí)便開(kāi)始將其送入到輸入數(shù)據(jù)處理單元中，經(jīng)過(guò)重組以后的數(shù)據(jù)再一次被送入PE單元，這之間只要僅僅兩個(gè)時(shí)鐘的延遲便可觸發(fā)開(kāi)始做行變換，整個(gè)框架在控制單元的協(xié)同下逐步有序地進(jìn)行變換，降低了整個(gè)變換的周期數(shù)目。并且整個(gè)算法高度規(guī)則，使得最后的工作頻率相對(duì)較高。此外本文的設(shè)計(jì)雖是針對(duì)HEVC的8×8 DCT變換而實(shí)現(xiàn)的，但是卻適合于任何的8×8矩陣相乘，因此具有相當(dāng)高的通用性。

[1] AHMED N, NATARAJAN T, RAO K R. Discrete cosine transform[J]. IEEE Transactions on Computers,1974, c-23(1):90-93.

[2] SULLIVAN G J, OHM J, HAN W J, et al. Overview of the High Efficiency Video Coding (HEVC) standard[J]. IEEE Transactions on Circuits & Systems for Video Technology, 2012, 22(12):1649-1668.

[3] BUDAGAVI M, FULDSETH A, BJNTEGAARD G, et al. Core transform design in the High Efficiency Video Coding (HEVC) standard[J]. IEEE Journal of Selected Topics in Signal Processing, 2013, 7(6):1029-1041.

[4] MEHER P K, PARK S Y, MOHANTY B K, et al. Efficient integer DCT architectures for HEVC[J]. Circuits & Systems for Video Technology IEEE Transactions on, 2014, 24(1):168-178.

[5] AHMED A, SHAHID M U, REHMAN A U. N point DCT VLSI architecture for emerging HEVC standard[J]. Vlsi Design, 2012,2012(2):1-8.

[6] KALALI E, HAMZAOGLU I. FPGA implementations of HEVC inverse DCT using high-level synthesis[C]. Design and Architectures for Signal and Image Processing, IEEE, 2015:2-4.

[7] EDIRISURIYA A, MADANAYAKE A, CINTRA R J, et al. A multiplication-free digital architecture for 16×16 2-D DCT/DST transform for HEVC[C]. Electrical & Electronics Engineers in Israel, 2012:1-5.

[8] OPPENHEIM A V, SCHAFER R W. Discrete-time signal processing[M]. Prentice Hall: Englewood Cliffs, 1989.

Design and implementation of HEVC 8×8 integer DCT based on systolic array

Pan Suwen，Ye Yuhuang，Zheng Mingkui，Chen Zhifeng，Yang Xiuzhi

(School of Physics and Information Engineering, Fuzhou University,Fuzhou 350116, China)

In this paper, based on systolic array to achieve the HEVC(High Efficiency Video Coding) 8×8 integer DCT transform, and to improve the commonly used butterfly algorithm. The overall architecture based on the thought of systolic array can achieve row and column transform synchronization operation, make full use of PE cells, reduce the conversion time and improve the parallelism of FPGA. The designed architecture is not only suitable for DCT transform, but also can be used for any 8x8 matrix multiplication.Finally the synthetical results show that this design can work in the highest frequency of 213.8 MHz.Compared with other algorithms only 35 cycles of time,and less resource cost.The algorithm is very suitable for the real-time requirement of HEVC video image coding, provides a reference for hardware implementation of HEVC encoding standard.

HEVC; DCT; FPGA; systolic array

福建省科技重大專(zhuān)項(xiàng)基金資助項(xiàng)目(2014HZ0003-3)；福建省自然科學(xué)基金資助項(xiàng)目(2015J01251)；福建省教育廳項(xiàng)目(JA14065)；福州市科技項(xiàng)目計(jì)劃資助(2015-G-61)

TN919.81

A

10.19358/j.issn.1674- 7720.2017.09.016

潘蘇文，葉宇煌，鄭明魁，等.基于脈動(dòng)陣列的HEVC 8×8整數(shù)DCT變換的設(shè)計(jì)與實(shí)現(xiàn)[J].微型機(jī)與應(yīng)用，2017,36(9)：53-56,59.

2017-01-10)

葉宇煌(1961-)，男，碩士，教授，主要研究方向：數(shù)字電視與廣播技術(shù)、微波通信。

鄭明魁(1976-)，男，博士，副教授，主要研究方向：視頻編碼、多媒體通信。