/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，所以二者的计算量相同
2、FFT算法的基本思想 考察DFT与IDFT的运算发现，利用以下两个特性可减少运算 量： 1)系数=e 是一个周期函数，它的周期性和 对称性可用来改进运算，提高计算效率。 例wN-)=wWN-0=wW 又如w2=-因w2》=-w 利用这些周期性和对称性，使DFT运算中有些项可合并； 2)利用wW心的周期性和对称性，把长度为N点的大点数的 DFT运算依次分解为若千个小点数的DFT。因为DFT的计算量正 比于N2,N小，计算量也就小。 F℉T算法正是基于这样的基本思想发展起来的。它有多种形 式，但基本上可分为两类：时间抽取法和频率抽取法
2、FFT算法的基本思想 考察DFT与IDFT的运算发现，利用以下两个特性可减少运算 量： 1）系数 是一个周期函数，它的周期性和 对称性可用来改进运算，提高计算效率。 例 又如 因此 利用这些周期性和对称性，使DFT运算中有些项可合并； 2）利用 的周期性和对称性，把长度为N点的大点数的 DFT运算依次分解为若干个小点数的DFT。因为DFT的计算量正 比于N 2 ，N小，计算量也就小。 FFT算法正是基于这样的基本思想发展起来的。它有多种形 式，但基本上可分为两类：时间抽取法和频率抽取法
3.3 FFT算法具体实现
3.3 FFT算法具体实现
一、按时间抽取的FFT(N,点DFT运其的分解》 先从一个特殊情况开始，假定N是2的整数次方（基2） N=2M,M:正整数 首先将序列x()分解为两组，一组为偶数项，一组为奇数项， x(2r)=x() r=0,1,.,N/2-1 x(2r+1)=x2(r)
一、按时间抽取的FFT（N点DFT运算的分解） 先从一个特殊情况开始，假定N是2的整数次方（基2） N=2M ，M：正整数 首先将序列x（n）分解为两组，一组为偶数项，一组为奇数项， r=0,1，.，N/2-1
将DFT运算也相应分为两组： x(K)=DFT(m]=∑xn)w n=0 偶数n=0 奇数n=1 N/2 W/2-1 ∑x(2rw+∑x(2r+1)wr+ r=0 r=0 N/2- N/2-1 ∑x(2r)w+w∑x(2r+1w r三0 r三0
将DFT运算也相应分为两组：
21 2元 2n 因为 =e =e =w 故 N/2-1 N/2-1 X(k)=∑x(2m)w*+T∑2r+1W 2 =G(k)+WH(k) 其中 N/2-1 Gk)=∑(2r)w N/2-1 A(k)=∑x(2r+w r=0 AN
因为 故 其中