摘 要： 二維傅立葉變換" title="傅立葉變換">傅立葉變換" title="快速傅立葉變換" title="快速傅立葉變換">快速傅立葉變換">快速傅立葉變換(FFT)在一個(gè)傳統(tǒng)概念的處理機(jī)上實(shí)現(xiàn)時(shí),，需要芯片具有更多的邏輯資源,。本文給出了基于FPGA的自定義處理機(jī)（CCM）的二維FFT算法和實(shí)現(xiàn),。在CCM的Splash-2平臺(tái)上實(shí)現(xiàn)了二維FFT，計(jì)算速度達(dá)到180Mflops,，最快速度超過(guò)Sparc-10工作站的23倍,。同時(shí),，對(duì)于一個(gè)N×N圖像，這種實(shí)現(xiàn)方法可以滿(mǎn)足二維FFT所需要的O(N2log2N)次的浮點(diǎn)算術(shù)運(yùn)算。
關(guān)鍵詞： 自定義處理機(jī)（CCM）,；二維；快速傅立葉變換（FFT）,； 圖像,；Splash-2
?
當(dāng)被處理的圖像像素相對(duì)較小時(shí)，可以直接采用空間域?yàn)V波的方法,。但隨著像素的增多,，計(jì)算量也隨之增大。針對(duì)這種情況,，本文對(duì)像素較大的圖像,，采用了一種將圖像先從空域轉(zhuǎn)換到頻域，執(zhí)行點(diǎn)到點(diǎn)的乘法濾波,，然后通過(guò)反傅立葉變換,，將頻域內(nèi)濾波器圖像再轉(zhuǎn)換到空間域的方法。在此基礎(chǔ)上,，對(duì)二維快速傅立葉變換采用了基于FPGA的CCM的Splash-2平臺(tái)實(shí)現(xiàn)方式,，目的是為了對(duì)視頻信號(hào)進(jìn)行實(shí)時(shí)濾波。實(shí)現(xiàn)過(guò)程中需要對(duì)浮點(diǎn)數(shù)" title="浮點(diǎn)數(shù)">浮點(diǎn)數(shù)進(jìn)行計(jì)算,，采用了CCM可以自定義數(shù)據(jù)格式和算法數(shù)據(jù)流以滿(mǎn)足應(yīng)用的需要,。
1 用傅立葉變換進(jìn)行圖像濾波
圖1是用快速傅立葉變換進(jìn)行圖像濾波處理的實(shí)現(xiàn)過(guò)程[1]，其中,，預(yù)處理階段包括確定圖像大小,、獲得填充參數(shù)和生成一個(gè)濾波函數(shù)等過(guò)程,；后處理階段包括計(jì)算結(jié)果的實(shí)部" title="實(shí)部">實(shí)部，修剪圖像以及將圖像進(jìn)行轉(zhuǎn)換等操作,，其他部分將在以下環(huán)節(jié)分別進(jìn)行介紹,。
?
1.1 離散傅立葉變換（DFT）
一個(gè)N×N圖像的二維的DFT，f(x,，y)定義為：
二維的DFT變換可以分解成多個(gè)一維的傅立葉變換,，則(1)式等同于：
公式(1)、(2)表明一個(gè)N×N的二維DFT可以通過(guò)先進(jìn)行N個(gè)一維DFT（行）,，然后再進(jìn)行另外N個(gè)一維DFT（列）來(lái)計(jì)算,，即所謂的行列分解法[2]。
1.2 快速傅立葉變換（FFT）
? 執(zhí)行一個(gè)N點(diǎn)DFT所需的復(fù)雜乘法和加法運(yùn)算次數(shù)與N2成正比,。由于一維DFT可以被分解,，所以進(jìn)行乘法與加法運(yùn)算的次數(shù)正比于N×log2N。而FFT算法通過(guò)“分而治之”的方法來(lái)實(shí)現(xiàn)其較高的計(jì)算效率,。通過(guò)時(shí)間與頻率采樣的分組,，具有N個(gè)值的DFT運(yùn)算可以表示成兩點(diǎn)DFT的組合方式。這兩點(diǎn)DFT稱(chēng)為蝶形運(yùn)算,，它需要一次復(fù)乘和兩次復(fù)加來(lái)實(shí)現(xiàn),。蝶形結(jié)構(gòu)的符號(hào)如圖2所示（左側(cè)：基2的蝶形結(jié)構(gòu)）。
?
用FFT“分而治之”的方法,，一個(gè)8點(diǎn)的FFT的計(jì)算如圖2所示,。N點(diǎn)FFT的每一級(jí)運(yùn)算由N/2基2的蝶形組成，總共有l(wèi)og2N次運(yùn)算,。因此,，每個(gè)FFT共有(N/2)×log2N個(gè)蝶形結(jié)構(gòu)。一個(gè)二維FFT可以拆分為兩組一維的DFT運(yùn)算,，且每個(gè)DFT可以用一維的FFT來(lái)計(jì)算,。此外，數(shù)據(jù)以倒位序輸入而以正常的線性順序輸出,。
2 浮點(diǎn)算法
2.1 浮點(diǎn)格式的表示
為了實(shí)現(xiàn)本文給出的FFT運(yùn)算,，在此設(shè)計(jì)了一個(gè)較小的18bit的浮點(diǎn)格式。用這種格式來(lái)滿(mǎn)足兩種特定要求：(1)動(dòng)態(tài)范圍需要非常大,，以便能夠準(zhǔn)確地表示一個(gè)實(shí)數(shù)的大小,、正負(fù)；(2)進(jìn)入Splash-2平臺(tái)的XILINX 4010處理器的數(shù)據(jù)通道寬度為36bit,，且每一個(gè)時(shí)鐘周期" title="時(shí)鐘周期">時(shí)鐘周期內(nèi)都輸入復(fù)數(shù)的實(shí)部與虛部,。基于這些要求，使用的浮點(diǎn)格式如圖3所示,。
?
2.2 浮點(diǎn)加法減法與乘法
為了在每個(gè)時(shí)鐘周期產(chǎn)生一個(gè)結(jié)果,，開(kāi)發(fā)浮點(diǎn)加減法程序來(lái)實(shí)現(xiàn)管道化單元,，所實(shí)現(xiàn)的浮點(diǎn)加法與減法算法與最傳統(tǒng)的處理器相似,。
浮點(diǎn)乘法與整數(shù)乘法類(lèi)似。因?yàn)楦↑c(diǎn)數(shù)是以“符號(hào)－數(shù)字”的形式存儲(chǔ),，乘法器僅需要處理無(wú)符號(hào)整數(shù),，與浮點(diǎn)加法器的結(jié)構(gòu)類(lèi)似[3]，浮點(diǎn)乘法器單元也是每個(gè)時(shí)鐘周期產(chǎn)生一次結(jié)果,，這種設(shè)計(jì)的瓶頸是整數(shù)乘法器,。
本文將VHDL語(yǔ)言放在XILINX芯片相應(yīng)開(kāi)發(fā)工具ISE中進(jìn)行編譯，同時(shí)給出時(shí)延,、速度等相關(guān)參數(shù),。
浮點(diǎn)運(yùn)算單元還與FIR濾波器組合一起使用。FFT運(yùn)算以10MHz工作,，轉(zhuǎn)換的結(jié)果存儲(chǔ)在Splash-2開(kāi)發(fā)板的存儲(chǔ)器中,。算術(shù)單元的最大時(shí)鐘速度至少可以工作在10MHz。
3 FFT的實(shí)現(xiàn)
本文從一個(gè)幀緩沖區(qū)得到連續(xù)的視頻圖像提供給FFT和IFFT參與并行計(jì)算從而構(gòu)建出濾波算法,。以下討論用于實(shí)現(xiàn)FFT,、FFT中的蝶形操作以及濾波處理的再循環(huán)算法。
3.1 FFT再循環(huán)算法
為了計(jì)算二維的FFT,，需要設(shè)計(jì)一個(gè)通過(guò)蝶形運(yùn)算的數(shù)據(jù)循環(huán)算法,。圖4給出了相應(yīng)的結(jié)構(gòu)圖。
?
?
兩列存儲(chǔ)器用來(lái)存儲(chǔ)FFT的每一級(jí)運(yùn)算的輸入輸出數(shù)據(jù),。每一列存儲(chǔ)器包括三個(gè)處理單元,，用來(lái)把兩個(gè)18bit浮點(diǎn)數(shù)的實(shí)部與虛部存儲(chǔ)到它們的本地內(nèi)存。由于本地內(nèi)存只有16bit寬,，先將兩個(gè)18bit浮點(diǎn)數(shù)值進(jìn)行分割,，然后按順序放在三個(gè)存儲(chǔ)單元中。為了計(jì)算輸入圖像的FFT,，來(lái)自于幀緩沖區(qū)中的數(shù)據(jù)幀從8bit的整數(shù)被轉(zhuǎn)換為18bit的浮點(diǎn)數(shù)存儲(chǔ)在第一列中,。在計(jì)算二維FFT時(shí)，首先計(jì)算圖像每一行的一維FFT,，然后計(jì)算行變換后每一列的FFT,。一維FFT的計(jì)算與圖2中所示方法相同。FFT的第一級(jí)通過(guò)從第一列存儲(chǔ)區(qū)以倒位序讀取數(shù)據(jù)采樣點(diǎn)的每一行,，然后將它送給蝶形操作進(jìn)行計(jì)算,。蝶形計(jì)算的結(jié)果存儲(chǔ)在第二列存儲(chǔ)區(qū)。當(dāng)?shù)谝患?jí)中的蝶形計(jì)算完成時(shí),，開(kāi)始第二級(jí)計(jì)算,，從第二列存儲(chǔ)區(qū)中順序讀取數(shù)據(jù)然后送入蝶形處理器,，這一操作的結(jié)果存儲(chǔ)在第一列存儲(chǔ)區(qū)。這一循環(huán)方法通過(guò)從一個(gè)存儲(chǔ)區(qū)中讀數(shù)而在另一外存儲(chǔ)區(qū)存儲(chǔ)計(jì)算結(jié)果來(lái)進(jìn)行,。當(dāng)圖中每一行一維FFT計(jì)算完時(shí)循環(huán)終止,。第二組一維FFT與第一組以相同的方法進(jìn)行計(jì)算，直到第二組的FFT計(jì)算完第一組的所有結(jié)果,。當(dāng)最后一次FFT的最后一級(jí)計(jì)算完時(shí),，數(shù)據(jù)從X11傳到X15進(jìn)行濾波。一次完整的二維FFT過(guò)程包括2×N2×log2N次蝶形操作,。
3.2 蝶形實(shí)現(xiàn)
蝶形操作是FFT算法的核心,。蝶形運(yùn)算框圖如圖2所示，它包括了一次復(fù)乘與兩次浮點(diǎn)加法,、減法,。復(fù)乘包括4次乘法和兩次加減。每個(gè)時(shí)鐘周期內(nèi)以10MHz進(jìn)行8次浮點(diǎn)操作,。蝶形操作的計(jì)算量為80Mflops,。圖5表示在Splash-2平臺(tái)上如何將蝶形運(yùn)算在5個(gè)處理單元之間進(jìn)行分割計(jì)算。
復(fù)乘的實(shí)部與虛部分別用下式來(lái)表示：
圖2中蝶形運(yùn)算輸入A與輸入B如圖5中的f（x）所示,。A值先送入計(jì)算,，在下個(gè)時(shí)鐘周期再送入B的值。輸入A不與旋轉(zhuǎn)因子相乘而是通過(guò)多路選擇開(kāi)關(guān)對(duì)它乘1加0無(wú)改變地通過(guò)循環(huán)運(yùn)算,。當(dāng)B的實(shí)部與虛部送入時(shí),，它們依次通過(guò)4個(gè)處理單元來(lái)得到復(fù)乘結(jié)果。處理單元1（PE1）讀出相應(yīng)旋轉(zhuǎn)因子的實(shí)部并將它與B的實(shí)部相乘,，計(jì)算結(jié)果與旋轉(zhuǎn)因子送到處理單元3（PE3）,，B的實(shí)部與虛部送到處理單元2（PE2）。PE2將B的虛部與相應(yīng)旋轉(zhuǎn)因子相乘結(jié)果送入PE3,。PE3從PE1中讀取B.re.re,，把它與從PE2中讀取的B.im.im相加，得到復(fù)乘實(shí)部的最終結(jié)果.re,；復(fù)乘虛部.im可用同樣的方法在PE3與PE4中得到,。在第一個(gè)時(shí)鐘周期內(nèi)將A與相加得到X，在第二個(gè)時(shí)鐘周期內(nèi)將A減去得到Y(jié),，這樣就完成了蝶形運(yùn)算,。
?
由于存儲(chǔ)器數(shù)據(jù)總線的寬度僅為16bit，在本地PE1,、PE2的存儲(chǔ)器中無(wú)法存儲(chǔ)18bit格式的旋轉(zhuǎn)因子,。因此從18bit浮點(diǎn)指數(shù)域中減去2bit來(lái)產(chǎn)生一個(gè)較小的16bit格式，而用歐拉定理可以將旋轉(zhuǎn)因子表示成正余弦函數(shù)的形式，因此浮點(diǎn)數(shù)的值將不會(huì)有大于0的指數(shù),。因此,，指數(shù)域范圍從0～－31變化，這樣指數(shù)域的長(zhǎng)度從7bit減到5bit,。當(dāng)旋轉(zhuǎn)因子被讀入處理單元時(shí),，在相應(yīng)運(yùn)算單元中進(jìn)行一次從16bit格式到18bit格式的轉(zhuǎn)換即可。
3.3 濾波
當(dāng)輸入圖像轉(zhuǎn)換到頻域時(shí),，矩陣濾波系數(shù)H(u,，v)和轉(zhuǎn)換后的圖像可以通過(guò)濾波器得到濾波后的圖像,。矩陣H(u,，v)元素值的范圍為0～1.0，它與蝶形運(yùn)算旋轉(zhuǎn)因子以相同的的存儲(chǔ)方式存儲(chǔ)在本地的存儲(chǔ)器中,。濾波系數(shù)存儲(chǔ)在X15和X16芯片的本地存儲(chǔ)器中,。濾波器芯片包括一個(gè)浮點(diǎn)乘法單元和濾波系數(shù)地址邏輯單元，X15與X16用來(lái)對(duì)轉(zhuǎn)換后圖像的實(shí)部和虛部分別進(jìn)行濾波,。
不同類(lèi)型的濾波器如理想濾波器以及其他類(lèi)型濾波器可以先計(jì)算,，然后從宿主機(jī)下載到開(kāi)發(fā)平臺(tái)的存儲(chǔ)器中。
由于CCM的靈活性,，浮點(diǎn)格式可以通過(guò)自定義方式以最小的比特?cái)?shù)來(lái)達(dá)到最大精度,。利用Splash-2的并行結(jié)構(gòu)，地址計(jì)算,、蝶形運(yùn)算以及濾波可以并行地進(jìn)行計(jì)算,。通過(guò)蝶形運(yùn)算操作，每個(gè)時(shí)鐘周期內(nèi)可以以10MHz的速度得到一個(gè)實(shí)數(shù)或復(fù)數(shù)結(jié)果,。這種應(yīng)用的性能類(lèi)似于一個(gè)典型的DSP處理器所達(dá)到的性能,。
參考文獻(xiàn)
[1] RAFAE1 C G，RICHARD E W,，STEVEN L E.數(shù)字圖像處理.北京：電子工業(yè)出版社,，2006.
[2] DAN E D，RUSSELL M M.多維數(shù)字信號(hào)處理.北京：科學(xué)出版社,，1991.
[3] SHIRAZI N,，WALTERS A P A.Quantitative analysis of floating point arithmetic on FPGA based custom computing?machines.IEEE Symposium on FPGAs for Custom Computing Machines，1995,，(4).