《[工学]第三章-3离散信号的dft_fft分析》由会员分享，可在线阅读，更多相关《[工学]第三章-3离散信号的dft_fft分析（33页珍藏版）》请在金锄头文库上搜索。
1、1三、离散傅立叶变换（DFT)- 有限长序列的离散频谱表示三、离散傅立叶变换（DFT)- 有限长序列的离散频谱表示2三、离散傅立叶变换（DFT) -有限长序列的离散频谱表示三、离散傅立叶变换（DFT) -有限长序列的离散频谱表示?从有限长序列的从有限长序列的DTFT到到DFT?从从DFS到到DFT?DFT的性质的性质31、从有限长序列的DTFT到DFT从有限长序列的DTFT到DFT10()( )( )N jj nnX ex n eX =201( )( )2j nx nXed=?非周期信号的频谱都是频率的连续函数，无法用 计算机进行计算。非周期信号的频谱都是频率的连续函数，无法用 计算机进行计算
2、。?离散信号的离散信号的DTFT，它是的连续周期函数，尽 管在理论上有重要意义，但在计算机上实现有困 难。为此，需要一种时域和频域上都是离散的傅 里叶变换对，实现计算机的快速计算，这就是离 散傅里叶变换，它是的连续周期函数，尽 管在理论上有重要意义，但在计算机上实现有困 难。为此，需要一种时域和频域上都是离散的傅 里叶变换对，实现计算机的快速计算，这就是离 散傅里叶变换 DFT。4能量有限、时间长度为能量有限、时间长度为L的有限长序列的的有限长序列的DTFT为为 10( )( )L j nnXx n e = =1 2/02()( )L jkn NnX kx n eN =1 2/0( )( )L
3、 jkn NnX kx n e =频率采样点数频率采样点数N已知，已知，2 /N为定数为定数N点点DFT是有限长序 列（是有限长序 列（LN)的的DTFT 的的N点均匀取样值， 也就是非周期序列 频谱的样值。点均匀取样值， 也就是非周期序列 频谱的样值。频率离散化频率离散化02 /kkN =52、从、从DFS到到DFT为了计算的方便，通常将为了计算的方便，通常将1/N移到中，而且二者所具有的物理意义和性质都相同移到中，而且二者所具有的物理意义和性质都相同2110011( ) ( )( )NNNNNjnknk NNNN nnXkxn exn w=%21100( )( )( )NNjknnkN N
4、NNN kkxnXk eXk w=%DFS:DFS:210( ) ( )NNjnk NN nXkxn e=%2101( )( )NjknN NN kxnXk eN=%( )Nxn%62、从DFS到DFT2、从DFS到DFT?设设, 令令( )( )DFS NNxnXk %( ),0 1( )( )( )0,N NNxnnNx nRn xnn=%其他( ),0 1( )( )( )0, N NNXkkNX kRk Xkk=% 其他?x(n)、X(k)分别称作、的主值分别称作、的主值( )Nxn%( )NXk%10( )( )N nk N nX kx n w =101( )( )N nk N kx
5、 nX k wN=DFTIDFTDFT又可看作以 有限长序列又可看作以 有限长序列x(n) 为一个周期，进 行周期延拓后所 形成的周期序列为一个周期，进 行周期延拓后所 形成的周期序列 xp(n)的离散频谱的离散频谱RN(n) 为矩形 序列为矩形 序列7)(nxp n N0N2N)(kXp02NNkN0N0nk)(nx)(kXDFSDFT2N8DFT小结小结?DFT 是是 DFS 的主值序列的主值序列?DFS 是严格按傅立叶分析的概念得来的是严格按傅立叶分析的概念得来的?DFT 只是一种借用形式，一种算法只是一种借用形式，一种算法?用用DFT 计算信号的频谱时计算信号的频谱时?采样频率必须大于
6、两倍的信号最高截止 频率采样频率必须大于两倍的信号最高截止 频率?对周期信号要取一个整周期对周期信号要取一个整周期93、DFT的性质?线性线性?对称性对称性?圆周位移圆周位移?圆周卷积圆周卷积10(1) 线性线性?若?那么11( )( )DFTx nX k 22( )( )DFTx nXk 1212( )( )( )( )DFTax nbx naX kbXk+ +如果如果x1(n)、x2(n) 长度不同，长度 短的序列要补 零，使它与另一 序列长度相同长度不同，长度 短的序列要补 零，使它与另一 序列长度相同如果如果x1(n)、x2(n) 长度不同，长度 短的序列要补 零，使它与另一 序列长度
7、相同长度不同，长度 短的序列要补 零，使它与另一 序列长度相同11(2)对称性对称性?若x(n)为实序列，则X(k)具有共轭对称性：?若x(n)为虚序列，则X(k)具有共轭反对称性：?(N-k)modN表示“Nk对N取模”，即：如果N k写成N-k=qN+l，q、l为整数， 则有( )()()mod)X kXkXNkN=( )()()mod)X kXkXNkN= = 0lN ()modNkNl=12(3)圆周位移圆周位移?序列x(n)的圆周位移定义?n0是位移值，RN(n)是矩形序列% 00()mod)( )()( )NNNx nnN Rnxnn Rn=13圆周位移的概念圆周位移的概念?有限长
8、序列有限长序列?周期延拓周期延拓?线性位移线性位移?加窗加窗?得到圆周位移序列得到圆周位移序列%()Nxnm)(nx( )Nxn%10Nn%()Nxnm()( )NNxnm Gn%)(nx)(nGN01Nnnnnmm( )Nxn%()( )NNxnm Gn%14时移特性时移特性?若若?则则?时域序列的圆周位移的时域序列的圆周位移的DFT 为原来的为原来的 DFT乘以一个因子乘以一个因子 ( )( )( )()( )NNDFT x nX ky nxnm Gn=%)()(0kXenyDFTmkj=0jmke 15频移特性频移特性?若若?则则?IDFT在时域在时域x(n)乘以一个乘以一个 ( )(
9、)( )()( )NNDFT x nX kY kXkl Gn=%lnjenxkYIDFT0)()(=0jlne16(4)时域圆周卷积定理时域圆周卷积定理?若?则)()()(kHkXkY=10( )( )( )( )( )( )()( )NNN my nx nh nx nh nx m hnm Gn=%定义为 圆周卷积10( )( )( )()( )NNN mx nh nh m xnm Gn=%)()(nhnxNN点的 圆周卷积x(n)和h(n)都 需是N点17例6 计算x1(n)、x2(n)的N点圆周乘积，其中?解： x1(n)、x2(n)的N点DFT为112 00( )( )0N nk N n
10、NkX kXkw =其他121 01( )( )0nNx nx n=其他?因此，有 2120( )( )( )0kNX kX k Xk=其他?x1(n)、x2(n)的N点圆周卷积是X(k)的反DFT变换 01( )0nNNx n=其他18频域圆周卷积定理频域圆周卷积定理?若若?则则)()()(nhnxny=1010( ) ( )1( )()( )1( )()( )NNN lNNN lY kDFT y nX l Hkl GkNH l Xkl GkN=%19四、快速傅立叶变换（FFT）四、快速傅立叶变换（FFT）?DFT的计算量的计算量?DFT的特点的特点?FFT的基本思想的基本思想?FFT应用中
11、的注意事项应用中的注意事项201、DFT的计算量?DFT?N点DFT的计算量：?每计算一个X(k)值需要进行N次复数相乘， N-1次复数相加；?对于N个X(k)点，完成全部DFT运算共需N2 次复数相乘和N(N-1)次复数加法。10( )( )N nk N nX kx n w =1 10( )( )N nk NN kx nX k w=212、DFT的特点的特点?（1）Wr的周期性的周期性?（2）Wr的对称性的对称性2jN Nwe =001,1,1NmN NNNNr mNr NNWWWWWW+=2 2222()1,1NNNNNjmNj NNrr NNWeeWWW+= = = 222、DFT的特点
12、的特点?（3）由于DFT计算量与N成几何级数增 长，可以将长序列分解成多个短序列信 号，然后分别求各个短序列的DFT，最后 将它们组合，得到原序列的DFT。233、FFT的基本思想3、FFT的基本思想?把原始的N点序列，依次分解成一系列短 序列。同时充分利用DFT计算式中所具有 的对称性和周期性，求出这些短序列相 应的DFT，并进行适当组合，最终达到删 除重复运算，减少乘法运算，提高速度 的目的。?直接利用DFT（IDFT）计算，需要 N2次复数乘法和 N(N-1) 次复数加法。一次复数乘(a+jb)(c+jd)=(ac-bd)+j(ad+bc)共需2次实数加法和4次实数乘法。一次复数加 a+
13、jb+c+jd=(a+c)+j(b+d)共需2 次实数加法。所以完成整个DFT运算需要N2次实数乘法和N2N(N-1)N2次实数加法。当较大时，所需的运算工作量相当大。例如当N101024时，总共约需 400 万次实数乘法运算，对于实时信号处理 来说，将对计算速度有十分苛刻的要求。按时间抽取的基按时间抽取的基2FFT算法算法?主要思路主要思路：将x(n)或X(k)的次序重排，并利用WN的特性，将长序列的离散傅里叶变换运算逐次分解成较短序列的离散 傅里叶变换计算，从而提高运算效率。?若算法是对输入序列x(n)进行逐次分解进行的，则叫做时间抽选时间抽选(Decimation In Time, DI
14、T)FFT算法算法。?若序列x(n)的长度N=2，是整数（可以对序列增补零值点来达到）。则通过分解，其最小的DFT运算单元是2点。通常将FFT运算中最小DFT运算单元称为基（基（radix），），因而把这种算法称为基基2时间抽选时间抽选FFT算法算法。( )( )( )( )()()()()()()()()()( )( )101122212 .0012.20112212.222000221221212N nk N nnknk NN nnNNlkl k NN llNl kk NN llklk NNNNkk NN llNl kN lXkx n Wx n Wx n Wxl WxlG kHWxlWWW
15、Wxl WxlWWxkl=+=+=+=+=+=+偶数奇数( )x n 的序号为偶数的序列( )x n 的序号为奇数的序列（P128）1202( )(2 )Nlk N lX kxl W=+1202(21)(01)Nklk NN lWxlWkN=+( )( )k NWG kH k=+G(k) (k=0N/2-1)H(k) (k=0N/2-1)X(k)=G(k)+WNkH(k) (k=0N-1)(3)X(0)=G(0)H(0) X(1)=G(1)H(1) X(2)=G(2)H(2) X(3)=G(3)H(3) X(4)=G(4)H(4)G(0)H(0) X(5)=G(5)H(5)G(1)H(1) X(6)=G(6)H(6)G(2)H(2) X(7)=G(7)H(7)G(3)H(3)0 8W3 8W1 8W 2 8W4 8W 5 8W 6 8W 7 8W0 8W 1 8W 2 8W3 8W对称性(3)X(k)=G(k)+ H(k)k NW()kk rN NNWW+=()2Nkk NNWW+= rkk NN
