4-5视频在线视频

大家好

这节课我们分析

基2-FFT算法运算量以及运算规律

主要内容包括

基2FFT算法运算量

基2FFT算法运算规律

DIT-FFT算法与DIF-FFT算法比较

以及IDFT的高效算法

在分析基2FFT算法运算量之前

我们先来回顾一下

基2DIT-FFT算法运算流图

当N等于8的时候

基2FFT需要三级蝶形运算

每级需要四个碟形

也就是N/2个碟形

所以当N等于2的M次方的时候

一共有M级蝶形

M等于以2为底N的对数

每级有N/2个蝶形运算

下面我们来看

基2FFT算法的运算量

也就是它所需要的复数乘法次数

和复数加法次数

对于一个蝶形来讲

它需要一次复数乘法

和两次复数加法

那么每级有N/2个蝶形运算

所以一级蝶形需要

N/2次复数乘法和N次复数加法

而M级蝶形需要

M乘以N/2次复数乘法

和MN次复数加法

这就是基2FFT所需要的运算量

如果直接计算离散傅里叶变换

需要的复数乘法次数是N的平方次

需要的复数加法次数是N乘以N-1次

所以直接计算离散傅里叶变换

所需要的复数乘法和基2-FFT

所需要的复数乘法运算的比值

是2N除以以2为底的N的对数

例如N等于1024

这二者之比就是204.8

也就是说 直接计算的运算量

比基2FFT的运算量要大很多

下面我们来看

基2FFT算法的运算规律

第一个是原位运算

当数据输入到存储器以后

每个蝶形运算的结果

仍然存放在这一组存储器里面

这就叫做原位运算

也就是说 蝶形运算的输出

还放到原来存放蝶形运算

输入的存储器中

所以原位运算的结构

可以节省存储单元

降低设备成本

我们来举例说明一下

对于这个蝶形运算

x(0) x(4)是输入

把它们分别存放在

A(0)和A(1)存储器里面

系数存放在暂存器中

经过蝶形运算得到输出X3(0)和X3(1)

还存放到A(0)和A(1)中

这个就是原位运算

由于每个蝶形

它的输入只对该蝶形起作用

比如说x(0)和x(4)

它就只对这个蝶形起作用

和别的蝶形没有关系

并且每个蝶形的输入和输出节点位置

是在同一个水平线上

不会影响到其它的蝶形

所以在这个蝶形计算之后

输入就没有用了

因此这一级蝶形运算的输出

还是放在A(0)到A(7)这些存储器里面

覆盖了原来的输入

这样是没有问题的

同样第二级的输出

还是存到A(0)到A(7)这些存储器里面

直到最终的输出

这个就是原位运算

那么对于N点的FFT

它只需要N个存储单元就可以了

对于DIT-FFT

A(0)到A(7)顺序存放了

X(0)到X(7)可以直接输出

第二个是旋转因子的变化规律

在每级蝶形里面都需要乘以系数

这个系数叫做旋转因子

当N等于2的M次方的时候

第L级的旋转因子如公式(1)所示

其中J是从0到2的L-1次方减1

p等于J乘以2的M-L次方

例如N等于8

M等于3 就是有三级蝶形

L等于2 就是第二级

那么第二级需要有两个旋转因子

J等于0的时候

p是等于0的

旋转因子是W8的0次方

等于W4的0次方

J等于1的时候

p等于2

旋转因子是W8的2次方

还等于W4的1次方

那么从这个运算流图里面我们看

最后一级是4个大碟形

需要4个旋转因子

在第二级这两个碟形

需要两个旋转因子

上下两部分是一样的

那我们看后一级中

指数是偶数的旋转因子

就是前一级的旋转因子

W8的0次方等于W4的0次方

W8的2次方等于W4的1次方

所以前一级的旋转因子

是后一级旋转因子中

指数是偶数的那些旋转因子

这是旋转因子的规律

第三个就是倒序

就是码位倒读规则

在DIT-FFT中

输入是按照倒序来进行排列的

输出是按照自然顺序排列的

在DIF-FFT中输入是自然顺序

输出是倒序

那么自然顺序和倒序

它的关系是什么呢

我们从这个表中来看一下

n是自然顺序 从0到7

把它用二进制数来进行表示

就是000 001 一直到111

然后进行码位倒读

就是二进制数从后往前读

所以码位倒读

就是000 100 010 110

再写出它相对应的十进制数

就是它的倒序0 4 2 6 1 5 3 7

如果N等于16

那么自然顺序就是0到15

然后用四位二进制数来表示

再进行码位倒读

就可以得到它的倒序

把输入数据从自然顺序变成倒序

就需要进行数据的交换

输入x(n)存放到存储器A(0)到A(7)中

要把它变成倒序

A(1)和A(4)要进行数据交换

A(3)和A(6)要进行数据交换

那么其它几个存储器

不需要进行数据交换

这个过程就是变址的过程

当n等于倒序的时候

数据不需要交换

当n小于倒序的时候

1小于4

这时候要进行数据的交换

当n大于倒序的时候

表示已经调换过了

所以对于DIT-FFT来讲

在输入的时候要有这个变址运算

而对于DIF-FFT

在输出的时候要进行变址运算

下面我们对DIT-FFT算法

和DIF-FFT算法进行比较

首先看相同之处

两种算法的运算量相同

也就是说

它所需要的复数乘法和复数加法

次数是相同的

第二个相同之处就是

基本的DIT-FFT与DIF-FFT两种算法

都是原位运算

有一些变体运算就不是原位运算了

我们再来看不同之处

一个就是基本的

DIT-FFT与DIF-FFT两种算法结构不同

DIT-FFT输入是倒序

输出是自然顺序

DIF-FFT输入是自然顺序

输出是倒序

同样这个基本的

DIT-FFT和DIF-FFT就是我们

前面介绍的这两种算法

那么在变体结构当中

比如说DIT-FFT它也可以是

输入是自然顺序

输出是倒序的

所以我们在这里说的是

基本的这个算法结构是不一样的

那么DIT和DIF根本的区别就在于

它的蝶形结不一样

蝶形运算不一样

DIT-FFT它是先乘后加减

而DIF-FFT它是先加减后乘

这个就是相同和不同之处

最后我们再来看一下IDFT的高效算法

第一种方法

我们对离散傅里叶变换的

正反变换式进行比较

可以看出

在正变换式中是WN的nk次方

在反变换中是WN的-nk次方

并且最后再乘以一个1/N

所以在原来的FFT算法当中

可以把旋转因子从

WN的p次方变成WN的-p次方

最后输出结果

再乘以1/N就可以得到IFFT

这是第一种方法

在这种方法里面

需要对FFT的程序进行修改

如果我们不想修改FFT算法

而想直接用它的话

可以用下面的这种方法

对IDFT的公式

两边同时取共轭

然后再取一次共轭

这样等式左边还是x(n)

等式右边 我们看中括号里面

它实际上就是X(k)的共轭的

离散傅里叶变换式

所以这个式子又可以写成

X(k)的共轭 进行FFT

再取共轭 乘以1/N

就可以得到X(k)的反变换x(n)了

在这种方法里面

可以直接用FFT的程序

这节课我们学习了

基2FFT算法的运算量

对DIT-FFT和DIF-FFT进行了比较

并且介绍了IDFT的高效算法

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

再见