按時間抽取的FFT算法及蝶形運算

FFT算法的引入

通過計算、推導我們知道，N點序列x[n]的DTFT，可以表示成N/2點序列g[n] = x[2n]和h[n] = x[2n+1]的DTFT形式。由于DFT可以看作對DTFT的采樣，故X[k]同樣可以表示成g[n]和h[n]的DFT形式。

FFT算法推導

1. 數學推導：

   （1）參考上述引入可以知道，X[k]可以由N/2點序列的DFT表示，其中WkN是由序列的以為造成的。

   

   （2）其中G[k]，H[k]的表達式如下：

   

   （3）由于G[k]、H[k]是N/2點的DFT，是以其周期為N/2，故可以将(1)式子改寫成：

   

2. 信号流圖如下：

• H[k]、G[k]由于其周期性，是以有x[4/5/6/7]均可以由G[0/1/2/3]和H[0/1/2/3]計算得出；W因子是由時序移位所造成的，這樣子友善記憶。

  

• G[0/1/2/3]為N/2點的DFT，故可以将其分解為2個N/4點的DFT；H[0/1/2/3]的計算同理。

  說明：G[0/1/2/3]的計算可以通過将x[0]、x[2]、x[4]、x[6]序列拆分成奇偶序列進行N/4點的DFT計算。G[0/1/2/3]需要4個點的組合運算，這四個數值是由2對長度為N/4序列的DFT的結果得到。這樣子就便于了解為什麼，我們前面還要有一層運算。

  

• 我們将N/4點的DFT補充，有流圖如下：

  下圖中所有的W都是以N為底數，實際上，我們每一層分别以N、N/2、N/4為底數，隻不過我們可以通過約分将底數均表示為N，這樣子較為美觀。

  

FFT的進一步化簡----蝶形運算

1. 利用系數WNr 的對稱性和周期性可以進一步減小流圖的計算量：

• 有如下推導：

  

• 是以有：

  

• 故有如下簡化方法：

  

1. 是以有如下的化簡方式：