离散傅里叶变换数字信号处理陈后金

1、 ntnnXtx0j0e)()( ttxTnXtnTde)(1)(00j00 de)j (21)( jtXtx ttxXtde)()j ( j de)e (21)e (IDTFTjjjkXXkxkkkxkxX jjeDTFT)e (mkNNmmkNNmWmXNmXNmXkx 102j101e1IDFS mkNNkmkNNkWkxkxkxmX 102j10eDFS 1, 2, 1, 0,e12j10 NkmXNkxmkNNm符号表示符号表示IDFTmXkx1, 2, 1, 0,e2j10 NmkxmXmkNNmDFTkxmX 有限长序列有限长序列xk离散傅里叶变换离散傅里叶变换Xm是其离散时是其

2、离散时间傅里叶变换间傅里叶变换X(ej )在一个周期在一个周期0,2 )的等间隔抽样的等间隔抽样1, 2, 1, 0,)e ( DFT2j NmXkxmXmN kkkxkxXj -jeDTFT)e (1, 2, 1, 0,e2j -10 NmkxmXmkNNke12j10kRkxmXNkxNmkNNm e2j10mRmXkxmXNmkNNk DFT可以看成是截取可以看成是截取DFS的主值区间构成的变换对的主值区间构成的变换对。DFT, 10,:1的的点序列点序列求求例例kxNNkkkx 。DFT, 10),2cos(:2点点求求例例NNkkNkx 1 , 1, 1 , 1 kx求有限长求有限长

3、4点序列点序列 的的DFT。有限长有限长4点序列点序列DFT矩阵表示。矩阵表示。mkNNkmkNNkWkWkxmX1010 101 Nm)e2e2(1)1(2j2jkNNkNNNNkx 其他其他01, 12/NmNmX 求有限长求有限长4点序列点序列 的的DFT。1 , 1, 1 , 1 kxmkNNkWkxkxmX 10DFT23210004140 xxxxWkxXkk2321 01 34241414140 WxWxWxxWkxXkk232 1 0264442424140 WxWxWxxWkxXkk2321 0394643434140 WxWxWxxWkxXkk0 , 0 , 0 , 0 ,

4、 1 , 1, 1 , 11 kx如果序列后补零，其如果序列后补零，其DFT有何变化有何变化? ? 32 1 032 1 094643404644424043424140404040404xxxxWWWWWWWWWWWWWWWWXXXX 22221111j1j11111j1j1111132 1 0XXXXXm=2，2，-2，2, m=0,1,2,3有限长有限长4 4点序列点序列DFT矩阵表示矩阵表示:1 , 1, 1 , 1 kxmkNNkWkxkxmX 10DFTmkkmkNNkWkxWkxkxmX43010DFT 1 2 1 011111111 1 2 1 0)1()1()1(21)1(2

5、42121NxxxxWWWWWWWWWNXXXXNNNNNNNNNNNNNNNmkNNkWkxkxmX 10DFT 计算计算M点的点的DFT。M是序列是序列x的长度。的长度。 计算计算N点的点的DFT。 M N，将原序列裁为将原序列裁为N点计算点计算N点的点的DFT； M N，将原序列补零至将原序列补零至N点，然后计算点，然后计算N点点DFT。x=1 1 -1 1; xm=fft(x,4);subplot(311);stem(0:3,abs(xm);axis(0 4 -1 3);xm1=fft(x,8);subplot(312);stem(0:7,abs(xm1);axis(0 8 -1 3)

6、;xm2=fft(x,16); subplot(313);stem(0:15,abs(xm2);axis(0 16 -1 3);1 , 1, 1 , 1 kxmXmXmXmmm4 N8 N16 N? kx：思思考考x=0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0;xm=fft(x,16);subplot(311);stem(0:15,abs(xm);axis(0 16 -1 7);subplot(312);xm1=fft(x,64);stem(0:63,abs(xm1);axis(0 64 -1 7); subplot(313);xm2=fft(x,256);stem(0:2

7、55,abs(xm2);axis(0 256 -1 7); mXmXmXmmm16 N64 N256 N? kx：思思考考x=0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0;x1=0 0 0 0 0 1;N1=6;xm1=fft(x1);subplot(211);stem(0:N1-1,abs(xm1);xm16=fft(x1,16);subplot(212);stem(0:15,abs(xm16);x2=0 0 0 0 0 1 1;N2=7;xm2=fft(x2);subplot(211);stem(0:N2-1,abs(xm2);gridxm16=fft(x2,16);su

8、bplot(212);stem(0:15,abs(xm16);gridx3=0 0 0 0 0 1 1 1;N3=8;xm3=fft(x3);subplot(211);stem(0:N3-1,abs(xm3);xm16=fft(x3,16);subplot(212);stem(0:15,abs(xm16);gridx4=0 0 0 0 0 1 1 1 1;N4=9;xm4=fft(x4);subplot(211);stem(0:N4-1,abs(xm4);gridxm16=fft(x4,16);subplot(212);stem(0:15,abs(xm16);gridxm=fft(x,16);

9、subplot(515);stem(0:15,abs(xm); DFTDFTDFT2121kxbkxakbxkax 需将较短序列补零后，再按长序列的点数做需将较短序列补零后，再按长序列的点数做DFT 10)2(NkkmNjekbykaxkbykaxDFT 10)2(10)2(NkkmNjNkkmNjekybekxa mbYmaX )(kRnkxkyNN 循环位移定义为循环位移定义为:注意：隐含的周期性注意：隐含的周期性若若 DFT xk = Xm 则则 DFT xpk nRNk = WNnm Xm 表明：序列在时域上圆周移位，频域上将产生附加相移。表明：序列在时域上圆周移位，频域上将产生附加相

10、移。 10NkkmNpWnkx 1)(nNnimniNpWix1mXWWWixnmNnmNnNniimNp 证明：证明：DFT xpk nRN k nki 若若 DFT xk = Xm 则则 DFT xk WN lk = Xp m l RNm 表明：若序列在时域上乘以复数指数序列表明：若序列在时域上乘以复数指数序列WN lk，则在，则在频域上，频域上， Xm将圆周移位将圆周移位 l 位，也称位，也称“调制定理调制定理”。设设xk为实序列，为实序列， DFT xk = Xm ，则，则 Xm的实部的实部XRm是是m的偶函数的偶函数,虚部虚部XIm是是m的奇函数的奇函数 Xm的幅频是的幅频是m的偶函

11、数，相位是的偶函数，相位是m的奇函数。的奇函数。 具有半周期对称的特点，即具有半周期对称的特点，即 Xm = X*N m -1）实数序列）实数序列xk 102NkkmNjekxmX 1010)2sin()2cos(NkNkkmNkxjkmNkx 22mXmXmXIR arctanargmXmXmXRI mjXmXIR 1010)(mXWkxWkxmNXNkNNkNkmmNk x=0 0 0 1 1 1 1 0 0 0;xm=fft(x,10);subplot(221);stem(0:9,abs(xm);subplot(222);stem(0:9,angle(xm);subplot(223);x

12、m1=fft(x,11);stem(0:10,abs(xm1);subplot(224);stem(0:10,angle(xm1);设设xk为实序列，为实序列， DFT xk = Xm ，则，则 Xm的实部的实部XRm是是m的偶函数的偶函数,虚部虚部XIm是是m的奇函数的奇函数 Xm的幅频是的幅频是m的偶函数，相位是的偶函数，相位是m的奇函数。的奇函数。 具有半周期对称的特点，即具有半周期对称的特点，即 Xm = X*N m 10 N11 NmXmXargmXargmXopepkxkxkx 21*epkNxkxkx 21*opkNxkxkx ReDFTepmXkx ImjDFTopmXkx j

13、irkxkxkx 21DFTep*rmXmNXmXkx 21j DFTop*imXmNXmXkx 2）复数序列）复数序列xk若若x*k是有限长序列是有限长序列xk的共轭复数的共轭复数序列，并设序列，并设 xk = xRk + jxIk, x*k = xRk jxIk 有有 DFT x*k = X*N m 且且 Xepm = DFT xRk = Xm + X*N m/2 Xopm = DFT jxIk = Xm X*N m/22）复数序列）复数序列 )(1010NkkmNkkmNWkxWkxkxDFT21211010* NkNkkmNkmNepWkxWkxmNXmXmX2110kxDFTWkxk

14、xRNkmkmN 10)(mNXWkxNkmNk 1010nkxnhnkhnxkhkxkyNNnNNNnN DFT2121mXmXkxNkx1DFT2121mXNmXNkxkx2102101mXNkxNkNk 0,)(10 zzkxzXkNkkmNNkkxmX2j10e 有限长序列有限长序列xk的的DFT：有限长序列有限长序列xk的的z变换：变换：mNjezzXmX2)( mNNmNWzmXNzzX 1101)1()()e (jX)(zXmXzje mN2 mNjez2 0,e 1)(10102j10 zzmXNzkxzXkNkNmkmNkNk?)(1110101010 kNmNkmNkNkN

15、mmkNzWNmXzWmXNh(n)x(n) y(n)()()()()(mnhmxnhnxnym 如果序列如果序列x(n)的长度为的长度为 N1 、序列、序列h(n)的长度为的长度为N2 ，那么线，那么线性卷积性卷积y(n)也是一个有限长序列，且其长度为也是一个有限长序列，且其长度为 N1+N2 1。 每个每个x(n)的样值都必须与每个的样值都必须与每个h(n)的样值相乘，需的样值相乘，需N1N2次乘次乘法运算，在法运算，在 N1 = N2 = N 时，需时，需 N2次乘法运算。次乘法运算。 能否用圆周卷积代替线性卷积能否用圆周卷积代替线性卷积 ? 将进行卷积的两序列长度均加长至将进行卷积的两

16、序列长度均加长至N N1 + N2 1，然后再进，然后再进行圆卷积，则其圆卷积的结果与线卷积的结果相同。行圆卷积，则其圆卷积的结果与线卷积的结果相同。nkhnxkhkxkyn 3,2,1 ,0,2,1 ,0hhhhkhxxxkx 60,20 knkhnxnkhnxkhkxkynnnkhnxkhkxkyn 3,2,1 ,0,2,1 ,0hhhhkhxxxkx 0 , 0,3,2,1 ,0,0 , 0 , 0,2,1 ,0hhhhkhxxxkx 能否用圆周卷积代替线性卷积能否用圆周卷积代替线性卷积 ?10,10 NknkhnxkhkxkyNn50,50 knkhnxkhkxkyn20nkhnxkh

17、kxkyn 50nkhnxkhkxkyn khkxkhkxLL 序列补零加序列补零加长至长至LxkN点点L点点DFTXkL N + M 1序列补零加序列补零加长至长至LhkM点点L点点DFTHkIFFT yk相乘相乘直接线卷积直接线卷积：N1N2次乘运算，次乘运算， N1 N2 = N 时，需时，需 N 2乘。乘。利用圆卷积利用圆卷积：两次两次FFT，一次，一次IFFT 在一般的数字滤波器中，由于在一般的数字滤波器中，由于h(k)或或H(m)是预先设计好的，是预先设计好的，已置于存储器中，故实际只需二次已置于存储器中，故实际只需二次FFT的运算量。假定的运算量。假定N = M= L，补零后长度

18、补零后长度 N + M 1 2L，需要需要2 ( L log22L )次乘。次乘。此外完成此外完成X(k)与与H(k)两序列相乘，全部复运算次数为两序列相乘，全部复运算次数为2 ( L log22L ) + 2L = 2L ( 1 + log22L ) 比如比如 L = 210 = 1024 L = 26 = 64直接线卷积直接线卷积：1048576 64 64=4096利用圆卷积利用圆卷积： 24576 896 显然，随显然，随L ，利用圆卷积利用圆卷积比比L 2显著减小，所以采用圆卷积显著减小，所以采用圆卷积的方案可以加快完成卷积运算。的方案可以加快完成卷积运算。 两序列长度接近或相等的情

19、况下，采用圆卷积的方两序列长度接近或相等的情况下，采用圆卷积的方案可以加快完成卷积运算。如果其中一个序列较短，而案可以加快完成卷积运算。如果其中一个序列较短，而另一序列很长，圆卷积方案的相对运算量可能减小不多，另一序列很长，圆卷积方案的相对运算量可能减小不多，甚至增多。这时，可采用分段卷积（分段过滤）的方法。甚至增多。这时，可采用分段卷积（分段过滤）的方法。 其基本原理是：将较长的一个序列，比如其基本原理是：将较长的一个序列，比如xn分成分成许多小段，每小段长度都与许多小段，每小段长度都与hn接近，将接近，将xn的每个小的每个小段分别与段分别与hn作卷积，最后取和。这时，仍有可能发挥作卷积，最

20、后取和。这时，仍有可能发挥快速卷积的优越性。此方案的具体实现不是唯一的。快速卷积的优越性。此方案的具体实现不是唯一的。(1) 信号要全部输入后才能进行计算，延迟太多。信号要全部输入后才能进行计算，延迟太多。(2) 内存要求大。内存要求大。(3) 算法效率不高。算法效率不高。分段卷积可采用分段卷积可采用和和将长序列将长序列xk 分为若干段长度为分为若干段长度为L的序列的序列10,01110 LkLkxkx10,11111 LkLkxkx10,111 LkLnkxkxn00khkxky 11khkxky 0khnLkxkhkxnn 0nLkynn y0k的长度及起止点：的长度及起止点：20 MLk

21、y1k L的长度及起止点：的长度及起止点：22 MLkL注意：序列注意：序列 y0k, y1k的重叠部分的重叠部分2 MLkL重叠的点数：重叠的点数：L+M 2 L+1=M 1:khkxkynn 记记3,2,1 ,05,4,3,2,1 ,0hhhhkhxxxxxxkx 5,4,32,1 ,010 xxxkxxxxkx (1) 将将xk长序列分段，每段长度为长序列分段，每段长度为L。 (2) 各段序列各段序列xnk与与 M点短序列点短序列hk循环卷积。循环卷积。 (3) 从各段循环卷积中从各段循环卷积中提取提取线性卷积结果。线性卷积结果。因因ynk=xn k hk前前M-1个点不是线性卷积的点，

22、故分段时，个点不是线性卷积的点，故分段时，每段与其前一段每段与其前一段有有M-1个点重叠个点重叠。L)1( Mkxk0kx1kx1 M1 L) 1( MLML 2第一段前需第一段前需补补M-1个零个零10),1( LkMLnkxkxn记：ynk =xn k L hk01Lk0k1LM -1M-100khkxky 11khkxky 2,1 ,05,4,3,2,1 ,0hhhkhxxxxxxkx 2135 重叠，L选？kx？kx？kx 2100kx1kx2kx 已知序列已知序列xk=k+2,0 k 12, hk=1,2,1，试分别利试分别利用重叠相加法和重叠保留法计算线性卷积用重叠相加法和重叠保留

23、法计算线性卷积, , 取取L=5 。 已知序列已知序列xk=k+2,0 k 12, hk=1,2,1，试分别利试分别利用重叠相加法和重叠保留法计算线性卷积用重叠相加法和重叠保留法计算线性卷积, , 取取L=5 。 已知序列已知序列xk=k+2,0 k 12, hk=1,2,1，试分别利用重叠相试分别利用重叠相加法和重叠保留法计算线性卷积加法和重叠保留法计算线性卷积, , 取取L=5 。0 , 0 , 1, 2, 1 kh0 , 0 , 1, 2, 1 kh0 , 0 , 1, 2, 1 kh0 , 0 , 1, 2, 1 kh0 , 0 , 1, 2, 1 kh14,13,12,11,10,

24、9, 8, 7, 6, 5, 4, 3, 2 kx ttxXtxtFTde)()j()(j TtnTFSTttxTnXtxde)(1)()(0j0 kkDTFTkxXkxjje )e( 102jeNkmkNDFSkxmXkx 102je NkmkNNNDFTNkxmXkxFTFSDTFTDFSDFT)( txkxN假设连续信号持续时间有限，假设连续信号持续时间有限，频带有限频带有限离散化抽样mXN点 DFT)2( j 1)e (jTnXTXn 1, 0,)e (2j NmXmXN？时，对应的N思考：当m 2/2s ？时，对应的Nm思考：当N 12/例：已知语音信号例：已知语音信号x(t)的最高

25、频率为的最高频率为fm=3.4kHz, 用用fsam=8kHz对对x(t)进行进行抽样。如对抽样信号做抽样。如对抽样信号做N=1600点的点的DFT，试确定，试确定Xm中中m=600和和m=1200点所分别对应原连续信号的连续频谱点点所分别对应原连续信号的连续频谱点f1 和和f2 (kHz)。 解：解：2s 160022 N离散频率间隔：sfNmNTmTmNNm 22220 ，时，时，当当)22()22()22(12ssfNmfNTmTTmNNmN ，时，时，当当求x(t)=e-t u(t)的幅度谱fs=16Hz,N=256-50-40-30-20-100102030405000.20.40.

26、60.81近 似 值理论 值 j11)j ( X211)j ( X010203040506070809010000.81t=(0:N-1)*T;x=T*exp(-t);X=fft(x);-50-40-30-20-100102030405000.81近 似 值理论 值-50-40-30-20-100102030405000.81近 似 值理论 值N=100;fs=100;t=(0:N-1)/fs;x=exp(-t)/fs;X=fft(x);subplot(121);stem(t*fs,abs(X);gridw=-50:0.01:50;Xjw=

27、1./(1+j*w);subplot(122);plot(w,abs(Xjw);gridhold onXX1=X(1:50);XX2=X(51:100);XX=XX2 XX1;stem(-50:49,abs(XX);gridN=100;fs=16;t=(0:N-1)/fs;x=exp(-t)/fs;X=fft(x);subplot(121);stem(t*fs,abs(X);gridw=-50:0.01:50;Xjw=1./(1+j*w);subplot(122);plot(w,abs(Xjw);gridhold onXX1=X(1:50);XX2=X(51:100);XX=XX2 XX1;s

28、tem(-50:49,abs(XX);grid讨论讨论1：x(t)无限长，其频带有限无限长，其频带有限mXkx加窗加窗22)(jeXN022)(jeX0TAm)j (X0AmmmX01N)(tx抽样抽样kxNDFT讨论讨论2：x(t) 有限长，其频带无限有限长，其频带无限)j (X0A22)(jeX0mmX01N)(tx抽样抽样kxmXDFT讨论讨论3：x(t)无限长，其频带无限无限长，其频带无限出现三种现象：混叠(抽样频率)、泄漏(加窗截断)、栅栏(离散频率点)j (X0A22)(jeX022)(jeXN0mmX01Nkx)(tx抽样抽样mXDFTkxN加窗加窗混叠现象、泄漏现象、栅栏现象(

29、1)混叠现象混叠现象)250cos()(191ttxn Hzfs2000 DFT点点1024Hzfs500 DFT点点1024f1=50.0; w1=2*pi*f1; fs=2000; t=-10:1/fs:10; x=-cos(w1*t) ;for n=1:19x=x- cos(n*w1*t)/n;endsubplot(311); plot(t,x);N1=400;x1=x(1:N1);X1=fft(x1,N1);subplot(312);stem(0:N1-1),abs(X1)/N1*2);gridN2=512;x2=x(1:N2);X2=fft(x2,N2);subplot(313);s

30、tem(0:N2-1),abs(X2)/N2*2);gridf1=50.0; w1=2*pi*f1; fs=2000; t=-10:1/fs:10; x=-cos(w1*t) ;for n=1:19x=x- cos(n*w1*t)/n;endsubplot(411); stem(t,x);N1=1024;x1=x(1:N1);X1=fft(x1,N1);subplot(412);plot(0:N1-1),abs(X1)/N1*2);gridf1=50.0; w1=2*pi*f1; fs1=500; t=-10:1/fs1:10; xx=-cos(w1*t) ;for n=1:19xx=xx-

31、cos(n*w1*t)/n;endsubplot(413); stem(t,xx);N2=1024;x2=xx(1:N1);X2=fft(x2,N2);subplot(414);plot(0:N2-1),abs(X2)/N2*2);grid混叠现象、泄漏现象、栅栏现象(2)泄漏现象泄漏现象)250cos()(191ttxn | )(| jeXDFTNHzfs点点1024,2000 100 200 300 400 | )(|mXmt)(tx混叠现象、泄漏现象、栅栏现象(3)栅栏现象栅栏现象)250cos()(191ttxn DFTNHzfs点点1024,2000 DFT点点1024DFT点点256DFT点点64DFT点点1024DFT点点256DFT点点64)(tx)(txfs=1000; t=0:1/fs: