FFT（快速傅立葉變換）是DFT的一種特殊情況，就是當運算點的個數是2的整數次冪的時候進行的運算（不夠用0補齊）。FFT計算原理及流程圖：原理：FFT的計算要求點數必須為2的整數次冪，如果點數不夠用0補齊。例如計算{2，3，5，8，4}的16點FFT，需要補11個0後進行計算。FFT計算運用蝶形運算，在蝶形運算中變化規律由W(N, p)推導，其中N為FFT計算點數，J為下角標的值。L = 1時，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0;L = 2時，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0, 1;L = 3時，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0, 1, 2, 3;所以，W(N, p) = W(2^L, J)，其中J = 0, 1, ..., 2^(L-1)-1又因為2^L = 2^M*2^(L-M) = N*2^(L-M)，這裡N為2的整數次冪，即N=2^M，W(N, p) = W(2^L, J) = W(N*2^(L-M), J) = W(N, J*2^(M-L))所以，p = J*2^(M-L)，此處J = 0, 1, ..., 2^(L-1)-1，當J遍歷結束但計算點數不夠N時，J=J+2^L，後繼續遍歷，直到計算點數為N時不再迴圈。
FFT（快速傅立葉變換）是DFT的一種特殊情況，就是當運算點的個數是2的整數次冪的時候進行的運算（不夠用0補齊）。FFT計算原理及流程圖：原理：FFT的計算要求點數必須為2的整數次冪，如果點數不夠用0補齊。例如計算{2，3，5，8，4}的16點FFT，需要補11個0後進行計算。FFT計算運用蝶形運算，在蝶形運算中變化規律由W(N, p)推導，其中N為FFT計算點數，J為下角標的值。L = 1時，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0;L = 2時，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0, 1;L = 3時，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0, 1, 2, 3;所以，W(N, p) = W(2^L, J)，其中J = 0, 1, ..., 2^(L-1)-1又因為2^L = 2^M*2^(L-M) = N*2^(L-M)，這裡N為2的整數次冪，即N=2^M，W(N, p) = W(2^L, J) = W(N*2^(L-M), J) = W(N, J*2^(M-L))所以，p = J*2^(M-L)，此處J = 0, 1, ..., 2^(L-1)-1，當J遍歷結束但計算點數不夠N時，J=J+2^L，後繼續遍歷，直到計算點數為N時不再迴圈。