1、基4FFT算法的FPGA實(shí)現(xiàn),FFT是快速的傅立葉變換，它不是一種新的變換，是人們意識(shí)到DFT（離散傅立葉變換）運(yùn)算的一些內(nèi)在的規(guī)律，從而很快發(fā)展和完善的一套高速有效的運(yùn)算方法。 在進(jìn)行高速實(shí)時(shí)的數(shù)字信號(hào)處理過(guò)程中，F(xiàn)FT運(yùn)算是很耗時(shí)的，因此本文提出了基于FPGA的基-4FFT算法的實(shí)現(xiàn)，隨著帶硬件乘法器的FPGA越來(lái)越普遍，用硬件來(lái)代替軟件的今天，用FPGA實(shí)現(xiàn)FFT，提高了運(yùn)算速度，縮短了計(jì)算時(shí)間。,傳統(tǒng)基2FFT的算法,以按時(shí)間抽取基2算法為例： 設(shè)N（N= ） 為正整數(shù)， A 、B 為時(shí)間序列， A 、B 為頻率序列， 為旋轉(zhuǎn)因子，如右圖1 可知其基本迭代運(yùn)算為：,（1-1）,設(shè) 則代

2、入 （1-1）式得： 由1-1式可以看出來(lái)基2按時(shí)間抽取的FFT蝶形單元運(yùn) 算需要一次復(fù)數(shù)乘法運(yùn)算、兩次復(fù)數(shù)加（減）法運(yùn)算 由1-2式可以看出4次實(shí)數(shù)乘法運(yùn)算和6次實(shí)數(shù)加（減)法運(yùn)算。 傳統(tǒng)的基-2對(duì)于 個(gè)點(diǎn),有 次迭代運(yùn)算, 每次迭代運(yùn)算包含N/2個(gè)蝶形單元。,（1-2）,基-4算法原理,我們也同樣采用按時(shí)間抽取的方式講解基-4算 法的蝶形單元。 設(shè)A、B 、C 、D 為時(shí)間序列，A、B、C、D 為頻率序列， 為旋轉(zhuǎn)因子，則蝶形 單元運(yùn)算表達(dá)式為式1-3：,（1-3）,基-4蝶形單元信號(hào)流圖如下：,圖 1-2 基-4單元信號(hào)流圖,由1-3式可以看出，基-4蝶形單元需要三個(gè)復(fù)數(shù) 乘法器及十二個(gè)

3、復(fù)數(shù)加法（減）器，而且對(duì)于 N= 有 次迭代運(yùn)算，每次迭代運(yùn)算 包含N/4次蝶形運(yùn)算，每個(gè)基-4的蝶形單元與四個(gè) 基-2蝶形相比較，減少一次復(fù)數(shù)乘法，在相同N點(diǎn) 的FFT運(yùn)算過(guò)程中，基-4運(yùn)算的迭代運(yùn)算和每次迭 代包含的蝶形單元要少于基-2FFT算法，可以看出 基-4算法的研究可以大大提高FFT運(yùn)算的速度，更 加發(fā)揮FFT運(yùn)算快的優(yōu)勢(shì) 。,基-4算法的模塊實(shí)現(xiàn),FFT模塊的構(gòu)成： 1：旋轉(zhuǎn)因子乘法器；2：基-4蝶形運(yùn)算器； 3：地址產(chǎn)生器； 4：控制信號(hào)產(chǎn)生器 5：中間變量存放組 本文設(shè)計(jì)的FFT模塊的劃分圖如圖1-3,圖中 各個(gè)模塊在中央控制單元的管理下并行工作。,圖 1-3 FFT實(shí)現(xiàn)框圖

4、,在圖1-3中，運(yùn)算模塊為基-4運(yùn)算模塊，控制模塊產(chǎn)生 所有的控制信號(hào)、存儲(chǔ)器1和2的讀寫(xiě)地址、寫(xiě)使能、 運(yùn)算模塊的啟動(dòng)信號(hào)因子表的讀寫(xiě)地址等信號(hào)。,存儲(chǔ)器1作為當(dāng)前輸入標(biāo)志對(duì)應(yīng)輸入N點(diǎn)數(shù)據(jù)緩 沖器，存儲(chǔ)器2作為中間變量結(jié)果存儲(chǔ)器，用于 存儲(chǔ)運(yùn)算模塊計(jì)算出各個(gè)通道的結(jié)果。 舉例：外部輸入為N點(diǎn)數(shù)據(jù)段流和啟動(dòng)信號(hào)，一方 面，外部數(shù)據(jù)存入存儲(chǔ)器1中，同時(shí)通過(guò)控制模塊的 控制，讀出存儲(chǔ)器1中的前段N點(diǎn)數(shù)據(jù)和ROM表中的 因子及相關(guān)控制信號(hào)送入運(yùn)算核心模塊進(jìn)行各個(gè)Pass 運(yùn)算,每個(gè)Pass運(yùn)算的輸出都存入存儲(chǔ)器2中，最后一個(gè) Pass的計(jì)算結(jié)果存入存儲(chǔ)器2中，啟動(dòng)并在下一個(gè)啟動(dòng) 頭到來(lái)后，輸出計(jì)算結(jié)

5、果。,FFT硬件實(shí)現(xiàn),1：旋轉(zhuǎn)因子乘法器的實(shí)現(xiàn) FFT設(shè)計(jì)一個(gè)旋轉(zhuǎn)因子存儲(chǔ)單元可以提高FFT的 計(jì)算速度，因此需要合理的設(shè)計(jì)旋轉(zhuǎn)因子的存 儲(chǔ)單元，在FFT硬件設(shè)計(jì)中占重要地位。本文采用 一種高效的算法來(lái)實(shí)現(xiàn)存儲(chǔ)旋轉(zhuǎn)因子。 設(shè)復(fù)數(shù)旋轉(zhuǎn)因子乘法器R+ jI=(X+ jY) (C+ jS) 因?yàn)镃、S可以預(yù)先計(jì)算的，并可以存儲(chǔ)在一個(gè)表 中。所以我們可以存儲(chǔ)下面三個(gè)系數(shù)： C、C+S、C-S,有了這3個(gè)預(yù)先計(jì)算的因子，我們可以首先計(jì)算： E=X-Y和Z=C*E=C*（X-Y） 然后用： R=（C-S）*Y+Z I=（C+S)*X-Z 計(jì)算最后乘積，我們可以驗(yàn)證這種算法的 正確性： R=（C-S）*Y+

6、Z=（C-S）*Y+C（X-Y） =CY-SY+CX-CY=CX-SY,I=（C+S）*X-Z=（C-Z）*X-C（X-Y） =CX+SX-CX+CY=SX+C 該運(yùn)算只需要將C、C+S、C-S三個(gè)系數(shù)存在 表中，在通過(guò)查表計(jì)算出旋轉(zhuǎn)因子的實(shí)部和虛 部，選用一個(gè)地址發(fā)生器來(lái)通過(guò)調(diào)用不同的地 址來(lái)調(diào)用旋轉(zhuǎn)因子的實(shí)部和虛部。 本文設(shè)計(jì)了一個(gè)512*16的ROM，如圖1-4，把C、 C+S、C-S，分別存儲(chǔ)在ROM中，這樣蝶形單 元運(yùn)算就可以直接調(diào)用旋轉(zhuǎn)因子實(shí)部和虛部， 大大提高了FFT運(yùn)算速度。,圖 1-4 旋轉(zhuǎn)因子存儲(chǔ)器,2：蝶形運(yùn)算單元設(shè)計(jì)： 已知基-4的蝶形單元運(yùn)算如式1-3，設(shè)式1-3的

7、復(fù)數(shù)數(shù)據(jù)為： 并將其代入1-3式，按以上數(shù)據(jù)我設(shè)計(jì)了三個(gè) 模塊單元，他們分別是： 則在Quartus中設(shè)計(jì)的模塊圖如圖1-5,圖 1-5 單元4_fft模塊圖,使用4_fft模塊并按照將復(fù)數(shù)數(shù)據(jù)代入1-3式可搭建單元蝶形圖，其模塊圖如圖1-6,圖1-6 蝶形單元設(shè)計(jì)圖,小結(jié),本文通過(guò)設(shè)計(jì)一種基于FPGA的基-4的FFT，探討 FPGA在實(shí)現(xiàn)FFT算法中的應(yīng)用。本文重點(diǎn)設(shè)計(jì)了采用 一種旋轉(zhuǎn)因子存儲(chǔ)器搭建基-4FFT蝶形模塊，實(shí)現(xiàn)蝶 形運(yùn)算單元。本系統(tǒng)最大的優(yōu)勢(shì)在于利用FPGA豐富邏 輯資源，及其靈活的可編程特性使運(yùn)算速度較傳統(tǒng)方 法有了很大提高。 用FPGA實(shí)現(xiàn)基-4FFT可以獲得高性能，滿足成本 要求，并享有快速有效地對(duì)新設(shè)計(jì)進(jìn)行優(yōu)化