月亮雨小组的天地 YLY Studio

FFT(离散傅氏变换的快速算法)-1

FFT(Fast Fourier Transformation)是离散傅氏变换(DFT)的快速算法。即为快速傅氏变换。它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅立叶变换的算法进行改进获得的。


以上内容摘自百度百科,其实看了等于没看


首先先要知道一些预备知识:

1、多(door♂)项式


2、复数的运算(不是负数)


3、下面开始讲吧……


首先,多(door♂)项式是蛤?




也可表示为


这个就是多项式,一般是吧高次项写在前面,我这里这样写只是为了方便。


那么FFT是用来干蛤的?


这个问题问得好,FFT是用来算两个多项式相乘的。


那不可以暴力乘吗()?


那暴力可以做到  吗?


。。。。


---------------------------------------------------------------------------------先分个鸽-------------------------------------------------------------------------------------


首先先要有复数运算的知识


我们知道  (是个虚数)


那么对于形如,其中a,b为实数,i为虚数的东东我们称它为复数


a 为实部,bi为虚部。


加法运算: 实部+实部 虚部+虚部


减法运算:同上,‘+’ —> ‘-’


乘法运算:就和正常的多项式乘法差不多,只不过要注意 


除法运算:分数上下同时乘分母的共轭


即:


一个复数共轭就是一个实部相同,虚部为相反数的复数


如的共轭是


一个复数的共轭通常表示为


可得




因为所以分母必定为实数


 


对于  我们还可以这样子表示




其中a为实轴,b为虚轴, 就可以表示为在这样一个二维平面上的一个点


复数乘法在平面中就是辐角相加,模长相乘  (这个用三角函数可以证明,这里就不多说了)


真香


证明:对于可以表示为其中为辐角,为半径(即模长),然后相乘就直接r相乘指数相加就行了



作者:mysy2001 分类:通讯技术 浏览:449 评论:0
留言列表
发表评论
来宾的头像