fft的原理与实现过程
c语言实现fft实验原理？
c语言实现fft实验原理？
FFT可以用来加速多项式乘法。假设有两个n−1次多项式A(x)和B(x)，我们的目标是——把它们乘起来。
普通的多项式乘法的复杂度是O(n2)的，我们要枚举A(x)中的每一项，分别与B(x)中的每一项相乘，来得到一个新的多项式C(x)。
但是，如果A(x)，B(x)两个多项式用点值表示的方法进行相乘，复杂度是O(n)的。具体方法：C(xi)=A(xi)×B(xi)，所以枚举xi即可。
要是我们把两个多项式转换成点值表示，再相乘，再把新的点值表示转换成多项式岂不就可以O(n)的复杂度来解决多项式乘法了！
显然，把多项式转换成点值表示的朴素算法是O ( n 2 ) O(n^2)O(n 2 )的。难道大整数乘法就只能是O ( n 2 ) O(n^2)O(n 2 )吗？不甘心的同学可以发现，大整数乘法复杂度的瓶颈可能在“多项式转换成点值表示”这一步做改进，只要完成这一步就可以O(n)的复杂度求答案了。傅里叶变换的发明就是为完成这个使命。
分步傅立叶算法原理？
快速傅氏变换（FFT）是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N 2（N/2）2=N N2/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50\%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1\%，点数越多，运算量的节约就越大，这就是FFT的优越性。