1、因此需要利用离散信号 x（nT）来计算信号 x（t）的频谱。有限长离散信号 x（n），n=0，1，N-1 的 DFT 定义为：可以看出，DFT 需要计算大约 N2 次乘法和 N2 次加法。当 N 较大时，这个计算量是很大的。利用 WN 的对称性和周期性，将 N 点 DFT 分解为两个 N2 点的DFT，这样两个 N2 点 DFT 总的计算量只是原来的一半，即（N2）2+（N2）2=N22，这样可以继续分解下去，将 N2 再分解为 N4 点DFT 等。对于N=2m点的 DFT 都可以分解为 2 点的 DFT，这样其计算量可以减少为（N2）log2N次乘法和 Nlog2N 次加法。图 1 为 FF
2、T 与 DFT-所需运算量与计算点数的关系曲线。由图可以明显看出 FFT 算法的优越性。将 x（n）分解为偶数与奇数的两个序列之和，即x1（n）和 x2（n）的长度都是 N2，x1（n）是偶数序列，x2（n）是奇数序列，则其中X1（k）和X2（k）分别为x1（n）和x2（n）的N2点DFT。由于X1（k）和X2（k）均以 N2 为周期，且 WNk+N/2=-WNk，所以 X（k）又可表示为：上式的运算可以用图 2 表示，根据其形状称之为蝶形运算。依此类推，经过m-1 次分解，最后将 N 点 DFT 分解为 N2 个两点 DFT。图 3 为 8 点 FFT 的分解流程。FFT 算法的原理是通过许
3、多小的更加容易进行的变换去实现大规模的变换，降低了运算要求，提高了与运算速度。FFT 不是 DFT 的近似运算，它们完全是等效的。关于 FFT 精度的说明：因为这个变换采用了浮点运算，因此需要足够的精度，以使在出现舍入误差时，结果中的每个组成部分的准确整数值仍是可辨认的。为了 FFT 的舍入误差，应该允许增加几倍 log2（log2N）位的二进制。以 256 为基数、长度为 N 字节的数可以产生大到（256）2N 阶的卷积分量，所以为了正确存储，需要 16+log2N 位精度，若数 i 是浮点尾数的二进制位数，则有条件：如果 i=24，对于任意感兴趣（N256）的 N 值，单精度是不合适的；如果 i=53，也就是采用双精度，则允许 N 大于 106，相当于几百万十进制位。所以，用 FFT作大数乘法时，向量数组选用双精度类型。
