数字信号处理-第4章

1、123nDFTDFT是信号分析与处理中的一种重要变换。但直是信号分析与处理中的一种重要变换。但直接计算接计算DFTDFT的计算量与变换区间长度的计算量与变换区间长度N N的平方成正的平方成正比，当比，当N N较大时，计算量太大，直接用较大时，计算量太大，直接用DFTDFT算法进算法进行谱分析和信号的实时处理是不切实际的。行谱分析和信号的实时处理是不切实际的。n19651965年年库里库里和和图基图基发现了发现了DFTDFT的一种快速算法，的一种快速算法，使使DFTDFT的运算效率提高的运算效率提高1 12 2个数量级，为数字信个数量级，为数字信号处理技术应用于各种信号的实时处理创造了条号处理技

2、术应用于各种信号的实时处理创造了条件，推动了数字处理技术的发展。件，推动了数字处理技术的发展。n19841984年，提出了分裂基快速算法，使运算效率进年，提出了分裂基快速算法，使运算效率进一步提高；一步提高；4DFTDFT的定义的定义两者形式类似，差别只在于的指数符号不同，及常数两者形式类似，差别只在于的指数符号不同，及常数因子因子运算量是相同的运算量是相同的10 ,)(1)(10 ,)()(1010NnWkXNnxNkWnxkXNknkNNnnkN567nkNWkNnNjkNnNnkNeWW)(2)(mnkmNnkNnmkmNnkNWWWW/,nkNnkNWW)(89二、二、按时间抽取按时间

3、抽取(DIT)(DIT)的基的基-2 FFT-2 FFT算法算法 设设MN2M M为自然数为自然数将长度为将长度为N N的序列的序列x(n)x(n)按按n n的的奇偶奇偶分成两组分成两组) 12/(, 1 , 0),12()() 12/(, 1 , 0),2()(21 NrrxrxNrrxrx1、算法原理、算法原理10则x(n)的DFT为 12/02212/02112/0)12(12/02)()() 12()2()()()(NrkrNkNNrkrNNrrkNNrkrNnnknNknNWrxWWrxWrxWrxWnxWnxkX偶数奇数)()(21kXWkXkN=12/0Nk =12/2/212/

4、2/1)()(NkrNkNNkrNWrxWWrxr=0r=011其中12/02/12/02/11)2()()(NrkrNNrkrNWrxWrxkX12/02/12/02/22) 12()()(NrkrNNrkrNWrxWrxkX是x(2r)与x(2r+1)的N/2点DFT。12由于)()2()()()2(22112/0)2(2/11kXNkXkXWrxNkXNrNkrN得)()(22221221kXWkXNkXWNkXNkXkNNkN12, 1 , 0Nk13bWabWa144点基2时间抽取FFT算法流图x0 x2x1x3X10X11X20X212点DFT2点DFT04W14W02W02WX

5、0X 1X 2X 31 , 0,241mmXWmXmXm1 , 0,2241mmXWmXmXm151) 1 ()0() 1 (1) 1 ()0()0(12120202WxWxXWxWxX02W168点基2FFT算法N/2点DFTN/2点DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X (0)X (1)X (2)X (3)X (4)X (5)X (6)X (7)1212()()()0 , 1 ,12()()()0 , 1 ,122kNkNNXkXkWXkkNNXkXkW

6、Xkk 1212()()()0 , 1 ,12()()()0 , 1 ,122kNkNNXkXkWXkkNNXkXkWXkk N=8点的DIT-2FFT(时域抽取图)一次分解图17 (3)第二次分解：n 将x1(r)按r取奇、偶可分解成2个长度为N/4的子序列 x3(l)= x1(2l)、 x4(l) = x1(2l+1)，根据上面推导可得：X1 (k)= X3(k)+ WN/2kX4(k)， k=0,1,N/2-1n将x2(r)按r取奇、偶可分解成2个长N/4的子序列 x5(l)= x2(2l) ， l=0,1,，N/4 x6(l) = x2(2l+1) ； 同理得l=0,1,，N/4-1；

7、X1 (k+N/2)=X3(k)WN/2kX4(k)， k=0,1,N/4-1；X1 (k)=X3(k)+WN/2kX4(k)， k=0,1,N/4-1；X2(k) = X5(k)+ WN/2kX6(k)， k=0,1,N/4-1 ；X2(k+N/2) = X5(k) WN/2kX6(k), k=0,1,N/4-1；18N / 4 点DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X (0)X (1)X (2)X (3)X (4)X (5)X (6)X (7)N / 4

8、 点DFTN / 4 点DFTN / 4 点DFTX3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)WN/20WN/21WN/21WN/20N=8点DFT的二次时域抽取分解图 X1 (k+N/2)=X3(k)WN/2kX4(k)X1 (k)=X3(k)+WN/2kX4(k)X2(k) = X5(k)+ WN/2kX6(k)X2(k+N/2) = X5(k) WN/2kX6(k)k=0,1,N/4-1 ；19再次分解，对N=8点，可分解三次。X (5)N=8点DIT-FFT运算流图x(0)x(4)x(2)x(6)x(1)x(5)x(3)X1(1)X1(2)X1(3)

9、X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X (0)X (1)X (2)X (3)X (4)X (6)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)WN/20WN/21WN/20WN/40WN/40WN/40 x(7)WN/21WN/40L=1级L=2L=3X (7)X3(0)X1(0)20) 1 ()0() 1 ()0() 1 () 1 ()0() 1 ()0()0(1202xWxxWxXxWxxWxXoNoN0NW218点基2DIT-FFT算法N=8点DIT-FFT运算流图x(0)x(4)x(2)x(6)x(1)x(5)x(3)WN0WN1WN

10、2WN3X (0)X (1)X (2)X (3)X (4)X (5)X (6)WN0WN2WN0WN0WN0WN0 x(7)WN2WN0L=1级L=2L=3X (7)22基2 DIT-FFT算法n 由于这种方法每一步分解都是按输入时间序列是属于偶数还是奇数来抽取的，所以称为“按时间抽取法”或“时间抽取法”。23整个运算流图中有M级蝶形，每一级运算流图中有N/2个蝶形，每个蝶形需一次复乘和两次复数加运算。2425（1）蝶形运算）蝶形运算（2）原位计算）原位计算 （3）序数重排）序数重排（4）蝶形类型随迭代次数成倍增加）蝶形类型随迭代次数成倍增加26（1）蝶形运算）蝶形运算对于对于N=2M，总是可

11、以通过，总是可以通过M次分解最后成为次分解最后成为2点的点的DFT运算。这样构成从运算。这样构成从x(n)到到X(k)的的M级运算过程。级运算过程。从上面的流图可看到，每一级运算都由从上面的流图可看到，每一级运算都由N/2个蝶形运个蝶形运算构成。因此每一级运算都需要算构成。因此每一级运算都需要N/2次复乘和次复乘和N次复次复加，这样经过时间抽取后加，这样经过时间抽取后M级运算总共需要的运算：级运算总共需要的运算： 复乘复乘 复加复加 而直接运算时则与而直接运算时则与N2 成正比。成正比。NNMN2log22NNMN2log27（2）原位计算）原位计算 n当数据输入到存储器中以后，每一级运算的结

12、当数据输入到存储器中以后，每一级运算的结果仍然储存在同一组存储器中，直到最后输出，果仍然储存在同一组存储器中，直到最后输出，中间无需其它存储器，这叫原位计算。中间无需其它存储器，这叫原位计算。n每一级运算均可在原位进行，这种原位运算结每一级运算均可在原位进行，这种原位运算结构可节省存储单元，降低设备成本，还可节省构可节省存储单元，降低设备成本，还可节省寻址的时间。寻址的时间。28（3 3）序数重排）序数重排n对按时间抽取对按时间抽取FFTFFT的原位运算结构，当运算完毕时，的原位运算结构，当运算完毕时，正好顺序存放着正好顺序存放着 x(0)x(0)， x(1)x(1)， x(2)x(2)， x

13、(7) x(7)，因此可直接按顺序输出，因此可直接按顺序输出，n但这种原位运算的输入但这种原位运算的输入 x x（n n）却不能按这种自然顺）却不能按这种自然顺序存入存储单元中，而是按序存入存储单元中，而是按x(0)x(0)，x(4)x(4)，x(2)x(2)，x(6)x(6)，x(7)x(7)的顺序存入存储单元，这种顺序看起的顺序存入存储单元，这种顺序看起来相当杂乱，然而它也是有规律的。当用二进制表示来相当杂乱，然而它也是有规律的。当用二进制表示这个顺序时，它正好是这个顺序时，它正好是“码位倒置码位倒置”的顺序。的顺序。n例如，原来的自然顺序应是例如，原来的自然顺序应是 x(1)x(1)的地

14、方，现在放着的地方，现在放着 x(4)x(4)，用二进制码表示这一规律时，用二进制码表示这一规律时， 则是在则是在 x x（0 0 10 0 1）处放着）处放着 x x（1 0 01 0 0），）， x x（0 1 10 1 1）处放着）处放着 x x（1 1 01 1 0）。）。2930 x(000)x(100)x(010)x(110)010101x(001)x(101)x(011)x(111)01010101x(n2n1n0)n2n1n031323210,310,20,1222/24/，时，时，时，JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLLpNWpNW12L33对

15、的一般情况，第L级的旋转因子为MN212 , 2 , 1 , 0,222212 , 2 , 1 , 0,12J212MLJNNpNMLMLMLLJpNJWWWNJWWLMLLLMJp2从而可以确定第L级运算的旋转因子。34FFT算法流图35363738JN/2？JN/4输入当前倒序数十进制数值JNYNY2NJ 22NJ JN/2MNYMNJ2 结束J=J-N/2倒序数的十进制运算规律39存储单元自然顺序输入变址倒位序A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(

16、3)x(7)N=8 倒位序的变址处理 分析上图N=8点倒序规律，顺序数I与倒序数J 存在关系： I = J时，不交换； I J时，不交换，直接更新序数值；40LH=N/2J=LHN1=N-2I=1,N1I JT=A(I)A(I)=A(J)A(J)=TK=LHJKJ=J+KJ=J-KK=K/2NN YY计算倒序值的程序流图4142仍设序列点数为N=2M，M为正整数。将X(k)按k的奇偶分组之前，先将输入序列按前一半、后一半分开。nkNNnNkNkNnNNnnkNNnNNnnkNNnnkNNnnkNWWNnxnxWNnxWnxWnxWnxWnxkX1202/212012012101202)(2)(

17、)()()()(k=0, 1, , N-1 43nkNNnkWNnxnxkX1202) 1()()( k=0, 1, , N-1 按k的奇偶可将X(k)分为两部分: 12, 1 , 0NrXrx nx nNWx nx nNWnNNrnnNNrn() ( )(/ )( )(/ )/22202 1202 12rnNnNNnnrNNnWWNnxnxWNnxnxrX2/12/0)12(12/0)2/()()2/()() 12(44nNWNnxnxnxNnxnxnx2)()(2)()(2112, 1 , 0Nr12/02/212/02/1)() 12()()2(NnnrNNnnrNWnxrXWnxrX令

18、则x(n)x1(n)=x(n)+x(n+N/2)x2(n)=x(n)x(n+N/2)WNnWNnx(n+N/2)DIF-FFT蝶形运算流图符号45X (3)N/2点DFTN/2点DFTx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)WN0WN1WN2WN3X (0)X (2)X (4)X (6)X (1)X (5)X (7)N=8时第1次分解的运算流图4647x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)WN0WN1WN2WN3X (0)X (4)X (2)X (6)X (1)X (5)X (3)X (7)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)WN0WN2WN0WN2WN0WN0WN0WN04849