整型2D－IDCT算法的優化與實現

胡小濤，梁利平

(中國科學院微電子研究所，北京 100029)

自從Ahmed和Rao于1974年給出離散余弦變換(DCT)定義以來，這類變換被廣泛應用，對于這類變換的快速算法的研究發展也十分重要，特別是對特定條件下的快速算法的研究對于整個系統的性能提高有很大幫助。

在IDCT計算中，對于一個8×8大小的圖像塊而言，如果要直接計算，將需要4096次乘法和4032次加法。而IDCT的3種經典快速算法為B.G.Lee算法、AAN算法和LLM算法，都是基于如何減少運算次數而設計。而對于整數2D-IDCT變換而言，如何保證計算精度滿足IEEE Standard 1180—1990與離散余弦變換標準也是一大挑戰。

本文基于自身的DSP平臺，通過不同算法之間的比較與分析，設計出滿足標準前提下的解決方案，設計并確保計算精度，在此算法基礎上進行匯編優化，盡可能地減少消耗，得到滿足預期的實現結果。

1 整型2D-IDCT算法設計

1.1 算法描述

為了下一步的算法設計，本文首先對公式進行簡單變換

把公式轉換為矩陣并經過余弦函數化解得到

于是可采取常用的蝶形運算方法(Loeffler，Chen W等IDCT快速算法)，過程如下

計算后的y［0］～y［7］作為輸入再次運算便可得到2D-IDCT 結果［1-3］。

1.2 算法設計

進行整數IDCT變換［4-6］，需將上述公式中矩陣C(泛指)中的浮點運算定點化，因此如何最大限度保證數據精確性成為這一步的首要工作。在已有的蝶形運算優化的基礎上，本文根據精度標準需求，提出保證精度的解決方案，在保證數據精確性的前提下實現優化。

由于擴展時會進行一次舍入，因此第一次運算的擴展位數應該達到最大限度。而轉換成2次1D-IDCT運算后，第一次運算結果為32位，進入第二次計算時需要縮小到16位參與運算，必須舍棄低位數據來參與第二次運算。

本文暫且遵循這樣一個原則:盡量保留第二次運算前輸入數據位數。本文在后面會對比矩陣C與保留位數之間的優劣。

第一次IDCT運算的輸入是16位數據，實際有效位數為12位整數(-2048～2047)。運算中共有8個數據參與加減，須空余3位緩沖區域，故而最大可用于矩陣C位數為17位。而根據上面得到的第二次運算輸入數據保留最多的原則。第二次矩陣運算時輸入數據要保留16位。同樣會進行8個數據加減占用3位，因此第二次的運算中矩陣C的可設定位數為13位，參考圖1。

圖1 矩陣C參考

于是有兩種方案選擇:

1)方案1，固定選取矩陣C為13位，參與2次矩陣運算。

2)方案2，第一次選擇17位矩陣C，第二次選擇13位，分別運算。

如果2次選擇的矩陣相同，后面實現起來將會更加簡潔;但如果精度不能滿足要求，則需要采取方案2。但經過考慮認為，每次二維IDCT計算都要使用2個矩陣來進行，損耗太大。特別是在匯編實現時，每次IDCT運算的第一次計算結果緩存之后，還需要更新一次矩陣C，不僅會導致寄存器緊張，而且耗時較多。

實際操作中發現每一步蝶形運算中y［0］=a0+b0=(x［0］× C4+x［2］× C2+x［4］× C4+x［6］× C6)+(x［1］×C1+x［3］×C3+x［5］×C5+x［7］×C7)，未能飽和利用數據位。cos(n×π/16)是0.195～0.98之間的。這樣就算是輸入比特流x［0］到x［7］都為12位數(比如2000以上的數據)，相加之后的 y［0］只有4.577×2000，而預留的3位總共能達到8×2000大小的數據。于是在矩陣C中乘，因為 4.577×≈6.47，沒有超過8。同樣的2個矩陣C相乘之后相當于=2，這樣在之后的右移移位還原中多移一位即可，不用再做額外的變換。

于是，提出方案3:選取固定的13位矩陣再乘作為矩陣C參與運算。

3種方案實驗結果對比參見表1，顏色加深處表示結果未達標。

IEEE Standard 1180—1990標準主要要求有:

1)經過浮點運算得到參考結果f’(x，y)與整數IDCT運算結果f(x，y)誤差值不大于1。

表1 3種方案實驗結果對比

2)下面4個誤差不越界:

本文選擇方案3進行測試。精度遠遠超過IEEE Standard 1180—1990標準的要求。與參考文獻［7］中針對精度提升的離散余弦變換的測試精度相仿，其中在體現整體性能的Pme(點平均誤差)參數上本文精度要優于文獻［7］。

在大幅度滿足精度要求的基礎上，繼續進行標準離散余弦變換要求測試，在［-5，5］，［-256，255］，［-384，383］這3個區間段之間隨機抽取1×104和1×106兩組數據參與測試，結果參照表2，陰影部分為文獻［7］中經過精度優化后的整體性能參數對比。

表2 標準離散余弦變換測試結果

由于本文之前遵循一個原則:盡量保留第二次運算前輸入數據位數。實際上如果減小第二次運算的保留位數，可以得到更精確的矩陣C。本文將保留位數與矩陣C大小的不同設定得到一個誤差對比，參數去除了相同的分母，保留分子誤差數據，結果見表3。

表3 矩陣C大小不同設定的誤差對比

由測試數據可以得知，選擇更大的矩陣C將使得Omse測試參數更小，選擇保留更多位數將使Ome測試參數更小。這是因為兩種選擇方式降低失真度的重點不同，實現者可以通過實際操作的需要有所取舍。在本次實現中兩者均能達到測試標準，最后本文采取優先保留位數的方法。

1.3 匯編設計

本文在自主設計的指令集環境下完成上述IDCT運算模塊，有包括MIPS 32個寄存器在內一共64個32位寄存器可供支配。由于IDCT運算中間結果為64個，在要求高并行度計算的前提下，無法提供足夠寄存器空間存儲中間數據，第一次IDCT計算結果將會回存并在第二次計算時再取出。實現流程如圖2所示。

圖2 匯編實現流程

由上述流程圖可知，2次8×8運算、轉置、數據搬運、邊界截取組成了一次IDCT計算的消耗主體，同時也是優化重點。

指令環境對于每次轉置運算，針對的是4×8的數據塊，轉置之后的數據參與第二次運算后要存在寄存器中然后順序存回內存。在匯編中轉置消耗較多，開銷主要在轉置后的數據調整和第二次運算后為后面邊界截取進行數據準備，本文經過分析轉置消耗，采取手動配置初始寄存器位置的方式將最終轉置控制消耗降低為2個周期。配置如圖3所示。

圖3 轉置運算寄存器分配

在每個4×8計算塊的數據并行性保證上，采用多指針電梯式掃描方式存取，將數據的轉移搬運冗余操作降低到最低限度。經過每次電梯式掃描方式存取之后，4×8數據塊運算完畢，進入下一個模塊計算時橫向移動即可，這樣既保證了數據的流水線操作，大大降低了損耗，同時也化簡了兩次運算中數據搬運的冗余操作。操作如圖4所示。

圖4 電梯掃描方式操作

在流程圖中可知，每次IDCT運算需要循環8次，而在上述的匯編優化中可知，為實現并行運算和優化方法，需要將每次運算的循環數減小，增加循環體內部計算。為找到最佳循環次數，本文在操作中將循環次數逐漸減小，并對每個循環次數下的結構進行盡可能的優化仿真，得到對比數據見表4，陰影處表示選擇此方法。

表4 循環次數選擇與周期損耗關系

從上面對比圖可以得知，隨著循環次數減小，行運算和列運算中每次循環的開銷變大，但綜合來說循環2次時總周期最小，最終優化結果需要(6×136+8)個周期(在6 blocks的情況下)。完全去除循環時，雖然減少了循環消耗，但增加了寄存器分配操作，且流水線利用率也已達到飽和，最終效率不及前者。于是采用2次循環方法。

2次循環方法最大限度地利用了之前的轉置控制寄存器分配和邊界截取時的并行處理能力，最大限度地發揮了流水線作用，使得最終的消耗在140以內。

2 實驗對比

純MIPS指令實現的計算如果不加優化，對于每次IDCT計算會進行4096次乘法和4032次加法，在仿真器下做一次計算，周期數接近20000。而采用快速算法優化之后用MIPS指令自動實現匯編進行一次IDCT計算周期數在1000左右，作為本文性能指標的縱向比較。

同時，本文參考了TI產品指標中的IDCT模塊消耗作為參照標準，這些數據是在TI平臺上優化之后得到的，采用的指令系統、算法和優化方法與本文不同，作為性能的橫向比較(見表5)。

表5 IDCT模塊性能對比表

在運行多個block下，各個不同產品性能指標有一定變化，DSP在6 blocks下周期數可到137，參照視圖見圖5。

圖5 IDCT模塊性能對比圖

經過分析，本文基于的DSP平臺下的IDCT計算效果好于TMS320C62X，差于TMS320C64X+系列。TMS320C64X+解第1個block的周期為135 cycles，在解到6 blocks之后速度會提升到103 cycle。這也是需要學習和改進的地方。

3 結束語

本文依據離散余弦變換和IEEE Standard 1180—1990標準分析并選擇符合要求的算法來實現2D-IDCT功能，所進行的驗證試驗符合預期。在匯編優化上針對本文所基于的DSP指令設計符合需要的相應代碼并使用并行流水線結構優化，實現了IDCT運算并達到計算優化度預期。在與同類IDCT運算方法進行結果比較之后也找到了一些不足，這也是下一步需要優化的方向。

［1］CHEN W H.A fast computational algorithm for the discrete cosine transform［J］.IEEE Trans.Communication，1977，25(9):1004-1009.

［2］FEIG E，WINOGRAD S.On the multiplicative complexity of discretecosine transform［J］.IEEE Trans.Inform.Theory，1992，38(6):1387-1391.

［3］LOEFFLER C，LIGHTENBERG A，MOSCHYTZ G S.Practical fast 1-DDCT algorithms with 11-Multiplications［EB/OL］.［2013-01-20］.http://ieeexplore.ieee.org/xpl/articleDetails.jsp reload=true&arnumber=266596.

［4］SLAWECKI D，LI W.DCT/IDCT processor design for high data rate image coding［J］.IEEE Trans.Circuits System Video Technology，1992，2(2):135-145.

［5］EI M，BELKOUCH S.An efficient pipelined fast and multiplier-less 2-D IDCT for image/video decoding［EB/OL］.［2013-01-20］.http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5945687.

［6］KIHO C，KIHOON L.Zero coefficient-aware fast IQ-IDCT algorithm［EB/OL］.［2013-01-20］.http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5657972&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D5657972.

［7］唐永亮.高速高精度離散余弦變換的設計與實現［D］.天津:天津大學，2008.