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时不再循环。
标签:DFT,FFT