4.2 按时间抽选的基-2FFT算法的算法原理在线视频

同学们好

今天我们来学习

按时间抽选的基2FFT算法

首先我们来看这种的算法原理

我们假设序列的点数N

是等于2的L次方

其中L为整数

如果序列的点数不满足这个条件

我们就对它进行补零

N为2的整数次幂的FFT的算法

就称为基2的FFT算法

我们将序列x(n)

按照n的奇偶把它分成两组

其中偶数组为x(2r)

这个序列我们把它称为x1(r)

奇数序列

x(2r+1)我们把它称为序列x2(r)

这两个序列r的范围

均为从0开始到N/2减1

我们在求序列x(n)的DFT的时候

X(k)是等于

∑求和

n从0开始到N-1

x(n)乘以WNnk

这个N项求和的式子

我们把它斩成两部分

其中一部分为n为偶数的

另一部分为n为奇数的情况

其中n为偶数的部分就是序列x(2r)

而n为奇数的部分就是x(2r+1)

而x(2r)这一部分我们刚才说过

又把它写成序列x1(r)

x(2r+1)

这个奇数序列

我们又把它写成x2(r)

写成这种形式之后

我们把旋转因子的上标上的指数

利用旋转因子的可约性

把它约成

两个式子

∑求和

r从0开始到N/2-1

x1(r)乘以WN/2

rk

加上一个WNk

乘以∑求和

r从0开始到N/2-1

x2(r)乘以WN/2rk

我们可以看得出来

在这个式子里面

有两个N/2点的DFT公式

其中一个是序列x1(r)

求N/2点DFT

另一个是x2(r)

求N/2点DFT

我们把序列x1(r)求

N/2点的DFT的结果

写成X1(k)

把序列x2(r)

求N/2点DFT的结果

写成X2(k)

就得到结果

X(k)是等于

X1(k)加上一个WNk乘以X2(k)

其中

r和k的范围

都应该是从0开始到N/2-1

我们都知道

序列x(n)原本的点数是N点

那么计算N点的DFT之后

所得到的X(k)

也应该是一个N点的序列

我们把它按照时间域

进行奇偶分解之后

得出来的X(k)

K的范围只有

从0~N/2-1这一部分

也就是

X(k)的前半部分

在计算X(k)的后半部分的时候

我们主要要利用到周期性

首先是

X1(k)和X2(k)

本身都是以N/2为周期的

所以X1(k+N/2)就等于X1(k)

X2(k+N/2)就等于X2(k)

然后我们来看旋转因子

旋转因子WN(K+N/2)

把上面的指数进行拆分

拆成两项之后

其中WNN/2这一项

它应该等于-1

所以

最后WN(k+N/2）就应该等于

-WNk

现在我们就可以把

求出来的X(k)

写成前半部分和后半部分的表达式

前半部分X(k)

是等于X1(k)

加WNk乘X2(k)

后半部分

X(k+N/2)

就等于X1(k)减WNk乘以X2(k)

k的范围

是从0开始到N/2-1

我们把求出来的前半部分

和后半部分的表达式

用一个蝶形图来把它描述出来

这个图形就是按时间抽选的

蝶形运算流图

输入信号分别为X1(k)和X2(k)

在X2(k)这条支路上

我们要乘上一个旋转因子WNk

由箭头我们可以看得出来

上面这条支路的输出

就为X1(k)加上X2(k)乘以WNk

而下面这个支路它的结果

就是它等于X1(k)减去X2(k)乘以WNk

根据我们刚才的第1次分解

我们现在以N等于8点的序列为例

来看

原序列应该是从x(0)开始

一直到x(7)这样的一个8点的序列

按照n的奇偶把它分成两组序列

得到偶数组的序列分别是

x(0) x(2) x(4) x(6)

这4点序列组成一个新的序列

叫x1(r)

也就是x1(0) x1(1) x1(2) x1(3)

n为奇数组成的一个序列

x(1) x(3) x5) x(7)

组成了一个新的序列为x2(r)

这一个8点的序列

被分成偶数一组

和奇数一组

两个序列

分别来求4点的DFT计算

计算完之后

x1(r)求出来的一个4点的DFT为X1(k)

序列x2(r)

求出来的4点DFT的结果为X2(k)

其中X1(k)和X2(k)

再进行组合

就可以得到我们最终的X(k)的8个取值

X1(k)+WNk(X2(k))得到

最终频谱的前半部分

X1(k)

-WNk(X2(k))

得到输出频谱的后半部分

经过刚才的一次分解之后

我们把一个N点的序列分成了

两个N/2点的序列

因为点数N是等于2的L次方

所以N/2依然为一个偶数

我们可以进一步分解

把一个N/2点的序列

分成两个N/4点的序列

分解的思路

和前一步的分解思路完全一样

我们把序列x1(r)

按照r的奇偶把它分成两组

一组为x1(2l)

令其为x3(l)

一组为x1(2l+1)

令其为x4(l)

分别来计算这两个系列的N/4点DFT

其结果为

X3(k)和X4(k)

它们再进行组合

得到的结果就是

X1(k)

等于X3(k)+WN/2k(X4(k))

而它的后半部分

X1(k+N/4)

就应该等于X3(k)

-WN/2k

乘以X4(k)

我们把再进一步分解的过程

也可以用图形把它描述出来

在这个图形中我们可以看到

我们把4点的序列x1(r)

分解成两个2点的序列之后

我们只需要计算

两个2点的DFT

得到

X3(k)和X4(k)

X3(k)和X4(k)进行组合之后

又可以得到X1(k)的值

刚才我们分解的是

序列x1(r)

同样的道理

我们可以用这种方法来分解序列x2(r)

把一个4点的序列分成两个2点的序列

继而求其

两点的DFT运算

在计算的过程中

旋转因子

因为序列的点数的原因

变成WN/2

我们可以采用旋转因子的可约性

把它上下同乘以2

变成WN2k

把一个8点的序列

进行一次

按照N的奇偶分之后

得到两个4点的DFT

进一步把两个4点的序列

再进行一次偶积分

我们可以得到

4个2点的DFT

我们就可以得到

下面这个流图

我们就要通过逐级分解

最后

就落脚到要求两点的DFT运算

当N等于8的时候

我们就可以把它分解到

要求X3(k)X4(k)

X5(k) X6(k)

其中k是等于0和1的

我们现在把两点的DFT的公式写出来

以X3(k)为例

X3(k)是等于

∑求和

l从0开始到1/4-1

X3(l)(WN/4lk)

又等于

l从0开始到1

X3(l)(WN/4lk)

其中k是从0~1

我们把k的值

和l值分别代入

把这个求和式展开得到

X3(0)=X3(0)×W20

+W20(X3(1))

代入到原序列中

它就等于X(0)

加上一个WN0乘以X(4)

而X3(1)

它是等于X3(0)

乘以W2(0)

再加上一个W21乘以X3(1)

也把它代回原序列里

它就等于X(0)减去一个W0乘以X(4)

我们现在来观察X3(0)和X3(1)的形式

后面的表达式一看

就和我们前面讲过的

按时间抽选的蝶形图是一样的形式

所以

我们在后续是可以把两点的DFT

也用

蝶形图的形式把它表示出来

我们刚才是以X3(k)为例

其中X4(k) X5(k) X6(k)

也是一样的原理

把刚才所做的所有的分解

我们都把它汇总到这张图上来

我们就可以看到

左边的

这一列应该是我们的输入值

右边的这8项是我们输出的频谱

也就是说

利用按时间抽选的FFT算法

来求DFT

我们在计算过程中

只需要反复的来计算

蝶形就可以了

以上就是我们所讲授的

按时间抽选的基2FFT算法的算法原理

同学们

今天这节课我们就讲说到这儿

谢谢大家