很明顯，目前已經(jīng)有許多途徑可以實現(xiàn)dft。現(xiàn)在就從圖中給出的算法中選定一種短dft算法開始介紹。而且短dft可以用cooley-tukey、good-thomas或winograd提出的索引模式來開發(fā)長dft。選擇實現(xiàn)的共同目標(biāo)就是將乘法的復(fù)雜性降到最低。這是一種可行的準(zhǔn)則，因為乘法的實現(xiàn)成本與其他運算，比如加法、數(shù)據(jù)訪問或索引計算相比較而言要高得多。

　　圖給出了各種fft長度所需要乘法的次數(shù)。從中可以得出結(jié)論，單純從乘法復(fù)雜性準(zhǔn)則考慮，winograd fft是最有吸引力的。在本章中，給出了幾種形式的n=4×3＝12點fft的設(shè)計。表1給出了直接算法、rader質(zhì)數(shù)因子算法和用于簡單dft的模塊和3種分別稱為cooley－tukey、good－thomas和winograd fft的不同索引映射的winograd fft算法。

　　表 長度為12復(fù)雜輸入fft算法的實數(shù)乘法的數(shù)量，假設(shè)一個復(fù)雜的乘法使用了4個實數(shù)乘法

　　圖 基于所需要的實數(shù)乘法次數(shù)的不同fft算法的比較

　　除了乘法的次數(shù)以外，還需要考慮其他的約束條件，例如可能的變換長度、加法的次數(shù)、索引計算開銷、系數(shù)或數(shù)據(jù)存儲器規(guī)模和運行期間代碼的長度。在許多情況下，cooley-tukey方法提供了最佳總體解決方案，請參閱表2。

　　表2 長度n＝∏nk的fft算法的重要屬性

　　目前fpga所達(dá)到的復(fù)雜性己經(jīng)超過1m門，fft完全可以集成在單片fpga中。由于這樣的fft模塊設(shè)計是勞動密集的，通常使用大批供應(yīng)的“知識產(chǎn)權(quán)”（intellectual property，ip）模塊（有時候也稱作虛擬組件（virtual component，vc））更有意義。例如可以訪問www，xilinx．com或www．a(chǎn)ltera．com，參閱ip合作程序。多數(shù)大批供應(yīng)的設(shè)計都是基于radix－2或radix－4的。

　　表3總結(jié)了一些已公布的fpga實現(xiàn)。goslin^[120]的設(shè)計是基于radix-2fft的。dandalis等人^[136]的設(shè)計是基于采用所謂的算術(shù)傅立葉變換的dft近似。

　　表3 一些fpga fft實現(xiàn)的比較^[5]

　　歡迎轉(zhuǎn)載，信息來源維庫電子市場網(wǎng)（www.dzsc.com）