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

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

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

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

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

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

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

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

　　表3 一些fpga fft實現的比較^[5]

　　歡迎轉載，信息來源維庫電子市場網（www.dzsc.com）