FFT算法研究報告

1、程序設計背景(FFT算法理解)

FFT(fast fourier transformation),快速傅里葉變換。是對DFT算法的改進，其利用了WNnk的周期性、共軛對稱性和可約性，使得DFT中有些項可以合并，大大減小了計算量。

按輸入序列在時間上的次序是屬于偶數還是奇數來分解稱為“按時間抽取法”(DIT)。另一種是把輸出序列X(k)按順序的奇偶分解為越來越短的序列，稱為按頻率抽樣的FFT算法(DIF)。DIT算法是先作復乘后作加減，而DIF的復乘只出現在減法之后。本次程序采用DIT算法實現FFT。

用c語言實現FFT的難點在于數據倒位序的處理，以及各級蝶形運算的實現。倒位序的實現可以使用“反向進位加法”，即倒位序二進制數的下面一個數是上面一個數在最高位加一并由高位向低位進位而得到的。

對于點數為N = 2^L的FFT運算，可以分解為L階蝶形圖級聯，第M階蝶形圖內又分為2^(L-M)個蝶形組，每個蝶形組內包含2^(M-1)個蝶形。而且旋轉因子與蝶形階數和蝶形分組內的蝶形個數存在關聯。因此我們就可以構造循環來實現蝶形運算。

2、FFT算法流程圖

總結

以上是生活随笔為你收集整理的matlab 倒位序fft程序,FFT算法设计与实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。