4-6 视频在线视频

大家好

这节课我们学习

进一步减少运算量的措施

主要内容包括

多类蝶形单元运算

旋转因子的生成

以及实序列的FFT算法

我们首先看一下

基2DIT-FFT算法运算流图

在FFT运算中

每个蝶形都有一个旋转因子

有一些旋转因子的值比较特殊

不需要进行乘法运算

例如W8的0次方等于1

也就是WN的0次方等于1

任何数和1相乘都等于它本身

所以不需要乘法

再有W8的2次方等于-j

也就是WN的N/4次方等于-j

一个复数a+jb和-j相乘等于b-aj

所以也不需要乘法运算

这样的旋转因子叫做

无关紧要的旋转因子

那么去除无关紧要的旋转因子

就可以减少运算量

在DIT-FFT当中

第一级和第二级当中的

所有的旋转因子

都是无关紧要的旋转因子

不需要乘法运算

在第三级以后

也包含了这两个旋转因子

在第一 二级中

每级都有N/2个蝶形

所以原来是需要N/2次复数乘法

基2FFT

它所需要的复数乘法次数是MN/2

那么从这里面去除掉

第一 二级的复数乘法次数

剩下的复数乘法次数就由公式(1)所描述

对于DIF-FFT

它和DIT-FFT是相反的

所以最后两级中的旋转因子

都是无关紧要的旋转因子

在DIT-FFT中

当L大于等于3的时候

也就是第三级以后

每级都有两个无关紧要的旋转因子

而每级当中每一个旋转因子都对应着

N除以2的L次方个蝶形运算

那么第L级它减少的复数乘法次数

就是2N除以2的L次方

这样从第三级到第M级

减少的复数乘法次数

就是2N除以2的L次方求和

利用等比级数求和

我们可以算出

从第三级到第M级

减少的复数乘法次数是N/2-2

把刚才(1)式中的

复数乘法次数 再减去

从第三级到第M级的复数乘法次数

就是去除了无关紧要的旋转因子

以后所剩的这个乘法次数

另外

还可以利用特殊的复数运算

来减少运算量

实现一次复数乘法

需要四次实数乘法和两次实数加法

但是有些特殊的复数

和其它复数相乘的时候

所需要的实数运算会少一些

比如WN的N/8次方

这个数和其它的复数相乘

只需要两次实数乘法和两次实数加法

在进行程序实现的时候

如果包含了所有的旋转因子

就叫做一类蝶形单元运算

去除掉等于正负1的旋转因子

就是二类蝶形单元运算

去除掉等于正负j的旋转因子

就是三类蝶形单元运算

再处理特殊的这个旋转因子

那么就是四类蝶形单元运算

很明显

蝶形单元类型越多

所需要的运算量就会越少

但是编程肯定是越来越复杂了

第二个就是旋转因子的生成

一种方法是在进行每级的运算的时候

直接产生旋转因子

所以计算速度慢

另外一种方法就是预先计算出旋转因子

形成旋转因子表

在进行FFT的时候进行查表

这种方法计算速度快

但是因为要事先形成一个旋转因子表

所以占用内存多

在实际当中

一般都是实序列

如果直接对它进行FFT

可以把实序列看成是

虚部为零的复序列

但是这样的话就会浪费运算量

浪费计算时间

那么有两种情况

一种情况就是有两个实序列

需要进行离散傅里叶变换

我们只想用一次N点的FFT来完成

这种情况我们在第三个模块里面

已经学习过了解决办法了

因为这两个序列都是实序列

所以可以把它们两个合成一个复序列

其中一个实序列作为实部

另外一个实序列作为虚部

形成一个新的序列

也是N点的序列x(n)

对x(n)进行N点的离散傅里叶变换

得到X(k)

那么X(k)

可以分解成有限长共轭对称分量

和有限长共轭反对称分量

根据离散傅里叶变换的共轭对称性

序列x1(n)

它的离散傅里叶变换

应该是

序列离散傅里叶变换的

有限长共轭对称部分Xep(k)

序列的虚部乘以j

也就是jx2(n)

它的离散傅里叶变换是jX2(k)

应该是X(k)的有限长共轭反对称部分

也就是Xop(k)

等式两边同时除以j

就可以得到X2(k)

等于1/j乘以Xop(k)

这样我们就用一次N点的FFT

计算了两个N点实序列的

离散傅里叶变换X1(k)和X2(k)

由X(k)计算X1(k)和X2(k)的公式

如公式(3)和公式(4)所示

另外一种情况是只有一个实序列

假设这个实序列是2N点

现在我们需要用一次N点的FFT

来进行计算它的离散傅里叶变换

如果计算N点的FFT

那么序列的长度应该是N

而现在的序列是2N点

所以我们可以借鉴DIT-FFT算法

将一个2N点的实序列

分解成两个N点的实序列

也就是y(n)的偶数点组成一个序列

y(n)的奇数点组成一个序列

x1(r)和x2(r)都是N点的序列

对它们进行离散傅里叶变换

可以得到X1(k)和X2(k)

然后再经过一级蝶形运算

就可以得到Y(k)的前一半的值

和后一半值

现在是有两个N点的实序列

我们需要用一次N点FFT来进行计算

就是前面的第一种情况

用一次N点FFT

来计算两个N点的实序列的

离散傅里叶变换

下面我们来看一下具体的步骤

首先对y(n)进行分解

形成两个实序列

然后把这两个实序列

组合成一个复序列

再进行N点的离散傅里叶变换

得到X(k)

根据前面一种情况

我们已经推导出来的结果

就是x1(r)的离散傅里叶变换

X1(k)是Xep(k)

x2(r)的离散傅里叶变换X2(k)

是等于(1/j)Xop(k)

就是公式(3)和公式(4)

有了X1(k)和X2(k)

再用蝶形运算公式就可以求出

Y(k)的前一半值和后一半值

也就是公式(5)

这样我们就得到了一个

2N点的离散傅里叶变换Y(k)

那么Y(k)的后一半数据

还有一种方法可以进行计算

就是先利用蝶形运算求出Y(k)的

前一半数据

因为2N点的序列y(n)是实序列

所以它的离散傅里叶变换

应该是共轭对称的

所以可以利用这个性质

求出Y(k)的后一半的数据

这些就是减少运算量的措施

第四模块的内容到这节课我们就完成了

下面我们来总结一下

在这个模块中

首先分析了

采用快速傅里叶变换的原因

是因为

离散傅里叶变换的运算量太大了

不利于信号与系统的实时处理

因此需要减少运算量

那么减少运算量的途径

是利用系数的固有特性

以及将长序列分解成短序列来进行计算

然后我们学习了时域抽取法

和频域抽取法

基2FFT算法原理以及运算流图

在DIT-FFT中

是按照时域变量的奇偶

不断的对时域序列进行分解

直至两点

形成蝶形运算

在DIF-FFT中

是按照频域变量的奇偶进行分解

也是形成了蝶形运算

在此基础上

我们分析了基2FFT算法的运算量

以及运算规律

对两种算法进行了比较

学习了IDFT的高效算法

以及进一步减小运算量的措施

FFT是DFT的快速算法

在实际应用当中

当需要用到DFT的时候

例如对信号的谱分析

计算LTI系统的输出

进行FIR滤波器的设计

都可以采用FFT来进行实现

这节课的内容我们就学习到这里

再见