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

　?。ǜＶ荽髮W 物理與信息工程學院，福建 福州 350116）

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

　　關鍵詞：高效率視頻編碼；離散余弦變換；FPGA；脈動陣列

　　中圖分類號：TN919.81文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.09.016

　　引用格式：潘蘇文，葉宇煌，鄭明魁，等.基于脈動陣列的HEVC 8×8整數DCT變換的設計與實現［J］.微型機與應用，2017,36（9）：53-56,59.

0引言

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

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

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

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

1DCT變換和脈動陣列原理分析

　　1.1DCT原理分析

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

　　這里式（1）也可以寫成矩陣運算形式

　　N=Cn（2）

　　其中C為M點DCT變換矩陣，且C中對應索引（m,n）的系數值cmn為：

　　作為正交變換，反變換n=CTN。因為DCT有內核可分解的性質，因此可以把2D DCT分解成兩個一維DCT進行運算。設X是一個N×N維的矩陣，則對X進行2D DCT有式(4):

　　Y=CXCT(4)

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

　　Y=ZCT(5)

　　Z=CX(6)

　　式中，Z為中間值矩陣。因此，在做二維DCT變換時可以運用一維DCT變換來計算，流程框圖如圖1所示。

　　1.2脈動原理分析

　　脈動陣列是由卡內基梅隆大學的KUNG H.T.教授最早提出。它是由多個處理單元（PE）按照一定互聯規(guī)則組成的網絡，有一維線性、二維矩陣陣列等。每個PE單元具有相同的功能，并且PE單元只能與自己相鄰的PE進行通信，它們的通信是非常規(guī)則的，每個PE都有自己的內部存儲器，用于寄存由鄰近PE傳過來的待處理的數據。

　　DCT變換當以矩陣相乘的形式表示時，可以理解為3個矩陣的相乘。矩陣相乘之所以可以用脈動陣列去實現，原因在于脈動陣列適合那些高度規(guī)則的算法實現，而矩陣相乘本身就是一個高度規(guī)則的算法形式?？梢杂肈G依賴圖去判斷一個算法的規(guī)則性。所謂DG依賴圖判斷規(guī)則是指如果依賴圖的任一節(jié)點沿某個方向的邊都存在，則稱DG是規(guī)則的，換句話說DG的所有節(jié)點具有相同形式的邊。由于DCT變換算法最后可以用矩陣相乘的形式表示出來，用DG依賴圖的判斷規(guī)則可以判斷得到矩陣相乘是一個高度規(guī)則的算法，因此矩陣相乘形式的DCT變換非常適合用脈動陣列的思想去實現，滿足脈動設計的前提條件。

2脈動陣列8×8 DCT的設計與實現

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

　　2.1整體架構

　　如圖2所示，脈動陣列DCT的整體構架由輸入數據處理單元、PE陣列（核心單元）、控制單元和結果轉換單元4部分組成。輸入數據處理單元對8×8大小塊的TU殘差數據和8x8 DCT系數的數據進行重排和延遲，將處理好的數據傳給下個單元做處理。PE陣列單元由64個獨立PE單元組成，每個獨立的PE單元完成相乘和累加的操作。控制單元負責每個模塊的協同合作和控制數據的輸入輸出。結果轉換單元提取經過PE陣列處理后的最終DCT結果輸出。

　　2.2輸入數據處理單元

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

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

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

　　中間值會在下個階段做行變換時與系數一起作為輸入進入數據處理單元，重復列變換的操作。

　　2.3PE陣列

　　PE陣列模塊由64個獨立的PE單元構成，每個PE的功能主要有：負責接收輸入數據、結果輸出、乘法/累加操作、相鄰PE之間數據通信等。在PE內部使用兩個乘法器和兩個加法器完成乘法累加核心功能，兩個選擇器控制數據的輸入和結果的輸出，如圖5所示。圖中所示PE內部電路圖上下對稱，上半部分主要完成列變化，下半部分負責行變換，上下兩部分功能完全相同，不同的地方在于輸入參數的位深有所改變。In_a、In_b分別對應列變換的系數和殘差的輸入，2d_in_a、2d_in_b分別對應行變換的系數和中間值的輸入，前端選擇器在Count信號的控制下選擇輸入值進入乘法器。乘法器的輸出結果作為加法器的一個輸入，加法器的一個輸入由上一個結果值作為參數，最初值初始化為0。最后的輸出結果由后端選擇器控制。

　　2.4控制單元

　　本設計的控制單元相對比較簡單，由一個控制器組成，控制殘差數據、系數、中間值，以及何時輸入到PE陣列中，何時接收從PE陣列輸出的中間值和最后的結果并把它們存入相應的寄存器組中。

　　2.5結果轉換單元

　　在HEVC標準中，量化是在整數DCT變換之后，量化的同時會把之前由比例因子放大的倍數給予縮小，因此在變換這一步不做處理。結果轉換單元主要負責將最后的DCT變換結果從PE單元中輸出并配合控制單元得到整個設計的最終結果。

3試驗結果與分析

　　3.1功能仿真結果

　　本設計采用Verilog語言對硬件電路進行描述，使用ModelSim10.1d進行功能仿真,在ISE14.2平臺上進行綜合。本設計針對8×8的殘差值做HEVC的整數DCT變換，并在MATLAB上先得到精確結果，表1是原始殘差值，表2是在MATLAB上得到的DCT變換結果，圖6是在ModeSim中仿真的最終值，對比表2和圖6，可以看出兩者結果一致，從而證明本設計實現DCT變換功能的正確性。

　　3.2綜合結果

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

　　另外文獻［6］采用Vivado、LegUp、MATLAB等不同的HLS綜合工具對HM15中編寫的DCT部分進行了綜合，并對每一種尺寸都給出了直接使用乘法器的M模式、使用加法和移位代替乘法操作的AS模式的綜合結果。表3列出的是與本文配置最相近的一個對比結果，可以看出本文提出的算法在頻率、LUTs、每秒處理幀的數量上都有一定的優(yōu)勢。文獻［7］采用無乘法器架構，整個實現方式與本文類似，也是先實現列變換，再把結果做一次行變換。但是文獻［7］中所用周期數較多，對比文獻［7］綜合出的結果可知，在主頻近似的情況下，本文的周期是它的34%，LUTs是它的62%。

4結論

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

　　參考文獻

　?。?］ 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.

　?。?］ 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.

　?。?］ 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.

　?。?］ 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.

　?。?］ 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.