4.4 按频率抽选的基-2FFT算法的算法原理在线视频

同学们好

今天我们给大家讲述的内容是

按频率抽选的基2FFT算法

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

设序列的点数N

是等于2的L次方

L为整数

如果点数不满足条件

则在后边补零

我们将

输出的频谱X(k)

在按照k的奇偶分组以前

先把输入x(n)

按照n的顺序给它分成前后两半

也就是

序列x(n)

求N点的DFT

得到的结果为X(k)

我们把它

这个求和式写成两部分

一部分n的范围是从0~N/2-1

另一部分n是从N/2~N-1

前面这一部分

我们不动

后面这一部分

我们进行一个变量代换

用n加N/2来替换n

这样前后两个求和式

它们的求和区间变成一样的

这两个求和式的求和区间

变成一样的之后

我们就可以把它合并成一个求和式

后一项的旋转因子

上标有两项

我们把它进行一次拆分

拆分之后

前面一个求和式和后边一个求和式

都有一个WNnk这一项

我们把它提出来

最终就会得到

∑求和

n从0开始

到N/2-1

x(n)

加上

-1的k次方乘以x（n+N/2）

然后再乘以一个WNnk

我们把刚才计算的X(k)的表达式

按照k的奇偶把X(k)分成两部分

当k为偶数

也就是2r的时候

代入到刚才的公式

-1的k次方

就等于1

所以变成了n从0开始到N/2-1

然后x(n)+x(n+N/2)

乘以一个WN/2乘以nr

我们观察一下这个式子就会发现

这个式子其实就是

序列的前半部分x(n)

和后半部分x(n+N/2)

相加之后

再来求N/2点DFT

当k为奇数的时候

也就是2r加1

我们把它代入到X(k)的公式中

最终得到的公式为

∑求和

n从0开始到N/2-1

x(n)写x（n+N/2）之后

乘以个WNn

然后在一起乘一个

WN/2nr

在以上的两个式子中

我们令

x1(n)等于x(n)+x(n+N/2)

也就是序列的前半部分和后半部分相加

我们把它令成序列x1(n)

而序列的前半部分

x(n)

和后半部分相减

再乘以旋转因子Wn

就把它令成序列x2(n)

得

X(2r)和X(2r+1)

分别就为

x1(n)和x2(n)的

N/2点的DFT

我们把它记为

X1(k)和X2(k)

根据上面的计算公式

我们画出按频率抽选的蝶形运算流图

在流图中

两个输入分别为x(n)和x(n+N/2）

上面这条输出相为x(n)

+x(n+N/2)

下边这条输出为

x(n)-x(n+N/2)之后

再乘以旋转因子WNn

这个按频率抽选的蝶形运算的流图中

我们可以看出来

要完成一次蝶形运算

我们也是需要

一次复数乘法

两次复数加法

这个运算量

和按时间抽选的蝶形运算流程运算量是相同的

我们把刚才进行的一次分解

用图形描述出来

以N等于8点为例

这个8点的序列

前半部分

就是从x(0)~x(3)和后半部分

x(4)~x(7)

我们把它进行组合

相加得到第1个序列x1(n)

前半部分和后半部分相减之后

再乘以旋转因子WNn

得到第2个序列x2(n)

也就是说

这样我们还是把一个8点的序列

组合成了两个

4点序列

接下来我们需要把这两个4点的

序列

分别计算4点的DFT

在刚才进行第一步分解之后

得到两个N/2点的序列

又因为N/2仍然为一个偶数

所以我们可以对它进行进一步的分解

把两个N/2的序列

分解成

4个N/4点的序列

分解的方法和前面一样

序列的前半部分和后半部分相加

得到一个新的序列

序列的前半部分和后半部分相减之后

乘以旋转因子

得到第2个序列

这两个序列

分别求DFT运算

得到X3(k)和X4(k)

第2步的分解

用图形描述出来

是这个样子的

x1(n)

前半部分和后半部分进行组合

相加得到x3(n)

相减乘以旋转因子之后

得到x4(n)

两点序列x3(n)

求一个两点的DFT

就会得到X3(k)

2点的序列x4(n)

计算一个两点的DFT

就可以求出X4(k)

同样的道理

我们可以采用这种方法

来把序列x2(n)

进行分解

前半部分和后半部分相加

得到序列x5(n)

前半部分和后半部分相减之后

乘以旋转因子WN/2n

得到序列x6(n)

进而计算出它们的

N/4点的DFT

为X5(k) 和X6(k)

我们把经过两次分解之后的

内容

用图形描述出来

如图所示

其中序列x(n)

8点

分成两个4点的序列

分别为x1(n) 和x2(n)

其中x1(n)

这个4点的序列

再进行一次分解

得到序列x3(n) 和x4(n)

分别为两点

序列x2(n)

也在进行一次分解之后

就会得到序列

x5(n) 和x6(n)

我们得到了4个序列

x3(n) x4(n) x5(n) 和x6(n)

均为两点

所以它们可以直接计算

两点的DFT

得到最终输出的频谱

写成这种形式之后

我们就可以看得出来

X(0)和X(4)

这一主值求出来的结果

实际上是满足

我们刚刚所画过的

按频率抽选的

蝶形流图的结构

分别是X3(0)和X3(1)

进行相加

得到一个值

相减再乘以旋转因子

得到另一个值

所以

我们就可以把两点的DFT

也采用

按频率抽选的蝶形图的形式

把它画出来

经过刚才所有的分解之后

我们可以得到最终的一个

按频率抽选的一个流图

输入X(0)

一直到X(7)

是一个自然顺序

输出

X(0) X(4) X(2) X(6)

X(1) X(5) X(3) X(7)

这是一个按照频率

进行奇偶分解之后

得到的结果

也就是我们所说的

按频率抽样算法

同学们

关于

按频率抽选的基2FFT算法的算法原理

我们就介绍到这儿

谢谢大家