今天就跟大家聊聊有关快速傅里叶变换FFT的原理及公式是什么，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。
快速傅里叶变换FFT)的原理及公式
原理及公式
非周期性连续时间信号xt)的傅里叶变换可以表示为
式中计算出来的是信号xt)的连续频谱。但是，在实际的控制系统中能够得到的是连续信号xt)的离散采样值xnT)。因此需要利用离散信号xnT)来计算信号xt)的频谱。
有限长离散信号xn)，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算法的优越性。
将xn)分解为偶数与奇数的两个序列之和，即
x1n)和x2n)的长度都是N／2，x1n)是偶数序列，x2n)是奇数序列，则
其中X1k)和X2k)分别为x1n)和x2n)的N／2点DFT。由于X1k)和X2k)均以N／2为周期，且WN k+N/2=-WN k，所以Xk)又可表示为：
上式的运算可以用图2表示，根据其形状称之为蝶形运算。依此类推，经过m-1次分解，最后将N点DFT分解为N／2个两点DFT。图3为8点FFT的分解流程。
FFT算法的原理是通过许多小的更加容易进行的变换去实现大规模的变换，降低了运算要求，提高了与运算速度。FFT不是DFT的近似运算，它们完全是等效的。
关于FFT精度的说明：
因为这个变换采用了浮点运算，因此需要足够的精度，以使在出现舍入误差时，结果中的每个组成部分的准确整数值仍是可辨认的。为了FFT的舍入误差，应该允许增加几倍log2log2N)位的二进制。以256为基数、长度为N字节的数可以产生大到256)2N阶的卷积分量，所以为了正确存储，需要16+log2N位精度，若数i是浮点尾数的二进制位数，则有条件：
如果i=24，对于任意感兴趣（N>256）的N值，单精度是不合适的；如果i=53，也就是采用双精度，则允许N大于106，相当于几百万十进制位。所以，用FFT作大数乘法时，向量数组选用双精度类型。