8点基于DIT的FFT的实现 - 图文

课程设计任务书

学生姓名： 专业班级： 指导教师： 工作单位： 题 目：8点基于DIT的FFT的实现 初始条件：

具备Matlab编程能力；

熟悉基于DIT的FFT的实现原理； 提供编程所需要的计算机一台。

要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明

书撰写等具体要求）

1、 编写一个8点的基于DIT的FFT函数，不能使用matlab自带的FFT实现函数；

2、 并调用该函数实现16点的FFT运算，用matlab自带函数对运行结果进行验证；

3、 完成符合学校要求的设计说明书。 时间安排：

一周，其中3天程序设计，2天程序调试

指导教师签名： 年 月 日

系主任（或责任教师）签名： 年 月 日

目 录

摘 要.............................................................................................................................. I Abstract ......................................................................................................................... II 1 概述............................................................................................................................ 1

1.1 快速傅立叶变换(FFT)简介 ........................................................................... 1 1.2 MATLAB简介 ................................................................................................ 2 2 直接计算DFT的问题及改进 .................................................................................. 4

2.1 直接计算DFT的运算量 ............................................................................... 4 2.2 改进措施......................................................................................................... 5 3 按时间抽选的基-2FFT算法（DIT-FFT) ................................................................ 6

3.1 DIT-FFT算法原理 .......................................................................................... 6 3.2 DIT-FFT的运算量 ........................................................................................ 13 3.3 DIT-FFT算法的特点 .................................................................................... 14 3.4 N=16时的DIT-FFT算法 ............................................................................. 16 4 MATLAB程序代码 ................................................................................................. 18

4.1 N=8点DIT-FFT代码 ................................................................................... 18 4.2 N=16点DIT-FFT代码 ................................................................................. 19 5 MATLAB仿真结果及验证 ..................................................................................... 20

5.1 DIT-FFT函数调试 ........................................................................................ 20 5.2 DIT-FFT函数运行结果 ................................................................................ 21 5.3调用系统函数验证........................................................................................ 22 6 心得体会.................................................................................................................. 24 7 参考文献.................................................................................................................. 25

武汉理工大学《信号分析与处理》课程设计说明书

摘 要

此次课程设计的目的是利用MATLAB实现8点基于DIT的FFT的仿真，不使用MATLAB自带的FFT实现函数。本文先就直接计算傅立叶变换（DFT）存在的问题进行讨论，之后详细介绍了快速傅立叶变换（FFT）的原理以及推导过程，给出了8点FFT的蝶形流图以及MATLAB仿真的程序代码，并通过调用该函数代码计算16点的FFT。最后给出了仿真调试结果和此次课程设计的总结。

关键词： FFT MATLAB 仿真

I

武汉理工大学《信号分析与处理》课程设计说明书

Abstract

The aim of this Course Design is to use MATLAB to achieve 8-point DIT-FFT simulation, and cannot use the built-in MATLAB FFT function to realize. The beginning of this article discuss the problems of direct calculation of the Fourier transform (DFT) , and then introduces the principle of Fast Fourier Transform (FFT) and the process of derivation. Then there is given butterfly flow diagram of 8-point FFT and the MATLAB simulation program code, and realize 16-point FFT calculation by calling the function code. Finally, enumerate the simulation results and make the summary of this curriculum design.

Keywords: FFT MATLAB Simulation

II

武汉理工大学《信号分析与处理》课程设计说明书

1 概述

1.1 快速傅立叶变换(FFT)简介

傅立叶变换，表示能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。傅立叶变换是一种分析信号的方法，它可分析信号的成分，也可用这些成分合成信号。傅立叶变换是声学、语音、电信和信号处理等领域中一种重要的分析工具。在不同的研究领域，傅立叶变换具有多种不同的变体形式，如连续傅立叶变换和离散傅立叶变换。

离散傅立叶变换（DFT），是傅立叶变换在时域和频域上都呈现离散的形式，将时域信号的采样变换为在离散时间傅立叶变换（DTFT）频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作经过周期延拓成为周期信号再作变换。有限长序列可以通过离散傅立叶变换(DFT）将其频域也离散化成有限长序列。但其计算量太大，很难实时地处理问题，因此引出了快速傅立叶变换(FFT)。

1965年，Cooley和Tukey提出了计算离散傅立叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅立叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基2DIT和基2DIF。FFT在离散傅立叶反变换、线性卷积和线性相关等方面也有重要应用。

计算离散傅立叶变换的快速方法，有按时间抽取的FFT算法（DIT-FFT）和按频率抽取的FFT算法（DIF-FFT)。前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。它们都借助于的两个特点：一是周期性；二是对称性。这样，便可以把离散傅立叶变换的计算分成若干步进行，计算效率大为提高。快速傅立叶变换（FFT），是离散傅立叶变换的快速算法，它是根据离散傅立叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。

1

武汉理工大学《信号分析与处理》课程设计说明书

它对傅立叶变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。

1.2 MATLAB简介

MATLAB是美国Math Works公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。

MATLAB是matrix&laboratory两个词的组合，意为矩阵工厂（矩阵实验室）。是由美国Math Works公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如C、Fortran）的编辑模式，代表了当今国际科学计算软件的先进水平。

MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。

MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多，并且MATLAB也吸收了像Maple等软件的优点，使MATLAB成为一个强大的数学软件。在新的版本中也加入了对C，FORTRAN，C++，JAVA的支持。

优势特点:

1) 高效的数值计算及符号计算功能，能使用户从繁杂的数学运算分析中解脱出来；

2) 具有完备的图形处理功能，实现计算结果和编程的可视化；

2

武汉理工大学《信号分析与处理》课程设计说明书

3) 友好的用户界面及接近数学表达式的自然化语言，使学者易于学习和掌握；

4) 功能丰富的应用工具箱(如信号处理工具箱、通信工具箱等) ，为用户提供了大量方便实用的处理工具。

3

武汉理工大学《信号分析与处理》课程设计说明书

2 直接计算DFT的问题及改进

DFT在数字信号处理中有着重要的作用。然而直接计算DFT的运算量非常大，它与序列长度的平方成正比，因此制约了DFT的应用。快速傅立叶变换（Fast Fourier Transform,FFT）是实现DFT的一种快速算法。

2.1 直接计算DFT的运算量

离散傅立叶变换对为：

正变换： X(k)?DFT[x(n)]??x(n)WN , n?0,1,2...,N?1

n?0N?1nk（2.1.1）

1N?1?nk 反变换： x(n)?IDFT[X(k)]??X(k)WN , k?0,1,2,...,N?1

Nk?0（2.1.2）

WN为旋转因子且WN?e其中，?j2πN，x(n)表示输入的离散数字信号序列，X(k)为输入序列x(n)对应的N个离散频率点的相对幅度。 比较两式，正变换与反变换的差别就在于旋转因子的指数差个负号及少一个比例因子。因此DFT与IDFT的计算量极为相似，所以只需以正变换为例来考虑直接计算DFT时所存在的问题。 一般情况下，序列WN、x(n)及其离散频谱X(k)都是复序列，因此,要计算离散频谱X(k)的一个值就需要N次复数乘法与N-1次复数加法运算，而计算一个完整的N点的X(k)（对应k?0,1,2,...,N?1），就需要N次复数乘法与N(N-1)次复数加法运算，当N很大时，N(N-1)≈N2，因此直接计算DFT的运算量就几乎与N2成正比，随着N的增加，运算量将急剧增大，即使采用计算机，也很难实时处理。 当然，以上的分析的DFT计算量与实际的运算量稍有出入，例如，计算

4

2

武汉理工大学《信号分析与处理》课程设计说明书

W0N但是当N很大时，这种情况对整个DFT的计算?1时就不需要做乘法运算，

量影响很小，一般不做特别统计。

2.2 改进措施

FFT主要利用DFT旋转因子的周期性与对称性来减少运算量：

周期性： WN?WNnk(n?N)k?WN(N?k)n

（2.2.1）

-nkk(N?n)对称性： (Wnk )*?WN?WNN（2.2.2）

利用周期性与对称性，一方面可以在DFT的运算过程中把有些项进行合并，另一方面可以把长序列的DFT分解成若干短序列的DFT。因为DFT的运算量与变换长度的平方成正比，如果可以把一个长序列DFT分解成若干短序列DFT再进行计算，就可以大大减少运算量。

5

武汉理工大学《信号分析与处理》课程设计说明书

3 按时间抽选的基-2FFT算法（DIT-FFT)

常用的FFT算法有两大类，一类是按时间抽取的FFT算法（简称DIT-FFT），另一类是按频率抽取的FFT算法（简称DIF-FFT）。

最早提出的基-2FFT算法，使DFT的运算效率提高了1~2个数量级，从而为DFT由理论研究到实际应用创造了条件。

3.1 DIT-FFT算法原理

按时间抽取的FFT算法基本思想是：时域下的序列x(n)按序列n的奇偶分组，频域下序列X(k)按序列k前后分组。有限长序列x(n)，设其长度N?2，L为整数，若不满足该条件，加零补足。显然N为偶数，可以按序列序号分为奇、偶两组序列，长度分别为N/2，如：

x(n)?{x(0),x(1),...,x(N?1)}

L

按n的奇偶分组，对x(n)重新排列，得：

{x(1),x(3),...,x(N?1｜x(0),)x(2),...,x(N-2)}

令

x(2r)?{x(0),x(2),...,x(N?1)},r?0,1,2,...,N/2?1

（3.1.1）

x(2r?1)?{x(1),x(3),...,x(N?1)},r?0,1,2,...,N/2?1

（3.1.2）

再令

x1(n)?x(2r)

（3.1.3）

x2(n)?x(2r?1)

（3.1.4）

6

武汉理工大学《信号分析与处理》课程设计说明书

N点序列x(n)的DFT为：

X(k)?DFT[x(n)]??x(n)WNn?0N?1nk???n为偶数N/2?1r?0?x(n)WnkN?n为奇数?x(n)WN/2?1r?0nkN(2r?1)k

?x(2r)WN?2rkr?02rk?x(2r?1)WNkN/2?1r?0N/2?1?x1(r)WN?WN?x2(r)WN2rk因为

WN?e2rk?j2?2rkN?e?j2?rkN/2?WN/2

rk（3.1.5）

所以

N/2?1

X(k)??r?0x1(r)WN/2?WNkrkrkN/2?1?r?0x2(r)WN/2rk

?X1(k)?WNX2(k)（3.1.6）

其中X1(k)与X2(k)分别是x1(n)与x2(n)的N/2点的DFT，即：

N/2?1X1(k)?DFT[x1(n)]? ?r?0x1(r)WN/2,k?0,1,2,...rkN?12N/2?1X2(k)?DFT[x2(n)]??r?0Nrkx2(r)WN/2,k?0,1,2,...?12

（3.1.7）

式（3.1.6）把一个N点的DFT分解成了两个N/2点的DFT的组合，但是X1(k)与X2(k)分别是x1(n)与x2(n)的N/2点的DFT，r与k的取值满足r,k=0,1,2,...,N/2-1，而X(k)是一个N点的DFT，因此式（3.1.7）只计算X（k)前N/2点的值。利用旋转因子的周期性来计算

7

武汉理工大学《信号分析与处理》课程设计说明书

X(k)后N/2的值。由式（2.1.1）得：

WN/2?WN/2nkr(k?N)2

（3.1.8）

这样X(k)后N/2点的值为：

NNNNk?2X(k?X(k?)?X1(k?)?WN/2) 2222

考虑周期性：

N/2?1NNr(k?)X1(k?)??x1(r)WN/222r?0N/2?1 ??r?0x1(r)WN/2rk

?X1(k)（3.1.9）

同理可得：

X2(k?N)?X2(k) 2（3.1.10）

式（3.1.9）与式（3.1.10）表明X1(k)与X2(k)前N/2点的值与后N/2的值相同，实际上就是DFT隐含的周期性。 再考虑对称性：

k2?? W(N2?k)?WkWN NWNNN（3.1.11）

所以：

NNNN(k?)X(k?)?X1(k?)?WN/22X2(k?)222

k?X1(k)?WNX2(k)（3.1.12）

8

武汉理工大学《信号分析与处理》课程设计说明书

这样利用式（3.1.11）与式（3.1.12）就可以把一个完整的N点的DFT分解成两个N/2点的DFT来运算。上述讨论的运算过程可以用图3.1所示的信号流图来表示。

X1(k) X1(k)?WNX2(k) X2(k) X1(k)?WNX2(k)

kk图3.1 DIT-FFT蝶形运算符号

如图3.1所示，任一支路上的值等于支路起始节点的值乘以支路传输系数，任一节点上的值等于所有输入支路值之和。从图中可以看出，每个蝶形的运算需要一次复数乘法运算和两次复数加法运算。 在图3.1中，输入为两个N/2点的DFT输出为一个N点的DFT结果，输入输出点数一致。运用这种表示方法，8点的DFT可以用图3.2来表示。 当N=8为例，采用蝶形图表示，DFT的分解运算如图3.2所示。其中X(0)?X(3)由式（3.1.7）给出，X(4)?X(7)由式（3.1.12）给出。 x(0)X1(0)x(2)x(4)x(6)X(0)X(1)X(2)N/2点DFTX1(1)X1(2)X(3)X1(3)x(1)x(3)x(5)x(7)0WN?1X2(0)X(4)X(5)X(6)X(7)N/2点DFT1WNX2(1)X2(2)X2(3)?1?1?1W2N3WN 图3.2 DIT-FFT一次分解 根据式（3.1.11）与式（3.1.12），一个N点的DFT可以由两个N/2点的DFT运算构成，再结合图3.1的蝶形信号流图可以得到图3.2的8点DFT的第一次分解。

9

武汉理工大学《信号分析与处理》课程设计说明书

该分解可以用以下几个步骤来描述： 1.将N点的输入序列按奇偶分为2组分别为N/2点的序列； 2.分别对1中的每组序列进行DFT变换得到两组点数为N/2的DFT变换值X1和X2； 3.按照蝶形信号流图将2的结果组合为一个N点的DFT变换结果。 经过一次分解，计算一个完整的N点DFT需要2(N/2)2?N/2?N2/2次复数乘法，以及N(N/2?1)?N?N2/2次复数加法，运算量减少了将近一半，由于N/2依然是偶数，故可将N/2点的DFT按同样方法分解成两个N/4点的DFT。 与第一次分解相同，把序列x1(r)按r的奇偶次序分解成两个N/4点的序列x3(l)与x4(l)，即： x1(2l)?x3(l)?N,l?0,1,2,...,?1 ?x1(2l?1)?x4(l)?4（3.1.13） 代入x1(r)的N/2点的DFT表达式中有： X1(k)?DFT[x1(r)]N/2?1? ?x(r)W1r?0rkN/22lkN/4?1N/4?1???l?0x1(2l)WN/2?lk?l?0kx1(2l?1)WN/2

N/4?1(2l?1)kN/4?1?l?0x3(l)WN/4?WN/2k?l?0x4(l)WN/4lk?X3(k)?WN/2X4(k)（3.1.14） 且由对称性和周期性有： X1(k?Nk)?X3(k)?WN/2X4(k) 4（3.1.15） 其中：

10

武汉理工大学《信号分析与处理》课程设计说明书

N/4?1X3(k)?DFT[x3(l)]? ?l?0l?0x3(l)WN/4,k?0,1,2,...rkrkN?14N?14N/4?1

X4(k)?DFT[x4(l)]??x4(l)WN/4,k?0,1,2,...（3.1.16） 所以，当N=8时，上一步分解出的一个N/2点的DFT可以分解成两个N/4点的DFT，运算流图如图3.3所示。 x(0) N/4点 X3(0) X1(0) DFT x(4) X3(1) X1(1) x(2) N/4点 X4(0) WN/2 -1 X1(2) DFT x(6) X4(1) WN/2 -1 X1(3) 图3.3 由两个N/4点DFT组合成1个N/2点DFT 同理，X2(k)也做同样的分解，得： X2(k)?X5(k)?WN/2X6(k)

（3.1.17） X2(k?Nk)?X5(k)?WN/2X6(k) 4k11（3.1.18） 其中： N/4?1X5(k)?DFT[x5(l)]? ?l?0l?0x5(l)WN/4,k?0,1,2,...rkN?14N/4?1X6(k)?DFT[x6(l)]??Nrkx6(l)WN/4,k?0,1,2,...?14

11

武汉理工大学《信号分析与处理》课程设计说明书

（3.1.19）

这样就可以把两个N/2点的DFT分解成四个N/4点的DFT。当N=8时，经过两次分解后的运算流图如图3.4所示。

图3.4 DIT-FFT二次分解

由于满足N?2L，所以经过二次分解后N/4仍然是偶数，可以继续分解。根据上述讨论，经过L-1次分解后，就可以把一个N点的DFT分解成N/2个两点的DFT，而每一个两点的DFT可以根据如图3.1所示的蝶形图来进行计算。当N=8时，于是就可以把一个完整的8点的DFT分解成4个两点的DFT进行运算。计算一个完整的N=8点的DIT-FFT蝶形图如图3.5所示。

12

武汉理工大学《信号分析与处理》课程设计说明书

x(0)

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

x(1)

0WN?10WN2NX(1)?1?1W0NX(2)X(3)X(4)X(5)X(6)W0N?1W?1?1?1?1x(5)

x(3)W0N?1W0N1WN

W0N?1?1W2Nx(7)

?12WNW

3NX(7)图3.5 N=8 DIT-DFT的蝶形图

3.2 DIT-FFT的运算量

观察图3.5，可见当N?2L时，经过L-1次分解，整个DIT-FFT运算有L级蝶形，每一级蝶形有N/2个蝶形运算，每一个蝶形运算有一次复数乘法好人两次复数加法，所以整个运算流图的运算量为： 复数乘法： mF?L?NN?1?1bN 22(3.2.1) 复数加法： aF?L?N?2?N1bN 2(3.2.2) 直接计算DFT需要N2次复数乘法与N(N-1)次复数加法运算，直接计算DFT与DIT-FFT的复数乘法运算量之比为：

13

武汉理工大学《信号分析与处理》课程设计说明书

N2N22N ??NNL1bN1bN22(3.2.3) 3.3 DIT-FFT算法的特点

1. 原位运算

在DIT-FFT的蝶形图中，取第m级且两输入节点分别在第k、j行的蝶形为例，讨论DIT-FFT的原位运算规律。如图3.6所示，蝶形运算的关系式可表示为：

r??Xm(k)?Xm?1(k)?WNXm?1(j)? ?Xm(j)?Xm?1(k)?WrXm?1(j)

N?(3.2.4)

从式中可以看出，第m级蝶形第k行与第j行的输出，只与第m-1级的第k行与第j行的输出有关，换言之，第m-1级的第k行与第j行的输出Xm?1(k)与

Xm?1(j)在运算流图中的作用就是用来计算第m级的第k行与第j行的输出Xm(k)与Xm(j)。这样当计算完Xm(k)与Xm(j)后，Xm?1(k)与Xm?1(j)在运算流图不再起作用，因此就可以把Xm(k)与Xm(j)直接存放在原来存放Xm?1(k)与Xm?1(j)的存储单元中。同理，可以把第m级蝶形的N个输出值直接存放在第m-1级蝶形输出的N个存储单元中，这样从第一级的输入x（n）开始，到最后一级输出X(k)，只需要N个存储单元。

X1(k)

X1(k)?WNX2(k)

k

X2(k)

X1(k)?WNX2(k)

k WN -1

r14

武汉理工大学《信号分析与处理》课程设计说明书

图3.6 按时间抽取蝶形运算结构 2. 倒序规律 从图3.5可以看出，按原位计算时，蝶形图的输出正好是自然顺序X(0),X(1),...,X(7)，但是输入却不是自然顺序，而是x(0),x(4),x(6)...，表面看起来好像是“混乱无序”的，实际上是有规律的，即倒序的排列方法。 倒序的形成原因是FFT不断对序列进行奇偶分组造成的，重新排列了序列的存放顺序，因此它是按码位倒置顺序排放的。由于N=2M，所以倒序数可用M位二进制数表示。第一次分组，按n0的0和1分成奇偶两组，n0=0相当是偶序列，n0=1相当是奇序列。第二次分组按n1的0和1分成两组??依次类推，直到M次分组。 0 0 1 0 0 1 1 0 0 ?n0n1n2?2 1 1 0 1 1 图3.7 倒序形成的树状结构 3. 蝶形运算两节点之间的“距离” 从图3.5可以看出，第一级蝶形每个蝶形运算两节点之间的“距离”为1，第二级每个蝶形运算两节点之间的“距离”为2，第三级蝶形每个蝶形运算两节点之间的“距离”为4。依次类推，对于N?2L的DIT-FFT，可以得到第M级蝶形每一个蝶形运算两节点之间的“距离”为2M?1。 4. 旋转因子的变化规律 以图3.5的8点FFT为例，每一级的每一个蝶形运算都要乘以一个旋转因子

15

武汉理工大学《信号分析与处理》课程设计说明书

WrN，r是旋转因子的指数。在第一级蝶形，r=0；在第二级蝶形，r=0,1；在第

三级的蝶形，r=0,1,2,3;依次类推，对于第M级蝶形，旋转因子的指数为 ：

r?J?2L?M,J?0,1,2,..2.M,?1?1

这样就可以算出每一级的旋转因子。对于M级的任一蝶形运算所对应的旋转因子的指数，可以 如下方法得到：

(1) 将待求的蝶形输入节点中上面节点的行标号值k写成L位二进制数； (2) 将此二进制数乘以2L?M，即将L位二进制数左移L-M位，右边的空位补零，然后从低位到高位截取L位，即得到要求的指数r所对应的二进制数。

3.4 N=16时的DIT-FFT算法

先将序列x(n)奇偶分组得：

x1(r)?x(2r)

x2(r)?x(2r?1) r=0,1,2,...,7

(3.4.1)

将DFT运算也分为两组：

X(k)?DFT[x(n)]??x(n)WNn?0N?1nk?n为偶数N/2?1?x(n)WnkN?n为奇数?x(n)WN/2?1r?0k7nkN(2r?1)k ??x(2r)WN?r?07rkk2rk?x(2r?1)WNrkr?0

??x1(r)W8?W16?x2(r)W8r?0?X1(k)?W16X2(k)(3.4.2)

其中X1(k)与X2(k)分别是x1(n)与x2(n)的8点DFT，即：

X1(k)?DFT[x1(n)]??x1(r)W8,k?0,1,2,...,7r?077rk

X2(k)?DFT[x2(n)]??x2(r)W8,k?0,1,2,...,7r?0rk

16

武汉理工大学《信号分析与处理》课程设计说明书

(3.4.3)

这样，一个16点的DFT就被分解为两个8点的DFT，即：

X(k)?X1(k)?W16X2(k)X(k?8)?X1(k)?W16X2(k)kk，k=0,1,2,...,7

(3.4.4)

对两个8点的DFT再分别做进一步分解，每个8点的DFT分解成两个4点的DFT，即：

X1(k)?X3(k)?W16X4(k)X1(k?4)?X3(k)?W16X4(k)2k2k，k=0,1,2,...,7

(3.4.5)

对四个4点的DFT再分别做进一步分解，每个4点的DFT分解成两个2点的DFT，即：

X3(k)?X5(k)?W16X6(k)X3(k?2)?X5(k)?W16X6(k)4k4k，k=0,1,2,...,7

(3.4.6)

所以，N=16点的DFT最终可以分解成8个2点的DFT。

17

武汉理工大学《信号分析与处理》课程设计说明书

4 MATLAB程序代码

4.1 N=8点DIT-FFT代码

根据蝶形图一级一级依次分解，可以把一个完整的8点的DFT分解成4个两点的DFT进行运算。

function y=fft8(x) 数

Wn=exp(-j*2*pi/8); x1(1)=x(1)+x(5); x1(1)=x(1?)W0Nx(5 ) x1(2)=x(1)-x(5); x1(3)=x(3)+x(7); x1(4)=x(3)-x(7); x1(5)=x(2)+x(6); x1(6)=x(2)-x(6); x1(7)=x(4)+x(8); x1(8)=x(4)-x(8); x2(1)=x1(1)+x1(3); x02(1)=x1(1?)WNx1(3 ) x2(2)=x1(2)+x1(4)*(Wn.^2); x2(3)=x1(1)-x1(3); x2(4)=x1(2)-x1(4)*(Wn.^2); x2(5)=x1(5)+x1(7); x2(6)=x1(6)+x1(8)*(Wn.^2); x2(7)=x1(5)-x1(7); x2(8)=x1(6)-x1(8)*(Wn.^2); y(1)=x2(1)+x2(5);

%定义根据蝶形图计算8点DIT-FFT的函?%定义旋转因子计算公式WNN?e?j2

%计算第一级蝶形图输出

%x01(2)=x(1)-WNx(5) %x01(3)=x(3)?WNx(7) %x01(4)=x(3)-WNx(7) %x01(5)=x(2)?WNx(6) %x01(6)=x(2)-WNx(6) %x01(7)=x(4)?WNx(8) %x01(8)=x(4)-WNx(8)

%计算第二级蝶形图输出

%x22(2)=x1(2)?WNx1(4) %x02(3)=x1(1)-WNx1(3) %x22(4)=x1(2)-WNx1(4) %x02(5)=x1(5)?WNx1(7) %x22(6)=x1(6)?WNx1(8) %x02(7)=x1(5)-WNx1(7) %x2(8)=x21(6)-WNx1(8)

%计算第三级蝶形图输出18

武汉理工大学《信号分析与处理》课程设计说明书

y(1)=x2(1)?WNx2(5)

0 y(2)=x2(2)+x2(6)*(Wn.^1); %y(2)=x2(2)?WNx2(6) y(3)=x2(3)+x2(7)*(Wn.^2); %y(3)=x2(3)?WNx2(7) y(4)=x2(4)+x2(8)*(Wn.^3); %y(4)=x2(4)?WNx2(8) y(5)=x2(1)-x2(5); %y(5)=x2(1)-WNx2(5) y(6)=x2(2)-x2(6)*(Wn.^1); %y(6)=x2(2)-WNx2(6) y(7)=x2(3)-x2(7)*(Wn.^2); %y(7)=x2(3)-WNx2(7) y(8)=x2(4)-x2(8)*(Wn.^3); %y(8)=x2(4)-WNx2(8)

32103214.2 N=16点DIT-FFT代码

调用计算N=8点时编写的函数fft8来实现N=16点的DIT-FFT运算。可以先将N=16点的DFT根据奇偶分解成两个8点的DFT，然后再分别用函数fft8对这两组8点的DFT进行计算。

function y=fft16(x) %定义计算16点DIT-FFT的函数 Wn=exp(-j*2*pi/16); %定义旋转因子计算公式WN?e y1=fft8(x(1:2:16)); %计算偶数组的8点FFT y2=fft8(x(2:2:16)); %计算奇数组的8点FFT y(1:8)=y1+y2.*(Wn.^[0:7]); %计算前八个点 y(9:16)=y1-y2.*(Wn.^[0:7]); %计算后八个点

?j2?N

19

武汉理工大学《信号分析与处理》课程设计说明书

5 MATLAB仿真结果及验证

5.1 DIT-FFT函数调试

1. 运行MATLAB，点击file-new-function新建函数编辑窗，输入N=8点DIT-FFT的代码并保存为fft8.m。

图5.1 N=8点DIT-FFT函数调试

2. 运行MATLAB，点击file-new-function新建函数编辑窗，输入N=16点DIT-FFT的代码并保存为fft16.m。

20

武汉理工大学《信号分析与处理》课程设计说明书

图5.2 N=16点DIT-FFT函数调试

5.2 DIT-FFT函数运行结果

1. 在命令窗口输入x=[1 2 4 6 8 10 12 14 ]; fft8(x)后，按回车运行程序。

图5.3 N=8点DIT-FFT函数运行结果

21

武汉理工大学《信号分析与处理》课程设计说明书

2. 在命令窗口输入x=[1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30]; fft16(x)后，按回车运行程序。

图5.4 N=16点DIT-FFT函数运行结果

5.3调用系统函数验证

1. 在命令窗输入x=[1 2 4 6 8 10 12 14 ]; fft(x) 后按回车，通过调用系统函数FFT计算8点FFT，计算结果与上面一致，结果如下：

图5.5 调用系统函数验证N=8点DIT-FFT

22

武汉理工大学《信号分析与处理》课程设计说明书

2. 在命令窗输入x=[1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30]; fft(x) 后按回车，通过调用系统函数FFT计算8点FFT，计算结果与上面一致，结果如下：

图5.6 调用系统函数验证N=16点DIT-FFT

经过调用MATLAB系统自带函数的验证，所编写的程序运行的结果与系统自带函数运行的结果一致，可以实现8点和16点的按时间抽取的基2-FFT运算。

23

武汉理工大学《信号分析与处理》课程设计说明书

6 心得体会

通过此次课程设计,巩固了我在课堂上所学的关于快速傅里叶变换的相关

知识，加深了对课堂抽象概念的理解,巩固了课堂上所学的理论知识,并能很好地理解与掌握数字信号处理中的基本概念、基本原理、基本分析方法。设计过程中，学习了许多数字信号处理课程中关于数字滤波器的设计的内容。同时掌握编程方法和解决实际问题的技巧。

与其他高级语言的程序设计相比，MATLAB环境下更方便、快捷，节省大量的编程时间，提高编程效率，且参数的修改也十分方便，还可以进一步进行优化设计。

此外，在此次数字信号处理原理与实现课程设计中，通过查阅资料、请教同学等途径，在摸索中不仅完成了教学任务，还对MATLAB这个强大的仿真软件有了一定的认识。在完成了此次课程设计之后，掌握了自己的基础理论知识，提高了学习能力和基本动手能力，同时掌握了基本的文献检索和材料阅读的方法，提高了我们的基本素质。培养了我们独立思考和解题的能力，树立了对所学知识运用的信心，这些必将在我们今后的学习工作和生活中起到非常大的帮助。

在课程设计的这段时间里，我认为收获还是很多的，不但进一步掌握了信号分析与处理的基础知识及一门专业仿真软件的基本操作，还提高了自己的设计能力及动手能力。更多的是让我看清了自己，明白了凡事需要耐心，实践是检验学习的唯一标准。理论知识的不足在这次课程设计中表现的很明显。这将有助于我今后的学习，端正自己的学习态度，从而更加努力的学习。

总之这次课程设计使我受益匪浅，让我学到了很多东西。尽管此次课程设计完成的效果并非很好，但是我觉得在设计过程中所学到的东西才是此次经历的最大收获和财富。课程设计不仅是对前面所学知识的一种检验，同时也是对自身能力的一种提高。学习本身就是一个长期积累的过程，在以后的工作和生活中都应该不断学习，努力提高自己的知识和综合素质。

24

武汉理工大学《信号分析与处理》课程设计说明书

7 参考文献

[1]李勇，徐霞.MATLAB辅助现在工程数字信号处理.西安：西安电子科技大学出版社.2002

[2]高西全，丁玉美.数字信号处理(第三版).西安：西安电子科技大学出版社.2008

[3]程佩青.数字信号处理教程（第3版）.清华大学出版社，2007 [4]周利清，苏菲.数字信号处理基础.北京：北京邮电大学出版社.2005 [5]万永革.数字信号处理的MATLAB实现.科学出版社，2008.9

[6]郭仕剑、王宝顺、贺志国.MATLAB数字信号处理.人民邮电出版社，2007.11

25

武汉理工大学《信号分析与处理》课程设计说明书

本科生课程设计成绩评定表

姓 名 专业、班级 安虎 电信1205班 性 别 男 课程设计题目： 8点基于DIT的FFT的实现 课程设计答辩或质疑记录： 成绩评定依据： 最终评定成绩（以优、良、中、及格、不及格评定）

指导教师签字：

年 月 日

26

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