一種基于FPGA的二維DCT和IDCT的新算法

趙 濱，黃大慶

（南京航空航天大學(xué) 無(wú)人機(jī)研究院，江蘇 南京210016）

一種基于FPGA的二維DCT和IDCT的新算法

趙 濱，黃大慶

（南京航空航天大學(xué) 無(wú)人機(jī)研究院，江蘇 南京210016）

提出了一種新的二維DCT和IDCT的FPGA實(shí)現(xiàn)結(jié)構(gòu)，采用行列快速算法將二維算法分解為兩個(gè)一維算法實(shí)現(xiàn)，其中每個(gè)一維算法采用并行的流水線結(jié)構(gòu)，每一個(gè)時(shí)鐘處理8個(gè)數(shù)據(jù)，大大提高電路的數(shù)據(jù)吞吐率和運(yùn)算速度。通過(guò)Modelsim仿真工具對(duì)該設(shè)計(jì)進(jìn)行仿真，證明該算法的功能的正確性，進(jìn)行一次8*8的分塊二維DCT變換僅僅需要16個(gè)時(shí)鐘，滿足圖像以及視頻實(shí)時(shí)性的要求。

二維DCT算法；二維IDCT算法；流水線；FPGA

近年來(lái)，數(shù)字形式的圖像信息的應(yīng)用需求不斷增加，對(duì)數(shù)字圖像處理的要求也不斷提高。隨著信號(hào)處理技術(shù)的不斷發(fā)展，使得數(shù)字圖像處理技術(shù)與系統(tǒng)在各個(gè)行業(yè)與領(lǐng)域中得到廣泛而充分的應(yīng)用。DCT廣泛應(yīng)用于圖像壓縮，語(yǔ)音壓縮和數(shù)字水印等技術(shù)中，JPEG，MPEG和H.264等標(biāo)準(zhǔn)都采用了DCT技術(shù)作為壓縮編碼的主要方案[1]。JPEG算法中8*8圖像塊的二位DCT變換如果直接進(jìn)行運(yùn)算，運(yùn)算量巨大，傳統(tǒng)的MCU和DSP難以滿足實(shí)時(shí)處理的需要，而FPGA的并行處理能力，特別適合于數(shù)字信號(hào)處理領(lǐng)域的應(yīng)用，過(guò)去的幾年，就DCT算法的快速VLSI實(shí)現(xiàn)已經(jīng)做了很多的工作，在硬件實(shí)現(xiàn)時(shí)資源利用率和互聯(lián)復(fù)雜性等方面有著優(yōu)異的性能[2]。筆者在此基礎(chǔ)上提出了一種并行流水線結(jié)構(gòu)，充分利用FPGA片上豐富的嵌入式算法器和可編程邏輯資源，構(gòu)建了一個(gè)每一個(gè)時(shí)鐘處理8個(gè)數(shù)據(jù)的結(jié)構(gòu)單元，大大提高了數(shù)據(jù)的吞吐量。

1 算法描述

1.1 DCT算法

1.1.1 一維DCT算法

設(shè){x（n）}為N點(diǎn)實(shí)序列集合，n=0 ，1 ，……N-1，其一維DCT 定義[3]為：

其中：

利用c的對(duì)稱性，由式（2）可得：

所以，可得：利用三角公式：cos（a+b）=cosa·cosb-sina·sinb 得到：

從而有：

從而可以得到計(jì)算一維DCT變換的流水線示意圖，如圖1所示。

1.1.2 二維DCT算法

對(duì)于一個(gè)大小為N×N的像素快來(lái)說(shuō)，假設(shè)x（i，j）為輸入的像素點(diǎn)陣數(shù)據(jù)，其二維DCT變換公式如下：

圖1 一維DCT的流水線結(jié)構(gòu)Fig.1 The pipeline framework of the 1-dimensional DCT

上式很容易寫成矩陣形式：z=cxcT，其中c為帶余弦基本函數(shù)的變換系數(shù)矩陣，更進(jìn)一步，可以將二維DCT變換分解:z=cy，y=xcT，這樣，在進(jìn)行二維DCT變換時(shí)，可以應(yīng)用一維DCT變換來(lái)計(jì)算，即先沿x的行進(jìn)行一維DCT計(jì)算獲得y，再對(duì)y的裝置行進(jìn)行一維DCT變換[5]。

1.2 IDCT 算法

1.2.1 一維IDCT算法

N點(diǎn)的DCT（IDCT）反變換的計(jì)算公式如下：

根據(jù)n分解為奇數(shù)和偶數(shù)項(xiàng)，得到：

分解可得，一維逆DCT的流水線結(jié)構(gòu)如圖2所示。

這里采用與DCT變換相似的方法，將逆DCT變換設(shè)計(jì)為8個(gè)時(shí)鐘的流水線操作，每個(gè)時(shí)鐘輸出一個(gè)數(shù)據(jù)。以方便與DCT變換模塊交互。

圖2 一維逆DCT的流水線結(jié)構(gòu)Fig.2 Pipeline framework of the 1-dimensional iDCT

1.2.2 二維IDCT算法

與二維DCT變換一樣，相應(yīng)的逆DCT變換也可以采用分布的方式實(shí)現(xiàn)，即先對(duì)圖像塊的每一行進(jìn)行一維DCT變換，實(shí)行行變換，然后對(duì)經(jīng)過(guò)行變換的圖像塊的每一列再進(jìn)行一維逆DCT變換，從而實(shí)現(xiàn)二維逆DCT變換[6]。

2 功能仿真與驗(yàn)證

整個(gè)電路使用Verilog語(yǔ)言進(jìn)行描述，在Quartus2中綜合后，在Modelsim工具中進(jìn)行仿真，我們輸入以下2個(gè)8×8的矩陣塊 A，B：

通過(guò)2-DCT模塊的仿真結(jié)果如圖3所示，與MATLAB結(jié)果比較，驗(yàn)證了模塊功能的正確性，同時(shí)由一維DCT模塊可以看出，由于使用了流水線結(jié)構(gòu)，這樣可以實(shí)現(xiàn)每個(gè)時(shí)鐘處理8個(gè)數(shù)據(jù)，大大提高了變換的速度，可以使用在需要實(shí)時(shí)進(jìn)行DCT的應(yīng)用中，而進(jìn)行一個(gè)二維8×8的DCT只需要16個(gè)時(shí)鐘，滿足圖像處理實(shí)時(shí)性的要求。

將上述輸出結(jié)果輸入的二維IDCT變換模塊，得到的輸出結(jié)果如圖4所示，與原始輸入比較，證明了該模塊的正確性：

3 結(jié)論

圖3 二維DCT變換模塊的仿真結(jié)果Fig.3 Simulational result of the 2-dimensional DCT module

圖4 二維DCT反變換的仿真結(jié)果Fig.4 Simulational result of the 2-dimensional IDCT module

提出了基于FPGA的二維DCT變換和IDCT變換實(shí)現(xiàn)結(jié)構(gòu)，并行的流水線算法使得該二維DCT和IDCT變換具有較高的數(shù)據(jù)吞吐率和處理速度，完成一次一維DCT和IDCT變換的計(jì)算僅僅消耗一個(gè)時(shí)鐘，同時(shí)進(jìn)行一次二維DCT和IDCT僅僅需要16個(gè)時(shí)鐘，與其他設(shè)計(jì)相比，大大提高了運(yùn)算的速度，滿足圖像、視頻處理中實(shí)時(shí)性的要求。可以用于實(shí)時(shí)性要求較高的視頻和圖像處理系統(tǒng)中。

[1]Conzalez R C，Woods R E.數(shù)字圖像處理[M].阮秋琦，阮宇智，譯.北京:電子工業(yè)出版社，2003.

[2]陳普躍，趙新璧，陳斌.二維DCT快速算法及FPGA實(shí)現(xiàn)[J].電子質(zhì)量，2008（2）:5-7.

CHEN Pu-Yue， ZHAO Xin-bi， CHEN Bin.Fast 2-D discrete cosine transform algorithm and its implementation based on FPGA[J].Electronics Quality，2008（2）:5-7

[3]鐘文榮，陳建發(fā).二維DCT算法的高速芯片設(shè)計(jì)[J].廈門大學(xué)學(xué)報(bào)，2005（2）:198-201.

ZHONG Wen-rong，CHEN Jian-fa.FPGA implementation of high throughput 2D-DCT[J].Journal of Xiamen University，2005（2）:198-201.

[4]田耘，徐文潑，張延偉.數(shù)字信號(hào)處理的FPGA實(shí)現(xiàn)[M].北京：電子工業(yè)出版社，2008.

[5]郭愛(ài)平.DCT算法優(yōu)化及其在數(shù)字水印中的應(yīng)用[D].蘭州：蘭州大學(xué)，2010.

[6]李芳.基于H.264/AVC的視頻編碼技術(shù)研究與FPGA實(shí)現(xiàn)[D].重慶:重慶大學(xué)，2008.

A new algorithm of two dimesion DCT and IDCT based on FPGA

ZHAO Bin，HUANG Da-qing
（Research Institute of Unmanned Aircraft，Nanjing Universty of Aeronautics and Astronautics，Nanjing210016，China）

A new algorithm of two dimentional cosine transform （DCT） and inverse discrete cosine transform （IDCT）based on FPGA is presented.The architecture uses a row-column decompostion to break the 2-D algorithm into two 1-D algorithm.The 1-D algorithm uses the parallel pipling architecture and one clock can process 8 datas that makes the circuit work with high data throughput and speed.Through the design tools of Modelsim and Quartus，the circuit is simulated and verified.The result shows the corroctness of the design and it can finish a two dimesional DCT or IDCT in 16 clocks，so it can meet the requirement of real_time in video processing.

2-D DCT；2-D IDCT；pipeline；FPGA

TP391

A

1674－6236（2011）24-0126-04

2011-10-14 稿件編號(hào)：201110059

趙 濱（1982—），男，吉林吉林人，碩士。研究方向：遙控遙測(cè)。