现代信号分析理论与处理

1、离散时间信号分析内容提要变换（DTFT）序列的拉氏变换、傅氏变换与z变换之间的关系级数（DFS）变换（DFT）变换（FFT）变换的应用离散离散快速快速1离散时间信号分析变换 DTFT变换的关系离散时间与连续时间性质变换 DFT离散定义性质离散原理流程应用变换的快速算法 FFT2离散时间信号的实际信号的特点：时域：连续时间信号 ;频域：频谱是连续的分析持续时间较长数字处理设备（计算机）的特点：空间有限-只能有限多的数据离散的时间点有限长的时间范围表示空间有限-只能表示有限多的数值取值在一定精度内取值在一定范围内3） 1要解决（的在时域如何对信号进行离散化？要求保证信号的信息不受损！信息不受损=可

2、以恢复原信号理论问题已在第二章解决乘以冲激串信号，进行时域抽样要求抽样过程满足抽样定理信号频带有限，抽样频率是信号最高频率的两倍1已基本解决4） 2要解决（的如何用抽样信号的频谱来恢复原信号的频谱？抽样信号频谱与原信号频谱是什么关系？理论上如何恢复？工程实践上如何实现？5） 3要解决（的抽样信号的频谱如何计算？得到抽样信号后，如何计算其频谱？输入：抽样信号（序列）输出：抽样信号的频谱 在工程上，计算机接受的输入是一系列数值6X1X2X3X4X5X6） 4要解决（的信号被截短时，频谱发生什么变化？有时信号持续时间超出处理能力时域信号需要被截断截断会不会影响对信号的分析？截断对信号的频谱有何影响？

3、7） 5要解决（的与计算有限长离散信号频谱的频谱是连续周期的 1. 只能有限长的频谱一个周期即可2. 只能有限多的频谱离散频率点处的频谱值离散频率点谱值的计算法一：先有连续谱，后有离散谱值（频域采样）法二：直接用时间抽样值计算离散谱值（公式）？8）6、7要解决（的如何由频谱恢复抽样信号？离散频谱值是有限的恢复抽样信号的计算公式如何编程实现（如何进行快速计算）按定义实现-计算量太大由离散信号计算离散频谱由离散频谱恢复离散信号9方法从工程需要出发，理解信号频谱分析的实际问题。即在实践中领悟处理原理的意义从解决问题出发，理解各种信号处理方法的目的。即在中思考工程实现的背景10在解决过程中感受知识的力

4、量、体会学习的4.1序列的变换1.定义x (n)的z变换为X (z) x(n)zn n圆上是收敛的，则把在如果X (z)在圆上的z变换变换，表示为定义为序列的 x(n)e jnnX (ej ) X (z) |(4.1)j z e114.1序列的变换相对应序列的线积分公式反变换，由z反变换的围x(n) 1 vX (z)zn1dz2 jC若把积分围线C取在圆上，则有12 j v z ejX (ej )(ejne j )d(ej )x(n) 1 2X (ej )ejnd（4.2）124.1序列的变换2物理意义把序列的变换称作非周期序列的频谱，为什么把序列的 可以与连续信号的已知连续信号的变换和序列的

5、频谱联系在一起?变换进行对比进行分析.变换为F ()=Ff (t)e jtdt f (t)12 F ()ej td()=f(t)=F-1F134.1序列的变换F ()有频谱密度的意义，是频谱的概念，在式（4.1）中，X (e j)是序列的变换，与F()在连续信号变换的表达式中一样起着相同的作用，所以看作是序列的频谱。f (t) 和x (n)的两个表达式都具有叠加重构（综合）时域信号即反变换的作用，因此把式（4.2）称为序列的反变换。144.1序列的变换将式（4.1）和（4.2）重写并表示为x(n) X (ej ) x(n)e jnnF(4.3) 1 2 X (e) x(n) jX (ej )e

6、jnd1(4.4)F154.1 序列的变换3特点由式 (4.3)知，序列频谱X (e j) 是e j n的函数，而e是j n以2为周期的函数，并且由于序列在时域上是非周期的，因而，序列的频谱是周期的连续频谱。同时X (e j)是 的复函数，可进一步表示为(ej )(4.5)164.1序列的变换其幅度谱如图4.1所示j) | X (ex (n)0n-2-02图4.1序列及其幅谱图174.1序列的变换序列变换存在的条件圆上的z变换，序列的z由于序列的变换在件，即变换是圆上必须收敛是序列变换存在的条上式表明，序列变换存在的条件是：序列必须绝对可和。(充分条件)18|x (n) |n4.1序列的变换变

7、换。例4.1求出下列序列的x2 (n) = (n+3) - (n-4)解:193X (e j ) (n 3) (n 4)e jn e jn n n 3 e jn e jn e jn e jn e jn jn j333332e en 0n 1n 0n 1n 0 n 0 1 e j4 1 e j3j 1 e j4 1 e j3 1 e j7 j31 e j1 e j e1 e j1 e-j1 e j e j7 j7 j7 7e2 e 2e2sin e j3 2j1 j1 j1 sin 1 e2 e 2e2 24.2傅氏变换、拉氏变换与z变换的关系目的:找出连续信号与离散信号各种变换的关系变换关系的

8、纽带:冲激抽样信号沟通连续和离散信号的桥梁204.2傅氏变换、拉氏变换与z变换的关系1.冲激抽样信号的拉氏变换X s (s)与连续信号的拉氏变换X a (s)之间关系：拉氏变换的指数形式为 snT(s) Xx (nT )esan周期为T的周期冲激信号傅氏级数的表达式(周期延拓)为m 1Te jms t(t ) nT ) Tn 见例2.12的证明214.2傅氏变换、拉氏变换与z变换的关系 2T为采样角频率，则冲激抽样信号可表示为sx (t) x (t) (t) x (t) 1 ejmstsaTaTm可导出冲激抽样信号拉氏变换的另一种形式1x (t )e st dtX (s) ssx (t ) 1

9、e jmst e st dtaTm (t )e ( s jms ) t dtxaT1Tm m X (s jm )(4.13)as224.2傅氏变换、拉氏变换与z变换的关系由此，到冲激抽样信号的拉氏变换有指数级数与周期延拓表示的两种等价表达式。即 sTnX (s)x (nT )esanm 1TX (s jm)(4.14)as234.2傅氏变换、拉氏变换与z变换的关系2冲激抽样信号的拉氏变换Xs(s)与抽样序列的z变换X(z)之间关系z与s变量之间的关系z = e sT ，若离散时间信号为抽样序列，即x (nT) = x (n)，并引入z = e sT 时，得到序列z变换为n x(n)zn n s

10、nTX (z) X(s) |x (nT )e|sasTsTz ez e上式表示，z变换可以看成沖激抽样信号的拉氏变换由s平面到z平面的变换。244.2傅氏变换、拉氏变换与z变换的关系3冲激抽样信号的拉氏变换Xs(s)与其傅氏s (j)之间的关系为X s (s) |s j X s ( j)变换X由，s j 0若，而且拉氏变换收敛域包含虚轴时，则虚轴上的拉氏变换即为其傅氏变换，或者说，沖激抽样信号的变换。变换是其在虚轴上的拉氏254.2傅氏变换、拉氏变换与z变换的关系s (j)与连续时间信号的傅氏4冲激抽样信号的傅氏变换X变换X a (j)之间：冲激抽样信号傅氏变换的指数级数的形式，以及连续时间变

11、换X a (j)的周期延拓形式，对沖激抽样信号的信号而言是等价的，表示为jX (j) Tnx (nT)esan 1 X (j jm )asTm264.2傅氏变换、拉氏变换与z变换的关系5激抽样信号傅氏变换的指数形式与序列的变换表达式：两相比较，若序列为抽样序列，有：x (n) = x a (nT)，而且数字角频率与模拟角频率，满足 = T ，则相应频率点上的频谱值相等。X (ej ) x(n)e jn n274.2傅氏变换、拉氏变换与z变换的关系变换X ( ej )之间：6序列z变换X (z)与序列X (z) |j X (e)jz e变换X ( e j )为X (z)在序列的圆上的特例。284

12、.2傅氏变换、拉氏变换与z变换的关系把上述分析的结论，用图来形象地描绘如下：1 X (s jm )ze X(z) x(n)znsT X (s)sTnx (nT)eassaTmnnx(n)xa (nT)s j z ej1TmX(e ) x(n)e jm) X(j) jTnTjnjX(jx(nT)eassann此图非常清晰地表明了：冲激抽样信号是沟通离散信号与连续信号各种变换的桥梁。294.3级数（DFS）离散4.3.1变换在时域和频域中的对称规律一连续非周期信号，由前述，其变换（频谱）X a ()是非周期的连续谱，时域上的非周期对应频域上的连续，或频域上的连续对应时域上的非周期，由此可以得到时、

13、频域的第一个对称规律：时域上的非周期将产生频谱的连续，或者说，频域的连续导致时域的非周期总之一个域中函数的连续对应另一个域的非周期。如下图4.4（a）所示30| X a () |x a (t)0连续非周期信号t0非周期连续频谱（a）| X p (k1) |x p (t)0连续周期信号T1t1非周期离散频谱（b）310s /2周期连续频谱s0T2n离散非周期信号（c）x ps (nT), x p (n)| X s (k1) | , | X (e j k 1 )|1s20T01 =2/N周期离散频谱T1N-1n离散周期信号（d）信号在时、频域中的对称规律图4.4324.3级数（DFS）离散如图4.

14、4（b），一周期信号x p (t)，其频谱是离散谱X p(k1)。可以从另一个角度来理解：X p (k)正是对图4.4（a）中的频谱X a ()以采样频率1进行抽样 ，即频域被离散化，则在时域上产生单周期信号x(t)的周期延拓，延拓周期为T1a= 21，形成周期延拓波形x p (t).时、频域的第二个对称规律：时域上的周期化将产生频谱的离散化，或者说，频域的离散化导致时域的周期化，总之，一个域的离散化对应另一个域的周期化。334.3级数（DFS）离散各种信号变换在时域、频域上对称性的一规律可概括归纳为：1在某一个域（时域或频域）中是连续的，相应地在另一个域（频域或时域）中肯定是非周期性的。在某

15、一个域（时域或频域）中是离散的，相应地在另一个域（频域或时域）中肯定是周期性的。2上述规律是由所决定的。变换的对称性（对偶性）344.3离散级数（DFS）离散级数DFS4.3.2对于连续周期函数x(t)，有px (t) )ejk 1 tX (kpp1k 1T10 x (t)e jk X (k ) t1p1pT1对x p (t)进行抽样，变成了离散时间周期信号x ps (nT) 或x p (n)（以抽样序列形式的x p (n)为例），周期序列在时域可用复指数序列级数来表示，将t = nT、X p (k1 ) X p (k)代入上式中，得jk( 1)nTkx (nT) x (n)jknX (k)e

16、X (k)eT1ppppk35 T 11N 2 ,T1T14.3级数（DFS）离散从而有记作k rN (n) k (n)由于复指数序列的周期性，显然有361x (nT) x (n) X (k)ejk( T )nT pppk X (k)ejk1npkj2 knk (n) e Nj 2 kn e j k 1 n eN4.3级数（DFS）离散由上述分析可知：周期离散信号在时、频域上均为周期序列，根据周期信号的特点，当k变化一个N的整数倍时，得到的是完全一样的序列，所以，一个周期序列可以表示成一个有限项（N项）指数序列分量的叠加（即用任一个周期的序列情况，可以描述、代表所有其他周期序列的情况），则37

17、N 1xp (n) X p (k )k rN (n) X p (k)k (n)k k 0N 1j2 kn X p (k)e Nk 04.3级数（DFS）离散j2 kn NN 11上表示为 X p (k )ek 0 xp (n) N级数（DFS）的定义式，是反变换的概念。上式就是离散根据反变换的表达式来导出正变换X p (k)的表达式38N 1 j2 knX p (k) xp (n)eNn04.3级数（DFS）离散级数的正变换以符号DFS表示，级数的反变换，符号IDFS表示，离散写成 j 2为表达简洁,引入符号WN eN39N 1 j2 knX p (k ) DFSxp (n) xp (n)eN

18、(4.26)n01 N 1j2 knxp (n) IDFS X p (k) X p (k )e N(4.27)N k 04.4 离散变换（DFT）DFT要解决两个问题：一是离散与量化，二是快速运算。离散量化DFT(FFT)信号处理40傅氏变换4.4 离散变换（DFT）一.DFT是重要的变换1.分析有限长序列的有用工具。2.在信号处理的理论上有重要意义。3.在运算方法上起作用，谱分析、卷积、相关都可以通DFT在计算机上实现。414.4 离散变换（DFT）变换DFT定义式4.4.1离散对于一个周期为N的周期序列x p (n)，把它的第一个周期的有限长序列定义为这一周期序列的主值序列，用x (n)表

19、示0 n N 1x(n) xp,n(),0其它nxr)N42n( p)x(n r4.4 离散变换（DFT）周期序列X p (k)、x p (n)换成主值序列X (k)、x (n)，这样就得到了两个有限长序列的变换对，并表示为式（4.35）称为离散示，式（4.36）是离散IDFT表示正变换，以符号DFT表反变换，以符号43N1X(k) DFTx(n) x(n)Wkn ,0 k N 1(4.35)Nn01 N1knx(n) IDFTX(k) X(k)WN,0 n N 1(4.36)N k04.4 离散变换（DFT）DFT ， IDFT可简写为:式中，X (k)与x (n)分别为N行的列矩阵，分别为

20、N N 的对称方阵。而Wn k与W- n k例4.2用矩阵形式求矩形序列x (n) = R 4 (n)的DFT，再由所得X (k)经IDFT求 x (n)，验证所求结果的正确性。44X(k) Wnkx(n)(4.39)x(n) 1 WnkX(k)(4.40)N4.4 离散变换（DFT）4.4.2变换DFT与序列离散变换的关系设一有限长序列x (n)长度为N点，其z变换为N 1X (z) x(n)zn n0因序列为有限长，满足绝对可和的条件，其z变换的收敛域为整个z平面，必定包含圆，则序列的变换为N 1 x(n)e jnn0X (ej ) X (z) |j z e454.4 离散变换（DFT）圆

21、（表示为e j ）均匀现以为间隔，把等分为N个点，则在第k个等分点j2 kn NN 1X (ej ) | x(n)e DFTx(n) X (k ) 2 kn0NX (k ) X (ej ) | X (z) | 或 2 kNj2 k Nz e由上式可以得出：有限长序列的DFT就是序列在圆上的z2 1 变换（即序列变换）在圆上以为间隔N的抽样值，参见下图。46 21N4.4 离散变换（DFT）jIm z2/N2 0DFT与序列变换对比474. 5离散变换的性质1线性特性若 :则X (k) = DFT x (n) ,Y (k) = DFT y (n)DFT a x (n) + b y (n) = a

22、 X (k) + b Y (k)式中，a、b为任意常数。如果两个序列的长度不相等，以最长的序列为基准，对短序列要补零，使序列长度相等，才能进行线性相加，经过补零的序列频谱会变密，但不影响问题的性质。484. 5.时移特性离散变换的性质2（1）圆周移位圆周移位也叫循环移位，简称圆移位。它是序列的这样一种移位：将一有限长序列x (n)，进行周期延拓，周期为N，周期序列x p (n) ，然后对周期序列x p (n)作m位移位处理得移位序列x p(n-m)，再取其主值序列（x p(n-m)与一矩形序列RN (n)相乘），得x p (n-m)R N (n)，就是所谓的圆周移位序列。494. 5离散变换的

23、性质x (n)n0N-1504. 5离散x(n)变换的性质x(n)N周期延拓n0 x n 2Nx ( n2)左移20n514. 5离散变换的性质x (n 2) RN(n)N取主值n0N-1524. 5离散变换的性质2.圆周位移的含义取主值序列，即只观察n=0到N-1这一主由于值区间，当某一抽样从此区间一端移出时，与它相同值的抽样又从此区间的另一x(n) 端进来。如果把x(n) 排列一个N等分的圆周上，序列的移位就相当于 x(n) 在圆上旋转，故称作圆周移位。当围着圆周观察几圈时，x (n) 。看到就是周期序列 :534. 5离散变换的性质21n=0左移顺时3N=645544. 5离散变换的性质

24、（2）时移定理所谓时移定理是指：mk NWX() kDFT x (n) = X (k)若则DFT x(n-m)R N (n) =p时移定理表明：序列在时域上圆周移位，频域上将产生附加相移。554. 5 离散移特性频变换的性质3DFT x (n) = X (k)若l nk)x( n)WX(Rl(k)DFT则NpN( ln n)l ) Rk )XID FT k(xW并pNN上述特性表明：若序列在时域上乘以复指数j 2 ln W ln eN序列，则在频域上，X (k)将圆N周移位l 位，这可以看作调制信号的频谱搬移，因而又称“调制定理”。564. 5离散变换的性质4圆周卷积特性（1）时域圆周卷积若对

25、N点的序列有X (k) DFT x (n) , H (k) DFT h (n) ,Y (k) DFT y (n) ，Y (k) = X (k) H(k)N 1则y(n) IDFTY (k )x(m)h (n m)R(n)pNm0若x (m)保持不移位，h是n)圆周移位，故称即为圆周卷积。N 1h (n) = x(m)hp (n m)R N (n)y (n) = x (n)m057N1 x(m)hp (n m)R N (n)m04. 5离散变换的性质（2）频域圆卷积y (n) = x (n) h (n)若：则：N 1Y (k ) DFT y(n) 1 X (l)H(k l)R(k )pNNl 0

26、58DFT变换的性质N 1N 1= x(m)y(n m) x(m)yk(n m)IDFT X(k)Y (k) = 反褶循环移位相乘相加 0N 1 x(m)y(n m)x(n) y(n) =频域卷积DFTx(n)y(n) =m =0 编程实现容易 1 X(k) Y (k)N59也是一种卷积! 为了突出新“卷积”与“旧”卷积的不同, 同时也为了突出它们之间的相同, 称过去传统的卷积为线卷积,而称此“新卷积”为序列的圆周卷积，简称圆卷积。4. 5离散变换的性质5奇偶性（1）实数序列设x (n)为实序列，X (k) DFT x (n) ，则j2 nk NN 1X (k) x(n)en0N 1N 1 x

27、(n) cos 2nk j x(n) sin 2nkNNn0n0 X R (k) jX I (k)可知：X (k)的实部为k的偶函数 ，X (k)的虚部是k的奇函数。604. 5离散变换的性质X (k)的幅度和相位分别为( k )|k )2R2I|XX(X ()kX I(k)(X)k argarctanX R(k)设x (n)是实序列，其DFT可写成kDFT(X)x n()N 1Wnk x(nn0)N*N 1N 1 x (nx N( WN nkn)k)n)WNNn0*(n0(4.53)XN)k614. 5离散变换的性质从而有| X(k)| X*(Nk)| X(Nk)|(4.54)(4.55)a

28、rgX(k)argX (Nk)argX(Nk)*由上述式子表明：实数序列x (n)的离散变换X (k)，在0至N的范围内，对于N/2点，| X (k) | 呈半周期偶对称分布，arg X (k) 呈半周期奇对称分布。但由于长度为N的X (k)有值区间是0 （N-1），而在式（4.53）中增加了第N点的数值，因此所谓的对称性并不是很严格。624.5离散变换的性质（2）复数序列对于共轭复数序列。若有限长序列x * (n)是x (n)的共轭复数序列，并设 x xn)xx(n )( n *)(RjIx (x (n)n)(n)jRIn (1(x 2) *x)n(x)nR1j n I ()*x(x)n(x

29、)n2634. 5离散变换的性质则(n) 1 X (k) X *(N k)X (k) DFTx(4.57)RR2X (k) DFT jx (n) 1 X (k) X *(N k)(4.58)II2X (k) XR (k) XI (k)(4.59)利用式（4.57）、（4.58）可以计算出一个N点复序列DFT的同时，计算出两个N点实序列的DFT。644. 5离散变换的性质6 帕若则定理X (k) DFT x (n) N 1N 1| x(n) |2 1 | X (k) |2Nn0k 0上式左端代表离散信号在时域中的能量，右端是代表在频域中的能量，表明变换过程中能量是守恒的。65计算DFT的快速算法

30、- FFTN 1n =0 x(n)W nk ,DFT x(n) =(k = 0,1, N 1)N计算DFT的计算量：每算一个X(k)，需要N次复数乘法，N-1次加法。因此，N点DFT需要N*N次复数乘法，N(N-1)次复数加法。尽管预先算好并保存旋转因子W k可以节省部分运N算，但按定义求DFT的运算量仍然很大。66直接计算DFT的复杂度为O(N2)4.6变换（FFT）和改进思路快速4.6.1DFT直接运算1DFT直接运算的工作量直接对DFT进行计算的基本问题是运算量大，很难实现信号的实时处理，如某序列2Nj ex(n)，N 4，WN，则序列x (n)的DFT为00 xW(0) X (0W)0

31、W0 W2 W4W6W W WW03 Wx(1) X (1) 1W 006 xW(2) X (2W)2 X (3)39x(3)WW674.6变换（FFT）快速若要求X (k)的N = 4个值，N 2 = 4 2 =16，N (N-1) 12，复数乘的次数：复数加的次数：这样简单的DFT计算，其计算量已经不小。如果N =2 10 = 1024，则复数乘的次数：复数加次数：N 2 =1,048,576， N 2 =1,048,576，难以实现信号的实时处 理，若N大大增加，运算量也会随之大大增加，实时处理几乎就变得不可能了，因此必须改进DFT的算法。684.6变换（FFT）快速2改进思路N 1nn

32、kDFT(DFT的定义(X式)为kxn)x( W )Nn0W nk的周期性（1）NnW（2）Wnk的对称性NNj 2 N W 21eN2NW69(nk N )NWN2W nkW 2 nkNNNnknW( N )k Wn (lN )k Wk(mN )NNNN4.6变换（FFT）快速将上述（1）、（2）中的结果，代入矩阵W，可以简化为 0W0WW0W0 W2 W4W600W0W0 W0W00W W WWW W WWW WWW 031 101W WW 0W6W0 200W 09W3011W W（）矩阵W中，许多元素是相等的，可明显减少计算量。（）由于运算量正比于N2，因此可以把大点数（大N）DFT的

33、计算化为小点数（如N/2又可进一步地把，）DFT计算量大幅度减下来。综合应用上述的改进思路，实现变换的快速计算的Fourier Transform）。算法，就是快速变换，FFT（Fast70FFT的原理特别说明：FFT是DFT的快速算法，不是新的变换方法。其算法基础是：W的两个性质。 1. W具有周期性( k m N ) n Wnk NWN 2. W具有对称性( nk N ) WnkW2DFT的复杂度与点数N有关！71N点DFT运算可以分解为两组N/2 点DFT运算，然后再取和。经过周期性与对称性简化之后,容易发现DFT运算中存在着不 必要的重复计算,避免这种重复,是简化运算的关键.4.6变换

34、（FFT）快速4.6.2基2按时间抽取的FFT算法（时析型）1算法原理“基2”序列x (n)，设：N = 2 M （M为整数），如果N不是2的幂次，应在序列后面补零到2 M ，这是“基2”的意思。随后按照n的奇偶性以及时间的先后抽取序列值，把序列分成奇数序号与偶数序号两组序列之和（大点数化为小点数），这也就是所谓的“按时间抽取”的基本含意。1FFT的原理偶数nx(n)W nkx(n)W nkX(k) =+NN奇数nN 1N 122)rk)rkr =0r =0 x(2r)(W 2x(2r + 1)(W 2+W k=NNN+ W k=Ny(r) = x(2r)Nr = 0,1, 2. 1z(r)

35、= x(2r + 1)22N 12 x (2r + 1)WNrkr = 02N 12 x (2r )WNrkr = 02FFT的原理WkN注意Y(k)与Z(k)的周期是N/2 !3N1N 1 2rk2rk x(2r)WN /2 = y(r)WN /2 =Y(k) r=0r=0k = 0,1,2.N 1N 1N 12 22 x(2r + 1)Wrk= z(r)Wrk= Z(k) r=0N /2r=0N /2FFT的原理(k ) N N WW k W kW22NNNN 于是，N点X(k)可用N/2点的Y(k)和Z(k)来计算：X(k) = Y (k) + Wk Z(k)NN(+k )X(N+ k)

36、 = Y (NN2+ k) + W+ k)Z(2N22= Y (k) Wk Z(k)N4k = 0,1, N 12Y (N + k ) = Y (k )2Z (N + k ) = Z (k )2FFT的原理8点示例X(k) = Y (k) + Wk Z(k)NX(N + k) = Y (k) Wk Z(k)N218点DFT4点DFT（先按奇偶序分组，再求4点DFT）500k ,1 , N ,26420FFT的原理 8点示例8-DFT2-DFT4-DFT67753166422400FFT的原理 8点示例8-DFT4-DFT2-DFT1-DFT77764622400FFT的原理 8点示例 x(n)

37、 X(k)不必算啦8-DFT4-DFT2-DFT1-DFT8777365146622244000逐级迭代计算FFT 就地置换无需缓存X (0)X (1)X (2)X (3)?X (4)X (5)X (6)X (7)?9第三级第二级第一级x(7)N/4点 DFTx(3)x(5)x(1)N/2点 DFTN/4点 DFTx(6)x(2)x(4)x(0)N/4点 DFTN/2点 DFTN/4点 DFTN点组合相加FFT的流程图x(0)x(4) x1(0) x1(1) x2(0) x2(1) X (0)X (1)蝶形运算单元x(2)x(6) x1(2) x1(3) x2(2) x2(3) X (2)X

38、(3)群x(1)x(5) x2(4) x2(5) X (4)X (5) x1(5) x(3)x(7) x1(6) x1(7) x2(6) x2(7) X (6)X (7)10第三级第二级第一级x1(4)FFT的蝶形运算单元 x(0) x1(0) W 0 x(4) x1(1) 可以共享W 0 x(4)W 0 x(4)W 011一个蝶形单元只需一次复数乘法和两次复数加法FFT算法流程说明 全部计算分解为M级，或称为M次迭代。 每级都包含N/2个蝶形单元。12 输入序列x(n)按码位倒读顺序排列，输出序列 X(k)按自然顺序排列。FFT算法流程说明 同一级中，各个群的W分布规律完全相同13 每个蝶形

39、单元都包含乘Wnk与-Wnk的运算（可简化为乘Wnk与加、减法各一次）。 每级的若干蝶形单元组成“群”。第1级群数为 N/2，第2级群数为N/4，第i级群数为N/2i，最后一级的群数为1。FFT算法流程说明 各级中W的排列规律（自上而下） N第1级：W 0N第2级：W 0W4NNW的指数为：次序*本级群数 N 3 N0第3级：WNWN8W8N次序 N2 N第i级：W 0W2iWW2iNNNN第M级：W 0W 1W 2W 3NNNNN14(2i1 1)N2iFFT算法流程说明15所谓“倒读”，是指按二进制表示的数字首尾位置颠倒，重新按十进制读数。输入序列x(n)的排列次序不符合自然顺序。此现象是

40、由于按n的奇偶分组进行DFT运算而造成的，这种排列方式称为“码位倒读”的顺序。码位倒读FFT算法流程说明码位倒读示例（N=8）自然顺序二进制顺序码位倒置码位倒读顺序0011004201001023011110641000011510110156110011371111117FFT算法的复杂度N 2MkW设预先计算好N一个蝶形单元的计算需要2次复数加法和1次复数乘法对任一次迭代：共有N/2个蝶形单元，因此需N次复数加法和N/2次复数乘法M 2 N / 2 N log2N 复数加法次数M次迭代的总计算量为M N 1 N log 2N22N )17IDFT同样可用FFT实现，算法复杂度相同。算法复杂

41、度O(N log2复数乘法次数4.7IDFT的快速算法（IFFT）N 点IDFTx(n)=x (n)+W-n x(n)2r) 21N2X(x(n)1X (1,k)N2( r 0,1),1,n = 0 , 1, ( ,N/2)-10k ,N, 1)(N 点IDFT) 2x(n+N/2)WN-nX(2 r1x2(n)-n x= x (n)-W(n)1N2图4.15IFFT的蝶形图184.8FFT的实现1FFT算法的C语言程序设计FFT运算的基本单元是“蝶形单元”，其蝶形运算式为Xk)Yk( k)NW(Z )(Zk) kNk( k )Y 2k()WNX为简便，把所有蝶形单元的运算表示为A kWDCN

42、WkCBDNA和B蝶形单元的输出，C和D是输入。194.9离散变换的应用4.9.1用FFT实现快速卷积1用FFT计算线卷积的基本原理和方法将进行卷积的两序列的长度（即两序列的点数，分别为N1和N2）均加长至NN12 1+N，然后再进行圆卷积，则其圆卷积的结果与线卷积的结果相同。根据上述原理，可以得出用FFT求解两序列线卷积的原理框图。204.9离散变换的应用x (n)N1 点y(n)= x(n)*h(n)X (k)H (k)h (n)N2 点图4.18 应用FFT计算线卷积21N点FFTH (k)序列补零加长至 NN1+N2 -1IFFTN点FFT序列补零加长至 NN1+N2 -1为保证FF运

43、算：N=2M4.9离散变换的应用“分段快速卷积”的方法-（“相加法”）一个序列较短，一个序列相对较长，如果短序列补零多，会导致无谓计算量的增加。这时，可采用：（1）把序列分成若干小段，每小段分别与短序列作卷积运算；（2）把所有的分段卷积结果相叠加，就是线卷积的最后结果。下面对这种所谓的“相加法”作一简单的介绍。224.9离散变换的应用设x (n)为无限长序列，h (n)的长度为M，将x (n)进行分段,它们的线卷积可表示为n()xx)每段线卷积的结果长度均为N+ M 1，每段的起始序列号k N。这表明：相邻卷积段存在M 1个点的段。快速卷积法（圆卷积）求解各段卷积，可以在各段的尾部补M 1个零

44、。23n() h (n)x ( m)(hn)mm0N 12 N 1m( h) n (m ) x(m)( h n)mm0m N(k 1) N 1x(m) h ( n)m(4.77mkN（a）0nx 0 (n)（b）n0N-1N+M-2x 1 (n)（c）n0N-1N+M-2x 2 (n)（d）24y 0 (n)叠加（e）M-1项0N+M-2n叠加y 1 (n)M-1项（f）N2N+M-2ny 2 (n)（g）2N03N+M-2 n图4.19相加法分段卷积254.9离散变换的应用4.9.2连续时间信号的数字谱分析连续时间信号要应用FFT进行分析和处理，必须在时、频域对参数进行：（1）有限化；（2）

45、离散化处理。1时域的有限化和离散化时域的有限化，就是对信号的延续时间沿时间轴进行截断。时域的离散化，就是对连续信号进行抽样。26x s (t) ， x a (t)0T1tT图4.22连续信号时域的有限化和离散化有限化和离散化处理后原连续信号的频谱应近似表示为X27N 1()T x (n)TjenTaan0Tn 0,1, 2, ., N 1,xa t xs t T4.9离散变换的应用2频域的有限化和离散化与时域类似，应对x s ( t ) 的频谱X和离散化处理。X s ()s ()进行有限化- s s0图4.23时域离散化后的x s ( t )的频谱X()s频域的有限化，在频率轴上取一个周期的频

46、率区间，通常取所谓的“主值区间”，即 0 , s 。频域的离散化（频域抽样）就是对一个周期内的频谱进行抽样。284.9X a (k 1 )离散变换的应用用来表示非周期信号频谱离散化后的频谱。其结果分别如下图和下面所推得的公式X a (k1 ) s0 1图4.24信号x s ( t )频谱上一个周期上的有限化和离散化X29N 1 jk 2 nT(ka) 1 T ax()nTeNTn0N 1 j2 nkT x (an)T e Nn0T DFTx an(T)TX()k4.9离散变换的应用3误差分析（1）混叠误差产生混叠误差的原因是由于信号的离散化是通过抽样实现的，而抽样频率再高总是有限的，除带限信号

47、外，如果信号的最高频率 m ，则实即 s 2 m ，抽样际器件抽样定理，过程如果不满足抽样定理，就会产生频谱的混叠，即混叠误差，要减少或避免混叠误差，应提高抽样频率，以设法满足抽样定理，或者采用抗混叠滤波这样的信号预处理措施。304.9离散变换的应用（ 2）栅栏效应对于非周期信号来说，理论上应当具有连续的频谱，但数字谱分析是用DFT来近似，是用频谱的抽样值近连续频谱值，只能观察到有限（ N ）个频谱值，每一个间隔中的频谱都观察不到了，如同通过“栅栏”观察景物一样，一部分景物被“栅栏”所阻档，看不见，把这种现象称为栅栏效应，连续时间信号只要采用数字谱分析的方法，就必定产生栅栏效应，只能减小而无法

48、避 免。把能够感受的频谱最小间隔值，称为频谱分辨力，一般表示为 F 。314.9离散变换的应用若抽样周期为T，抽样点数为N ，则有 F = 1 / ( NT )NT 实际就是信号在时域上的截断长度T 1 ，分辨力 F 与T成反比，因此为了减小栅栏效应，1应当增加T 1 ，可用两种方法来实现：通过加长数据的截断长度，即增加数据点数N在所截断得到的数据末端补零，增加T 1324.9离散变换的应用（3）截断误差（频谱泄漏）截断误差就是由于对信号进行截断，把无限长的信号限定为有限长，即令有限区间以外的函数值均为零值的近似处理而产生的，这种处理相当于用一个矩形（窗）信号乘待分析的连续时间信号。信号被截断

49、后的频谱为) 33Y( )1 X )W()(a21 ( X )W (d2a4.9离散变换的应用 t xa (t) cos0t设则有Xa () ( 0 ) ( 0 )W() T Sa( T1 )121212W() ( ) ( Y () X () W() )a00 1 W( ) 1 W( )0022画成谱图，。34X a ()(-0)x a ( t ) = cos0t( +0)- 0 0-T1/20T1/2t0W ()w (t)主瓣旁瓣-T1 /20T1/2t-2/T02/T11Y ()y (t)-T1/20T1/2t-0频谱泄漏现象 00图4.26354.9离散变换的应用余弦信号被矩形窗信号截断

50、后，两根冲激谱线变成了以0 为中心的Sa（）形的连续谱，相当于频谱从0 处“泄漏”到其它频率处，也就是说，原来一个周期内只有一个频率上有非零值，而现在几乎所有频率上都有非零值，这就是频谱泄漏现象。更为复杂的信号，造成更复杂的“泄漏”，互相叠加，造成信号难以分辨。虚拟频谱分析仪364.9离散变换的应用减小频谱泄漏的方法一般有两种：增加截断长度T 1改变窗口形状从原理上看，要减少截断误差，应使主瓣和 / 或旁瓣缩小，从而使实际频谱接近原频谱。但是从能量守恒的角度分析：旁瓣减小，则主瓣增大；或旁瓣增大，则主瓣缩小，后者容易造成旁瓣、主瓣分辨不清，引起有两个主瓣的误解。因此，一般宁可以增大主瓣为代价，

51、缩小旁瓣，使能量集中于主瓣。374.9离散变换的应用可以考虑改用幂窗、 三角函数窗和指数窗。由于这些窗口函数时域上变化相对平缓，窗口的边缘值为零，高频分量衰减增快，旁瓣明显受到抑制，减少了频谱泄漏。但旁瓣受到抑制的同时，主瓣相应加宽，而且旁瓣只是受到抑制，不可能完全被消除，因此不管采用哪种窗函数，频谱泄漏只能减弱，不能消除，抑制旁瓣和减小主瓣也不可能同时 兼 顾 ， 应 根 据 实 际 需 要 进 行 综 合 考 虑 。384.9离散变换的应用4周期信号的数字谱分析周期连续信号x p ( t )的频谱由下式近似计算,1)()x2,1连续周期信号是非时限信号，若要用FFT做数字谱分析，必须在时域进行有限化（截断）和离散化（采样）处理，对于一个带限（频谱为有限区 间）的周期信号，若抽样频率满足抽样条件，并且作整周期截断，不会产生频谱的混叠。实际 上，要实现真正的整周期截断是很难的，如果是非整周期截断，则会产生频谱的泄漏误差，要通过加合适窗的方法来减少频谱泄漏。39n p IDFTN(X)kn0,1N ,XDF(T k) 1( x)n(k0,1 , N2 ,p N4.9离散变换的应用5DFT参数的选择（1）抽样频率f s 。根据抽样定理