4.1 直接计算DFT的运算量及减少运算量的途径在线视频

同学们好

今天我们一起来学习第4章

快速傅里叶变换

快速傅里叶变换它不是一种新的变换

它是离散傅里叶变换的快速算法

这种快速算法

有数量级意义上的速度提升

首先我们来看一看

直接计算DFT存在的问题

和它的改进途径

我们来看一个有限长序列x(n)

它的点数为N

我们直接计算DFT的时候它的公式如下

其中计算出来的傅里叶变换X(k)

也是一个N点的有限长序列

我们求离散傅里叶逆变换的公式

也就是由X(k)来求x(n)的公式如下

我们在直接计算DFT的时候

先来考虑

只计算一个X(k)

在这个公式 ∑求和

n从0开始到N-1

然后x(n)乘以WNnk这个公式

我们把x(n)认为是一个复数序列

WNnk也认为复数序列

我们不考虑其中的

x(n)和WNnk

为实数和虚数的这种特殊情况

一律看成是复数的情况

那么序列 x(n)和WNnk

相乘的次数就为N次

也就是复数乘法的次数是N次

x(n)乘以WNnk

一共有从0~N-1是N个

那么复数加法的次数就是N-1次

我们再来看

我们要想计算一个完整的

N点的DFT

那么就需要计算N个X(k)的值

所以

计算N点的DFT

一共需要的复数乘法次数就应该是N的平方

而复数加法的次数就应该是

N乘以N-1次

我们现在把复数乘法和复数加法

再考虑到实数乘法和实数加法的次数上

对

复数乘法和复数加法进行分解

对一次复乘(a+jb)

乘以(c+jd)

它就等于(ac-bd)

然后再加上j(ad+cb)

在计算过程中

所需要的实数乘法是4次

实数加法是2次

我们再来看一个复数加法

a+jb

加上一个c+dj

它其实就等于a+c再加上一个j(b+d)

这个过程中

实数乘法的次数为零

而实数加法的次数为2

所以我们计算一个X(k)

所需要的实数乘法次数为4N次

实数加法的次数为2N

再加上一个2(N-1)

而计算N个X(k)

所需要的实数乘法的次数就为

4N的平方

实数加法的次数就为

2N(2N-1)

通过运算量的计算

可以让我们看得出来

直接计算DFT它所需要的运算量

和我们序列的点数N是密切相关的

点数N确定之后

运算量是N的平方级

所以点数越多

运算量就越大

这也就是我们直接

计算DFT存在的一个问题

接下来我们来

研究旋转因子WNnk的特性

继而利用它的特性

来减少我们的运算量

旋转因子WNnk

它写成之后就是一个复指数

e的-j2π/N乘以nk次方

它的第1个特性就是对称性

WNnk它的共轭函数

是等于WN-nk

也等于WN(N-n)k

这一条的推理

我们可以把

旋转因子上标的两项给它拆分

拆成WNnk乘以WN-nk

其中

WNNk这一项

它是等于1的

所以可以得到这一项和它前一项相等的结论

同时它还等于WN

n(N-k)

这一项的计算方法和前面也是一样的

我们把旋转因子上标的两项进行拆分

拆成WNnN乘以WN-nk

WNnN这一项

它就等于1

所以由对称性可得

这几项都是相等的

接下来我们来

研究旋转因子周期性

WNnk

等于WN

(N+n)k

又等于

WNn

(N+k)

这个周期性的计算

和它的讨论和上面对称性一样

把旋转因子上标了两项进行拆分之后

其中的有一项是等于1的

就剩WNnk的一项

周期性对我们减少计算量

也会有很大的帮助

接下来看第3条

叫可约性

旋转因子WNnk

又等于WmNmnk

这个可约性的推断

主要可以依据

我们前面写的旋转因子的另外一种形式

把它展开成指数形式

在指数形式里边

上标和下标应该分别是在

分子和分母的位置

m和m消掉之后

得到的结果就依然是

WNnk

同样的道理

我们可以在上标和下标上

同时除以一个m

这两个m

在展开的过程中

在复指数这种形式里

依然是在分子分母中

同时除以m

结果依然是相等

旋转因子还存在几个特殊点

是我们经常需要用到的

一个就是WN0

代入复指数函数

我们就知道它的结果应该是等于1

第2个是WNN/2

代入复指数函数结果求出来等于-1

WN(k+N/2)

它求出来的结果

应该是等于-WNk

这三个特殊点

在后续的计算过程中

有时会用到

快速傅里叶变换算法的基本思想

就是要利用离散傅里叶变换系数的特性

合并离散傅里叶变换中的某些项

把长序列的DFT

变成短序列的DFT

改变求DFT系列的点数

从而减少其运算量

快速傅里叶变换算法的分类

主要分为两类

一种叫做按时间抽选法

还有一种叫按频率抽选法

同学们今天这节课我们就讲到这

谢谢大家