第4章快速傅里叶变换(FFT)本章主要内容直接计算DFT的问题及改进的途径按时间抽取的基2-FFT算法按频率抽取的基2-FFT算法快速
傅里叶逆变换(IFFT)算法4.1引言DFT在实际应用中很重要:可以计算信号的频谱、功率谱和线性卷积等。直接按DFT变换进
行计算，当序列长度N很大时，计算量非常大，所需时间会很长。FFT并不是一种与DFT不同的变换，而是DFT的一种快速计算的算法。4
.2.1直接计算DFT的问题及改进的途径DFT的运算量设复序列x(n)长度为N点，其DFT为k=0，，…，N-1（1）计算
一个X(k)值的运算量复数乘法次数：N复数加法次数：N－1DFT的运算量（2）计算全部N个X(k)值的运算量复数乘法次数：
N2复数加法次数：N(N－1)（3）对应的实数运算量DFT的运算量一次复数乘法：4次实数乘法＋2次实数加法一个X(k)
：＋4N次实数乘法2N+2(N-1)=2(2N-1)次实数加法所以整个N点DFT运算共需要：实数乘法次数：4N2实数加法次
数：N×2(2N-1)=2N(2N-1)DFT运算量的结论N点DFT的复数乘法次数举例NN2NN2246440494161281
6384864256655361625651226214432102810241048576结论：当N很大时，
其运算量很大，对实时性很强的信号处理来说，要求计算速度快，因此需要改进DFT的计算方法，以大大减少运算次数。减少运算工作量的途径
主要原理是利用系数的以下特性对DFT进行分解：（1）对称性（2）周期性（3）可约性另外，4.2.2按
时间抽取的基2-FFT算法算法原理按时间抽取基-2FFT算法与直接计算DFT运算量的比较按时间抽取的FFT算法的特点按时间抽取F
FT算法的其它形式流程图算法原理设N＝2L，将x(n)按n的奇偶分为两组：r=0，1，…，则算法原理式中，X1(k)
和X2(k)分别是x1(n)和x2(n)的N/2的DFT。另外，式中k的取值范围是：0，1，…，N/2－1。算法原理因此，
只能计算出X(k)的前一半值。后一半X(k)值，N
/2，N/2＋1，…，N？利用可得到同理可得算法原理考虑到及前半部分X(k)k=0，1，…，N/2－1因此可
得后半部分X(k)k=0，1，…，N/2－1蝶形运算蝶形运算式蝶形运算信号流图符号蝶形运算符号因此，只要求出2个N/2点的
DFT，即X1(k)和X2(k)，再经过蝶形运算就可求出全部X(k)的值，运算量大大减少。以8点为例第一次按奇偶分解以N=8为例，
分解为2个4点的DFT，然后做8/2=4次蝶形运算即可求出所有8点X(k)的值。图4.2.28点DFT一次时域抽取分解运算流图
蝶形运算量比较N点DFT的运算量复数乘法次数：N2复数加法次数：N(N－1)分解一次后所需的运算量＝2个N/2的DFT＋N/
2蝶形：复数乘法次数：2(N/2)2+N/2=N2/2+N/2复数加法次数：2(N/2)(N/2－1)+2N/2=N2/
2因此通过一次分解后，运算工作量减少了差不多一半。进一步按奇偶分解由于N＝2L，因而N/2仍是偶数，可以进一步把每个N/2点
子序列再按其奇偶部分分解为两个N/4点的子序列。以N/2点序列x1(r)为例则有k=0,1,…,进一步按奇偶分解且k=0,
1,…,由此可见，一个N/2点DFT可分解成两个N/4点DFT。同理，也可对x2(n)进行同样的分解，求出X2(k)。图4.
2.38点DFT二次时域抽取分解运算流图算法原理对此例N=8，最后剩下的是4个N/4=2点的DFT，2点DFT也可以由蝶形
运算来完成。以X3(k)为例。k=0,1即/4/4这说明，N=2M的DFT可全部由蝶形运算来完成。以8点为例第三次按奇偶分解图
4.2.48点DIT-FFT运算流图4.2.3DTF-FFT算法与直接计算DFT运算量的比较L由按时间抽取法FFT的信号流
图可知，当N=2L时，共有级蝶形运算；每级都由个蝶形运算组成，而每个蝶形有次复乘、次复加，因此每级运算都需次复乘和次
复加。N/212N/2NDTF-FFT算法与直接计算DFT运算量的比较L这样级运算总共需要：复数乘法：复数加法：直接D
FT算法运算量复数乘法：N2复数加法：N(N－1)直接计算DFT与FFT算法的计算量之比为MDIT-FFT算法与直接DFT算
法运算量的比较NN2计算量之比MNN2计算量之比M2414.01281638444836.641644.025665536
102464.0864125.45122621442304113.816256328.0102410485765120
204.83210288012.82048419430411264372.464404919221.40≤n≤0≤n≤后半子
序列4.2.5按频率抽取的基2-FFT算法算法原理先把输入按n的顺序分成前后两半再把输出X(k)按k的奇偶分组设序列长度为N
=2L，L为整数前半子序列x(n)算法原理由DFT定义得k=0，1，…，N算法原理由于所以则k=0，1，…，Nr=0
，1，…，算法原理然后按k的奇偶可将X(k)分为两部分则式可转化为r=0，1，…，n=0，1，…，算法原理令代入可
得为2个N/2点的DFT，合起来正好是N点X(k)的值。蝶形运算将称为蝶形运算与时间抽选基2FFT算法中的蝶形运算符号略有不同。例
按频率抽取(N=8)例按频率抽取，将N点DFT分解为两个N/2点DFT的组合(N=8)例按频率抽取(N=8)与时
间抽取法的推导过程一样，由于N=2L，N/2仍然是一个偶数，因而可以将每个N/2点DFT的输出再分解为偶数组与奇数组，这就将N/
2点DFT进一步分解为两个N/4点DFT。N=8例频率抽取IFFT流图(N=8)4.2.6IDFT的高效算法4.3
进一步减少运算量的措施-实序列的FFT算法在实际工作中，数据x(n)常常是实数序列。如果直接按FFT运算流图计算，就是把x(n
)看成一个虚部为零的复序列进行计算，这就增加了存储量和运算时间。处理该问题的算法有三种：1.用一个N点FFT计算两个N点实序列的FFT，一个实序列作为x(n)的实部，另一个作为虚部，计算FFT，根据DFT的共轭对称性，用例3.2.2所述方法输出X(k)分别得到两个实序列的N点DFT；2.用N/2点FFT计算一个N点实序列的DFT（自己练习）；3.用离散哈特莱变换（DHT）。 |
|
