基于FPGA的可擴(kuò)展高速FFT處理器的設(shè)計(jì)與實(shí)現(xiàn)

　　一、引言

　　DFT（離散傅里葉變換）作為將信號(hào)從時(shí)域轉(zhuǎn)換到頻域的基本運(yùn)算，在各種數(shù)字信號(hào)處理中起著核心作用，其快速算法FFT（快速傅里葉變換）在無(wú)線(xiàn)通信、語(yǔ)音識(shí)別、圖像處理和頻譜分析等領(lǐng)域有著廣泛的應(yīng)用。用大規(guī)模集成電路FPGA（現(xiàn)場(chǎng)可編程門(mén)陣列）來(lái)實(shí)現(xiàn)FFT算法時(shí)，需要重點(diǎn)考慮的不再是算法運(yùn)算量，而是算法的復(fù)雜性、規(guī)整性和模塊化，因?yàn)樗惴ǖ暮?jiǎn)單性和規(guī)整性將更適合大規(guī)模集成，更方便于版圖設(shè)計(jì)，而算法的模塊化更有利于FFT處理器的靈活擴(kuò)展。組合數(shù)FFT算法和CORDIC（坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算機(jī)）算法結(jié)合起來(lái)，在計(jì)算長(zhǎng)點(diǎn)數(shù)、可擴(kuò)展FFT時(shí)具有較大的優(yōu)越性［1，2］。而面向高速、大容量數(shù)據(jù)流的FFT的實(shí)時(shí)處理，可以通過(guò)VLSI（超大規(guī)模集成電路）器件的并行處理或多級(jí)流水線(xiàn)處理等來(lái)達(dá)到。特別是多級(jí)流水線(xiàn)處理的FFT結(jié)構(gòu)使得基于FPGA器件的FFT處理器完成不同點(diǎn)數(shù)的FFT計(jì)算時(shí)可以通過(guò)增減模塊級(jí)數(shù)很容易地實(shí)現(xiàn)。

　　二、組合數(shù)N=r1r2點(diǎn)混合基FFT原理

　　計(jì)算N點(diǎn)DFT：

　　式中k=0，1，…，N-1。

　　若N=r1r2的組合數(shù)，可將n（n＜N）表示為

　　式（2）的意

　　義在于，計(jì)算組合數(shù)N=r1r2點(diǎn)DFT，等價(jià)于先求出r?2組r?1點(diǎn)的DFT，其結(jié)果經(jīng)過(guò)對(duì)應(yīng)旋轉(zhuǎn)因子的相位旋轉(zhuǎn)后，再計(jì)算r1組r2點(diǎn)的DFT。實(shí)際應(yīng)用中，DFT往往用它的快速算法FFT實(shí)現(xiàn)，因而式（2）中的r1點(diǎn)DFT和r2點(diǎn)DFT都用r1點(diǎn)FFT和r2點(diǎn)FFT實(shí)現(xiàn)。

　　三、可擴(kuò)展FFT處理器實(shí)現(xiàn)結(jié)構(gòu)

　　根據(jù)式（2）的FFT算法原理設(shè)計(jì)FFT處理器的可擴(kuò)展結(jié)構(gòu)如圖1所示。

　　采用流水線(xiàn)模塊化級(jí)聯(lián)結(jié)構(gòu)，把FFT處理器劃分成短點(diǎn)數(shù)FFT、級(jí)間混序RAM和相位旋轉(zhuǎn)等功能模塊，設(shè)計(jì)的各功能模塊可以重復(fù)利用，通過(guò)復(fù)用或增減各功能模塊可以靈活改變FFT處理器的計(jì)算規(guī)模，而且不增加設(shè)計(jì)量。在圖1結(jié)構(gòu)中，當(dāng)Li＝1時(shí)，就演變成了基2 FFT；當(dāng)Li＝2時(shí)，就演變成了基4 FFT；同理，當(dāng)Li≠Lj時(shí)，就演變成了高組合數(shù)的混合基FFT。

　　1.短點(diǎn)數(shù)FFT陣列結(jié)構(gòu)

　?。璗ukey算法結(jié)構(gòu)實(shí)現(xiàn)時(shí)，有大量的復(fù)數(shù)乘法實(shí)際上轉(zhuǎn)化為加減運(yùn)算，所以用陣列結(jié)構(gòu)實(shí)現(xiàn)不但具有速度快的優(yōu)點(diǎn)，而且所用器件資源也減少很多，通過(guò)對(duì)陣列結(jié)構(gòu)短點(diǎn)數(shù)FFT進(jìn)行時(shí)分復(fù)用，可以提高運(yùn)算單元的使用效率。

　　2.相位旋轉(zhuǎn)運(yùn)算單元

　　實(shí)現(xiàn)短點(diǎn)數(shù)FFT級(jí)間相位旋轉(zhuǎn)，采用ROM存儲(chǔ)旋轉(zhuǎn)因子與數(shù)據(jù)復(fù)乘的傳統(tǒng)方法，不僅涉及乘法運(yùn)算，而且會(huì)消耗大量存儲(chǔ)器資源。

　　利用CORDIC算法實(shí)現(xiàn)組合數(shù)FFT級(jí)間數(shù)據(jù)的相位旋轉(zhuǎn)，把乘法轉(zhuǎn)化成加減法運(yùn)算，適合FPGA的大規(guī)模集成?？梢栽O(shè)計(jì)出統(tǒng)一結(jié)構(gòu)的CORDIC處理器模塊，重復(fù)利用于不同級(jí)間實(shí)現(xiàn)相位旋轉(zhuǎn)，而且其控制邏輯非常簡(jiǎn)單。

　?。?）CORDIC算法原理

　　如果旋轉(zhuǎn)角度θ可以分解成n個(gè)小角度φi之和，即：

　　公式：

　?。?）CORDIC處理器結(jié)構(gòu)設(shè)計(jì)

　　本文提出了一種流水線(xiàn)CORDIC處理器結(jié)構(gòu)的解決方案。實(shí)現(xiàn)式子（4）的迭代運(yùn)算時(shí)采用補(bǔ)碼移位和補(bǔ)碼加減運(yùn)算，可以減少大量求補(bǔ)運(yùn)算，其迭代結(jié)構(gòu)如圖2所示。

　　前者在于左移補(bǔ)零的位數(shù)的不同，這樣，只需要改變n0k0的放大倍數(shù)（改變左移低位補(bǔ)零的位數(shù)），就可以把同一方向向量功能模塊級(jí)聯(lián)到圖1 FFT處理器的不同級(jí)間來(lái)計(jì)算CORDIC處理器的MSBi，這就大大地減小了重復(fù)設(shè)計(jì)，其迭代結(jié)構(gòu)如圖3所示。