4-3视频在线视频

大家好

这节课我们学习时域抽取法基2FFT算法

主要内容包括

时域抽取法基2FFT定义

原理以及运算流图

我们首先看一下时域抽取法基2FFT定义

假设序列长度是N等于2的M次方

基数是2 所以叫基2

M是正整数

把序列x(n)按照n的奇偶分解成子序列

就称为时域抽取法基2FFT

也就是DIT-FFT

也叫做库利图基算法

如果N不等于2的M次方

可以进行补0

使序列达到这个长度

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

序列x(n)的离散傅里叶变换是X(k)

k从0到大N-1 如公式(1)所示

把序列x(n)按照n的奇偶分成两组

形成两个子序列

n是偶数的时候 设n等于2r

n是奇数的时候 设n等于2r+1

其中r等于0到N/2-1

这样形成了两个子序列x1(r)和x2(r)

分别对这两个子序列进行

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

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

我们来分析一下

X(k)和X1(k) X2(k)的关系

因为我们要按照n的奇偶对x(n)进行分解

所以离散傅里叶变换的公式

就分解成两部分

一部分n是偶数

另外一部分n是奇数

n是偶数 令n等于2r

n是奇数 令n等于2r+1

对于这个系数

它可以写成两项的乘积

一项是WN的k次方

一项是WN的2rk次方

由系数的可约性

我们可以得到这个公式

前面这一项

是x1(r)的N/2点离散傅里叶变换X1(k)

后面这一项是WN的k次方乘以

x2(r)的N/2点离散傅里叶变换X2(k)

k是从0到N/2-1

这样我们就得到了x(k)的前一半值

也就是k等于0到N/2-1的时候对应的值

那么后一半的数据呢

k+N/2对应的就是N/2到N-1这一部分

那么也就能得到X(k)的后一半的值了

所以我们把k加N/2带到公式(2)里面来

得到公式(3)

在公式(3)中

这个系数在上一讲中

我们已经推导出来了

它是等于负的WN的k次方

那么X1(k+N/2)等于什么呢

把k+N/2代入到

X1(r)的N/2点离散傅里叶变换式当中

这一部分分成两部分的乘积

那么乘积的后一项

它是等于1的

把化简的结果再代回到公式里面来

我们就可以看到

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

同理

我们可以得到X2(k+N/2)等于X2(k)

把这几个值代入到公式(3)中

就可以得到X(k)的后一半的数据值

是由公式(4)所描述的

所以如果求出来了

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

X1(k)和X2(k)

那么就可以由公式(2)和公式(4)

求出X(k)的前半部分和它的后半部分

同理可以把N/2点的离散傅里叶变换

继续分解

分解成N/4点的离散傅里叶变换

依此类推

直到两点的离散傅里叶变换

那么公式(2)和公式(4)所描述的关系

可以用蝶形运算来表示

这个是蝶形运算符号

左边是输入

C表示支路系数

右边是输出

向上的支路是相加

也就是A+CB

向下的支路是相减

也就是A-CB

那么这两个公式

我们用蝶形运算符号来表示的话

就是输入是X1(k)和X2(k)

支路系数是WN的k次方

输出就是

X(k)的前一半数据和后一半数据

下面我们以N等于8为例

对完整的过程进行一下介绍

首先把8点的序列分解成两个N/2点的序列

也就是n等于偶数的时候

形成的序列是x1(r)

n等于奇数的时候

形成一个子序列是x2(r)

在频域上X(k)的值是

由公式(2)和公式(4)所求出来的

也就是说

它要分成前一半的数据和后一半的数据

这样的话

X(0)到X(3)是由公式(2)给出的

X(4)到X(7)是由公式(4)给出来的

我们把它画成运算流图的形式

x(n)先分成两个子序列

x1(r)和x2(r)

它们分别去进行4点的离散傅里叶变换

得到X1(k)和X2(k)

然后经过一级蝶形

就可以得到X(k)的前一部分值

和X(k)的后一部分值

比如说X(0)

它是等于X1(0)加上X2(0)乘以W8的0次方

这个蝶形的另外一个输出是X(4)

它等于X1(0)减去X2(0)乘以W8的0次方

所以它们两个是一个蝶型的输出

其它的点也是一样的

然后再把N/2点的子序列

按照r的奇偶来分解成N/4点的子序列

也就是把x1(r)和x2(r)

按照r的奇偶来进行分解

这样形成了4个N/4点的子系列

x3(l)到x6(l)

l是等于0到N/4-1

我们以8点的序列为例

来再看一下这个过程

第一次分解是把n为偶数的点

作为一个序列x1(r)

把n为奇数的点

作为另外一个序列x2(r)

第二次分解是把x1(r)

r的偶数点形成一个序列

奇数点形成一个序列

同样x2也是这样

这样就形成了4个两点的序列

分别对应着x3(l)到x6(l)

对x3(l)和x4(l)进行两点的离散傅里叶变换

得到X3(k)和X4(k)

再经过一级蝶形就得到了X1(k)

同理也可以得到X2(k)

那么两点的离散傅里叶变换

也是一级蝶形

x3(l)的两点离散傅里叶变换是X3(k)

把这个求和号展开

就可以得到蝶形运算的这种形式

左边的这个图

就是两点的蝶形运算流图

下面我们把刚才的过程总结一下

首先把x(n)按照n的奇偶分成两个子序列

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

得到的结果进行一级蝶形运算

得到输出

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

继续分解

分解成N/4点的离散傅里叶变换

由于x1(r)和x2(r)

又分别按照r的奇偶进行了抽取

所以N/4点的离散傅里叶变换

它的输入顺序就变成了

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

然后分别去进行N/4点离散傅里叶变换

如果它还是2的整次幂

可以继续进行分解

因为这里N等于8

所以这个N/4点离散傅里叶变换

就是两点的了

那么两点的离散傅里叶变换

也是一级蝶形

这样得到了完整的

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

其中W8的0次方

W8的1次方

这些叫做旋转因子

因为8是2的3次方

所以它一共是分解成了三级

这个就是时域抽取法基2-FFT原理

和它的运算流图

下面我们来举一个例子

利用时域抽取法基2-FFT求X(k)

在实际当中

输入它是按照自然顺序排列的

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

但是FFT它的输入不是自然顺序

是因为n按照奇偶不断的进行了抽取

得到这样一个顺序

这个顺序叫做倒序

所以我们要把这个自然顺序变成倒序

才能够进行FFT的运算

因此我们进行一个变址运算

变成倒序

这个输入经过一级蝶形运算

我们看它得到什么值

这一点的值应该是

x(0)加上x(2)乘以W4的0次方

所以它等于4

蝶形运算向上是相加 向下是相减

所以这一点的值是-2

同理我们可以得到

下面这两个点的值是6和-2

然后这些值再进行第二级蝶形运算

就可以得到X(k)的值

X(0)是等于10

X(2)等于-2

X(1)是等于-2+2j

X(3)是等于-2-2j

那么由这个结果我们也可以验证

在DFT模块中学习的性质

如果输入是实序列

那么它的离散傅里叶变换

应该是共轭对称的

X(1)和X(3)这两个值是共轭的

另外对于没有对称点的这两个点

一个是k等于0

一个是k等于N/2

k等于0的时候

它应该是序列的所有值之和

对于k等于N/2这一点

因为在这里面N是等于4

所以N/2是等于2

所以X(2)这一点

它的值应该是序列的值

加一项 减一项 加一项 减一项

所以它等于-2

和我们进行离散傅里叶变换的结果

是一样的

这些就是时域抽取法基2-FFT的内容

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

再见