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

离散傅里叶变换

赵德华

（哈尔滨工业大学 电子与信息工程学院 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快速傅里叶变化。

1. DFT与FFT的定义

DFT的定义：设h?nTs?是连续函数h(t)的N个抽样值n?0,1,?,N?1，这N个点的宽度为N的DFT为：

第 1 页 共 10 页

DFTN?h(nTs)??N?1??kh(nTs)e?j2?nk/N?H??NTs?n?0??k???,(k?0,1,...,N?1)。H与之对应的反变换，即IDFT的定义：设?NT?s??k?0,1,?,N?1????是连续频率函数

??1DFTN?H???k???NTs??1???????NH(f)N?1的N个抽样值， 这N个点的宽度为N的IDFT为：

?kH??NTsk?0????j2?nk/N??e?h?nTs?,(k?0,1,..N.,?1)。其中e?j2?nk/N称为N点DFT的变换核函数，??N?1ej2?nk/N称为N点IDFT的变换核函数。它们互为共轭。如果引入WN?e?j2?/N，正逆变换的核函数分别可以

nknk?nk?表示为WN和WN。DFT可以表示为：H??NT???h(nTs)WN,?s?n?0?k?(k?0,1,?,N?1)，IDFT可以表示为：

h(nTs)?1NN?1k?0??nk?H??NT?WN,?s??k?(n?0,1,?,N?1)。

用FFT实现DFT：先设序列点数为N=2M，M为整数。如果不满足这个条件，可以人为地加上若干零值点，使之达到这一要求。这种N为2的整数幂的FFT称基2 FFT。设输入序列长度为N=2M (M为正整数) ，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为按时间抽取(DIT )的FFT算法。下面给出8点基 2 FFT的运算流图：

图1-1

下面对两种变化的运算量进行比较。设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数

2

加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N次运算。当N=1024点甚至更多的

2

时候，需要N=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正

2

整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）次运算，再用N次运算把两个N/2

22

点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成2*（N/2）=N/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。

2. DFT与FFT等价性验证

第 2 页 共 10 页

如上面论述的，FFT只是DFT的快速实现算法，它仍是以DFT为理论基础的，因此他们两者完全等价。这里将在VC6.0下编制DFT与FFT 的程序，用其对两组离散序列进行变化，并输出变换结果。

矩形脉冲信号，序列长64，其中前16点为1，其余为0。其DFT与FFT前5点输出如下图：

图2-1

正弦脉冲信号，序列长61，数字角频率为PI/2。其DFT与FFT前5点输出如下图：

图2-2

比较可以发现用DFT和FFT对同一序列变化得到的结果是完全一样的。这说明DFT与FFT是完全等价的，而区别仅在于其具体算法。

3. DFT与FFT运算速度比较

如上面介绍的，N点DFT需进行N次运算，而N（N=2）点FFT只需要Nlog2N次运算。因此DFT的运算时间与FFT的运算时间比应为：N/log2N。这里将对上述结论在数量级层次进行验证。

为了严谨，这里先验证DFT与FFT运算时间仅与N有关，而与具体信号类型无关。这里分别对128点、256点、512点矩形脉冲信号和正弦脉冲信号进行DFT与FFT变换，运算时间如图：

2

M

图3-1

图3-2

图3-3

可以看出，对不同类型信号进行DFT与FFT变换，只要其点数相同，其运算时间也是大致相同的。考虑到C程序计时并不如汇编等机器语言准确，且100次重复计算会对每次运算时间之差进行累加，上面3次试验反映出的时间差是可以忽略的。由此可见，DFT与FFT运算时间仅与运算点数N有关，而与具体信

第 3 页 共 10 页

号类型无关。

当信号点数较多时，对不同类型信号进行DFT与FFT变化将花费大量时间，而上面已经验证DFT与FFT运算时间仅与N有关，而与具体信号类型无关。故下面将仅对同一类型不同点数信号的DFT与FFT的运算时间的比较，而这也具有一般代表性。

下面将仅对不同点数正弦信号做DFT与FFT变化，并进行运算时间比较。由于C程序中计时受机器滴

2

答时间限制，故对点数较小信号进行较多次数DFT与FFT变换。而当点数较多时，DFT运算时间将按N规律增长，故对点数较多信号进行较少次数DFT与FFT变换。各次DFT与FFT运算时间如下诸图：

图3-4

图3-5

图3-6

图3-7

图3-8

图3-9

图3-10

图3-11

第 4 页 共 10 页

图3-12

图3-13

图3-14

图3-15

图3-16

图3-17

+n

下面对以上数据进行整理分析。 （注：e+n表示*10） N 变换次数 TDFT/s TFFT/s mean(TDFT)/s mean(TFFT)/s TDFT/TFFT 理论比值 2 10000 0.032 0.031 3.2e-6 3.1e-6 1.03 2 4 10000 0.156 0.063 1.56e-5 6.3e-6 2.48 2 8 1000 0.062 0.016 6.2e-5 1.6e-5 3.875 2.67 16 1000 0.25 0.047 2.5e-4 4.7e-5 5.32 4 32 1000 1.016 0.109 1.016e-3 1.09e-4 9.32 6.4 64 100 0.406 0.016 4.06e-3 1.6e-4 25.38 10.67 128 100 1.703 0.063 1.703e-2 6.3e-4 27.03 18.29 256 100 6.609 0.141 6.609e-2 1.41e-3 46.87 32 512 100 26.218 0.313 2.6218e-1 3.13e-3 83.76 56.89 1024 10 10.531 0.063 1.0531 6.3e-3 167.16 102.4 2048 10 42.172 0.156 4.2172 1.56e-2 270.33 186.18 4096 10 167.047 0.344 1.67047e+1 3.44e-2 485.60 341.33 8192 1 67.141 0.078 6.7141e+1 7.8e-2 860.78 630.15 16384 1 267.485 0.156 2.67485e+2 1.56e-1 1714.65 1170.29 表3-1 在Matlab中对以上数据绘图如下：

第 5 页 共 10 页

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