基于TS101的DFT輸出子集算法研究及軟件實(shí)現(xiàn).pdf

1、自從庫利-圖基FFT算法出現(xiàn)以來，各種不同類型的FFT算法相繼出現(xiàn)，但是這些快速傅立葉變換的算法一般基于這樣一種假設(shè)，即假定輸入和輸出長度是相等的。在大部分應(yīng)用場合這是一個合理的假設(shè)，但是仍然有一些應(yīng)用場合輸入和輸出點(diǎn)數(shù)明顯不同，比如說矩陣處理計(jì)算本征值的高分辨率譜或者在濾波器設(shè)計(jì)中計(jì)算轉(zhuǎn)換域(通帶和阻帶之間)的響應(yīng)。另外FFT固有的頻率分辨率與計(jì)算量之間的矛盾從某種程度上也限制了它的應(yīng)用,因?yàn)橐岣逨FT的頻率分辨率，就要增加采樣點(diǎn)數(shù)

2、及計(jì)算量。而當(dāng)數(shù)據(jù)足夠長時，有時又不需要頻域的全部頻點(diǎn)，而只要得到頻譜中某一頻帶或一部分頻點(diǎn)的值即可，那么對無關(guān)頻點(diǎn)的計(jì)算就是多余的，找到能夠有效的計(jì)算DFT部分輸出點(diǎn)(輸出子集)的算法一直是學(xué)者們所關(guān)注的。
　　本文首先介紹了Goertzel算法、FFTPruning算法和變換分解法等DFT輸出子集應(yīng)用的算法，推導(dǎo)了它們的理論算法復(fù)雜度公式，并根據(jù)算法復(fù)雜度公式對各種算法的運(yùn)算量進(jìn)行了初步的對比。
　　然后結(jié)合分裂基算法和

3、Goertzel算法改進(jìn)了變換分解法，進(jìn)一步提高了變換分解法的運(yùn)算效率。之后，本文介紹了相關(guān)算法的軟件設(shè)計(jì)方法，并在VisualDSP++5.0上以TS101為目標(biāo)處理器仿真運(yùn)行得到相關(guān)數(shù)據(jù)，驗(yàn)證了理論推導(dǎo)的結(jié)果。結(jié)果表明變換分解法可以較大程度的提高DFT輸出子集應(yīng)用的計(jì)算效率，而且適用性較高。并討論了P的取值對變換分解法總運(yùn)算量的影響。考慮了實(shí)際的尋址運(yùn)算所需操作之后，推導(dǎo)得到了最優(yōu)P值的求取公式。對于1024點(diǎn)變換16點(diǎn)輸出的DFT