4-4 视频在线视频

大家好

这节课我们学习

频域抽取法基2-FFT算法

主要内容包括

频域抽取法基2-FFT定义

原理以及运算流图

我们首先看频域抽取法基2FFT定义

和时域抽取法基2FFT一样

序列的长度也是2的整次幂

把序列的离散傅里叶变换X(k)

按照k的奇偶分解成子序列

就是频域抽取法基2-FFT

也就是DIF-FFT

这种算法也称作Sander-Tukey算法

下面我们来看频域抽取法基2-FFT原理

x(n)的离散傅里叶变换

如公式(1)所示

在频域X(k)按照k的奇偶来分解

那么在时域上

x(n)不能够按n的奇偶来分解了

在时域上是按照n的顺序

分成前后两部分

也就是把x(n)分成前一半子序列

和后一半子序列

例如n等于8的时候

x(0)到x(3)是前一半子序列

x(4)到x(7)是后一半子序列

把前一半子序列和后一半子序列相加

形成一个序列x1(n)

前一半子序列和后一半子序列相减

乘以一个系数

形成一个序列x2(n)

分别对它们进行

N/2点的离散傅里叶变换

得到X1(r)和X2(r)

分别对应

X(k)在偶数点上的值和奇数点上的值

公式(2)和公式(3)也是蝶形运算

输入就是序列的前一半值和后一半值

输出是它们

分别去相加和相减乘以一个系数

我们来看一下

基2DIF-FFT运算流图的画法

还是以N等于8为例

首先把8点的序列分成两个4点的序列

也就是把N点的序列分成

两个N/2点的序列

在时域上x(0)到x(3)是序列的前一半值

x(4)到x(7)是后一半值

利用公式(2)和公式(3)

产生新的子序列x1(n)和x2(n)

然后分别去做N/2点的离散傅里叶变换

就可以得到

频域上X(k)偶数点的值和奇数点的值

那我们来看一下

频域抽取法基2-FFT算法的推导过程

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

我们把x(n)分成前后两个部分

n从0到N/2-1是前半部分

从N/2到N-1是后半部分

对于第二项n不是从0开始的

所以我们要做一个变量代换

令n等于n'+N/2

为了和前面这一项的变量统一

把n'再换成n

那么现在求和的范围

都是从0到N/2减1了

所以把这两项合到一起

对于这个系数

可以把它写成两项相乘的形式

然后把WN的nk次方

提到中括号的外面来

因为WN的N/2次方是等于-1的

所以这一项等于-1的k次方

这样X(k)就可以写成公式(4)这种形式

同学们注意

现在X(k)还没有按照

k的奇偶来进行分解

k的取值还是从0到N-1

下面我们把X(k)按照

k的奇偶来进行分解

当k是偶数的时候

令k等于2r

把k等于2r代到公式(4)中

-1的k次方是等于1的

得到这个公式

然后利用系数的可约性

得到下面这个公式

令中括号里面的这个序列是x1(n)

也就是序列x(n)的

前一半数据加上后一半数据

而这个求和公式

就是x1(n)的N/2点

离散傅里叶变换X1(r)

所以X1(r)是X(k)在偶数点上的值

同理当k是奇数的时候

令k等于2r+1

那么-1的k次方就等于-1

我们也可以得到序列x2(n)

以及x2(n)的离散傅里叶变换X2(r)

也就是x1(n)是序列的前一半数据

和后一半数据相加

序列x2(n)是前一半数据

和后一半数据相减再乘以一个系数

它们分别去做离散傅里叶变换

就可以得到X(k)的偶数点上的值

和奇数点上的值

那么由序列x(n)

构成x1(n)和x2(n)的这个过程

也是一个蝶形运算

例如x1(0)它是x(0)加上x(4)

x2(0)是这个蝶形的另外一个输出

就是x(0)减x(4)乘以W8的0次方

有了x1(n)和x2(n)

分别去做4点的离散傅里叶变换

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

也就是X(k)的偶数点上的值

和奇数点上的值

然后再将N/2点的序列

分解成N/4点的序列

也就是把4点的序列分成2点的序列

对x1(n)和x2(n)分别分成

前半部分序列和后半部分序列

然后相加或者是相减

再乘系数

形成4个新的子序列x3(l)到x6(l)

在这里l是0和1

例如x1(n)分成

前一半子序列和后一半子序列

经过一级蝶形可以得到x3(l)和x4(l)

分别对它们进行

两点的离散傅里叶变换

就可以得到X3(k)和X4(k)

而X3(k)是X1(k)的偶数点上的值

X4(k)是X1(k)的奇数点上的值

同理由x2(n)也可以得到X2(k)

前一半的值和后一半的值

两点的离散傅里叶变换

也是可以用一个蝶形来表示的

这样就可以得到

频域抽取法基2-FFT完整的运算流图

在这个运算流图中

输入是自然顺序

输出是倒序

也就是按照频域变量的奇偶

不断的进行分解得到的

因为8是2的3次方

所以它也是有三级蝶形运算

W8的0次方到W8的3次方

和DIT-FFT一样

也是旋转因子

那么在时域抽取法当中

输入是倒序

输出是自然顺序

先是小的蝶形

然后是大的蝶形

在频域抽取法当中

正好是反过来的

那么时域抽取法运算流图

和频域抽取法运算流图

它们是互为转置的关系

如果把这个流图的所有支路方向都反向

并且把输入输出进行交换

也就是这边如果是输入

这边是输出的话

就可以得到

时域抽取法基2-FFT运算流图

所以这两种流图是互为转置的

最后我们再举一个例子

利用频率抽取法基2-FFT

求x(n)的离散傅里叶变换X(k)

对于频域抽取法

它的输入是自然顺序

所以不用再进行变址运算了

首先把输入经过第一级蝶形运算

我们看第一级蝶形的输出

对于这个黑色的蝶形

这一点的输出应该是x(0)加上x(2)

下面这一点的输出

应该是x(0)减x(2)乘以W4^0

另外一个蝶形的输出

也是按照相同的方式得出

然后第一级蝶形的输出

作为第二级蝶形的输入

再进行计算

就可以得到X(k)的偶数点上的值

和奇数点上的值

而这个4呢 是x(0)加x(2)

6是x(1)加x(3)

所以X(k)在k等于0这一点的值

是序列的所有值之和

k等于2的时候这个值

就是4减6乘以1

所以它等于-2

由下面这个蝶形

可以求出k等于1和k等于3的时候这个值

它们两个是共轭的

但是这个值不能直接输出

因为它是倒序

所以还要进行一个变址运算

把它变成自然顺序输出

这些就是

频域抽取法基2-FFT的内容

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

再见