Lecture-6-有限长离散Fourier变换

1有限长离散变换主讲：薛洋[e-mail]第5章数字信号处理DigitalSignalProcessing2本讲主要内容离散傅里叶变换（DFT）离散傅里叶变换（DFT）性质DFT的基本性质及对称关系序列的圆周移位圆周卷积实序列的DFT计算用DFT实现线性卷积DFT计算3一、离散傅里叶变换41.1DFT定义（1）有限长变换：如何求有限长变换将一段有限长时间序列映射为等长的频域序列有限长序列和它的DTFT之间有一个简单的关系。要获得序列的DTFT，只要在w轴上，对均匀采样，采样频率点即，)10]([Nnnx)(jeX)10]([Nnnx)(jeX)20()10(2NkkNk1022][)(NnnNkjNkjenxeX)10(Nk51.1DFT定义（2）DFT定义：10,][][)(101022NkWnxenxkXNnknNeWNnnNkjNjN离散傅里叶逆变换（IDFT）10,)(1][10NnWkXNnxNkknN11111000001100111NNNNNklnlnknlnNNNNnnknkNNklnNknxnWXkWWXkWNNXkWXlN证明：61.1DFT定义（3）例：）次复加（次复乘，的运算量：和：：102/2/2121211010/2cos2011001121010/2/2NNNIDFTDFTotherwiserNkNrkNWWkXWWeenxNrNnNrnnxWkXotherwisemnnxkXotherwisennxNnnkrNNnnkrNrnNrnNNrnjNrnjkmNDFTDFT71.2矩阵关系DFT可以用矩阵形式表示TTNXXXNxxx110,110，，，，，，Xx令xDXN1112112421211111111NNNNNNNNNNNNNNNNIDFT的矩阵形式XDx1N*1112112421211111111111NNNNNNNNNNNNNNNNNDN其中，8DFT的快速算法FFTMatlab函数：X=fft(x);计算输入序列x的FFT频谱X=fft(x,N);计算输入序列x的N点FFT频谱1.3用MATLAB计算DFT（1）91.3用MATLAB计算DFT（2）其他,010,1][Nnnu例：计算如下N点序列的M点DFT)(kU101.3用MATLAB计算DFT（3）例：用MATLAB计算IDFT。K点DFT序列kotherKkKkkV,010,)(111.4DTFT和DFT的关系（1）N点DFT序列＝长度为N的序列的DTFT以采样得到的序列10Nk][nx)(kX)(jeXNk2DTFTDFT插值2/1/2102/1/2/2210/210/21010101022sin22sin122sin22sin1111NNkjNkjNNkjNkjkNjNnnNkjNnNknjnjNkNnnjNkknnNnnjjeNkNkNkXNeXeNkNkNeeeeekXNeWkXNenxeX121.4DTFT和DFT的关系（2）DFTDTFT采样当长度大于N时，不能由恢复。书上例题5.6][nx][ny][nx131.4DTFT和DFT的关系（3）用DFT进行DTFT的数值计算例：求长度为N的序列的DTFT][nx)(jeX用频率间隔的来估计Mk2)(kjeX)(jeXkXenxeXMnNNnnxnxeMnMknjejek10/211010][则定义10/210NnMknjNnnjjenxenxeXkk14二、DFT的性质152.1序列的圆周移位(CircularShift)定义：序列的移位序列仍然在范围内。即，10],[Nnnx10Nn）（nmmnnnnNxNnnnnxnnxnNmod0100000012345012345162.2序列的圆周卷积（1）线性卷积：N点圆周卷积：矩阵形式：172.2序列的圆周卷积（2）例：确定下面两个长度为4的序列的4点圆周卷积解：30n]3[]2[]1[]0[]3[]2[]1[][]3[]2[]1[]0[444444ggggmhmhmhmhyyyycccc182.3DFT基本性质性质长度为N的序列N点离散傅立叶变换线性圆周时移圆周频移对偶性N点圆周卷积相乘帕斯瓦尔公式[]gn[]hn[]Gk[]Hk[][]gnhn0Ng[{n-n}]0[]knNWgn[]Gn10[][{}]NNmgmhnm[][]gnhn1122001|[]||[]|NNnkxnXkN[][]kGkH0()knNWGk0[{}]NGkk[{}]NNgk()()GkHk101[][{}]NNmGmHkmN192.4复序列DFT的对称关系序列离散时间傅立叶变换[]xn*[]xn*[{}]NXk*[{}]Nxn*[]XkRe{[]}xn*1[]{[{}][{}]}2pcsNNXkXkXkIm{[]}jxn[]pcsxnRe{[]}Xk[]pcaxnIm{[]}jXk[]Xk*1[]{[{}][{}]}2pcaNNXkXkXk注:和分别代表着x[n]信号的周期共轭性对称及周期共轭性反对称部分.同时,Xpcs[k]和Xpca[k]分别代表着X[k]的周期共轭性对称及周期共轭性反对称部分[]pcsxn[]pcaxn202.5长度为N的实序列的DFT的对称关系序列离散时间傅立叶变换[]xn[]Re{[]}Im{[]}XkXkjXk[]pexnRe{[]}Xk[]poxnIm{[]}jXk*[][{}]NXkXkRe[]Re[{}]NXkXkIm[]Im[{}]NXkXk|[]||[{}]|NXkXkarg[]arg[{}]NXkXk对称关系21三、DFT的运算223.1实序列的DFT计算（1）用单次N点DFT实现两个实序列的N点DFTNNNNkNXkXkXkXjkHkXkXkGnjhngnxnhng****2121其中，则为实序列，令、设例题233.1实序列的DFT计算（1）jjkXkXjkHjjkXkXkGjjkXjjkXjjkXjjjjnjhngnxkHkGnhngNN1,0,1,6211,2,1,4212,2,2,64][2,2,2,64][2,2,2,64][1,,22,21)(),(1,1,2,21,0,2,1**44则，＋＝解：构造复序列：，求、例:243.1实序列的DFT计算（2）用单次N点DFT实现一个实序列的2N点DFT例题120122101222210210102101012210221202NkkHWkGWnhWWngWWnhWngWnvWnvWnvkVNnnvnhnvngNnvNkNNNnnkNkNNnnkNNnkNnkNNnnkNNnknNNnnkNNnnkN，，，点实序列，为设253.1实序列的DFT计算（2）例:4784438446844284458441844484408448433733322622211511100400070301,1,2,2121,0,2,121,1,1,0,2,2,2,1HWGVHWGVHWGVHWGVHWGVHWGVHWGVHWGVkkHWkGkVnnvnhnvngnvk，，，解：263.2用DFT实现线性卷积（1）两个有限长序列的线性卷积nhLngnynhngnyLnMMnnhnhLnNNnngngNMLMNnhngeeCLee则，定义，令和长为、设101010101273.2用DFT实现线性卷积（2）例：用DFT确定两个有限长序列的卷积283.2用DFT实现线性卷积（2）有限长序列和无限长序列的线性卷积nxnhnymNnymNlnxlhmNnxnhnyotherwiseNnmNnxnxmNnxnxnxNnxmethodaddoverlapnxnhlnxlhnynxMnhmmmmmmMlmmmmmmMl其中则，其中点序列为因果序列，切分为设）、重叠相加（为无限长序列点有限长序列，为设00100010][][010,129x[n]序列分割132],[12],[10],[10,210NnNnxNnNnxNnnxMnnh30点）均为和个样本重叠（－有处在与注：11M2232,132,22,12,20,10,10,111221100MNnynyMrNnrNnxnhnynxnhnyMNnNnyNnNnxMNnNnyNnNnxMNnnyNnnxMnnhrrrrrr重叠相加法：31323.2用DFT实现线性卷积（3）例：对噪声污染信号x[n]用一个长度为3的滑动平均滤波器进行滤波。x[n]=s[n]+d[n]，R=64;d=rand(R,1)-0.5;form=1:1:R;s(m)=2*(m-1)*((0.9)^(m-1));x(m)=s(m)+d(m);endk=0:1:R-1;M=input('滑动平均滤波器长度=');h=ones(1,M)/M;y=fftfilt(h,x,4);plot(k,s,'r-',k,y,'b*');legend('r-','s[n]','b*','y[n]');xlabel('时间序号n');ylabel('振幅');])9.0([2][nnns10][1][MkknxMny333.2用DFT实现线