12.5 快速Fourier变换在线视频

好 下面我们来看快速傅里叶变换

我们刚才说了离散傅里叶变换

它的计算量是ON的平方

那么快速傅里叶变换呢

它的计算量是ONlog2N

那么我们可以比较一下

这两个计算量之间的比值

当n等于256的时候

快速傅里叶变换

是离散傅里叶变换的64倍计算

效率

那么当N等于512的时候

快速傅里叶变换

计算的速度

是离散傅里叶变换的114倍

随着N越来越大

它之间的差距越来越大

实际上快速傅里叶变换

它的计算量随着N趋于无穷

比上离散傅里叶的计算量N＾2

最后是趋于0的

我们来看一个例子

当N等于4的时候

我们得到了

这样一个傅里叶矩阵的逆

乘上a0 a1 a2 a3

那么我们先引入记号

p q 得到了p+αq

那么这个等于q乘上一个α

那么我们确切地

把上面这个式子展开

我们来看一下

这个式子展开呢

实际上是4a0等于A0+A2

A1+A3

可以看到这个规律

A0+A2 A0+A2

这都是A0+A2 A0-A2

就这两种可能

这边呢A1+A3 A1-A3

A1+A3 A1-A3

然后这一块的规律也是明显的

这是+ 这块是-

这块- 这块就是+

所以我们把A0 A1 A2 A3

重新排一个序

就是A0A2放一组

A1A3放一组

这样我们就可以得到

中间这样四个量

然后这四个量再重新组合

但是组合的方式还是加或减

当A0A2和A1A3

这两个作为一组

进行加减的时候呢

我们看A0+A2 A1+A3

当这个A1+A3乘以1

我们就得到4倍的A0

那当然这个减的时候对应减1

这就得到了4倍的A2

同样地呢

A0-A2和A1-A3

我们看它有一个-i +i的过程

那么这里面呢

这样一个形式呢+α

和-α得到这个

我们把它叫做一个

butterfly operation这个

那么一般的呢

快速傅里叶变换呢

实际上是

把我们的离散傅里叶变换的算法

分成log2N段

就是一般这个大N取的时候

都取成2的一个若干次方

这样的分成log2N段以后呢

每一段有N/2个butterfly operation

比如说N等于8

那么8是2的三次方

那么第一步我们先把

A0 A1 到A7重新排个序

那么排序呢

我们是先把偶和奇分开

然后把偶中的4个倍数

和4除的有一个余数

那么用二进制的语言说

更方便一些

比如说0 1到7

它们的二进制

j的二进制数的反转为nj

那么比如说j小于nj的时候

那么我们就交换Aj和Anj

那么这里面的反转什么意思呢

就是比如说1

它的二进制数表示是001

那么反转一下就变成100

那么这个对应的数是4

1小于4呢

那么我们就交换A1和A4

那么按这种原则

我们把A0到A7重新排序呢

就排成这种形式

这种形式的排序呢

也可以分几步走

比如说首先把A0到A7

我们把奇偶分开

就是A0到A2 A4 A6

然后A1 A3 A5 A7

然后这一个呢

我们又重新排序

这个算1 2 3 4

那么A0它是第0个

就是0 1 2 3

那么我们可以看到

从这儿我们可以把

A0和A4提出来

然后A2 A6又放在后面

这就得到了前面这一部分

就是始终按照奇偶排序

不断地抽出来

第一步按奇偶排序

抽出了0 2 4 6

第二步0 2 4 6又按奇偶排序

第一个是0

第二个A2是在1位置

A4在2位置 A6在3位置

所有又把0和2抽出来

把1 3的位置再放下来

那么这一块也是一样的道理

A1 A3 A5 A7

最后我们可以排成这种形式

刚才我说这个原则呢

那么用上面这个反转

也是一样的道理

好 按照这种排序以后呢

我们就分成了四队

A0 A4 A2 A6 A1 A5

和A3 A7

那么对于这样的对呢我们可以作

刚才说的butterfly operation

那么基于这样奇偶分离的原因呢

为什么这样一分离以后呢

我们就可以减少计算量呢

我们可以看到

我们回到我们原来这个表达式

那么在这个表达式中

我们展开看一下

每一个A0呢到AN-1 小的这个ai

当它把它写成一个大的

ai实际上是这个的第i行

就是这个F逆的第i行

乘上A0到AN-1

但是我们注意它的第i行

实际上是一些幂次

所以最后我们可以写成一个

奇偶两个多项式的和

这种形式

比如说Aj就是使用它的第j行

大家可以看到它的第j行是

ω共轭的0次方

ω共轭的j次方

ω共轭的2j次方

再乘上这个

那么这个呢

我们可以给它分离出偶次项

和奇次项

那么这时候在计算的时候呢

我们就可以不用重复计算了

就是偶次项和奇次项

可以整体对待

那么另一个我们要观察的是Aj

就是这个分量中的第j项

和A的2n+j

它们之间有一个好的关系

当Aj是等于这样一个形式的时候

那我们可以看到A的2分之n加j

我们通过这样一些类比

我们最后可以看到

它等于这样一个形式

我们看到Aj如果是等于偶次项

多项式加上一个

ωNj倍的奇次多项式

那么A的2分之N加j

恰好是跟它

这个地方改成减号

所以呢当你算Aj的时候

这块用的乘法

到A的2分之N加j的时候

这个乘法就不需要再算一遍了

这就减少了一半的工作量

就是每进行一次这种二进制划分

就可以减少一半的工作量

那么因为N不断地2抛分下去

正好有这么长的这么多次

那么在这每一次中

我们都可以减少一半的工作量

最后在每一次中

我们实际上的计算量是2分之N

好 那么我们利用bj等于Pe

这个N/2

这个ω共轭的1/2j

这个是偶次项的

这个是奇次项的

那么我们现在就可以确切地写出

aj等于bj加上这个

N/2+j就等于

这个正好是减的形式

这个就是一个这样一个

butterfly operation这个形式

那么我们就可以通过bj bj′

通过这样一个傅里叶运算方式

得到了aj和a的N/2加j

那么要想计算这两个呢

那么我们又可以重复刚才的过程

把bj和bj′又可以看作

一个新的cj和cj′的进行

butterfly operation

我们可以看到

bj它本身是偶次项的

那么我们把这个偶次项

这个多项式又再分成偶次项

比如说x的2次方

x的4次方 x的6次方

这个a1+a2

这个比如说是a0加上这个

有这样一个多项式

这是偶次多项式

我们可以把偶次多项式

本身再分成两部分

一部分是可以看作a0+a2x4

这是一部分

就是说我们现在重新定义标准呢

你如果令x＾2等于y的话

那么这个变成

a0+a1y+ay＾2+a3y＾3

那么对这个我们再挑出奇偶项

那么所以我就写成a0+a2x＾4

也就是说

a0+a2y＾2

那么这两个又是这样

所以这个多项式本身

又可以写成一个

Pe的再偶次项多项式

再加上P8的再奇次多项式

所以这又可以进行

新的一个butterfly的这个算法

用cj和cj′

那cj′我们又可以重复

再把这个多相Pee或者Peo

再给它拆分成新的奇偶的

那么确切的

对于我们刚才这个n等于8的时候

是这样做的

开始这样

然后我们重新排序

0 4 2 6

1 5 3 7

那么用这种办法

我们可以算出这个aee aeo

这个e就是偶

这个o就表示的是奇

这样通过butterfly的算法

算出这个

然后这个我们再结合

算出了ae和ao

注意这个aee和a

都是从新从这两个组合出来的

最后我们就算出了

a等于a0 a1 一直到a7