fft算法有很多的應用，尤其在信號測量和分析方面。由于該算法的計算量大，需要高速度的運算速度和一定容量的內存，一般采用dsp來做這方面的運算，但是隨著現在單片機技術的發展，高速、大容量內存的單片機相繼出現，在實際的數據測量和處理中有很大的用處，為了使問題方便表達，下面我們以基2，8點fft為例子加以說明。傳統的基2變幾何結構算法如下圖表示，箭頭上面的字代表了旋轉因子中的k。圖中輸入的是按照碼位顛倒的順序來排放的，輸出是自然順序。

　　這種結構的特點是每個蝶形的輸出數據仍然放在原來的輸入數據存儲單元內，于是只需要2n個存儲單元(fft中的數據是復數形勢，每一點需要兩個單元存儲)，但其缺點是不同級的同一位置蝶形的輸入數據的尋址不固定，難以實現循環控制。
　　
　　對此結構進行進一步的變換，將第二級的輸出不送回原處而是將其存儲起來并按順序存放，則第三級中間的兩個蝶形跟著調換，并把輸入按順序排列，就變成了下圖所示的固定結構的fft了。于是在蝶形變換的同時，其旋轉因子也跟著做了調換。

　　從上面可以看出輸出數據的順序是不變的，因此每級幾何結構是固定的，明顯加快了fft的運算速度。

相關文章

• 上一篇： 神經網絡在測控系統中的實現
• 下一篇： 滾筒式全自動洗衣機的程序控制器