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

　　（福州大學(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)提供了參考。

　　關(guān)鍵詞：高效率視頻編碼；離散余弦變換；FPGA；脈動(dòng)陣列

　　中圖分類號(hào)：TN919.81文獻(xiàn)標(biāo)識(shí)碼：ADOI： 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.

0引言

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

　　離散余弦變換最早是由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)銷，并提出了一個(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ì)稱性和反對(duì)稱性屬性以及蝶型思路去完成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ì)較低的面積消耗和更高的工作頻率。

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

　　1.1DCT原理分析

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

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

　　N=Cn（2）

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

　　作為正交變換，反變換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.2脈動(dòng)原理分析

　　脈動(dòng)陣列是由卡內(nèi)基梅隆大學(xué)的KUNG H.T.教授最早提出。它是由多個(gè)處理單元（PE）按照一定互聯(lián)規(guī)則組成的網(wǎng)絡(luò)，有一維線性、二維矩陣陣列等。每個(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依賴圖去判斷一個(gè)算法的規(guī)則性。所謂DG依賴圖判斷規(guī)則是指如果依賴圖的任一節(jié)點(diǎn)沿某個(gè)方向的邊都存在，則稱DG是規(guī)則的，換句話說(shuō)DG的所有節(jié)點(diǎn)具有相同形式的邊。由于DCT變換算法最后可以用矩陣相乘的形式表示出來(lái)，用DG依賴圖的判斷規(guī)則可以判斷得到矩陣相乘是一個(gè)高度規(guī)則的算法，因此矩陣相乘形式的DCT變換非常適合用脈動(dòng)陣列的思想去實(shí)現(xià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í)也將作為TU的數(shù)據(jù)。在HEVC中DCT的系數(shù)是由有符號(hào)的整數(shù)組成，這些系數(shù)值是通過(guò)縮放因子為2(6+E/2)放大所得到的矩陣，這里E=log2M,M為TU的大小。以上所提到的殘差值和DCT系數(shù)以及經(jīng)過(guò)列變換的中間值將作為數(shù)據(jù)處理單元的輸入。

　　數(shù)據(jù)處理單元主要有兩個(gè)功能：輸入延遲和數(shù)據(jù)重PE陣列，第一象限是殘差值的輸入順序，第三象限是DCT系數(shù)的輸排。輸入延遲如圖3所示，坐標(biāo)的第四象限是入順序，橫縱坐標(biāo)軸所示為周期次序。第1周期X11（殘差矩陣左上角的第一個(gè)值，以此類推X12,X18,X81...）和C11（系數(shù)矩陣左上角的第一個(gè)值，以此類推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ù)輸入完成。

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

　　中間值會(huì)在下個(gè)階段做行變換時(shí)與系數(shù)一起作為輸入進(jìn)入數(shù)據(jù)處理單元，重復(fù)列變換的操作。

　　2.3PE陣列

　　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ì)稱，上半部分主要完成列變化，下半部分負(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é)果由后端選擇器控制。

　　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é)果

　　本設(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變換功能的正確性。

　　3.2綜合結(jié)果

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

　　另外文獻(xiàn)［6］采用Vivado、LegUp、MATLAB等不同的HLS綜合工具對(duì)HM15中編寫的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)方式與本文類似，也是先實(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ì)稱，這些都使得算法更易于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)高的通用性。

　　參考文獻(xiàn)

　　［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.