关于DFT与FFT运算速度的比较.doc

第 PAGE 5 页 共 NUMPAGES 10 页 离散傅里叶变换 赵德华 （哈尔滨工业大学 电子与信息工程学院 0705201班） 摘要：本文简要介绍了DFT的原理及其FFT实现算法。以实例验证DFT与FFT的等效性，并在VC6.0环境下对DFT与FFT的计算时间做了系统比较，验证理论得出的关系。 关键词：DFT，FFT，计算速度，C程序 Discrete Fourier Transform? Zhao Dehua (Electronics and Information Department, Harbin Institute of Technology) Abstract：This paper briefly introduces the principle of DFT and FFT.It verifies the equivalent of DFT and FFT with sevel examples.It also comples the elapsed time of DFT and FFT in VC6.0 to verify the theory. Key words: DFT, FFT, calculating speed , C program 目录 0.引言…………………………………………………………………………………………………………………………………………………………1 1.DFT与FFT的定义………………………………………………………………………………………………………………………………..1 2.DFT与FFT等价性验证………………………………………………………………………………………………………………………..2 3.DFT与FFT运算速度比较…………………………………………………………………………………………………………………….3 4.总结………………………………………………………………………………………………………………………………………………………..6 参考文献……………………………………………………………………………………………………………………………………………………6 0.引言 离散傅里叶变换（Discrete Fourier Transform），是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换（DTFT）频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作经过周期延拓成为周期信号再作变换。离散傅里叶变化的出现解决了信号离散化的问题，从而使其在数字滤波、功率谱分析、仿真、系统分析、通信方面得以应用。 快速傅里叶变换（Fast Fourier Transform），是离散傅里叶变换的快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。由于它应用的理论基础仍是离散傅里叶变换，所以它对离散傅里叶变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。 快速傅里叶变化最早于1965年由Cooly和Tukey提出，这使离散傅里叶变化运算次数由N2减少为Nlog2N次，使得离散傅里叶变换应用于实际变成现实。目前，快速傅里叶变化技术已广泛应用于各个领域，成为数字信号处理技术的一个重要组成部分。离散傅里叶变化除了本文介绍的基2快速傅里叶变化算法外，他们都不同程度上减少了运算次数，如戈泽尔（Goertzel）算法、Chirp-Z变化（CZT）算法、Winograd Fast Transform Alogrithm（WFTA）等。本文将仅介绍基2快速傅里叶变化。 DFT与FFT的定义 DFT的定义：设是连续函数的个抽样值，这N个点的宽度为N的DFT为：。与之对应的反变换，即IDFT的定义：设是连续频率函数的个抽样值， 这N个点的宽度为N的IDFT为：。其中称为N点DFT的变换核函数，称为N点IDFT的变换核函数。它们互为共轭。如果引入，正逆变换的核函数分别可以表示为和。DFT可以表示为：，IDFT可以表示为：。 用FFT实现DFT：先设序列点数为N=2M，M为整数。如果不满足这个条件，可以人为地加上若干零值点，使之达到这一要求。这种N为2的整数幂的FFT称基2 FFT。设输入序列长度为N=2M 2 FFT的运算流图： 图1-1 下面对两种变化的运算量进行比较。设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次