潘蘇文， 葉宇煌， 鄭明魁， 陳志峰， 楊秀芝
（福州大學 物理與資訊工程學院， 福建 福州 350116）
：文章基於脈動陣列實現HEVC（High Efficiency Video Coding）中8×8的整數DCT（Discrete Cosine Transform）變換， 改進通常使用的蝶型演算法。 整體架構基於脈動陣列的思想,並採用中間值資料重組的設計， 使得變換模組可同時實現行列變換操作。 只需得到列變換的第一個值便可開始行變換， 充分利用了PE單元， 減少變換時間並提高計算模組的並行性。 文中方法不僅適用於DCT變換， 也可用於其他的8×8矩陣相乘， 具有通用性。 綜合結果表明， 該設計最高可工作在203.8 MHz的頻率上， 與其他演算法相比時間上只需35個週期，
：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］,它具有很好的能量集中特性即所謂的去相關性， 在影像處理和視訊壓縮領域佔有重要地位。 在先前的視頻編碼標準中， 如MPEG4、H.264/AVC都使用了DCT變換， 並且對變換矩陣做了一定的改進， 使其具有一定的規律性， 有更好的快速變換演算法，
為了讓DCT有更好的實現演算法,前人做了很多的努力來減輕DCT/IDCT（Inverse Discrete Cosine Transform）所帶來的密集的操作。 Budagavi［3］等人利用DCT係數的奇偶可分解性和硬體共用技術來節約硬體開銷， 並提出了一個統一的架構實現正反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）按照一定互聯規則組成的網路，
DCT變換當以矩陣相乘的形式表示時， 可以理解為3個矩陣的相乘。 矩陣相乘之所以可以用脈動陣列去實現， 原因在於脈動陣列適合那些高度規則的演算法實現， 而矩陣相乘本身就是一個高度規則的演算法形式。 可以用DG依賴圖去判斷一個演算法的規則性。 所謂DG依賴圖判斷規則是指如果依賴圖的任一節點沿某個方向的邊都存在， 則稱DG是規則的， 換句話說DG的所有節點具有相同形式的邊。 由於DCT變換演算法最後可以用矩陣相乘的形式表示出來，用DG依賴圖的判斷規則可以判斷得到矩陣相乘是一個高度規則的演算法，因此矩陣相乘形式的DCT變換非常適合用脈動陣列的思想去實現，滿足脈動設計的前提條件。
2脈動陣列8×8 DCT的設計與實現
本設計基於脈動陣列高並行流水資料控制的特點，產生實體多個PE單元同時進行DCT變換。傳統PE陣列實現DCT變換要等到列變換做完後，繼續再做行變換，這樣使得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公司生產virtex6家族的Xc6vlx550t2ff1759系列晶片，圖7所示為綜合後的部分RTL圖。圖中PE00、PE01是產生實體出來的2個PE單元，以及它們之間的通信連接。
另外文獻［6］採用Vivado、LegUp、MATLAB等不同的HLS綜合工具對HM15中編寫的DCT部分進行了綜合，並對每一種尺寸都給出了直接使用乘法器的M模式、使用加法和移位代替乘法操作的AS模式的綜合結果。表3列出的是與本文配置最相近的一個對比結果，可以看出本文提出的演算法在頻率、LUTs、每秒處理幀的數量上都有一定的優勢。文獻［7］採用無乘法器架構，整個實現方式與本文類似，也是先實現列變換，再把結果做一次行變換。但是文獻［7］中所用週期數較多，對比文獻［7］綜合出的結果可知，在主頻近似的情況下，本文的週期是它的34%，LUTs是它的62%。
4結論
本文基於脈動陣列的思想，提出了一個可快速進行DCT變換的框架。演算法將DCT變換分解成行列兩個獨立的一維變換，並且行列變換模組共用硬體資源，其中核心部件PE單元的內部硬體電路也高度對稱，這些都使得演算法更易於FPGA的實現。在得到列變換的第一個值時便開始將其送入到輸入資料處理單元中，經過重組以後的資料再一次被送入PE單元，這之間只要僅僅兩個時鐘的延遲便可觸發開始做行變換，整個框架在控制單元的協同下逐步有序地進行變換，降低了整個變換的週期數目。並且整個演算法高度規則，使得最後的工作頻率相對較高。此外本文的設計雖是針對HEVC的8×8 DCT變換而實現的，但是卻適合於任何的8×8矩陣相乘，因此具有相當高的通用性。
參考文獻
［1］ AHMED N, NATARAJAN T, RAO K R. Discrete cosine transform［J］. IEEE Transactions on Computers,1974, c23(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 highlevel 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 multiplicationfree digital architecture for 16×16 2D DCT/DST transform for HEVC［C］. Electrical & Electronics Engineers in Israel, 2012:1-5.
［8］ OPPENHEIM A V, SCHAFER R W. Discretetime signal processing［M］. Prentice Hall: Englewood Cliffs, 1989.
由於DCT變換演算法最後可以用矩陣相乘的形式表示出來，用DG依賴圖的判斷規則可以判斷得到矩陣相乘是一個高度規則的演算法，因此矩陣相乘形式的DCT變換非常適合用脈動陣列的思想去實現，滿足脈動設計的前提條件。2脈動陣列8×8 DCT的設計與實現
本設計基於脈動陣列高並行流水資料控制的特點，產生實體多個PE單元同時進行DCT變換。傳統PE陣列實現DCT變換要等到列變換做完後，繼續再做行變換，這樣使得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公司生產virtex6家族的Xc6vlx550t2ff1759系列晶片，圖7所示為綜合後的部分RTL圖。圖中PE00、PE01是產生實體出來的2個PE單元，以及它們之間的通信連接。
另外文獻［6］採用Vivado、LegUp、MATLAB等不同的HLS綜合工具對HM15中編寫的DCT部分進行了綜合，並對每一種尺寸都給出了直接使用乘法器的M模式、使用加法和移位代替乘法操作的AS模式的綜合結果。表3列出的是與本文配置最相近的一個對比結果，可以看出本文提出的演算法在頻率、LUTs、每秒處理幀的數量上都有一定的優勢。文獻［7］採用無乘法器架構，整個實現方式與本文類似，也是先實現列變換，再把結果做一次行變換。但是文獻［7］中所用週期數較多，對比文獻［7］綜合出的結果可知，在主頻近似的情況下，本文的週期是它的34%，LUTs是它的62%。
4結論
本文基於脈動陣列的思想，提出了一個可快速進行DCT變換的框架。演算法將DCT變換分解成行列兩個獨立的一維變換，並且行列變換模組共用硬體資源，其中核心部件PE單元的內部硬體電路也高度對稱，這些都使得演算法更易於FPGA的實現。在得到列變換的第一個值時便開始將其送入到輸入資料處理單元中，經過重組以後的資料再一次被送入PE單元，這之間只要僅僅兩個時鐘的延遲便可觸發開始做行變換，整個框架在控制單元的協同下逐步有序地進行變換，降低了整個變換的週期數目。並且整個演算法高度規則，使得最後的工作頻率相對較高。此外本文的設計雖是針對HEVC的8×8 DCT變換而實現的，但是卻適合於任何的8×8矩陣相乘，因此具有相當高的通用性。
參考文獻
［1］ AHMED N, NATARAJAN T, RAO K R. Discrete cosine transform［J］. IEEE Transactions on Computers,1974, c23(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 highlevel 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 multiplicationfree digital architecture for 16×16 2D DCT/DST transform for HEVC［C］. Electrical & Electronics Engineers in Israel, 2012:1-5.
［8］ OPPENHEIM A V, SCHAFER R W. Discretetime signal processing［M］. Prentice Hall: Englewood Cliffs, 1989.