按频率抽取的快速傅里叶变换

《数字信号处理》

课程设计报告

按频率抽取的DFT快速算法分析及MATLAB实现

专 业： 通信工程

班 级： 组 次： 姓 名： 学 号：

目录

摘 要…………………………………………………………………… 1 关键字……………………………………………………………………1 0 引言……………………………………………………………………1 1 按频率抽取的DFT快速算法原理……………………………………1 2 DIF-FFT的运算规律及编程思想……………………………………2 2.1 原位计算…………………………………………………………2 2.2 序列的倒序………………………………………………………2 2.3 旋转因子的变换规律……………………………………………2 2.4 蝶形运算规律……………………………………………………4 2.5 编程思想及程序框图……………………………………………4 3 DIF-FFT算法运算量分析……………………………………………5 4 MATLAB程序实现 ……………………………………………………5 5 结束语…………………………………………………………………7 参考文献…………………………………………………………………7

按频率抽取的DFT快速算法分析及MATLAB实现

摘要：DFT是数字信号分析与处理中的一种重要变换。但直接计算DFT的计算量与变换区

间长度N的平方成正比，计算量非常大。DFT的快速算法使运算效率提高了1~2个数量级，为数字信号处理技术应用于各种信号的实时处理创造了条件。为了对FFT有更加深入的了解，本文对DIF-FFT的原理进行了分析，并给出MATLAB程序实现的方法与步骤。 关键词：DFT;DIF-FFT;MATLAB;

0 引言

DFT是数字信号分析与处理中的一种重要变换。但直接计算DFT的计算量与变换区间长度

N的平方成正比，计算量非常大。DFT的快速算法使运算效率提高了1~2个数量级，为数字信号处理技术应用于各种信号的实时处理创造了条件。本文通过对按频率抽取的DFT快速算法原理介绍与MATLAB实现以期使我们对傅里叶快速算法有更全面的理解，为我们以后更复杂的快速算法学习打下基础。

1 按频率抽取的DFT快速算法原理

设序列x(n)的长度为N?2M,将序列前后对半分开，得到两个子序列，如下：

X(k)??x(n)Wn?0N?12n?0N?1nkN??x(n)Wn?0N?12N?12nkNnk??x(n)WNn?N2N?1

?nkx(n)W?NN?12N???x?n?2n?0???W?N???n??k2??N

?kN/2?N?Nk/2?nk?x(n)?xn?WN??WN???2??n?0??

?(?1)k

式中：WN 将x(k)分解成偶数组与奇数组，当k取偶数（k=2m,m=0,1,…，N/2-1）时：

N/2?1 x(2m)??n?0N/2?1NN2mnmn[x(n)?x(n?)]WN??[x(n)?x(n?)]WN/2 （1）

22n?0 当k取奇数（k=2m+1,m=0,1,…,N/2-1）时，

N/2?1 x(2m?1)??n?0N/2?1NNn(2m?1)nnm[x(n)?x(n?)]WN??[x(n)?x(n?)]WN?WN/2（2）

22n?0令：

?Nn?x2(n)?[x(n)?x(n?)]WN 其中， n=0,1,2,…，N/2-1 2?x1(n)?x(n)?x(n?将x1(n)和x2(n)分别代入（1）、（2）式，可得：

N)2

??n?0N/2?1?nmX(2m?1)??x2(n)WN/2 （3）

?n?0?X(2m)?N/2?1?mnx1(n)WN/2（3）式表明，X(k)按奇偶k值分为两组，其偶数组是x1(n)的N/2点DFT，奇数组则是x2(n)的N/2点DFT。x1(n)、x2(n)和x（n）之间的关系可以用图1所示的蝶形运算流图符号表示。图2表示N=8的DIF-FFT运算流图。

x(n)x(n)＋x(n＋N / 2)

nWN nx(n＋N / 2)[x(n)－x(n＋N / 2)]WN －1 图1 DTF-FFT蝶形运算流图符号

x(0)X(0) 0WN x(1)X(4)－10 WNx(2)X(2)

－120WNWN

x(3)X(6) －1－10WN x(4)X(1)－110 WNWNx(5)X(5)

－1－120WNWN

x(6)X(3) －1－1320WNWNWN

x(7)X(7)－1－1－1

图2 DIF-FFT的运算流图（N=8）

2 DIF-FFT的运算规律及编程思想 2.1 原位计算

N?2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成。同一级中，每个蝶形的

两个输入数据只对计算本蝶形有用，而且每个蝶形的输入、输出数据结点又同在一条水平线上，这就意味着计算完一个蝶形后，所得输出数据可立即存入原输入数据所占用的存储单元。这样，经过M级运算后，原来存放输入序列数据的N个存储单元中便依次存放X（k）的N个值。原位计算可节省大量内存，从而使设备陈本降低。

2.2 序列的倒序

由图2可知，DIF-FFT算法输入序列为自然序列，而输出为倒序排列。因此M级运算完

后，要对输出数据进行倒序才能得到自然顺序的X(k)。图3为顺序与倒序二进制对照图。

顺序 十进制数I 0 1 2 3 4 5 6 7 二进制数 000 001 010 011 100 101 110 111 二进制数 000 100 010 110 001 101 011 111 倒序 十进制数J 0 4 2 6 1 5 3 7 图3 顺序与倒序二进制对照图

2.3 旋转因子的变换规律

P N点的DFT快速傅里叶运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子WN，

称其为旋转因子，P为旋转因子的指数。但各级的旋转因子和循环方式都有所不同。为了编

P写计算程序，下面列出旋转因子WN与运算级数的关系。用L表示从左到右的运算级数

（L=1,2,…，M），第L级共有2L?1个不同的旋转因子。

本文来源：https://www.bwwdw.com/article/rl4.html