一種基于Ｌｏｅｆｆｌｅｒ算法的快速實現(xiàn)２Ｄ ＤＣＴ／ＩＤＣＴ的方法

摘要：提出了一種基于Loeffler[8]算法的快速實現(xiàn)二維離散余弦變換/反離散余弦變換（2D DCT/IDCT）的方法。采用行列分解的方式，僅使用一個1D DCT/IDCT處理核快速完成8×8的2D DCT/IDCT變換。通過合理安排時鐘周期數(shù)和簡化各周期內(nèi)的操作，使1D DCT/IDCT模塊能在八個時鐘周期內(nèi)快速完成一次變換。仿真試驗表明，與目前使用相同F(xiàn)PGA芯片的商業(yè)IP核相比，所使用的資源減少了10％，而速度卻提高了10％。

關(guān)鍵詞：二維離散余弦變換； 行列分解法； 現(xiàn)場可編程門陣列

中圖法分類號：TP391文獻標識碼：A

文章編號：1001－3695(2007)01－0224－03

1引言

在有關(guān)圖像壓縮的眾多正交變換中，離散余弦變換(Discrete Cosine Transform，DCT)是十分有效的一種，其性能極為接近最佳的KL變換。通過采用行列分解法(RowColumn Classification)，人們只需使用少量的乘法計算就能完成二維離散余弦變換/反離散余弦變換(2D DCT/IDCT)。因此，2D DCT/IDCT變換被JPEG，H.263，MPEG1，MPEG2等眾多標準廣泛采用。MPEG2標準已經(jīng)成為數(shù)字電視、視頻點播、機頂盒等眾多視頻熱點產(chǎn)品的工業(yè)標準。在MPEG2中，圖像數(shù)據(jù)比特率最低為9Mbps，最高可達1．9Gbps。因此，研究設(shè)計一個高性能的2D DCT/IDCT結(jié)構(gòu)無疑是很有價值的。

硬件實現(xiàn)2D DCT/IDCT變換，目前主要有三種方法，即行列分解法[1]、直接實現(xiàn)法[2]和間接變換法[3]。行列分解法將二維變換分解成沿行和列兩個方向的一維變換及一個變換矩陣；直接實現(xiàn)法和間接變換法與行列分解法相比，主要是省去了變換矩陣的開銷。但是，由于行列分解法所使用的結(jié)構(gòu)比較規(guī)整，而且變換矩陣可以用廉價的存儲器來實現(xiàn)，性能較好，因此實際應(yīng)用中的二維離散余弦變換大多采用行列分解法。

行列分解法中使用得最多的是DA（Distribute Arithmetic）結(jié)構(gòu)[ 4~6 ]，但這種結(jié)構(gòu)的芯片面積隨數(shù)據(jù)字長呈指數(shù)式增大，而運算卻仍屬于位串式的，若要提高其運算速度，只能靠增加存儲器來完成，代價很高；而且，DA 結(jié)構(gòu)的部件不能被離散余弦正變換和離散余弦反變換所共用，這也正是DA 結(jié)構(gòu)多用于解碼器上的原因所在[7]。針對行列分解法，Loeffler提出了一種快速一維DCT算法[8]，用這個算法實現(xiàn)八個點的一維DCT變換只需進行11次乘和29次加。但由于受到數(shù)據(jù)相關(guān)性的影響，用傳統(tǒng)方法實現(xiàn)Loeffler算法時，一般需要用八個寄存器，并按順序分為五個時鐘周期執(zhí)行。而且，因為電路在關(guān)鍵路徑上包含了一次乘和兩次加，系統(tǒng)的運行速度受到限制。

本文提出一種新的實現(xiàn)Loeffler算法的方法。在不增加原算法所需要的乘、加操作次數(shù)的基礎(chǔ)上，通過合理延長時鐘周期數(shù)和簡化各周期內(nèi)的操作，使整個系統(tǒng)的運行速度得以提高。實驗表明，與目前同類結(jié)構(gòu)的商業(yè)IP核相比，本文所使用的邏輯單元減少了10％，而速度卻提高了10％，具有一定的實用價值。

22D DCT/IDCT的數(shù)學(xué)基礎(chǔ)

Loeffler隨后提出了一種快速的DCT算法[8]，用這個算法進行八個點的1D DCT變換只需進行11次乘法和29次加法。Loeffler算法示意圖如圖1所示，其中所使用的符號解釋如圖2所示。

圖2蝶形計算的符號解釋

圖2所示的蝶形計算原本需要4次乘和2次加，這樣一次八個點的1D DCT變換總共需要14次乘和26次加。然而利用式(5)和式(6)，可以對圖2所示的蝶形計算進行變形，減少乘法的次數(shù)。

通過以上的變形，一次蝶形計算只需要3次乘和3次加。從而進行一次1D DCT變換只需11次乘和29次加，達到了一維DCT變換所需乘法次數(shù)的理論極限。因為乘法運算的代價高于加法運算，所以這種變形是劃算的。

由于受到數(shù)據(jù)相關(guān)性的影響，用傳統(tǒng)方法實現(xiàn)Loeffler算法時，一般需要用八個寄存器，并按順序分五個時鐘周期執(zhí)行。算法的數(shù)據(jù)流如表2所示。IDCT變換可以看作是將DCT變換的五個步驟按照反方向執(zhí)行，只是在作蝶形計算時略有不同。

表2Loeffler算法的DCT數(shù)據(jù)流

表2中Reg為寄存器號，Cycle為時鐘周期；表中每一行代表與該行對應(yīng)的那個寄存器中的內(nèi)容及其隨時鐘周期變化的情況；表格中的數(shù)字代表將當前寄存器中的值通過乘法、加法運算后，將結(jié)果存入對應(yīng)的寄存器。例如，表中第5行第3列的“4+6”代表將第3時鐘周期時4號寄存器的內(nèi)容加上此時6號寄存器的內(nèi)容，再將結(jié)果存入4號寄存器。

3本文提出的結(jié)構(gòu)

傳統(tǒng)的二維離散余弦變換電路大多采用DA結(jié)構(gòu)或者乘加結(jié)構(gòu)（MAC），并且參照式(4)進行運算。采用這些結(jié)構(gòu)的好處是電路結(jié)構(gòu)比較規(guī)整，只需八個乘法器和八個加法器，消耗的硬件資源比較少。但是，這些方法因為在關(guān)鍵路徑上包含了串聯(lián)的一個乘法和一個加法操作，因此系統(tǒng)的運行速度較低。而且，一次八個點的一維離散余弦變換需要進行32次乘法和32次加法運算，運算次數(shù)較多，電路功耗較大。

如果直接根據(jù)Loeffler算法來設(shè)計電路，則一次八個點的1D DCT變換可以在五個時鐘周期內(nèi)完成，而且只需進行11次乘法和29次加法，運算次數(shù)較少，電路也較小。但是，因為電路在關(guān)鍵路徑上包含了1次乘和2次加（如表2中第3行第3列的“(2+3)×f+(c-f)×3”，因而系統(tǒng)的運行速度受到影響。

考慮到實際應(yīng)用中的二維DCT/IDCT變換電路常采用串行(逐個像素)的方式輸入數(shù)據(jù)，輸入一個8×8的圖像子塊需要64個時鐘周期。對于電路內(nèi)部的一維DCT/IDCT模塊來說，每八個時鐘周期才能獲得一行數(shù)據(jù)。因此，如果該模塊在五個時鐘周期內(nèi)完成一行數(shù)據(jù)的變換，那么該模塊在八個時鐘周期內(nèi)，每工作五個周期就需要等待三個周期。

據(jù)此，筆者對圖1的結(jié)構(gòu)進行變形，通過增加兩個寄存器，并且將一維DCT/IDCT變換的時間延長至八個時鐘周期，使得關(guān)鍵路徑上最多只包含1次乘，從而提高了系統(tǒng)運行頻率。對于八個點的1D DCT/IDCT，改進后的Loeffler算法數(shù)據(jù)流分別如表3和表4所示。 

表3改進的Loeffler算法的DCT數(shù)據(jù)流

表4改進的Loeffler算法的IDCT數(shù)據(jù)流

4誤差分析

在圖像壓縮過程中，2D DCT對圖像塊進行雙重卷積運算，將輸入圖像數(shù)據(jù)由空間域變換到頻率域，使之能更有效地被編碼。對一個8×8的圖像子塊而言，將對變換后的64個系數(shù)進行量化，并按照“之”字順序?qū)ο禂?shù)進行掃描和編碼，這種排列方法有助于將低頻非零系數(shù)置于高頻系數(shù)之前。直流系數(shù)由于包含了所有圖像特征中的關(guān)鍵部分而被單獨編碼。量化后的系數(shù)經(jīng)過熵編碼作進一步無損壓縮。

用本文設(shè)計的2D DCT/IDCT結(jié)構(gòu)完成圖3(a)到圖3(b)的2D DCT變換以及圖3(d)到圖3(e)的2D IDCT變換。由圖3可以看出，原始數(shù)據(jù)[10]與經(jīng)過DCT和IDCT變換后的數(shù)據(jù)不完全一致。產(chǎn)生誤差的主要原因有兩個，即量化誤差和計算誤差。量化誤差是在對系數(shù)矩陣進行量化的時候產(chǎn)生的，量化誤差的大小跟隨預(yù)期的圖像質(zhì)量不同而變化，而且是不可避免的。計算誤差則是因為筆者在對數(shù)據(jù)進行處理的時候，采用了有限字長的定點運算，丟失了部分計算精度。

有兩種方法可以提高計算精度，降低誤差：①增加定點運算的字長，它以增加硬件成本為代價。本設(shè)計中字長為15位，其中小數(shù)部分為3位，可以保證單次1D DCT/IDCT變換只在最后一位產(chǎn)生誤差。②增加常數(shù)因子的精度，這種方法的硬件代價較小。研究表明，當輸入數(shù)據(jù)為12位時，常數(shù)因子理論上最多有15位就能保證足夠的計算精度[11，12]。在實際的圖像壓縮過程中，當常數(shù)因子為12位時，誤差仍然只出現(xiàn)在15位字長的最后一位，故本文使用12位常數(shù)因子。

5硬件實現(xiàn)

本文設(shè)計的2D DCT/IDCT的結(jié)構(gòu)框圖如圖4所示。系統(tǒng)分為四個部分：串行到并行的轉(zhuǎn)換模塊(S/P)、1D DCT/IDCT計算模塊、并行到串行的轉(zhuǎn)換模塊(P/S)和雙端口RAM。主要處理過程如下：

（1）數(shù)據(jù)的串行到并行的轉(zhuǎn)換過程。串并轉(zhuǎn)換模塊逐字將輸入的圖像數(shù)據(jù)暫存起來，等待計算模塊所需的八個數(shù)據(jù)全部輸入完畢后，并行地將這些數(shù)據(jù)送入到計算模塊。

（2）計算模塊一次性將八個數(shù)據(jù)讀入自己的寄存器后，立即開始進行如表3或表4所示的計算，并在八個時鐘周期后并行輸出八個計算結(jié)果。

（3）八個從計算模塊并行輸出的計算結(jié)果最后由并行到串行的轉(zhuǎn)換模塊按一定順序串行送往RAM或輸出端口。

（4）雙端口RAM用于進行矩陣的轉(zhuǎn)置操作。先將行DCT/IDCT變換的結(jié)果逐行存入RAM，然后逐列將數(shù)據(jù)讀取出來送入1D DCT/IDCT計算模塊進行列DCT/IDCT計算。

本設(shè)計結(jié)構(gòu)上采用了時鐘同步的并行流水線設(shè)計，圖像數(shù)據(jù)為9位（其中一位為符號位），內(nèi)部計算精度為15位，輸出結(jié)果為12位（其中一位為符號位）。整個電路由一個8位的狀態(tài)機進行控制。

6實驗結(jié)果

實驗芯片采用ALTERA公司的MERCURY系列FPGA器件EP1M120F484C5。該器件共有4 800個邏輯單元（LUT）、12個嵌入式系統(tǒng)模塊（ESB）、303個用戶可使用的I/O引腳。本設(shè)計共使用了2 838個LUT，資源占用率為2 838/4 800≈59%；雙端口存儲器利用ESB完成，共使用了兩個ESB塊（每個ESB塊包含512位，實際共使用768位），資源占用率為2/12≈16%；共使用28個I/O引腳，資源占用率為28/303≈9%。

仿真實驗結(jié)果表明，系統(tǒng)最高工作頻率可達到115.9MHz，完成一個8×8圖像子塊變換需要161個時鐘周期，平均每個周期處理64/161≈0.39個像素，其處理能力大約為46M像素/秒。對于MP@ML層級的MPEG2圖像（760×576），處理速度可達到105fps，在速度與資源使用上獲得了良好的平衡。與目前使用相同芯片的類似的商業(yè)IP核[13]相比較，筆者所使用的邏輯單元只有他們的89％，頻率則為他們的112％。

另外，當采用與文獻[14]所使用的相同的FPGA芯片（xc2v250cs1446）進行綜合時，本設(shè)計的工作頻率為96．3MHz，比文獻[14]提高了20%，并且該設(shè)計可進行IDCT計算，文獻[14]提出的設(shè)計則不具有IDCT功能。

7結(jié)論

實驗表明，本文提出的通過延長時鐘周期數(shù)，簡化各周期內(nèi)的操作，從而提高DCT/IDCT變換速度的方法是可行的、有效的。仿真實驗結(jié)果表明，與目前使用相同芯片的類似的商業(yè)IP核相比較，筆者所提供的方法可以降低約10％的資源使用率，同時可以提高10％的運行速度。

參考文獻：

［1］L V Agostini， S Bampi， I S Silva. Pipelined Fast 2D DCT Architecture for JPEG Image Compression[C]. SBCCI’01， the 14th Symposium on Integrated Circuits and Systems Design，2001.226231.

［2］司馬苗， 周源華. 基于FPGA的二維DCT變換的實現(xiàn)[J]. 紅外與激光工程， 2003，32(4):436439.

［3］Y Zeng， G Bi， A R Leyman.New Polynomial Transform Algorithm for Multidimensional DCT[J]. IEEE Transactions on Signal Processing，2000，48(10):28142821.

［4］S Yu，E E Swartzlander Jr.DCT Implementation with Distributed Arithmetic[J].IEEE Transactions on Computers，2001，50(9):985991.

［5］A M Shams， W Pan， A Chidanandan， et al. A Low Power High Performance Distributed DCT Architecture[C]. ISVLSI 2002， IEEE CS Conference on VLSI，2002.2634.

［6］H ELBanna， A A ELFattah， W Fakhr. An Efficient Implementation of the 1D DCT Using FPGA Technology[C]. ECBS’04， the 11th IEEE International Conference and Workshop on the Engineering of Compu￣terbased Systems， 20-04.2427，356360.

［7］付宇卓， 季振洲， 胡銘曾. MPEG2編碼器中一種新型的DCT/ IDCT 結(jié)構(gòu)[J]. 高技術(shù)通訊， 2000，10(7):4550.

［8］C Loeffler， A Ligtenberg， G Moschytz. Practical Fast 1D DCT Algorithms with 11 Multiplications[J]. ICASSP’89， Proceedings of IEEE International Conference on Acoustics， Speech and Signal Processing， 1989，2(5):988991.

［9］W A Chen， C Harrison， S C Fralick. A Fast Computational Algorithm for the Discrete Cosine Transform[J]. IEEE Transactions on Communications， 1977，25(9):10-041011.

［10］M Rabbani， P Jones. Digital Image Compression Techniques[M]. SPIE Press， 1991.

［11］CCITT/ITU T.811992， Digital Compression and Coding of ContinuousTone Still Images:Requirements and Guidelines[S].

［12］CCITT/ITU T.831994， Digital Compression and Coding of ContinuousTone Still Images:Compilance Testing[S].

［13］Barco Silex. Bidimensional DCT/IDCT[EB/OL]. http://www.altera.com.cn/products/ip/dsp/transforms/mbarbidimensional.html， 2005.

［14］孫陽， 余鋒. 一種用于實時視頻處理的高速二維DCT的電路設(shè)計和實現(xiàn)[J]. 微電子技術(shù)， 2003， 31(2):2024.

作者簡介：

羅天煦(1980），男，湖南湘潭人，碩士，主要研究方向為SOC測試與設(shè)計；

鄺繼順（1959），男，湖南永興人，博導(dǎo)，主要研究方向為SOC測試與設(shè)計。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文