DFT的计算量

liyf

DFT的计算量
离散傅里叶变换在实际应用中是非常重要的，利用它可以计算信号的频谱、功率谱和线性卷积等。但是，如果使用定义式(3.20)来直接计算DFT，当N很大时，即使使用高速计算机，所花的时间也太多。因此，如何提高计算DFT的速度，便成了重要的研究课题。1965年库利 (Cooley)和图基(Tukey)在前人的研究成果的基础上提出了快速计算DFT的算法，之后，又出现了各种各样快速计算DFT的方法，这些方法统称为快速傅里叶变换(FastFourier Transform)，简称为FFT。FFT的出现，使计算DFT的计算量减少了两个数量级，从而成为数字信号处理强有力的工具。
快速傅里叶变换(FFT)是离散傅里叶变换(DFT)的快速算法。它是DSP领域中的一项重大突破，它考虑了计算机和数字硬件实现的约束条件、研究了有利于机器操作的运算结构，使DFT的计算时间缩短了1"2个数量级，还有效地减少了计算所需的存储容量，FFT技术的应用极大地推动了DSP的理论和技术的发展。
在导出FFT算法之前，首先来估计一下直接计算DFT所需的计算量。
DFT的定义



将DFT定义式展开成方程组
将方程组写成矩阵形式



用复数表示：



FFT算法是基于可以将一个长度为N的序列的离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算这一基本原理的。这一原理产生了许多不同的算法，但它们在计算速度上均取得了大致相当的改善。
在本章中我们集中讨论两类基本的FFT算法。
第一类 称为按时间抽取(Decimation-in-Time)的基2FFT算法，它的命名来自如下事实：在把原计算安排成较短变换的过程中，序列x(n)(通常看作是一个时间序列)可逐次分解为较短的子序列。
第二类称为按频率抽取(Decimation-in-Frequency)的基2FFT算法，在这类算法中是将离散傅里叶变换系数序列X(k)分解为较短的子序列。

前面两种算法特别适用于N等于2的幂的情况。
对于N为合数的情况，本章也将介绍两种处理方法。
离散傅里叶变换及其快速算法