H.266/VVC二維變換的統一硬件結構

陳俊煜，孫斌，黃曉峰，盛慶華，賴昌材，金心宇

(1.浙江大學 工程師學院，浙江 杭州 310015；2.杭州電子科技大學 通信工程學院，浙江 杭州 310018；3.杭州電子科技大學 電子信息學院，浙江 杭州 310018)

新一代國際視頻編碼標準通用視頻編碼(versatile video coding, VVC)[1]相比前一代的高效視頻編碼(high efficiency video coding, HEVC)[2]，在編碼效率上提高了大約1倍[3]，計算復雜度也大幅度提高[4].變換編碼是視頻編解碼的關鍵部分[5].可以從以下3個方面概括VVC與變換相關的特性[6].1）VVC總共有3種變換類型：DCT-II、DSTVII和DCT-VIII.相比于HEVC，VVC將最大變換尺寸擴展到64，采用變換尺寸為4、8、16、32、64的DCT-II和變換尺寸為4、8、16、32的DSTVII、DCT-VIII.VVC引入多變換核選擇技術(multiple transform selection, MTS)控制變換類型.2）VVC的高頻置零技術減少了大尺寸變換塊的計算量和存儲空間.當采用DCT-II時，長或寬為64的大尺寸變換塊在高頻置零后，只保持低頻32×32的有效數據；當采用DST-VII或DCTVIII時，長或寬為32的大尺寸變換塊在高頻置零后，只保持低頻16×16的有效數據.3）VVC的多類型樹劃分技術(multiple type tree, MTT)會產生非對稱變換塊.VVC在水平和垂直方向上可以采取不同的變換類型和尺寸.

研究者提出許多關于變換部分的硬件結構.在VVC編碼標準方面，1）Garrido等[7-9]基于通用乘法器提出二維變換的流水線結構，將雙端口靜態隨機存取存儲器(static random-access memory,SRAM)排列成矩陣形式實現轉置存儲，利用先入先出隊列(first input first output, FIFO)緩存塊信息.Garrido等[7-9]使用的轉置存儲器占用面積較大.2）Fan等[10]提出的支持混合塊處理的DST-VII、DCT-VIII變換結構，主要基于RAG-n(n-dimensional reduced adder graph)算法[11]優化后的多常量乘法(multiple constant multiplication, MCM)實現，在轉置存儲器的流水線結構設計上采用對角存儲和乒乓讀寫方式.Fan等[10]沒有實現DCT-II，也沒有結合高頻置零優化轉置存儲器.3）Farhat等[12-13]基于通用乘法器提出輕量級的變換結構，雖然實現VVC所有的變換類型和尺寸，但不支持流水線處理，導致結構的吞吐率低.4）Mert等[14]提出可重構的數據路徑，具有比傳統使用分離的數據路徑更小的面積.5）Hao等[15-16]在轉置存儲器的設計中使用統一的數據映射方案，針對一維變換提出矩陣分解算法來減小面積.在HEVC編碼標準方面，Meher等[17]提出尺寸復用結構，大尺寸變換可以復用小尺寸變換從而提高資源利用率；Zheng等[18]提出可重構的蝶形變換結構，解決了傳統結構在運算小塊時大塊計算資源閑置的問題.

本研究主要實現VVC的DCT-II、DST-VII、DCT-VIII變換類型.1）基于32個并行度實現全流水結構，支持混合塊的輸入.2）基于Hcub(heuristic cumulative benefit)算法[19]優化后的MCM設計統一的結構來實現不同變換類型和尺寸.3）在轉置存儲器的設計中引入讀寫指針，取代傳統的乒乓讀寫方案；采用對角線式存儲結構，并設計統一的數據映射方案.4）利用VVC變換過程中高頻置零的特性優化SRAM存儲空間，以FIFO取代傳統的寄存器緩存塊信息.

1 二維變換的流水線結構

1.1 VVC中的二維變換

DCT-II、DST-VII和DCT-VIII變換矩陣的數學定義式為

式中：T(i,j)為變換矩陣元素值;i為行索引，j為列索引，N為變換尺寸；i,j=0,1,···,N-1.對于所有的變換類型，N點一維變換的矩陣形式為

式中：X為像素殘差矩陣，TN為N點變換矩陣，Y1D為一維變換系數矩陣.任何像素塊二維變換的計算式為

式中：XM×N為寬度為M、高度為N的像素殘差矩陣，TM、TN分別為M、N點的變換矩陣，Y2D為二維變換系數矩陣.

直接進行變換操作涉及浮點數運算，浮點數的計算復雜度較高；在數字化處理過程中，舍入誤差不可避免，將導致編/解碼端出現失配的問題，因此從高級視頻編碼(advanced video coding,AVC)開始，采用整數變換.相比于浮點變換矩陣，整數變換的變換矩陣做了整數化處理，VVC對N點變換矩陣的每個元素標量數乘一個較大的放大因子進行整數化，從而在整數化過程中減小計算精度的損失.整數化后的矩陣仍然保持原本可以使用蝶形快速算法的規律.整數變換過程的表達式為

式中：E(N)為N點變換矩陣的放大因子，、分別為M、N點的整數變換矩陣，Yint為二維整數變換系數矩陣.

1.2 二維變換的流水線結構

如圖1所示，本研究所提二維變換流水線結構主要由3個部分組成：一維行變換模塊、轉置存儲器、一維列變換模塊，系統的并行度為每時鐘周期32個像素.一維行變換的輸入數據是預測得到的像素殘差，輸入位寬為9位，輸出位寬為16位，一維行變換得到的塊數據和塊信息（寬、高、類型等）將分別存入由SRAM實現的轉置存儲器中.完成整個矩陣的存儲后，數據和相應的信息會流入一維列變換，一維列變換的內部結構與一維行變換幾乎一致，只是輸入、輸出位寬都為16位.

圖1 二維變換的流水線結構Fig.1 Pipelined architecture of 2D transform

由于轉置存儲器處理非對稱小像素塊時讀寫速率不匹配，產生數據寫入碰撞問題，須將小塊的多行向量拼湊到同一并行度，使得讀寫速率匹配，進而實現流水線處理.以8×32的像素塊為例，其高度為8、寬度為32，若單周期只處理1個向量，則輸入到一維行變換需要8個周期，即寫入轉置存儲器需要8個周期，輸入到一維列變換需要32個周期，即從轉置存儲器中讀出需要32個周期.由于寫入時間小于讀出時間，導致存儲器堵塞，在轉置存儲器存滿后就會造成寫入碰撞.將小塊的輸入拼湊到32個并行度，同時處理多個尺寸小于32的向量（8組大小為4的向量，4組大小為8的向量，2組大小為16的向量），就可以使寫入和讀出時間相同.由于64×64的像素塊存在高頻置零，讀出時間短于寫入時間，不會造成流水的堵塞.

2 一維變換的統一結構

2.1 VVC中的一維變換

DCT-II可以使用Chen等[20]提出的蝶形快速算法進行計算，使計算量大大減少.如圖2所示，DCT-II8代表大小為8的變換矩陣，DCT-II4代表大小為4的變換矩陣，特點是1)偶數行偶對稱，奇數行奇對稱（首行是第0行）；2) 4×4的變換矩陣由8×8矩陣的偶數行的前一半元素組成.其他尺寸的變換矩陣也有這2個特點，因此可以設計基于蝶形快速算法的統一計算結構.

圖2 DCT-II的2種變換矩陣Fig.2 Two tgpes of transformation matrices for DCT-II

DST-VII和DCT-VIII沒有與DCT-II相同的蝶形特性，即便VTM (VVC 測試模型)為DST-VII和DCT-VIII提供快速算法，這樣的快速算法也難以用統一的結構實現.DST-VII、DCT-VIII的變換矩陣在數值上具有偶數行反序，奇數行反序且反號的特點（首行是第0行）.如圖3所示，DST-VII4和DCT-VIII4分別代表大小為4的2種變換矩陣，二者可以共享1套計算資源，只要在輸入輸出端分別采用1組選擇器簡單處理輸入輸出數據即可實現2種變換類型.

圖3 DST-VII4與DCT-VIII4的變換關系Fig.3 Relationship between DST-VII4 and DCT-VIII4

2.2 一維變換的統一結構

本研究所提一維變換結構基于MCM的方法實現.MCM優化問題將給定的1組常數生成僅用加法、減法和移位組成的常量乘法器塊，用以與輸入變量進行相乘運算，并通過算法來減少加法器、減法器、移位器的使用.在硬件設計中，加法器/減法器所需資源遠遠大于移位器，因此如何減少加法器/減法器的個數是硬件優化的關鍵.Hcub算法[19]的提出正是為了減少加法器/減法器的個數，尋找解決MCM問題的最優解.在文獻[19]中,該算法找到的解決方案所需加法和減法數量比RAG-n算法少20%.當常量個數和位寬不斷變大時，Hcub算法的優勢會更加明顯，其對中間計算結果的復用性更高.基于MCM實現的一維變換結構如圖4所示.由于系統的并行度為每周期32個像素，最大塊的尺寸為64，為了能夠在后級使用蝶形快速算法減少計算量，在模塊的輸入級加入串轉并模塊，將尺寸為64的2個周期輸入數據合為1個周期.由于存在高頻置零，一維變換最大輸出32個有效數據，因此無需在輸出端進行處理.

圖4 基于MCM的一維變換統一結構Fig.4 Unified architecture of 1D transform based on MCM

DCT-II可以采用蝶形快速算法進行計算的特性，大大降低了乘法和加法操作的個數，減少了后級MCM和加法樹中的資源消耗，DST-VII/DCT-VIII沒有相同的特性，采用直接計算的方法.如圖5所示的蝶形運算模塊用于對變換類型為DCT-II的輸入數據生成蝶形運算單元，對DST-VII、DCT-VIII的輸入數據僅進行延時操作.圖中，x為經過串轉并模塊后的向量，a為N點蝶形模塊的輸入向量，b為輸出向量，MUX為多路復用器，蝶形變換的輸入輸出關系為

圖5 蝶形運算結構Fig.5 Butterfly architecture

大尺寸的蝶形變換可以調用小尺寸的蝶形變換，從而提高資源利用率.小塊的多行向量須拼湊到同一并行度才能實現讀寫速率的匹配，因此例化2個16點蝶形模塊、4個8點蝶形模塊和8個4點蝶形模塊，在總體上實現32個并行度下的流水線結構.

如圖6所示，DST-VII和DCT-VIII可以共享1套計算資源，默認輸入下輸出為DST-VII的系數結果，若當前變換類型為DCT-VIII，則通過選擇器將輸入數據反序，輸出數據在奇數行添負號，得到系數結果.圖中，DMUX為分路器.

圖6 DST-VII和DCT-VIII的統一結構Fig.6 Unified architecture of DST-VII and DCT-VIII

基于MCM方法的結構是設計多組移位加法單元(shift-addition unit, SAU)作為常量乘法的運算單元.通過需要運算的變換系數得到所有可能與某個輸入數據相乘的常量，根據Hcub算法生成對應的SAU.本研究采用統一的計算結構，即生成的計算單元可以供所有的變換類型和變換尺寸使用.這樣的結構可以最大化地復用中間計算結果，也可以復用后級加法樹的資源，在最大程度上共享資源并降低功耗.在MCM的計算模塊中，輸入總共有64個數據，這64個輸入數據來自不同的數據路徑，因此可以根據所需要的變換矩陣系數為輸入數據設計相應的SAU.如圖7所示為不同輸入數據對應的SAU.圖中，c為輸入數據，其中SAUc[0:1]和SAUc[2:3]共同處理來自第1個4點蝶形模塊的數據，SAUc[4:5]和SAUc[6:7]共同處理來自第2個4點蝶形模塊或第1個8點蝶形模塊的數據.例如，變換類型為DCT-II且尺寸為8，有效輸入數據為c[0:31]，該輸入數據包含4組尺寸為8的輸入向量，分別由SAUc[0:7]、SAUc[8:15]、SAUc[16:23]、SAUc[24:31]處理.DST-VII/DCT-VIII與尺寸為64的DCT-II共同對應的有效輸入數據為c[32:63]，c[32:63]對應的常量乘法放在SAUc[32:63]中生成.這樣的MCM計算模塊發揮了利用多常量乘法進行優化的特點，常量越多，可以共用的中間計算單元也越多，因此功耗降低且邏輯資源的使用減少.經過MCM的計算后，根據當前變換的類型和大小對SAU輸出的結果進行選擇，并輸入加法樹模塊對數據進行累加求和.為了提高整體的時序，減少組合邏輯關鍵路徑的長度，整個加法樹劃分為3級.應限制一維變換的結果不超過16位，因此從加法樹模塊得到的數據須右移縮放，輸出的即為一維變換后的結果.

圖7 不同輸入數據對應的移位加法單元Fig.7 Shift-addition units for different input data

3 轉置存儲器

實現二維變換的流水線結構須存儲一維行變換的結果，待完成1個矩陣的計算后再開始一維列變換，為此須設計滿足流水線處理要求的轉置存儲器.如圖8所示，本研究提出的轉置存儲器基于雙口SRAM實現，使用對角線存儲方案并設計統一的數據映射方案，同時配合讀寫指針進行操作，利用FIFO來緩存塊信息.圖中，y1為一維行變換輸出數據，y2為轉置存儲器輸出數據.雙口SRAM由32塊存儲體(Bank)組成，由此實現32個數據的并入、并出.經過高頻置零優化后的轉置存儲器深度計算式為

圖8 轉置存儲器結構Fig.8 Transpose memory architecture

式中：VY為一維行變換后最大輸出塊的有效數據個數，H為系統的并行度，D為每個存儲體的深度.VVC中最大的變換塊為64×64，但其具有高頻置零的特性，在一維行變換后輸出的最大有效塊數據個數為64×32個.系統的并行度為32，因此可以計算出每個Bank的深度為128，需要7根地址線.圖8中的FIFO用來緩存包括變換尺寸、變換類型在內的塊信息.由于最大塊的讀出需要64個周期，FIFO的深度不超過讀時鐘的最大值，本研究中的FIFO深度為64.

為了實現數據的并入并出，考慮到SRAM在1個時鐘內只能在1個特定地址讀寫的特性，本研究在存儲上采用對角存儲的方案.實現思路為將32個并行數據經過移位操作后斜向寫入不同存儲體的不同地址內，在讀取時只需對存儲在不同存儲體同個地址的數據進行移位后便可獲得轉置后的向量.以4×32的輸入矩陣為例，該矩陣是一維行變換的輸出結果，如圖9(a)所示，數字0～31代表每周期處理的32個數據，不同的灰度色彩代表不同的周期，該矩陣須分4個周期進行存儲.由于在讀操作開始的時候，要在1個時鐘內讀出輸入矩陣1列所有的數據，并進行多向量的拼湊，轉置存儲器存儲結構的設計如圖9(b)所示.其中32個并行數據被對角寫入不同存儲體中，讀出時按照地址順序依次讀出并進行移位操作即可.為了避免讀寫碰撞的產生，在轉置存儲器結構上加入讀寫指針，寫指針指向一維變換中的向量存儲的地址，讀指針指向轉置存儲完畢的上一個矩陣的起始地址.

圖9 輸入矩陣與存儲結構Fig.9 Input matrix and storage structure

由于存在高頻置零，轉置存儲器的延遲(latency)是不固定的.對非64×64的變換塊來說，1個完整變換塊的讀寫周期均不超過64個時鐘；當64×64的變換塊進入時，高頻置零使得1個完整變換塊的寫入周期為128個時鐘，讀出周期只需64個時鐘.為了確保讀寫不發生碰撞，當64×64的變換塊進入時，讀出操作須等待64個時鐘才能進行.若64×64的變換塊后續讀出的為非64×64的變換塊時，可以直接進行讀出操作，從而縮短小塊的延遲.如圖10所示，在1個完整的二維變換過程中，非64×64的變換塊的延遲為81個時鐘周期，64×64的變換塊的延遲為145個時鐘周期.

圖10 二維變換流水線結構時序圖Fig.10 Timing diagram of pipelined 2D transform architecture

4 實驗結果與分析

使用Verilog HDL實現提出的結構，并使用Design Compiler在UMC 28 nm工藝庫下進行綜合實現.綜合實現的總面積為0.669 759 mm2(SRAM的面積為0.052 924 mm2，邏輯資源的面積為0.616 835 mm2).為了進行不同工藝下的面積對比，將邏輯資源的面積換算成等效邏輯門的數量(本實驗綜合環境下單位邏輯門的面積為0.55 μm2)，換算后的等效邏輯門數量(gate count，GC)計算式為

綜合得到的最大頻率為724 MHz，功耗為48.2 mW.作為對比，本研究同時實現分離MCM結構，該結構在Fan等[10]研究的基礎上增加DCT-II變換類型，將DCT-II與DST-VII/DCT-VIII變換核分離實現，并將最大尺寸擴展到64，同樣采用所提轉置存儲器，將時鐘頻率約束在724 MHz，在同一環境下進行綜合.綜合得到的NGC=1 135.7 ×103，功耗為95.4 mW.可見，相比分離的MCM計算結構，本研究的統一結構在同條件下可以減少1.3%的面積和49.5%的功耗.因為統一的計算結構可以發揮MCM的優勢，最大化的共享中間計算結果，并且共享一部分寄存器，所以在功耗上得到比較大的改善；又因為統一結構需要額外生成一些選擇邏輯，所以在面積上的改善并不明顯.

如表1所示為基于ASIC設計的關鍵參數，將本研究的實驗結果與其他相關文獻的實驗結果進行比對，包括HEVC標準和VVC標準的相關研究成果.表中，F為最大頻率，H為該系統的并行度，P為功耗.文獻[10]實現DST-VII/DCT-VIII變換核，得出結論：基于MCM實現的結構相比直接使用乘法器的結構在面積上節省了11.4%，在功耗上節省了9.9%.在相同并行度下，本研究的NGC是文獻[10]的2.26倍，原因是文獻[10]沒有實現最大尺寸為64的DCT-II變換核，DCT-II變換核的面積大約為DST-VII/DCT-VIII變換核的1.30倍，因此文獻[10]的面積與本研究對照實現的分離MCM結構基本一致.本研究實現的統一結構在功耗上得到比較大的改善.文獻[13]與本研究都實現了3種變換類型，Farhat等[13]提出的結構基于通用乘法器實現，文獻[13]的計算邏輯是根據不同的變換類型和尺寸來選擇送入乘法器的變換矩陣與輸入數據進行計算.文獻[13]的并行度為1 像素/周期，資源的利用率很高，面積也較小.從吞吐率的角度分析，文獻[13]不支持流水線處理，因此在吞吐率上低于本研究.在28 nm的工藝下，本研究實現結構的最大頻率高于文獻[13].文獻[14]同樣實現3種變換類型并改進傳統MCM的結構，通過選擇器對MCM結構進行重配置從而復用部分計算資源.文獻[14]沒有實現最大尺寸為64的變換塊，且在并行度為8 像素/周期的前提下實現面積僅略低于文獻[10].文獻[17]、[21]的實驗結果基于HEVC得出.Meher等[17]提出的DCT-II變換核是尺寸復用的蝶形結構，本研究對于DCT-II變換核的實現也采用這樣的方法，并結合DST-VII/DCT-VIII變換核的特性進行統一設計.Shabani等[21]提出的一維變化結構改進傳統MCM方法，采用Muxed-MCM結構，生成的SAU具有一定的可重用性和可擴展性，但該結構隨著常量的增加難以通過算法進行優化.

表1 基于ASIC實現的二維變換硬件設計對比Tab.1 Comparison of 2D transform hardware designs based on ASIC

轉置存儲器硬件設計的對比如表2所示.表中，NB為存儲體個數，D為每個存儲體的深度，W為每個存儲體的位寬.本研究所提轉置存儲器結構基于雙口SRAM實現.Garrido等[8]提出的結構將轉置存儲器排列成1個矩陣的形式，在4個并行度下使用16個存儲體，本研究所提結構采用對角線式的存儲結構實現并入、并出，使用4個存儲體就可以實現4個并行度的設計.文獻[8]沒有對高頻置零進行優化，按照本研究設計方法深度為256.Fan等[10]提出的轉置存儲器結構基于乒乓讀寫的方式實現，該結構將32×32的矩陣組成1組輸入實現流水.DST-VII、DCT-VIII中大小為32的變換存在高頻置零，實際上最大的中間結果只有32×16個有效數據，因此采用本研究所提讀寫指針的方式根據式(5)計算深度為32即可實現流水.

表2 轉置存儲器硬件設計對比Tab.2 Comparison of transpose memory hardware designs

5 結 語

本研究提出統一的二維變換硬件結構，支持VVC的DCT-II、DST-VII、DCT-VIII變換類型以及所有大小的變換尺寸.該結構基于Hcub算法優化后的MCM實現，對所有變換類型和尺寸設計共用的MCM計算單元，相比直接使用乘法器的方案和使用分離的MCM計算結構的方案可以節省面積和功耗.在二維變換的流水線設計上，基于32個并行度實現全流水結構，設計支持流水線處理的轉置存儲器，支持混合塊的流水輸入，結合高頻置零對轉置存儲器的大小與處理時間進行優化，在一定的初始延時后每個周期都會得到32個變換結果.對于整個二維變換而言，非64×64的變換塊的延遲為81個時鐘周期，64×64的變換塊的延遲為145個時鐘周期.本研究所提轉置存儲器基于雙口SRAM實現，使用對角線存儲方式并設計統一的數據映射方案，采用讀寫指針的方式并配合存儲塊信息的FIFO來實現轉置存儲.相比于乒乓存儲的結構，本研究的方案能夠結合VVC高頻置零的特性減少一半的存儲空間.本研究所提結構可以滿足VVC硬件編碼高性能的需求，比傳統方案的面積和功耗更小.由于VVC變換核與變換尺寸的增加，計算邏輯需要的資源也大幅度增加，若想追求更小的面積，可以考慮使用通用乘法器的結構并降低并行度滿足輕量化的需求.