DFT与FFT计算速度比较分析

xx大学

课 程 设 计 说 明 书

题目： DFT与FFT计算速度比较分析

系 别： 年级专业： 学 号：

学生姓名： 指导教师： 教师职称：

大神大学课程设计（论文）任务书

院（系）： xx工程学院 基层教学单位： xxx 学 号 设计题目 设 计 技 术 参 数 设 计 要 求 222222222222 学生姓名 xxx 专业（班级） xxx DFT与FFT计算速度比较分析 用MATLAB实现DFT及FFT对任意长度的序列进行傅里叶变换 DFT与FFT的运算时间比较 利用Matlab或者C语言设计DFT和FFT程序，比较两种频谱分析方法的计算速度，并与理论值进行比较。 工 作 量 先对两种算法进行介绍，包括推导过程及运算性质，然后用MATLAB实现两种算法，再分别对两种算法进行运算时间对比，并分析时间长短的原因。 第一周 工 作 计 划 第二周 周一 接受任务并查阅资料 周一到周四上午学习相关知识 下午编周二到周五上午学习相关知识 下午编写程序上机调试程序编写 写程序上机调试程序 任务书 1. 谢平、王娜、林洪斌等，信号处理原理及应用。机械工业出版社，2008.10 2. 王宏，MATLAB 6.5 及其在信号处理中的应用。清华大学出版社，2004.10 3. Sanjit K.Mitra 著 孙洪、余翔宇等译，数字信号处理实验指导书。电子工业出版社 2005.1 参 考 资 料 指导教师签字 xxx 基层教学单位主任签字 xxx 说明：此表一式四份，学生、指导教师、基层教学单位、系部各一份。

2011 年 7 月 13 日

大神工程学院课程设计评审意见表

指导教师评语： 认真 正确完善 完善 较为合理 合理 工作态度 较认真 理论分析 一般 软件设计 一般 不认真 较差 较差 平时成绩： 指导教师签字： 年 月 日 图面及其它成绩： 答辩小组评语： 清晰 正确 基本掌握 优化设计 基本正确 原理 了解 不正确 不清楚 答辩成绩： 组长签字： 年 月 日 课程设计综合成绩： 答辩小组成员签字：

年 月 日

大神 大 学 课 程 设 计 说 明 书

摘 要

时域分析方法和频域分析方法是信号和系统的分析的两种方法，本文介绍离散信号和系统的频域分析方法，它和连续信号和系统的频域分析方法有所不同，但也有相似之处。本说明书主要是在介绍两种用于信号处理的傅里叶变换算法——DFT（离散傅里叶变换）和FFT（快速傅里叶变换），分别介绍了这两种运算的推导过程，并且对这两种变换作了简要的介绍，分析了各自的性质。然后通过MATLAB分别实现了这两种傅里叶变换，并对这两种变换进行了运算时间的比较——分别对同一函数进行DFT和FFT计算两者的运行时间，并作图比较。

本说明书的程序部分都是在MATLAB环境下进行的运算。MATLAB是矩阵实验室（Matrix Laboratory）的简称，是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。 MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多。在新的版本中也加入了对C，FORTRAN，C++ ，JAVA的支持，可以直接调用,用户也可以将自己编写的实用程序导入到MATLAB函数库中方便自己以后调用。

本文介绍了DFT与FFT的原理与Matlab实现程序，以及DFT与FFT的计算速度的比较。并用guide函数亲自编写了一个界面。

关键词：DFT、FFT、Matlab、运算速度、guide

共 14 页 第 1 页

大神 大 学 课 程 设 计 说 明 书

目录

摘 要 ..................................................................................................................................... 1 第一章 DFT原理与Matlab实现 ............................................................................................. 3

1.1 DFT的原理 ................................................................................................................... 3 1.2 DFT的Matlab实现 ..................................................................................................... 4 第二章 FFT的原理与Matlab实现 .......................................................................................... 6

2.1 FFT的原理 ................................................................................................................... 6

2.1.1 FFT的基本思想 ............................................................................................. 6 2.1.2 基2 FFT算法 ................................................................................................. 7 2.2 FFT的Matlab实现 ...................................................................................................... 9 第三章 DFT与FFT计算速度比较分析 ................................................................................ 12

3.1 FFT与直接计算DFT的比较 .................................................................................... 12 3.2 FFT与DFT运算时间Matlab程序 ........................................................................... 13

3.2.1随机序列的DFT计算时间程序 ..................................................................... 13 3.2.2分析两者运算时间的差异： .......................................................................... 16

第四章 心得体会 ..................................................................................................................... 18 参考文献： ............................................................................................................................... 19

共 14 页 第 2 页

大神 大 学 课 程 设 计 说 明 书

第一章 DFT原理与Matlab实现

1.1 DFT的原理

傅里叶变换就是在以时间为自变量的“信号”与以频率为自变量的“频谱”函数之间的某种变换关系。随时间自变量形式的不同，其傅里叶变换的形式也有不同：周期序列的离散傅里叶级数(DFS)和非周期序列的傅里叶变换(DTFT)，其表示式分别为：

N1n0j2nkNkDFSxneXnxX(e)DTFT[x(n)]j (1.1.1)

nx(n)ejn (1.1.2)

在实际工作中，当用数字计算机对信号进行频谱分析时，要求信号必须以有限长度的离散值作为输入，而计算所得的频谱值自然也是有限、离散的。上述两种形式的傅里叶变换中，DFS变换满足时、频域自变量的离散化，但其时间变量和频率变量又同时具有周期性；DTFT变换满足时间自变量的有限长度(非周期能量有限信号)，但其频率变量为连续形式。可见，这两种变换都难以实际应用。考虑到DFS变换的时、频域形式虽是周期序列，但每个周期却只有N个独立的复值，知道其一个周期的内容即可得到其它的内容。因此，若从DFS变换的时、频域各取出一个周期，即可构造出时间和频率自变量皆为离散、有限长度的傅氏变换，这就是离散傅里叶变换(DFT)的引出思想，下面进行具体推导。

设

xn是一个长度为M的有限长序列，由周期序列与有限长序列的本质联系，可以

xnN(NM)为周期将

展开为无重叠的周期序列，即周期延拓为

nx再利用式(1.1.1)对

rxnrN (1.1.3)

nxk(k(,))X进行DFS变换，得到周期离散的频谱，取

共 14 页 第 3 页

大神 大 学 课 程 设 计 说 明 书

kX的主值序列(k0,1,...,N1)，代入DFS反变换公式(4-3b)，即

2N1jkn1NxnIDFSXkXke (1.1.4) Nk0~分析可见：在DFS正变换中，只要把一个周期内的xn乘以对应的

ej2nkN(n0,1,...,N1)~~XXk，即可得任意k下的；同理，在DFS反变换中，仅用k的

一个周期的值(k0,1,...,N1)，即可得到任意n下的xn。如果同时限制(1.1.1)式中的n和(1.1.4)式中的k，使其都只在0~N1区间内取值，就得到了一个周期的xn和一个周期的Xk间的对应关系

~Xk1xnNxnWn0N1k0N1knN 0kN1 (1.1.5) 0nN1 (1.1.6)

XkWknNWe式中，Nj2N，N为DFT变换区间的长度，上两式即称为有限长序列的离散傅

里叶变换对。(1.1.5)式称为离散傅里叶变换，简称DFT；(1.1.6)式称为离散傅里叶逆变换(Inverse Discrete Fourier Transform)，简称IDFT。

1.2 DFT的Matlab实现程序

DFT函数：

function[xk]=dft(xn,N)

%计算离散傅里叶变换 %----------------- %[Xk]=dft(xn,N)

%Xk=在0<=k<=N-1间的DFT系数数组 %xn=N点有限长度序列 %N=DFT的长度

n=[0:1:N-1]; %n的行向量 k=[0:1:N-1]; %k的行向量

共 14 页 第 4 页

大神 大 学 课 程 设 计 说 明 书

WN=exp(-1i*2*pi/N); %Wn因子

nk=n'*k; %产生一个含nk值的N乘N维矩阵 WNnk=WN.^nk; %DFT矩阵

q=xn*WNnk; %DFT系数的行向量

对一个单位抽样序列的DFT变换（N=64）：

clear all; N=64;

x=zeros(1,N); x(1)=1; xn=0:N-1;

subplot(121),stem(xn,x); axis([-1 33 0 1.1]); XK=dft(xn,N); subplot(122); stem(abs(XK));

DFT Matlab处理结果：

共 14 页 第 5 页

大神 大 学 课 程 设 计 说 明 书

第二章 FFT的原理与Matlab实现

2.1 FFT的原理

DFT在数字信号处理中有很重要的作用，如频谱分析、线性卷积等，但由于直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(Fast Fourier Transform,简称FFT)出现前，直接用DFT进行谱分析和信号的实时处理是不切实际的。直到1965年库利(J．W Cooley)和图基(J．W．Tukey)提出了DFT运算的一种快速方法以后，情况才发生了根本的变化。多年来，人们不断改进和完善，形成了一系列新型FFT算法，如基2FFT算法、分裂基FFT算法、N为复合数的FFT算法等。

必须强调指出：FFT并不是与DFT不同的另外一种变换，而是为减少DFT计算次数的一种快速算法。为了解FFT高效算法的重要及实现思路，先介绍DFT的运算特点，再具体讨论高效算法。

2.1.1 FFT的基本思想

从哪些方面能改进DFT的运算以减少运算工作量呢? 如前所述，DFT的运算量是与

N2成正比的。显然，如果一个大点数N的DFT能分解为若干小点数DFT的组合，则

可达到减少运算工作量的效果。充分利用系数WN的下列固有周期性和对称性，使DFT运算中的有些项可以合并，从而使长序列的DFT分解为更小点数的DFT，提高运算效率。

kNn的对称性 WNknWNnknkWNknWN

kNnknNnknkWN的周期性 WNWN WN快速傅里叶变换算法正是基于上述基本思想而发展起来的。下面介绍最常用的基2

共 14 页 第 6 页

大神 大 学 课 程 设 计 说 明 书

mFFT算法(N2，库利一图基算法)。

2.1.2 基2 FFT算法

基2 FFT算法主要包括两类：按时间抽取(Decimation-in-time，简称DIT)法和按频率抽取(Decmation-in-Frequence，简称DIF)法，本文只介绍DIT算法。

m设xn是列长为Nn0,1,,N1的输入序列，且N2，其中m为整数。如果不

满足这个条件，可以人为地加入若干零点来达到。将xn按n的奇偶分成两个子序列

x2rx1rN r0,1,1 (2.1.1) 2x2r1x2r则(1.1.5)式可化为

XkDFTxnN21n偶数xnWN21N1nkNn奇数xnW2r1kN1nkN

r0x2rW2rkNr0x2r1WNN21N21r0x1rW2rkNWkNr0x2rW2rkN

由于WNe2j22Nje2N2WN，故上式又可表示为

2XkN21r0xrW1N21rkN2xrW2r0rkN2kX1kWNX2k k0,1,,N1 (2.1.2)

其中X1k和X2k分别是x1r及x2r的N2点的DFT

X1kX2kN21r0rkx1rWN2DFT[x1r] (2.1.3)

N21r0rkx2rWN2DFT[x2r] (2.1.4)

(2.1.2)式表明了—个N点的DFT被分解为两个N2点的DFT。但是这里有一个问

共 14 页 第 7 页

大神 大 学 课 程 设 计 说 明 书

题，即x1r，x2r的列长为N2，它们的DFTX1k，X2k的点数也是N2，即k0,1,N12，而Xk却有N个点，所以按(2.1.2)式计算得到的只是Xk

(k0,1,N1)的前一半项数的结果，要用X1kX2k来表达全部的Xk值还必须应用W系数的周期性，即

Nrk2N2W这样可得

NX1k2N21r0rkN2W

xrW1Nrk2N2N21xrW1r0rkN2X1k

同理可得

NX2kX2k 2k另外又考虑到WN的对称性

Nk2WNNWN2kk WNWN因此，将上述公式代入(2.1.2)中，Xk又可表达为

XkX1kWNkX2kNk0,1,N1 (2.1.5) 2kNNNNk2 XkXkWX2kX1kWNX2kk0,1,1 (2.1.6) 1N2222N0~12区间由上分析可见，只要求出X2kx(n)内各个整数k值所对应的X1k和X2k值，即

可求出0~N1区间内的全部Xk值，这一

点恰恰是FFT能大量节省计算的关键所在。

kWNX2kX1kWNkX2k图2.1.1 蝶形运算符号

式(2.1.5)、(2.1.6)的运算可用图2.1.1的信号流图符号表示，根据其形状称之为蝶形运算符号。

共 14 页 第 8 页

大神 大 学 课 程 设 计 说 明 书

依此类推得8点的DIT-FFT的运算流图如下：

x(1)

x(0)A(0)

A(0)

A(0)

A(0)

X(0)

A(1) A(1) 0WNA(1) X(1)

A(2)x(2)

A(2) W0NA(2) X(2)

A(3) A(3) x(3)

A(3) 2WNX(3)WA(4)0N x(4)

x(5)

0WNA(4) 2WNA(4) 0WNX(4)

A(5)A(5)A(5) 1WN2WNX(5)x(6)

A(6) 0WNA(6)

A(7)0WNA(6)X(6)A(7)x(7)

A(7)W3NA(7) X(7)

图 2.1.2 N点DIT-DFT运算流图（N=8）

2.2 FFT的Matlab实现程序

FFT函数：

function xn=myfft(x) N=length(x); M=log2(N);

xtmp=zeros(1,N); value=zeros(1,M); for i=0:N-1 repr=i; for t=1:1:M

repr=bitshift(i,1-t); value(t)=bitand(repr,1); end

共 14 页 第 9 页

大神 大 学 课 程 设 计 说 明 书

pos=0;

for k=1:1:M

pos=pos+value(k)*2^(M-k); end

xtmp(pos+1)=x(i+1); end

for i=1:M

deepth=2^(i-1); width=2^(M-i); for t=1:2^i:N

for k=1:deepth

tmp=xtmp(t+k-1); wn=width*(k-1);

xtmp(t+k-1)=tmp+exp(-j*2*pi*wn/N)*xtmp(t+k+deepth-1);

xtmp(t+k+deepth-1)=tmp-exp(-j*2*pi*wn/N)*xtmp(t+k+deepth-1); end end end

xn=xtmp;

对一个单位抽样序列的FFT变换（N=64）：

clear all; N=64;

x=zeros(1,N); x(1)=1; xn=0:N-1;

subplot(121),stem(xn,x); axis([-1 33 0 1.1]); XK=fft(xn); subplot(122); stem(abs(XK));

共 14 页 第 10 页

大神 大 学 课 程 设 计 说 明 书

FFT Matlab处理结果

共 14 页 第 11 页

大神 大 学 课 程 设 计 说 明 书

第三章 DFT与FFT计算速度比较分析

3.1 FFT与直接计算DFT的比较

对于N点的DFT，需要计算的复数乘法和复数加法次数分别是N²和N(N-1)。 由前面介绍的按时间抽取的FFT运算流图可见，每一级都由N2个蝶形运算构成。因此每一级运算都需要N2次复乘和N次复加(每个结加减各一次)。这样m级运算总共需要

复乘数 mF复加数

NNmlog2N 22aFNmNlog2N

FFT计算量与DFT计算量比较 N DFT 复数乘法次数 4 16 64 256 1024 4096 16384 65536 262144 1048576 4194304 16777216 67108864 复数加法次数 2 12 56 240 992 4032 16256 65280 261632 1047552 4192256 16733120 67100672 FFT 复数乘法次数 1 4 12 32 80 192 448 1024 2304 5120 11264 24576 53248 复数加法次数 2 8 24 64 160 384 896 2048 4608 10240 22528 49152 106496 DFT的乘法次数与FFT的乘法次数之比 4 4 5.3 8.0 12.8 21.3 36.6 64.0 113.8 204.8 372.4 682.7 1260.3 DFT的加法次数与FFT加法次数之比 1 1.5 2.3 3.75 6.2 10.5 18.1 31.9 56.8 102.3 186.1 341.3 630.0 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192

共 14 页 第 12 页

大神 大 学 课 程 设 计 说 明 书

3.2 FFT与DFT运算时间Matlab程序 3.2.1随机序列的DFT计算时间程序

Guide 程序下的主函数

set(handles.TITLE,'string','calculating......'); Nmax=str2num(get(handles.N,'string')); axes(handles.FFT_axes) cla;

axes(handles.DFT_axes) cla;

fft_time=zeros(1,Nmax); for n=1:1:Nmax x=rand(1,n); t=clock; my_fft(x);

fft_time(n)=etime(clock,t); end

n=[1:1:Nmax];

axes(handles.FFT_axes) plot(n,fft_time,'.'); xlabel('N');

ylabel('时间 (单位:秒)') title('FFT执行时间')

my_dft_time=zeros(1,Nmax); for n=1:1:Nmax x=rand(1,n); t=clock; my_dft(x,n);

my_dft_time(n)=etime(clock,t); end

n=[1:1:Nmax];

axes(handles.DFT_axes) plot(n,my_dft_time,'.'); xlabel('N');

ylabel('时间 (单位:秒) ') title(' DFT执行时间')

共 14 页 第 13 页

大神 大 学 课 程 设 计 说 明 书

set(handles.TITLE,'string','DFT_AND_FFT_TIME');

3.2.2 Matlab实验结果： Guide程序界面

运行结果

Nmax =128

共 14 页 第 14 页

大神 大 学 课 程 设 计 说 明 书

Nmax =512

N=1024

共 14 页 第 15 页

大神 大 学 课 程 设 计 说 明 书

N=2048

3.2.2分析两者运算时间的差异：

由前面介绍的按时间抽取的FFT运算流图可见，每一级都由N2个蝶形运算构成。因此每一级运算都需要N2次复乘和N次复加(每个结加减各一次)。这样m级运算总共需要

复乘数 mFNNmlog2N (4.3.45) 22复加数 aFNmNlog2N (4.3.46)

01[由运算流图可见，这种情况共有实际计算量和这个数字稍有出入，因为WN12422l1n0l1n21NlN1次]，WN21，WNN4j，这几个系数是都不

用乘法运算的，但这种情况在直接计算DFT中也是有的，且当N较大时，这些影响也较小。所以为了统一作比较我们不考虑以上特例。

共 14 页 第 16 页

大神 大 学 课 程 设 计 说 明 书

综上所述，可以得出如下结论；按时间抽取法所需的复乘数和复加数都是与

Nlog2N成正比的，而直接计算DFT时所需的复乘数为N2，复数加为N(N-1)次。当

N>1时，

，从而，DIT-FFT算法比直接计算DFT的运算次数大大减小。

例如N2101024时，

N21048576204.8(N/2)log2N5120这样，就使运算效率提高200多倍。图4.3.16为FFT算法和直接DFT算法所需运算量与计算点数N的关系曲线。由此图更加直观地看出FFT算法的优越性，显然，N越大时，优越性就越明显。随着运算次数的减少，FFT的运算时间明显减少。

乘法次数(×1000) 1024

DFT算法 512

FFT算法 256 128 64 0

64 128 256 512 N(取样点数)

1024 图 3.2.2 FFT算法与直接计算DFT

所需乘法次数的比较曲线

共 14 页 第 17 页

大神 大 学 课 程 设 计 说 明 书

第四章 心得体会

紧张而又兴奋的两周数字信号处理课程设计，令我成长很多。先在图书馆里查找了相关的书籍，如MATLAB类的编程书籍，各类信号处理类的书籍等，即丰富了自己的知识范围，又对与自己所学的知识有了更深的了解和认识，同时也对它的应用有了一个大体的认识。

两周的课程设计，从拿到题目分析题目到编制相应程序、调试程序，其间的确遇到了不少难题，但通过老师的耐心辅导、与同组成员的互相讨论，终于将问题各个击破，完成了此次课设要求。

在设计的过程中，我深刻认识到了自己所学知识的不足。这也让我再次认识到知识是无尽的，只有不断的充实自己、完善自己的知识理论体系，才能够更好的胜任自己以后的工作。

在整个课程设计的过程中，我得到了其他其他同学的帮助，也帮助其他小组分析设计题目，不仅扩展大了自己的锻炼空间，也加强了我与其他同学合作的能力。查找资料的过程中我也增强自己学习的能力。真真正正的提高了我遇到问题分析问题解决问题的能力。这些都是我在以后的学习、生活和工作中的宝贵财富。

共 14 页 第 18 页

大神 大 学 课 程 设 计 说 明 书

参考文献：

1. 谢平、王娜、林洪斌等，信号处理原理及应用。机械工业出版社，2008.10 2. 王宏，MATLAB 6.5 及其在信号处理中的应用。清华大学出版社，2004.10

3. Sanjit K.Mitra 著 孙洪、余翔宇等译，数字信号处理实验指导书。电子工业出版社

2005.1

4. 薛年喜，MATLAB在数字信号处理中的应用（第二版）。清华大学出版社，2008.1 5. 陈亚勇等，MATLAB信号处理详解。人民邮电出版社，2001.6

共 14 页 第 19 页