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
版权声明：文章由 知识百答 整理收集，来源于互联网或者用户投稿，如有侵权，请联系我们，我们会立即处理。如转载请保留本文链接：https://www.zhshbaida.com/article/220978.html
