数字信号处理教程 (第三版)程佩青 清华大学出版社dsp-ch4-2

§4.4按频率抽取（DIF）的FFT算法1、算法原理设序列点数N=2L，L为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半：

按k的奇偶将X(k)分成两部分：令则X(2r)和X(2r+1)分别是x1(n)和x2(n)的N/2点DFT，记为X1(k)和X2(k)-1-1-1-1WWWWNNNN0123N=8时,按k的奇偶分解过程先蝶形运算，后DFT:N/2仍为偶数，进一步分解：N/2N/4x3(0)x3(1)-1-1x4(0)x4(1)N/4点DFTN/4点DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)按照以上思路继续分解，即一个N/2的DFT分解成两个N/4点DFT，直到只计算2点的DFT，这就是DIF-FFT算法。同理：其中：逐级分解，直到2点DFT当N=8时，即分解到x3(n)，x4(n)，x5(n)，x6(n)，n=0,1

(0)X(0)

(1)X(4)

(2)X(2)

(3)X(6)

(4)X(1)

(5)X(5)

(6)X(3)

(7)X(7)-1-1-1-1WWWWNNNN0123-1-1-1-1WWWWNNNN0202-1-1-1-1WWWWNNNN0000例如N=8时DIF的FFT流图如下：2、算法特点1）原位计算-1L级蝶形运算，每级N/2个蝶形，每个蝶形结构：

m表示第m级迭代，k，j表示数据所在的行数2）蝶形运算对N=2L点FFT，输入自然序，输出倒位序，两节点距离：2L-m=N/2m第m级运算：

蝶形运算两节点的第一个节点的k值，表示成L位二进制数，左移m-1位，把右边空出的位置补零，结果为r的二进制数。存储单元输入序列x(n):N个存储单元系数：N/2个存储单元3、DIT与DIF的异同基本蝶形不同DIT:先复乘后加减DIF:先减后复乘运算量相同都可原位运算DIT和DIF的基本蝶形互为转置一.稍微变动FFT程序和参数可实现IFFT

§4.5IDFT的FFT算法（FFT应用）

比较两式可知,只要DFT的每个系数换成,最后再乘以常数1/N就可以得到IDFT的快速算法--IFFT。另外,可以将常数1/N分配到每级运算中,∵,也就是每级蝶形运算均乘以1/2。

图DIT―IFFT运算流图二.不改(FFT)的程序直接实现IFFT

这就是说,先将X(k)取共轭,即将X(k)的虚部乘-1，直接利用FFT程序计算DFT；然后再取一次共轭；最后再乘1/N，即得x(n)。所以FFT，IFFT可用一个子程序。共轭FFT共轭乘1/N直接调用FFT子程序计算IFFT的方法：§4.10线性卷积的FFT算法（FFT应用）1、线性卷积的FFT算法需运算量：若系统满足线性相位，即：则需运算量：若L点x(n)，M点h(n)，则直接计算其线性卷积y(n)FFT法：以圆周卷积代替线性卷积1)H(k)=FFT[h(n)]N/2*log2N4)y(n)=IFFT[Y(k)]N/2*log2N3)Y(k)=H(k)X(k)N2)X(k)=FFT[x(n)]N/2*log2NN比较直接计算和FFT法计算的运算量讨论：1）当2）当1）重叠相加法

N

用FFT法实现重叠相加法的步骤如下:

①计算N点FFT，H(k)=DFT［h(n)］；②计算N点FFT，Xi(k)=DFT［xi(n)］；③相乘，Yi(k)=Xi(k)H(k)；④计算N点IFFT，yi(n)=IDFT［Yi(k)］；⑤将各段yi(n)（包括重叠部分）相加， 。重叠相加的名称是由于各输出段的重叠部分相加而得名的。例已知序列x[n]=n+2,0n12,h[n]={1,2,1}试利用重叠相加法计算线性卷积,取L=5。y[n]={2,7,12,16,20,24,28,32,36,40,44,48,52,41,14}解:重叠相加法x1[n]={2,3,4,5,6}x2[n]={7,8,9,10,11}x3[n]={12,13,14}y1[n]={2,7,12,16,20,17,6}y2[n]={7,22,32,36,40,32,11}y3[n]={12,37,52,41,14}2）重叠保留法

舍弃yi(n)的前M-1个点，保留后面的L个点，再将yi(n)顺次连接，即得y(n)。分段右移序列卷积N此方法与上述方法稍有不同。先将x(n)分段，每段L个点，这是相同的。不同之处是，序列中补零处不补零，而在每一段的前边补上前一段保留下来的（M-1）个输入序列值，组成L+M-1点序列xi(n)。如果L+M-1<2m，则可在每段序列末端补零值点，补到长度为2m，这时如果用DFT实现h(n)和xi(n)圆周卷积，则其每段圆周卷积结果的前（M-1）个点的值不等于线性卷积值，必须舍去。

y[k]={2,7,12,16,20,24,28,32,36,40,44,48,52,41,14}x1[n]={0,0,2,3,4}x2[n]={3,4,5,6,7}x3[n]={6,7,8,9,10}y1[n]=x1[n]h[n]={11,4,2,7,12}x4[n]={9,10,11,12,13}y2[n]=x2[n]h[n]={23,17,16,20,24}y3[n]=x3[n]h[n]={35,29,28,32,36}y4[n]=x4[n]h[n]={47,41,40,44,48}x5[n]={12,13,14,0,0}y5[n]=x5[n]h[n]={12,37,52,41,14}解:重叠保留法例已知序列x[n]=n+2,0n12,h[n]={