快速傅里叶变换的原理及公式.pdfVIP

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