快速傅里叶变换(Fast Fourier Transform,FFT)是一种可在时间内完成的离散傅里叶变换(Discrete Fourier transform,DFT)算法。
复数单位根
横轴为实轴,纵轴为虚轴的复平面上,
(将复平面单位圆均分成n份,以单位圆与实轴正半轴的交点一个等分点,以原点为起点,n个等分点为终点,做n个单位向量,其中幅角为正且最小的向量被称为n次单位向量,记为)
易知
所以,
(复平面中复数加法满足平行四边形法则,乘法满足幅角相加,模长相乘)根据这性质易几何证明以下两性质
复数单位根性质:
1、折半引理:
2、消去引理:
离散傅里叶变换的复杂度为
快速傅里叶变换的复杂度为
点FFT阶段数为而每一阶段的复杂度为,故复杂度为
以8点FFT为例,绿色的列表示一个阶段,每个空心圈表示一次乘加,一列共N个先看离散傅里叶变换(DFT)表达式 (时域,频域):
, k=0,1,...N-1
通过上述DFT的表达式,其可以用复数单位根表示成:
,
在这边我们要注意的是,我们所替换的G[k]与H[k]具有周期性:
此性质根据单位根的几何意义得证上述的推导可以划成下面的图,以8点DFT为例(N=8,左边一列为时域,右边一列为频域):
划红框处所示的点DFT架构如下图所示:
划红框处所示的点DFT架构如下图所示:
综上,下图是一个8点DIT FFT的完整架构图:
图中应用性质,例如左边的库利和图基的FFT算法的最基本运算为蝶形运算,每个蝶形运算包括两个输入点,因而也称为基-2算法。
FFT还能用来加速多项式乘法。朴素计算两个N-1次(N项)多项式复杂度为
多项式系数表达法 多项式的点值表达法设
点值表达法的多项式乘积十分方便,复杂度为这里有个点就是点值表示法的乘积,按理说两个n次的多项式乘积的最高次为2n,而点值表示法就像是解方程,2n次方程式需要2n个点值点才能唯一确定,所以我理解的是需要两次上图的点值表示法乘积才能确定结果。
而是用DFT和IDFT可以分别转换 系数表达法 到 点值表达法 和 点值表达法 到 系数表达法,FFT可以加速这两个转换过程。
大概过程是,先将两个系数表示法的多项式分别转化为点值表达式,再进行点值表达法的多项式乘积运算,再将结果转换回系数表达法。
需要注意的是,在求两个次数分别为和的多项式的乘积时,需要分别求出在至少个点处的值,这样才能保证相乘后唯一确定一个次多项式。
假设,A(x)、B(x)的点值表达式均有N个点,而他们的乘积C(x)因为次数为所以需要2N个点值点,那么怎么出现2N个点呢,多选一些点即可。所以在计算N次多项式的点值表达法时要取2N个点值点,我的理解是这2N个点在复平面上直接取,分成两组N个点(保证了两组中每个点均不同),对于一个系数表达式进行两次N点FFT,最终一个N次系数表达式得到2N个点值点。这一步通过4次FFT完成了两个待乘系数表达式到点值表达式的转换。然后进行后续计算。
至于为什么将2N个点要分成两组N计算,是因为系数表达式有N个点,所以通过FFT一次只能计算N个点值点,需要算两次完成一个表达式的转换,因为需要算的是两个N-1阶表达式的乘积,需要转换两个式子,所以这一步共需4次FFT。而后面的点值表示法再转回稀疏表示法可以直接一次2N点FFT搞定。个人理解,有待考证
关于FFT加速多项式乘法具体见下文:
网友评论