《数字信号处理：第三章 离散付里叶变换及其快速算法(重点)》由会员分享，可在线阅读，更多相关《数字信号处理：第三章 离散付里叶变换及其快速算法(重点)（207页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章离散付里叶变换及其快离散付里叶变换及其快速算法速算法(重点重点)3.1离散付里叶变换离散付里叶变换(DFT)3.2利用利用DFT进行频谱分析进行频谱分析3.3快速付里叶变换快速付里叶变换(FFT)3.4FFT应用中的几个问题应用中的几个问题前前面面我我们们讨讨论论用用付付里里叶叶变变换换和和z变变换换来来描描述述一一般般的的序序列列和和线线性性时时不不变变离离散散系系统统。但但有有时时序序列列是是有有限限长长序序列列，如如FIR系系统统的的单单位位脉脉冲冲响响应应就就是是一一个个有有限限长长序序列列。对对于于这这种种情情况况，正正如如本本章章要要讨讨论论的的，可可以以导导出出另另一
2、一种种付付里里叶叶表表示示式式，称作离散付里叶变换称作离散付里叶变换(DFT)。离离散散付付里里叶叶变变换换是是有有限限长长序序列列付付里里叶叶表表示示式式，它它本本身身也也是是一一个个序序列列，而而不不是是一一个个连连续续函函数数，它它相相当当于于把把信信号号的的付付里里叶叶变变换换进进行行等等频频率率间间隔隔取取样样。离离散散付付里里叶叶变变换换除除了了作作为为有有限限长长序序列列的的一一种种付付里里叶叶表表示示式式在在理理论论上上相相当当重重要要外外，由由于于存存在在计计算算离离散散付付里里叶叶变变换换的的有有效效算算法法(FFT)，因因而而其其在在实现各种数字信号处理算法时起着核心作用
3、。实现各种数字信号处理算法时起着核心作用。z变换变换分析工具分析工具付里叶变换（付里叶变换（DTFT）离散付里叶变换离散付里叶变换(DFT)意义意义在频域上实现数字处理在频域上实现数字处理有各种快速实现算法有各种快速实现算法(FFT)一般序列一般序列有限长序列有限长序列3.1离散付里叶变换离散付里叶变换(DFT)为为了了便便于于更更好好地地理理解解DFT的的概概念念，先先讨讨论论周周期期序序列列及及其其离离散付里叶级数散付里叶级数(DFS)表示。表示。3.1.1离散付里叶级数离散付里叶级数(DFS)我们用我们用来表示一个周期为来表示一个周期为N的周期序列，即的周期序列，即，k为任意整数，为任意
4、整数，N为周期为周期。 周期序列不能进行周期序列不能进行Z变换，因为其在变换，因为其在n=- 到到+ + 都周而复始永不衰减，在整个都周而复始永不衰减，在整个z z 平面上任何地方找不到平面上任何地方找不到一个衰减因子一个衰减因子zz能使序列绝对可和：能使序列绝对可和： 即即 z z 平面上没有收敛域。但是，正象连续时间周期信号平面上没有收敛域。但是，正象连续时间周期信号可用付氏级数表达，周期序列也可用离散的付氏级数来可用付氏级数表达，周期序列也可用离散的付氏级数来表示，也即用周期为表示，也即用周期为N N的正弦序列的正弦序列( (或复指数序列或复指数序列) )来表示。来表示。周期为周期为N
5、N的正弦序列其基频成分为：的正弦序列其基频成分为： k k次谐波序列为：次谐波序列为：但离散级数所有谐波成分中只有但离散级数所有谐波成分中只有N个是独立的，个是独立的，这是与连续付氏级数的不同之处，这是与连续付氏级数的不同之处，即即因此因此将将周周期期序序列列展展成成离离散散付付里里叶叶级级数数时时，只只需需取取k=0到到(N-1)这这N个个独独立立的的谐谐波波分分量量，所所以以一一个个周周期期序序列列的的离离散散付付里里叶叶级级数数只只需包含这需包含这N个复指数，个复指数，(1)利用正弦序列的周期性可求解系数利用正弦序列的周期性可求解系数。方法：方法：将将(1)式两边乘以式两边乘以，并对一个
6、周期求和，并对一个周期求和上上式式中中部部分分显显然然只只有有当当k=r时时才才有有值值为为1,其其他他任任意意k值值时时均均为为零零,所以有所以有或写为或写为1)可求可求N次谐波的系数。次谐波的系数。2)也是一个由也是一个由N个独立谐波分量组成的傅立叶级数。个独立谐波分量组成的傅立叶级数。3)为周期序列，周期为为周期序列，周期为N。周期序列的离散付里叶级数在频域上仍是一个周期序列。是一个周期序列的离散付里叶级数(DFS)变换对，这种对称关系可表为：习惯上：记，DFS变换对公式表明，一个周期序列虽然是无穷长序列，但是只要知道它一个周期的内容(一个周期内信号的变化情况)，就可以表示这个序列，所以
7、这种无穷长序列实际上只有N个序列值是有用的，因此周期序列与有限长序列有着本质的联系。则则DFS变换对可写为变换对可写为DFS离散付里叶级数变换IDFS离散付里叶级数反变换。DFS的几个主要特性：的几个主要特性：假假设设都都是是周周期期为为N的的两两个个周周期期序序列列，各自的离散付里叶级数变换为：各自的离散付里叶级数变换为：1)线性性线性性 a,b为任意常数为任意常数 2)序列移位序列移位证：证：因为因为及及 都是以都是以N为周期的函数，所以有为周期的函数，所以有由于与对称性，同样可证明3)周期卷积周期卷积若则或证：这这是是一一个个卷卷积积公公式式，但但与与前前面面讨讨论论的的线线性性卷卷积积
8、的的差差别别在在于于，这这里里的的卷卷积积过过程程只只限限于于一一个个周周期期内内(即即m=0N-1)，称称为为周周期期卷卷积。积。例：例：、，周期为，周期为N=7,宽度分别为宽度分别为4和和3，求周期卷积。求周期卷积。结论：卷积结果仍为周期序列，周期为结论：卷积结果仍为周期序列，周期为N。周周期期卷卷积积由于由于DFS与与IDFS的对称性，对周期序列乘积，存的对称性，对周期序列乘积，存在着频域的周期卷积公式，在着频域的周期卷积公式，若若则则3.1.2离散付里叶变换离散付里叶变换(DFT)从从上上节节的的讨讨论论，我我们们知知道道周周期期序序列列实实际际上上只只有有有有限限个个序序列列值有意义
9、，因此它的许多特性可推广到有限长序列上。值有意义，因此它的许多特性可推广到有限长序列上。一个有限长序列一个有限长序列x(n)，长为，长为N，为为了了引引用用周周期期序序列列的的概概念念，假假定定一一个个周周期期序序列列，它它由长度为由长度为N的有限长序列的有限长序列x(n)延拓而成，它们的关系为：延拓而成，它们的关系为：周期序列与有限长序列周期序列与有限长序列的关系：的关系：周期序列的主值区间与主值序列周期序列的主值区间与主值序列：对于周期序列对于周期序列，定义其第一个周期，定义其第一个周期n=0N-1，为，为的的“主值区间主值区间”，主值区间上的序列为主值序列，主值区间上的序列为主值序列。x
10、(n)与与的关系可描述为：的关系可描述为：数学表示：数学表示：RN(n)为矩形序列。为矩形序列。符号符号(n)N是余数运算表达式，表示是余数运算表达式，表示n对对N求余数。求余数。例：例：是周期为是周期为N=7的序列，求的序列，求n=11和和n=-2对对N的的余数。余数。因此因此频域上的主值区间与主值序列：频域上的主值区间与主值序列：周期序列周期序列的离散付氏级数的离散付氏级数也是一个周期序也是一个周期序列，也可给它定义一个主值区间列，也可给它定义一个主值区间，以及主值序列，以及主值序列X(k)。数学表示：数学表示：再看周期序列的离散付里叶级数变换再看周期序列的离散付里叶级数变换(DFS)公式
11、：公式：这两个公式的求和都只限于主值区间这两个公式的求和都只限于主值区间(0N-1)，它，它们完全适用于主值序列们完全适用于主值序列x(n)与与X(k)，因而我们可得，因而我们可得到一个新的定义到一个新的定义有限长序列离散付里叶变换定义。有限长序列离散付里叶变换定义。长长度度为为N的的有有限限长长序序列列x(n)，其其离离散散付付里里叶叶变变换换X(k)仍仍是是一个长度为一个长度为N的有限长序列，它们的关系为：的有限长序列，它们的关系为：x(n)与与X(k)是是一一个个有有限限长长序序列列离离散散付付里里叶叶变变换换对对，已已知知x(n)就就能能唯唯一一地地确确定定X(k)，同同样样已已知知X
12、(k)也也就就唯唯一一地地确确定定x(n)，实实际际上上x(n)与与X(k)都都是是长长度度为为N的的序序列列(复复序序列列)，都都有有N个独立值，因而具有等量的信息。个独立值，因而具有等量的信息。有限长序列隐含着周期性。有限长序列隐含着周期性。例：是一个N=12的有限长序列，由DFT得：DFT特性：特性：以以下下讨讨论论DFT的的一一些些主主要要特特性性，这这些些特特性性都都与周期序列的与周期序列的DFS有关。有关。假假定定x(n)与与y(n)是是长长度度为为N的的有有限限长长序序列列，其其各自的离散付里叶变换分别为：各自的离散付里叶变换分别为：X(k)=DFTx(n)Y(k)=DFTy(n
13、)(1)线性线性DFTax(n)+by(n)=aX(k)+bY(k),a,b为任意常数为任意常数(2)圆周移位圆周移位有限长序列有限长序列x(n)的圆周移位定义为：的圆周移位定义为：f(n)=x(n+m)NRN(n)含义：含义：1)x(n+m)N表示表示x(n)的周期延拓序列的周期延拓序列的移位：的移位：2)x(n+m)NRN(n)表表示示对对移移位位的的周周期期序序列列x(n+m)N取主值序列取主值序列,所以所以f(n)仍然是一个长度为仍然是一个长度为N的有限长序列。的有限长序列。f(n)实实际际上上可可看看作作序序列列x(n)排排列列在在一一个个N等等分分圆圆周周上上，并并顺顺时时针旋转针
14、旋转m位。位。圆周移位圆周移位周期延拓，拓，左移2位取主值取主值圆周移位圆周移位移位前左移两位后证：利用周期序列的移位特性：实际上，利用的周期性，将f(n)=x(n+m)NRN(n)代入DFT定义式，同样很容易证明。序列圆周移位后的序列圆周移位后的DFT为为F(k)=DFTf(n)=同样，对于频域有限长序列同样，对于频域有限长序列X(k)的圆周移位，有的圆周移位，有如下反变换特性：如下反变换特性：IDFTX(k+l)NRN(k)=x(n)频域的圆周移位等效于时域序列的调制。(3)圆周卷积圆周卷积若若F(k)=X(k)Y(k)则则或或证：这个卷积可看作是周期序列卷积后再取其主值序列。将F(k)周
15、期延拓，得：则根据DFS的周期卷积公式：因0mN-1时，x(m)N=x(m)，因此经过简单的换元可证明：这这一一卷卷积积过过程程与与周周期期卷卷积积比比较较，过过程程是是一一样样的的，只只是是这这里里只只取取结结果果的的主主值值序序列列，由由于于卷卷积积过过程程只只在在主主值值区区间间0mN-1内内进进行行，所所以以实实际际上上就就是是y(m)的的圆圆周周移移位位，称称为为“圆圆周周卷卷积积”，习习惯惯上上常常用用符符号号“”表表示示圆圆周周卷卷积积，以以区区别别于于线线性性卷卷积。圆周卷积也称为循环卷积。可以证明：积。圆周卷积也称为循环卷积。可以证明： 1）由有限长序列）由有限长序列x(n)
16、、y(n)构造周期序列构造周期序列循环卷积过程循环卷积过程:2）计算周期卷积）计算周期卷积3）卷积）卷积结果取主值结果取主值圆周卷积计算：圆周卷积计算：在一个周期内对应点相乘相加在一个周期内对应点相乘相加同样，若f(n)=x(n)y(n)，则(4)有限长序列的线性卷积与圆周卷积有限长序列的线性卷积与圆周卷积(圆周卷积的应用圆周卷积的应用)实实际际问问题题的的大大多多数数是是求求解解线线性性卷卷积积，如如信信号号x(n)通通过过系系统统h(n)，其其输输出出就就是是线线性性卷卷积积y(n)=x(n)*h(n)。而而圆圆周周卷卷积积比比起起线线性性卷卷积积，在在运运算算速速度度上上有有很很大大的的
17、优优越越性性，它它可可以以采采用用快快速速付付里里叶叶变变换换(FFT)技技术术，若若能能利利用用圆圆周周卷卷积积求求线线性性卷卷积积，会会带带来来很大的方便。很大的方便。现现在在我我们们来来讨讨论论上上述述x(n)与与h(n)的的线线性性卷卷积积，如如果果x(n)、h(n)为为有有限限长长序序列列，则则在在什什么么条条件件下下能能用用圆圆周周卷卷积积代代替替线线性性卷积而不产生失真卷积而不产生失真?有限长序列的线性卷积：有限长序列的线性卷积：假定假定x(n)为有限长序列，长度为为有限长序列，长度为N，y(n)为有限长序列，长度为为有限长序列，长度为M，它们的线性卷积它们的线性卷积f(n)=x
18、(n)*y(n)也应是有限长序列。也应是有限长序列。因因x(m)的非零区间：的非零区间：0mN-1，y(n-m)的非零区间：的非零区间：0n-mM-1，这两个不等式相加，得：这两个不等式相加，得：0nN+M-2，在这区间以外或在这区间以外或x(m)=0，或，或y(n-m)=0，因而，因而f(n)=0。因此，。因此，f(n)是一个长度为是一个长度为N+M-1的有限长序列。的有限长序列。圆周卷积：圆周卷积：重新构造两个有限长序列x(n)、y(n)，长度均为LmaxN,M，序列x(n)只有前N个是非零值，后L-N个为补充的零值；序列y(n)只有前M个是非零值，后L-M个为补充的零值。为了分析x(n)
19、与y(n)的圆周卷积，先讨论其周期卷积。将x(n)，y(n)周期延拓：其中f(n)就是线性卷积，也就是说，的的周期卷积，是周期卷积，是x(n)、y(n)线性卷积的周期延拓，周期为线性卷积的周期延拓，周期为L。它们的周期卷积序列为：根据前面的分析，f(n)具有N+M-1个非零序列值，因此，如果周期卷积的周期Lp+q，所以组合数的FFT计算效率要高于直接计算法。上述分解原则可推广至任意基数的更加复杂的情况。例如,如果N可分解为m个质数因子p1,p2,，pm，即N=p1p2p3pm则第一步：可把N先分解为两个因子N=p1q1，其中q1=p2p3pm，并用上述讨论的方法将DFT分解为p1个q1点DFT
20、；第二步：将q1分解为q1=p2q2，q2=p3p4pm，然后将每个q1点DFT再分解为p2个q2点DFT；：依此类推，：通过m次分解，一直分到最少点数的DFT运算，从而获得最高的运算效率。其运算量近似为N(p1+p2+pm)次复数乘法和复数加法。但计算效率的提高是要以编程的复杂性为代价的，一般较少应用。p1=p2=pm=2，为基2FFT算法。6、Chirp-z变换变换采用FFT算法可以很快算出全部N点DFT值，即z变换X(z)在z平面单位圆上的全部等间隔取样值，但要求N为复合数。问题的提出：不需要计算整个单位圆上z变换的取样，如对于窄带信号，只需要对信号所在的一段频带进行分析，这时,希望频谱
21、的采样集中在这一频带内，以获得较高的分辨率，而频带以外的部分可不考虑。对其它围线上的z变换取样感兴趣，例如语音信号处理中，需要知道z变换的极点所在频率，如极点位置离单位圆较远，则其单位圆上的频谱就很平滑，这时很难从中识别出极点所在的频率，如果采样不是沿单位圆而是沿一条接近这些极点的弧线进行，则在极点所在频率上的将出现明显的尖峰，由此可较准确地测定极点频率。要求能有效地计算当N是素数时序列的DFT，因此提高DFT计算的灵活性非常有意义。螺旋线采样是一种适合于这种需要的变换，且可以采用FFT来快速计算，这种变换也称作Chirp-z变换。算法原理：算法原理：已知x(n)，0nN-1令z的取样点为，k
22、=0，M-1，M：采样点数，A、W：任意复数，其中：A0表示起始取样点的半径长度，通常A01；0表示起始取样点z0的相角；0表两相邻点之间的等分角；W0螺旋线的伸展率，W01则螺线内缩(反时针)；W0=1表示半径为A0的一段圆弧；A0=1这段圆弧是单位圆的一部分。图螺旋线采样计算z变换在采样点zk的值k=0,1,M-1显然，同直接计算DFT情况相仿，按照以上公式计算出全部M点采样值需要NM次复乘和(N-1)M次复加，当N及M较大时，计算量迅速增加，但通过一定的变换，以上运算可转换为卷积形式，从而可采用FFT进行，这样可大大提高计算速度。利用zk的表示式代入 nk可以用以下表示式来替换则定义：则
23、上式说明，如对信号x(n)先进行一次加权处理，加权系数为，然后通过一个单位脉冲响应为h(n)的线性系统，最后，对该系统的前M点输出再作一次的加权，就可得到全部M点螺旋线采样值。 系统的单位脉冲响应 与频率随时间成线性增加的线性调频信号相似，因此这种算法称为Chirp-z变换。xxx(n)g(n)X(zk)算法实现：由于输入信号输入信号g(n)是有限长的，长为是有限长的，长为N，但序列是无限长的，而计算0M-1点卷积g(n)*h(n)所需要的h(n)是是取取值值在在n=-(N-1)M-1那那一一部部分分的的值值，因因此此，可可认认为为h(n)是是一一个个有有限限长长序序列列，长长为为L=N+M-
24、1。所以，Chirp-z变换为两个有限长序列的线性卷积g(n)*h(n)，可用圆圈卷积通过FFT来实现。h(n)的主值序列可由h(n)作周期延拓后取0nL-1部分值获得，将与g(n)作圆周卷积后，其输出的前M个值就是Chirp-z变换的M个值。这个圆周卷积的过程可在频域上通过FFT实现。Chirp-z变换的计算步骤：变换的计算步骤：(1)求h(n)的主值序列(2)用FFT求的付里叶变换:H(k)=FFT,L点(3)对x(n)加权并补零(4)G(k)=FFTg(n),L点(5)Y(k)=G(k)H(k),L点(6)y(n)=IFFTY(k),L点(7),0kM-1计算量估算：乘法数估计(1)(2
25、)两步可以事先计算，不必实时计算。(3)(7)两步两次加权共计N+M次复乘，形成Y(k)需L次复乘，一个FFT与一个IFFT需Llog2L次乘，所以总乘法数：L+N+M+Llog2L。直接计算乘法数：NM可见，N及M较大时，用FFT实现Chirp-Z变换，速度上有很大的改进。Chirp-z变换的特点：变换的特点：1)输入序列的长度N与输出序列的长度M不需要相等；2)N及M不必是高度复合数，二者均可为素数；3)相邻采样点zk之间的角间隔0是任意的，即频率分辨频率分辨率是任意的率是任意的；4)围线是任意的，不必是Z平面的单位圆；5)起始点z0可任意选定，即可从任意频率上开始对输入数据进行窄带高分辨
26、率分析；6)若A=1,M=N,可用Chirp-z变换变换计算DFT(即使N为素数)。$3.3FFT应用中的几个问题应用中的几个问题1)实数序列的实数序列的FFT以上讨论的FFT算法都是复数运算，包括序列x(n)也认为是复数，但大多数场合，信号是实数序列，任何实数都可看成虚部为零的复数，例如，求某实信号y(n)的复谱，可认为是将实信号加上数值为零的虚部变成复信号(x(n)+j0)，再用FFT求其离散付里叶变换。这种做法很不经济，因为把实序列变成复序列，存储器要增加一倍，且计算机运算时，即使虚部为零，也要进行涉及虚部的运算，浪费了运算量。合理的解决方法是利用复数FFT对实数据进行有效计算，下面介绍
27、两种方法。(1)用用一个一个N点点FFT同时计算两个同时计算两个N点实序列的点实序列的DFT设设x1(n)、x2(n)是彼此独立的两个是彼此独立的两个N点实序列，且点实序列，且X1(k)=DFTx1(n)，X2(k)=DFTx2(n)则则X1(k)、X2(k)可通过一次可通过一次FFT运算同时获得。运算同时获得。算法如下：首先将x1(n)、x2(n)分别当作一复序列的实部及虚部,令x(n)=x1(n)+jx2(n)通过FFT运算可获得x(n)的DFT值X(k)=DFTx1(n)+jDFTx2(n)=X1(k)+jX2(k)利用离散付里叶变换的共轭对称性，有:有了x(n)的FFT运算结果X(k)
28、，由上式可得到X1(k)、X2(k)的值。(2)用一个用一个N点的点的FFT运算获得一个运算获得一个2N点实序列的点实序列的DFT设设x(n)是是2N点点的的实实序序列列，现现人人为为地地将将x(n)分分为为偶偶数数组组x1(n)和奇数组和奇数组x2(n)x1(n)=x(2n)n=0,1,N-1x2(n)=x(2n+1)n=0,1,N-1然后将然后将x1(n)及及x2(n)组成一个复序列：组成一个复序列：y(n)=x1(n)+jx2(n)通过通过N点点FFT运算可得到：运算可得到：Y(k)=X1(k)+jX2(k)，N点点根据前面的讨论，得到根据前面的讨论，得到 为求2N点x(n)所对应X(k
29、)，需求出X(k)与X1(k)、X2(k)的关系：0kN-1而 所以所以,0kN-1计算步骤：计算步骤：1)由由x1(n)及及x2(n)组成复序列，经组成复序列，经FFT运算求得运算求得Y(k)(N点点FFT)；2)利用共轭对称性求出利用共轭对称性求出X1(k)、X2(k)；3)最后利用上式求出最后利用上式求出X(k)；4)X(k)，k=N2N-1，由实序列频谱的对称性，由实序列频谱的对称性X(k)=X*(2N-k)得到。得到。相关的概念很重要，互相关运算广泛应用于信号分析与统计分析，如通过相关函数峰值的检测测量两个信号的时延差；由自相关计算信号的能量，实现匹配滤波和信号能量检测等。2)用用F
30、FT计算相关函数计算相关函数相关用途分析功率谱作为二阶矩，描述平稳信号的统计特性构成相关检测器线性相关线性相关两个实有限长序列两个实有限长序列x(n)与与y(n)的互相关函数定义为：的互相关函数定义为：-20-1001020-50050100150200250300m-20-1001020-50050100150200250300m幅度幅度(a)(b)图2.23(a)延迟序列的互相关函数和(b)自相关函数圆周相关定理圆周相关定理两个长为两个长为N的实离散时间序列的实离散时间序列x(n)与与y(n)的互相关函数的互相关函数为为则可以证明，则可以证明，rxy(m)的离散付里叶变换为的离散付里叶变换
31、为其中其中X(k)=DFTx(n),Y(k)=DFTy(n),Rxy(k)=DFTrxy(m)，0kN-1证：将证：将x(n)、y(n)的逆离散付里叶变换代入互相关函数定义式的逆离散付里叶变换代入互相关函数定义式因因x(n)是实序列，是实序列，x(n)=x*(n)，得，得因得证毕。互相关函数与信号功率谱互为傅立叶变换对。互相关函数与信号功率谱互为傅立叶变换对。当x(n)=y(n)时，得到x(n)的自相关函数为：维纳维纳辛钦定理：辛钦定理：自相关函数与信号功率谱互为傅立叶变换对。自相关函数与信号功率谱互为傅立叶变换对。上面的推导表明，互相关和自相关函数的计算可利用上面的推导表明，互相关和自相关函
32、数的计算可利用FFT实现。实现。由于离散付里叶变换隐含着周期性，所以用由于离散付里叶变换隐含着周期性，所以用FFT计算离计算离散相关函数也是对周期序列而言的。散相关函数也是对周期序列而言的。利用圆周相关定理计算两个有限长序列的线性相关时，利用圆周相关定理计算两个有限长序列的线性相关时，为避免混淆，需采用与由圆周卷积求线性卷积相类似的方为避免混淆，需采用与由圆周卷积求线性卷积相类似的方法。法。利用利用FFT求两个有限长序列的线性相关求两个有限长序列的线性相关：设设x(n)长为长为N1，y(n)长为长为N2，求线性相关，求线性相关:(1)将将x(n)，y(n)补补零零至至长长为为N，NN1+N2-
33、1，且且N=2m，以以使使两两个个有有限限长长序序列列的的线线性性相相关关可可用用其其圆圆周周相相关关代代替替而而不不产产生生混淆。混淆。即即(2)用用FFT计算计算X(k)，Y(k)(k=0，1，N-1)(3)R(k)=X*(k)Y(k);(4)r(n)=RealIFFT(R(k);(n=0，1，N-1)x=13-112331;y=21-1120-13;k=length(x);xk=fft(x,2*k);yk=fft(y,2*k);rm=real(ifft(conj(xk).*yk);rm=rm(k+2:2*k)rm(1:k);m=(-k+1):(k-1);stem(m,rm)xlabel(
34、m);ylabel(幅度);-8-8-6-6-4-4-2-20 02 24 46 68 8-6-6-4-4-2-20 02 24 46 68 810101212mm幅度两个序列的相关函数3)线性卷积的线性卷积的FFT算法算法线线性性卷卷积积是是求求离离散散系系统统响响应应的的主主要要方方法法之之一一，许许多多重重要要应应用都建立在这一理论基础上，如卷积滤波等。用都建立在这一理论基础上，如卷积滤波等。以前曾讨论了用圆周卷积计算线性卷积的方法归纳如下以前曾讨论了用圆周卷积计算线性卷积的方法归纳如下:将长为将长为N2的序列的序列x(n)延长到延长到L，补，补L-N2个零，个零，将长为将长为N1的序列
35、的序列h(n)延长到延长到L，补，补L-N1个零，个零，如如果果LN1+N2-1，则则圆圆周周卷卷积积与与线线性性卷卷积积相相等等，此此时时，可用可用FFT计算线性卷积，步骤如下计算线性卷积，步骤如下:a.计算计算X(k)=FFTx(n)b.求求H(k)=FFTh(n)c.求求Y(k)=H(k)X(k)k=0L-1d.求求y(n)=IFFTY(k)n=0L-1可见，只要进行二次可见，只要进行二次FFT，一次，一次IFFT就可完成线性就可完成线性卷积计算。卷积计算。计算表明，计算表明，L32时，上述计算线性卷积的方法比直时，上述计算线性卷积的方法比直接计算线卷积有明显的优越性，因此，也称上述圆周
36、卷接计算线卷积有明显的优越性，因此，也称上述圆周卷积方法为快速卷积法。积方法为快速卷积法。上述结论适用于x(n)、h(n)两序列长度比较接近或相等的情况,如果x(n)、h(n)长度相差较多,例如,h(n)为某滤波器的单位脉冲响应,长度有限,用来处理一个很长的输入信号x(n)，或者处理一个连续不断的信号，按上述方法,有三个问题：（1）h(n)要补许多零再进行计算,计算量有很大的浪费，或者根本不能实现。（2）系统的存储量要求极高。（3）带来了很大的系统延迟。为了克服上述三个问题，保持快速卷积法的优越性为了克服上述三个问题，保持快速卷积法的优越性,可可将将x(n)分为许多段分为许多段,每段的长度与每
37、段的长度与h(n)接近接近,处理方法有两处理方法有两种：种： 重叠相加法重叠相加法 重叠保存法重叠保存法(1)重叠相加法重叠相加法由分段卷积的各段相加构成总的卷积输出由分段卷积的各段相加构成总的卷积输出h(n)假定假定xi(n)表示表示x(n)序列的第序列的第i段段：则输入序列可表为：则输入序列可表为：于是输出可分解为：于是输出可分解为：其中其中上两式表明，只要将x(n)的每一段分别与h(n)卷积，然后再将这些卷积结果相加起来就可得到输出序列。这样，每每一一段段的的卷卷积积都都可可用上面讨论的快速卷积来计算：用上面讨论的快速卷积来计算：1)先对先对h(n)及及xi(n)补零，补到具有补零，补到
38、具有N点长度，点长度，N=N1+N2-1，一般选一般选N=2M，通常取，通常取N=256，512或或1024。2)用基用基2FFT计算计算yi(n)=xi(n)*h(n)。3)重叠部分相加构成最后的输出序列。重叠部分相加构成最后的输出序列。由由于于yi(n)的的长长度度为为N，而而xi(n)的的长长度度为为N2，因因此此相相邻邻两两段段yi(n)序列必然有序列必然有N-N2=N1-1点发生重叠。点发生重叠。计算步骤：计算步骤：a.准备好滤波器参数准备好滤波器参数H(k)=DFTh(n)，N点点;b.用用N点点FFT计算计算Xi(k)=DFTxi(n);c.Yi(k)=Xi(k)H(k);d.用
39、用N点点IFFT求求yi(n)=IDFTYi(k);e.将重叠部分相加将重叠部分相加(2)重叠保存重叠保存这这种种方方法法和和第第一一种种方方法法稍稍有有不不同同，即即上上面面分分段段序序列列中中补补零零的的部部分分不不是是补补零零，而而是是保保留留原原来来的的输输入入序序列列值值，且且保保留留在在各各段段的的前前端端，这这时时，如如果果利利用用DFT实实现现h(n)和和xi(n)的的圆圆周周卷卷积积，则则每每段段卷卷积积结结果果的的前前N1-1个个点点不不等等于于线线性性卷卷积积值应舍去。实现步骤：值应舍去。实现步骤：1）定义定义xi(n)为为第第一一段段x(n)由由于于没没有有前前一一段段
40、保保留留信信号号，在在最最前前面面填填补补N1-1点个零点。点个零点。2）用用FFT计计算算每每段段与与h(n)的的圆圆周周卷卷积积，以以yi(n)表示，计算过程如图。表示，计算过程如图。3）对计算得到的对计算得到的yi(n)，去掉其前，去掉其前N1-1点，再把相邻各段输点，再把相邻各段输出出yi(n)顺次连接起来构成最终的输出序列顺次连接起来构成最终的输出序列y(n)。每段xi(n)（长为N）与h(n)(长为N1)的圆周卷积情况：圆周卷积圆周卷积2图用保留信号代替补零后的局部混淆现象h(-n)n=0n=N1-1h(n)xi(n)N1=4N=14由于h(n)的长度为N1，当0nN1-2时，h(
41、n-m)N将在xi(m)的尾部出现有非零值，如图n=1的情况就是如此，所以0nN1-2这部分yi(n)值中将混入xi(m)尾部与h(n-m)N的卷积值，从而使yi(n)不同于线性卷积结果，但当n=N1-1N-1时，则有h(n-m)N=h(n-m)，因此从n=N1-1点开始圆周圈卷积值完全与线性卷积值一样，yi(n)才是正确的卷积值，而每一段卷积运算结果的前N1-1点的值需去掉。为了不造成输出信号遗漏，对为了不造成输出信号遗漏，对x(n)分段时，需使相邻分段时，需使相邻两段有两段有N1-1个点的重叠，即每一输入段均由个点的重叠，即每一输入段均由N-N1+1个新点个新点和前一段保留下来的和前一段保
42、留下来的N1-1个点所组成。个点所组成。重叠保留法与重叠相加法的计算量差不多，但省去了重叠保留法与重叠相加法的计算量差不多，但省去了重叠相加法最后的相加运算。一般来说，用重叠相加法最后的相加运算。一般来说，用FFT作信号滤波，作信号滤波，只用于只用于FIR滤波器阶数滤波器阶数N1大于大于32(N1为为h(n)的长的长)的情况下，的情况下，且取且取N2=(510)N1，这样可接近于最高效的运算。，这样可接近于最高效的运算。4)用用FFT计算二维离散的付里叶变换计算二维离散的付里叶变换二维信号也是信号处理的研究对象。二维信二维信号也是信号处理的研究对象。二维信号有图象信号、时空信号、时频信号等。二
43、维离号有图象信号、时空信号、时频信号等。二维离散付里叶变换可用于处理二维离散信号。散付里叶变换可用于处理二维离散信号。二维离散付里叶变换的定义为：二维离散付里叶变换的定义为：k=0,1,N-1,l=0,1，M-1式中二维离散付里叶变换可通过两次一维离散付里叶变换来实现:1)作一维N点DFT(对每列m做一次，共M次)k=0,1,N-1，m=0,1,M-12)作M点的DFT(对每行k做一次，共N次)k=0,1,N-1，l=0,1,M-1这两次离散付里叶变换都可以用快速算法求得，若M和N都是2的幂，则可使用基二FFT算法，所需要乘法次数为而直接计算二维离散付里叶变换所需的乘法次数为(M+N)MN，当
44、M和N比较大时用用FFT运算，可节约很多运算量。5)DFT应用中的一些问题应用中的一些问题利用DFT进行连续信号频谱分析的过程：这是一个近似过程，各环节都有可能引入误差。(1)混叠混叠对连续信号x(t)进行数字处理前，要进行采样采样序列的频谱是连续信号频谱的周期延拓，周期为fs，如采样率过低，不满足采样定理，fs2fh，则导致频谱混迭，使一个周期内的谱对原信号谱产生失真，无法恢复原信号，进一步的数字处理失去依据。解决：采样前进行抗混叠滤波解决：采样前进行抗混叠滤波;对截短信号，提高采样频率。对截短信号，提高采样频率。连续指数信号在不同采样率下的幅度谱连续指数信号在不同采样率下的幅度谱(a)连续
45、指数信号的幅度谱连续指数信号的幅度谱(b)不同采样率下的不同采样率下的幅度幅度谱谱(2)泄漏处理实际信号序列x(n)时，一般总要将它截断为一有限长序列，长为N点，相当于乘以一个矩形窗w(n)=RN(n)。矩形窗函数，其频谱是一个抽样函数，有主瓣，也有许多副瓣，窗口越大，主瓣越窄，当窗口趋于无穷大时，就是一个冲击函数。我们知道，时域的乘积对应频域的卷积，所以，加窗后的频谱实际是原信号频谱与矩形窗函数频谱(抽样函数)的卷积，卷积的结果使频谱延伸到了主瓣以外，且一直延伸到无穷。当窗口无穷大时，与冲击函数的卷积才是其本身，这时无畸变，否则就有畸变。例如，信号为，是一单线谱，但当加窗后，线谱与抽样函数进
46、行卷积，原来在0处的一根谱线变成了以0为中心的，形状为抽样函数的谱线序列，原来在一个周期(s)内只有一个频率上有非零值，而现在一个周期内几乎所有频率上都有非零值，即的频率成份从0处“泄漏”到其它频率处去了。考虑各采样频率周期间频谱“泄漏”后的互相串漏，卷积后还有频谱混迭现象产生。解决：选择合适的窗函数，并截取反映信号特征的主要部分。解决：选择合适的窗函数，并截取反映信号特征的主要部分。IIR系统截短信号的频谱(3)栅栏效应N点DFT是在频率区间0，2上对信号频谱进行N点等间隔采样，得到的是若干个离散的频谱点X(k)，且它们限制在基频的整数倍上，这就好像在栅栏的一边通过缝隙看另一边的景象一样，只
47、能在离散点处看到真实的景象，其余部分频谱成分被遮挡，所以称之为栅栏效应。减小栅栏效应方法：尾部补零，使谱线变密，增加频域采样点数，原来漏掉的某些频谱分量就可能被检测出来。（4）DFT的分辨率DFT的频率分辨率取决于信号的有效长度。补零与频率分辨力补零与频率分辨力16点的DFT只能分辨频差为1/16的两个频率分量，不能分辨频差为1/64的两个频率分量，由于分辨率不够，第2个频率分量观察不到。h2=fft(x1,64);%信号长信号长16点，补零到点，补零到64点，同时改变了信号的周期性点，同时改变了信号的周期性N1=64;stem(fs/N1*(0:N1-1),abs(h2)figure(2),
48、N1=64;stem(fs/N1*(0:N1-1),abs(h2)补零并未提高分辨力补零并未提高分辨力信号长信号长64点点例例2-1对连续的单一频率周期信号按采样频率采样，截取长度N分别选N=20和N=16，观察其DFT结果的幅度谱。解：解：此时离散序列 。用MATLAB计算并作图，函数fft用于计算离散傅里叶变换DFT，程序如下：（5）周期信号的谱分析对周期信号的非整周期截断将产生频谱泄漏。下面举例说明。n1=0:1:19;xa1=sin(2*pi*n1/k);subplot(2,2,1)plot(n1,xa1)xlabel(t/T);ylabel(x(n);xk1=fft(xa1);xk1
49、=abs(xk1);subplot(2,2,2)stem(n1,xk1)xlabel(k);ylabel(X(k);n2=0:1:15;xa2=sin(2*pi*n2/k);subplot(2,2,3)plot(n2,xa2)xlabel(t/T);ylabel(x(n);xk2=fft(xa2);xk2=abs(xk2);subplot(2,2,4)stem(n2,xk2)xlabel(k);ylabel(X(k);(a)(b)(c)(d)图2.6不同截取长度的正弦信号及其DFT结果N=16N=20计算结果示于图2.1，(a)和(b)分别是N=20时的截取信号和DFT结果，由于截取了两个半周期，频谱出现泄漏；(c)和(d)分别是N=16时的截取信号和DFT结果，由于截取了两个整周期，得到单一谱线的频谱。上述频谱的误差主要是由于时域中对信号的非非整整周周期期截截断断产产生生的的频频谱谱泄泄漏。漏。小小结结DFT定义、物理意义及特性，定义、物理意义及特性，DFT、及及Z变换之间的关系。变换之间的关系。FFT基本思想，基二基本思想，基二FFT基本算法。基本算法。利用利用DFT进行频谱分析，进行频谱分析，FFT在分段卷在分段卷积、线性相关计算中的应用。积、线性相关计算中的应用。实验实验新建*.m文件保存,幅幅频特性特性
