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

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