1、 DFT 与 FFT 在实际应用时的性能比较许磊 （通信 2 班）摘 要:分析了离散傅立叶变换(DFT)和它的快速算法(FFT)的计算,对 DFT 和 FFT 在应用时的特点作了深入的比较,提出在某些实际应用场合 DFT 比它的快速算法 FFT 更有优势 .关键词:离散傅立叶变换;快速傅立叶变换;频谱分析快速傅立叶变换(FFT)是离散傅立叶变换(DFT)的快速算法,FFT已在数字信号处理的场合中得到非常广泛的应用.一般情况下在需要计算频谱的时候,往往首先会考虑采用 FFT,假如在使用 FFT 时会发现它在某些情况下存在一些局限性,则会退一步考虑 DFT 是否可以避免这些局限性,通过进一步分析比
2、较及实际应用表明其答案是肯定的.1 DFT 与 FFT 的算法 1DFT 是连续傅立叶变换的离散形式,其计算公式为X(k) = x(n)WnkN, k =0,1, ,N-1 n=0,1, ,N-1式中 x(n)为输入信号的时域采样序列,X(k)为计算输出信号的频域采样序列,其中 Wnk=j2nk/N=cos(2nk/N)-jsin(2 nk/N).从 DFT 的计算公式可看出对 N 点的 DFT 需计算 N2 个复数乘和 N2 个复数加运算.FFT 是 DFT 的快速算法 ,其原理是将长序列 DFT 根据其内在的对称性和周期性分解为短序列的 DFT 之和.N 点的 DFT 先分解为 2个 N/
3、2 点的 DFT,每个 N/2 点的 DFT 又分解为 N/4 点的 DFT.最小变换的点数即所谓 FFT 的“基数”.因此,基数为 2 的 FFT 最小变换是2 点 DFT(或称蝶形运算).在基数为 2 的 N 点 FFT 中,设 N=2M,则总共可分成 M 级运算,每级中有 N/2 个蝶算,则 N 点 FFT 总共有(N/2)log2N 个蝶算,而 1 个蝶算只需一个复数乘法,2 个复数加法,因此对 N点 FFT 需计算(N/2)log2N 个复数乘法、Nlog2N 个复数加法.2 DFT 与 FFT 的比较(1)运算量 一般来说,FFT 比 DFT 运算量小得多,N 点的 FFT需要做(
4、N/2)log2N 次乘法运算,而 N 点 DFT 需要做 N2 次乘法运算,由此看来 N 点 DFT 运算量大约是 FFT 的 2N/log2N 倍,例如对 1 024点的变换,DFT 大约是 FFT 的 200 倍.然而实际应用时存在下列情况 :实际应用时 DFT 中的乘法可以是实数和复数相乘,原因是输入信号可以是实数,而 FFT 只能是复数和复数的乘法,原因是 FFT 是分级运算的,中间运算过程都是复数运算,由此来看 DFT 的运算量大约是 FFT 的 Nlog2N 倍, 而不是 2N/log2N 倍.实际应用时往往只关心整个频谱中的某一部分,甚至是只关心某些个别频点的谱线.DFT 的特
5、点是可按式(1)单独计算某一部分的谱线,而直接进行 FFT 的算法必须计算整个频谱后才能得到需要的那一部分频谱,实际上已造成了浪费.如果 N 点的变换中只关心其中的 M个频点或称 M 条谱线,那么实际 DFT 的运算量大约是 FFT 的M/NN/log2N 倍,即 Mlog2N 倍.例如对 1 024 点的变换,只需关心 10条谱线,那么直接用 DFT 和用 FFT 的运算量是相同的 .因此,实际应用时 DFT 与 FFT 相比可能并没有那么慢 ,甚至有可能比 FFT 快.(2)点数或采样率的可选性 对 DFT 来讲,其变换点数可任意选定,如实际应用时采样率已确定为 1 000 Hz,如选变换
6、点数为 1 000 点,那么每条谱线正好可落在整数频点上.FFT 的变换点数必须是有规律的,如基数为 2 算法的 FFT 其点数必须是 2M,如 1 024 点、4 096 点等.在实际应用时为分析方便,采样率往往要定为变换点数的倍数,如 2 048 Hz、8 192 Hz,以避免变换后的频谱落在复杂的带小数点的频点上.因此实际应用时 FFT 在变换点数选择或采样率选择上可能会带来局限性.(3)实时性 DFT 运算可以用采一点后立即进行相乘、累加运算的方法,即可以采一点算一点,从采样结束到 DFT 变换结束只需要一个点的运算时间.而 FFT 运算必须在全部点采集结束后才能开始进行计算,因此从某
7、种角度讲 DFT 的实时性优于 FFT.(4)数据内存开销 对 N 点 DFT 来讲,如只需其中的 M 个频点,那么在计算时至少需 2M 个单元的数据内存,对 N 点 FFT 来讲则至少需 2N 个单元的数据内存,另外现有的 FFT 程序一般需要将系数放在数据内存区,因此需另选 N 个单元的数据内存 ,故 DFT 有可能比 FFT更节省数据内存.(5)程序的复杂性 DFT 计算程序非常简单而且可以非常方便地在非 DFT 专用芯片上实现,而 FFT 程序较为复杂 .(6)动态范围或抗溢出性 在定点运算的场合,DFT 较 FFT 更容易实现多精度的运算, 例如在 TI 公司的 16 位定点 DSP
8、 处理器中,采用的数据和系数为 16 位,而相乘并累加的结果可设为双字节即 32 位,一般来讲设计合理的话不会产生计算溢出的现象,免去了复杂的溢出控制,同时输入输出信号可保持较好的动态范围.FFT 在程序中有防溢出的措施,然而在定点运算的场合点数越多输入信号的动态范围越小.3 结论在某些具体的应用场合,DFT 与它的快速算法 FFT 相比可能更有优势,而 FFT 却存在某些局限性.在只需要求出部分频点的频率谱线时 DFT 的运算时间大为减少,所需的数据内存量也大为减小.DFT 与FFT 相比还具有变换点数或采样率选择更灵活、实时性更好、更容易控制溢出和动态范围、运算编程简单、可方便地在非 DSP 芯片中编程实现等优点.因此在实际应用中可以从具体条件出发来比较、选择 DFT 或 FFT,而不应片面地由于 FFT 是所谓的 DFT 的快速算法而只选用 FFT.参考文献:1吴湘淇 .数字信号处理技术及应用M. 北京: 中国铁道出版社,1986.332-516.2张雄伟 .DSP 芯片的原理与开发应用M.北京:电子工业出版社,1997.210-223.3胡广书 .数字信号处理理论、算法与实现M.北京: 清华大学出版社,1997.55-934奥本海姆 A V,谢弗 R W.离散时间信号处理M.北京: 科学出版社,1999.426-438
