【1】前言

1、DIF計算量

更加清楚地了解計算步驟：

觀察可知：
1、一次復數乘法需用四次實數乘法和二次實數加法；
2、一次復數加法需二次實數加法
3、整個 DFT 運算總共需要 4N^2 次實數乘法和 2N*(2N—1)次實數加法。
總結：
直接計算 DFT,乘法次數和加法次數都是和 N^2 成正比的。

2、利用性質改善

利用這些性質，將較大的N分解為若干個較小的N然后進行運算。

【2】公式推導

1、N 到 2*N/2

a、分解原序列

b、分解后的DFT變換

c、一系列化簡操作之后

d、蝶形信號流

以N=8的序列為例：

e、計算量總結

因而通過第一步分解后， 總共需要（N^2/2)+(N/2)=N(N+l )/2約等于 N^2/2 次復數乘法和 N( N/2-1 )+N = N^2/2 次 復數加法。由此可見，通過這樣分解后的運算工作量差不多節省了一半。

2、N/2 到 2*N/4

a、分解X2(k)序列

b、蝶形信號流（2列）

3、N/4 到 2*N/8

a、蝶形信號流（3列）

【3】公式總結

由于乘法的運算量較大，我們從乘法角度來探討一下，DFT和FFT的運算量。
設N=2^M；有M列的蝶形信號運算。

從乘法角度：DFT需要N^2,FFT需要N*lbN;

當N=2048時，這一比值為372.4,即直接計算DFT的運算量是FFT運算量的372.4倍。
當點數N越大時，FFT的優點更為明顯。

【4】特點以及程序框架講解

1、原址運算

計算之后，將新的X(k)覆蓋原本的X(k)。
注意：是將同一行的X進行覆蓋（后面的列覆蓋前面的列），不同行之間是沒有覆蓋關系的。
所以，最后只需要N個存儲單元。（N個數據,N行）

2、倒位序規律

輸出X(k),序列正常。
輸入序列不正常。
原因：X(n)按照標號n的奇偶而不斷分組。
例子：

步驟流程：
I+1，最低位+1，向左進位。
J在二進制最高位+1，逢2向右進位。
由此可以從當前的倒序值計算求得下一個倒序值。

觀察變址處理，可以發現，只有當J>I時，才將X(I)和X(J)存儲內容進行互換。

3、蝶形運算兩節點的距離

輸入為倒位序，輸出為正位序，N=2^ M,在第m級運算，兩個節點間的距離為2^(m-1);

4、WN^r的確定

r的變換規律：
1、運算兩個節點中第一個節點標號為k，表示為M位的二進制數。
2、將此二進制數乘以2^(M-m)，相當于左移M-m位，把右邊空出，此數位r的二進制數。

5、程序框架

【5】代碼實現

沒有驗證代碼的正確性，只是按照上面的流程圖進行敘述。

#define PI 3.14159//數位倒讀
int rev(int i, int m) {//i=0~2^m,m為二進制位數 int j = 0;while (m > 0) {j += (i & 0x01) * (0x01 << (m - 1));//j+=(i%2)*mypow(2,m-1);i >>= 1;//i/=2m -= 1;}return j;
}//快速傅里葉變換
//輸入x(n)、N
//輸出X(k)
void fft(const float real_in[], const float imag_in[], float real_out[], float imag_out[],int N) 
{//【1】獲取Mint M = log2(N);	//【2】倒序for (int i = 0;i < N;i++) {//數位倒讀 int j;j = rev(i, M);real_out[j] = real_in[i];imag_out[j] = imag_in[i];}//【3】for (int m = 1;m <= M;m++){int B = 2 ^ m - 1;for (int J = 0;J <= B - 1;J++){int P = 2 ^ (M - m) * J;for (int k = J;k <= N - 1;k++){float tmpr1, tmpi1, tmpr2, tmpi2;//臨時變量float theta = -2 * PI * P / N ;tmpr1 = real_out[k];tmpi1 = imag_out[k];tmpr2 = cos(theta) * real_out[k + B] - sin(theta) * imag_out[k + B];tmpi2 = cos(theta) * imag_out[k + B] + sin(theta) * real_out[k + B];real_out[k] = tmpr1 + tmpr2;imag_out[k] = tmpi1 + tmpi2;real_out[k + B] = tmpr1 - tmpr2;imag_out[k + B] = tmpi1 - tmpi2;}}}
}

---

參考資料：

《數字信號處理第三版.劉順蘭版》