/NJIANG UNIVERSITY 3.3DFT快速算法-FFT
3.3 DFT快速算法-FFT
引言 快速傅里叶变换(FFT)是计算DFT的一种 快速有效方法。从前面的讨论中看到，有限长 序列在数字技术中占有很重要的地位。有限长 序列的一个重要特点是其频域也可以离散化， 即离散傅里叶变换(DFT)
引言 快速傅里叶变换（FFT）是计算DFT的一种 快速有效方法。从前面的讨论中看到，有限长 序列在数字技术中占有很重要的地位。有限长 序列的一个重要特点是其频域也可以离散化， 即离散傅里叶变换（DFT）
虽然频谱分析和DFT运算很重要，但在很长 一段时间里，由于DFT运算复杂，并没有得到真 正的运用，而频谱分析仍大多采用模拟信号滤 波的方法解决，直到1965年首次提出DFT运算的 一种快速算法以后，情况才发生了根本变化， 人们开始认识到DFT运算的一些内在规律，从而 很快地发展和完善了一套高速有效的运算方 法一快速付里变换（FFT)算法。FFT的出现， 使DFT的运算大大简化，运算时间缩短一心二个 数量级，使DFT的运算在实际中得到广泛应用
虽然频谱分析和DFT运算很重要，但在很长 一段时间里，由于DFT运算复杂，并没有得到真 正的运用，而频谱分析仍大多采用模拟信号滤 波的方法解决，直到1965年首次提出DFT运算的 一种快速算法以后，情况才发生了根本变化， 人们开始认识到DFT运算的一些内在规律，从而 很快地发展和完善了一套高速有效的运算方 法——快速付里变换（FFT）算法。FFT的出现， 使DFT的运算大大简化，运算时间缩短一～二个 数量级，使DFT的运算在实际中得到广泛应用
DFT运算量 首先分析有限长序列x(n)进行一次DFT运算所需的运 算量。 N-1 (k)=DFI[x(n】=∑x(n)w k=0,1,.,N-1 一般，x(n)和wk、都是复数，因此，每计算一个X(k)值 要进行N次复数相乘，和N-1次复数相加，X(k)一共有N个 点，故完成全部DFT运算，需要NP次复数相乘和N(N-1)次复数 相加，在这些运算中，乘法比加法复杂，需要的运算时间多， 尤其是复数相乘，每个复数相乘包括4个实数相乘和2个实数相 加，例 X()=∑{R[(mR]-I[x(n].w]+k[x(n肛]+I[mR 又每个复数相加包括2个实数相加，所以，每计算一个 X(k)要进行4N次实数相乘和2N+2(N-1)=2（2N-1)次实数 相加，因此，整个DFT运算需要4N2实数相乘和2N(2N-1) 数相加
DFT运算量 首先分析有限长序列 x（n）进行一次DFT运算所需的运 算量。 一般，x（n）和w nk N都是复数，因此，每计算一个X（k）值 ，要进行N次复数相乘，和N-1次复数相加，X（k）一共有N个 点，故完成全部DFT运算，需要N 2次复数相乘和N（N-1）次复数 相加，在这些运算中，乘法比加法复杂，需要的运算时间多， 尤其是复数相乘，每个复数相乘包括4个实数相乘和2个实数相 加，例 又每个复数相加包括2个实数相加，所以，每计算一个 X（k）要进行4N次实数相乘和2N+2（N-1）=2（2N-1）次实数 相加，因此，整个DFT运算需要4N 2实数相乘和2N（2N-1）次实 数相加
从上面的分析看到，在DFT计算中，不论是乘法和 加法，运算量均与N2成正比。因此，N较大时，运 算量十分可观。例，计算N=10,点的DFT,需要100 次复数相乘，而N=1024,点时，需要1048576（一百 多万)次复数乘法，如果要求实时处理，则要求 有很高的计算速度才能完成上述计算量。 反变换IDFT与DFT的运算结构相同，只是多乘 一个常数1N,所以二者的计算量相同
从上面的分析看到，在DFT计算中，不论是乘法和 加法，运算量均与N 2成正比。因此，N较大时，运 算量十分可观。例，计算N=10点的DFT，需要100 次复数相乘，而N=1024点时，需要1048576（一百 多万）次复数乘法，如果要求实时处理，则要求 有很高的计算速度才能完成上述计算量。 反变换IDFT与DFT的运算结构相同，只是多乘 一个常数1/N，所以二者的计算量相同