数字信号处理－第二章.ppt

1、1,离散傅里叶变换(DFT) 利用DFT做连续信号的频谱分析 快速傅里叶变换（FFT） 关于FFT应用中的几个问题,内容提要,第二章 离散傅里叶变换及其快速算法,2,2.1 离散傅里叶变换DFT,FS Fourier Series,FT Fourier Transform,DTFT Discrete Time Fourier Transform,DFT Discrete Fourier Transform,3,Fourier变换的几种可能形式,时间函数 频率函数,连续时间、连续频率傅里叶变换(FT),连续时间、离散频率傅里叶级数(FS),离散时间、连续频率离散时间信号的傅里叶 变换(DTFT)

2、,离散时间、离散频率离散傅里叶变换(DFT),4,连续时间的周期信号、离散频率傅里叶级数,时域连续函数造成频域是非周期的谱，而频域的离散对应时域是周期函数。,5,连续时间的非周期信号、连续频率傅里叶变换,时域连续函数造成频域是非周期的谱， 而时域的非周期造成频域是连续的谱密度函数。,6,离散时间的非周期信号、连续频率离散时间信号的傅里叶变换,时域的离散化造成频域的周期延拓，而时域的非周期对应于频域的连续,7,离散时间、离散频率离散傅里叶变换,一个域的离散造成另一个域的周期延拓，因此离散傅里叶变换的时域和频域都是离散的和周期的,8,四种傅里叶变换形式的归纳,FT,FS,DTFT,DFS Disc

3、rete Fourier Series,9,FT,FS,DTFT,DFS,10,2.1.1 离散傅里叶级数(DFS),11,离散周期信号、离散周期频谱的序列周期都为N。 对于周期序列实际计算只需要计算一个周期的值（0 N-1），其余值可以通过周期扩展得到。所以可以定义一个有限序列（长度为周期）的傅氏变换便于计算。,DFS与IDFS,12,系数的性质,13,离散傅里叶级数(DFS)的性质,线性 序列的移位 共轭对称性,14,离散傅里叶级数(DFS)的性质,周期卷积,15,周 期 卷 积,周期卷积演示,16,离散周期信号、离散周期频谱的序列周期都为N。 对于周期序列实际计算只需要计算一个周期的值（

4、0 N-1），其余值可以通过周期扩展得到。 离散周期序列实际上只在有限个序列值有意义，因此，其离散傅里叶级数的表示式适用于有限长序列,17,2.1.2 离散傅里叶变换(DFT),定义,隐含周期性,18,DFT的矩阵方程表示,19,离散傅里叶变换(DFT)的性质,线性 循环移位 循环卷积 共轭对称性 选频性 DFT与z变换 DFT形式下的Parseval定理,20,离散傅里叶变换(DFT)的性质,循环移位 概念 周期延拓序列 记作： 主值序列,21,离散傅里叶变换(DFT)的性质,循环移位,22,循环移位,有限长序列,周期延拓,周期序列移位,取主值空间,23,圆周移位,移位前,左移两位后,周期序

5、列的圆周表示： 当序列x(n)为周期序列时，可以将序列元素按反时针方向顺序排列在N等分的圆周上。序列时移m，是将序列在圆周上顺时针旋转m个位置。,24,离散傅里叶变换(DFT)的性质,循环卷积(Circular Convolution),25,离散傅里叶变换(DFT)的性质,循环卷积(Circular Convolution),26,1）由有限长序列 x(n)、y(n) 构造周期序列,循环卷积过程:,2）计算周期卷积,3）卷积 结果取主值,27,28,循环卷积与线性卷积的关系,DFT只能计算循环卷积，但实际使用中经常要求的是两个序列的线性卷积，所以有必要讨论一下循环卷积与线性卷积的关系。,29

6、,循环卷积线性卷积的条件,若LN1N21，则L点循环卷积等于线性卷积而不产生混叠。,30,比较线性卷积与循环卷积,例: 设有两个序列，x（n）为N=4矩形序列，y（n）为M=6矩形序列，观察其线性卷积和圆周卷积。,a,b,c,d,e,f,g,h,当L=N+M-1=9时，循环卷积等于线性卷积，不失真,31,离散傅里叶变换(DFT)的性质,共轭对称性,32,离散傅里叶变换(DFT)的性质,共轭对称性有限长序列的共轭对称定义,33,离散傅里叶变换(DFT)的性质,共轭对称性,任一个复数序列可以表示为实部序列和虚部序列（分别为实数序列）,任一个复数序列可以表示为共轭偶对称和共轭奇对称和的形式,34,离

7、散傅里叶变换(DFT)的性质,共轭对称性,35,序列及其DFT的实、虚、偶、奇关系,36,共轭对称性,任一个复数序列可以表示为四个实数序列,离散傅里叶变换(DFT)的性质,37,XIm(k)为实数序列,序列及其DFT的实、虚、偶、奇关系,38,离散傅里叶变换(DFT)的性质,选频性,39,离散傅里叶变换(DFT)的性质,DFT与z变换,40,离散傅里叶变换(DFT)的性质,DFT与z变换,41,离散傅里叶变换(DFT)的性质,DFT与z变换,42,离散傅里叶变换(DFT)的性质,DFT形式下的Parseval定理,43,采样定律告诉我们，一个频带有限的信号，可以对它进行时域采样而不丢失任何信息

8、； DFT变换进一步告诉我们，对于时间有限的信号（有限长序列），也可以对其进行频域采样，而不丢失任何信息，这正反应了傅立叶变换中时域、频域的对称关系。它有十分重要的意义，由于时域上的采样，使我们能够采用数字技术来处理这些时域上的信号（序列），而DFT的理论不仅在时域，而且在频域也离散化，因此使得在频域采用数字技术处理成为可能。 FFT就是频域数字处理中最有成效的一例。,44,2.1 小结,傅里叶变换的几种形式 离散傅里叶级数DFS 离散傅里叶变换DFT定义 离散傅里叶变换DFT性质,45,2.2 利用DFT作连续信号的频谱分析,利用DFT对连续信号进行频谱分析的方法 混叠 泄漏 栅栏效应 DF

9、T的分辨率 周期信号的谱分析 参数选择的原则,46,离散傅氏变换虽然适合于在计算机上计算实现，但它是针对有限长离散信号（或离散周期信号）定义的。对于一般的连续非周期信号x(t)，如何使用DFT计算频谱？解决了这一问题DFT才具有实际意义。,47,利用DFT计算连续信号的频谱,信号的频谱分析：计算信号的傅里叶变换,2.2 利用DFT做连续信号的频谱分析,48,49,要求：,1 采样 混叠,50,解决办法：提高采样频率；抗混叠滤波器,51,2 截短 泄漏,52,53,时间无限的信号，其频带宽度有限,在矩形函数频谱的作用下，出现了频谱泄漏。 时间有限的信号其频带宽度无限,54,解决频谱泄漏的方法,增

10、加截短长度 选择合适的窗函数 合理选取信号的截取部分,55,加窗,窗函数的旁瓣降低可以减小泄漏，但会导致主瓣变宽,56,3 时域周期化 栅栏效应,57,假设信号为100Hz，频率分辨率为1Hz a中100Hz没有栅栏效应 b中100.5Hz存在 C中100.2Hz存在,栅栏效应,58,4 取主值区域进行计算,59,栅栏效应,DFT只计算离散点（基频F0的整数倍处）的频谱，而不是连续函数,改善方法： 增加频域抽样点数N（时域补零），使谱线更密,60,DFT的频率分辨率,误解：加零可以增加频率分辨率 通常规定DFT的频率分辨率为 ，N是指信号x(n)的有效长度 不同长度的x(n)其DTFT的结果是

11、不同的；而相同长度的x(n)尽管补零的长度不同其DTFT的结果应是相同的，他们的DFT只是反映了对相同的DTFT采用了不同的采样密度。 提高DFT频率分辨率的方法：增加采样长度N,61,加零的效果,解释X(k)的含义及加零的效果,62,参数选择的一般原则：,（1）若已知信号的最高频率 ，为防止混叠，选定采样频率 ； （2）根据频率分辨率 ，确定所需DFT的长度 (3) 和N确定以后，即可确定相应模拟信号的时间长度 这里T是采样周期。,63,信号最高频率与频率分辨率之间的矛盾,要提高频率分辨率,即 当N给定,采样频率fs ，要不产生混叠,同时提高信号最高频率和频率分辨率，需要增加采样点数N,64

12、,周期信号的谱分析,对于连续的单一频率周期信号 ， 为信号的频率。 可以得到单一谱线的DFT结果，但这是和作DFT时数据的截取长度选得是否恰当有关，截取长度N选得合理， 可完全等于 的采样。,65,6,8,10,k,X(k),(a),(b),(c),(d),不同截取长度的正弦信号及其DFT结果,66,结 论,对于一般连续信号通过采样、截断、周期化和主值计算的处理，可以使用DFT计算其频谱。处理过程中，可能产生混叠误差、泄漏误差和频谱采样栅栏效应。但只要采取适当的方法，可以在满足一定的精度要求之下，用DFT计算结果作为原连续信号频谱。,混叠误差处理：抗混叠滤波；提高采样频率。,泄漏误差处理：截断

13、窗函数的修正。,频谱采样栅栏效应：使频谱的频率分辨率满足分析要求（频率分辨率 F=1/NT），截断数据长度N的选定，即连续信号分析时间为tp=NT。,67,2.2 小结,利用DFT对连续信号进行频谱分析的方法 出现误差及解决办法 参数选择的原则,68,69,DFT复习,DFT与IDFT定义 DFT不区分周期信号与非周期信号 DFT是周期函数，周期为N DFT以 对DTFT采样 DFT标号k对应模拟频率(单位为Hz)为 基于其有限的频率分辨率，DFT会模糊频谱的尖峰,例：DFT的滤波器解释 例：心电图的频谱,70,2.3 快速傅里叶变换FFT,直接计算DFT的运算量 按时间抽取的FFT 按频率抽

14、取的FFT N为组合数的FFT和基四FFT（自学） Chrip-z变换（线性调频z变换）（自学）,71,直接计算DFT的计算量,72,直接计算DFT的计算量,FFT不是一种新的傅里叶变换，只是DFT的一种快速算法,73,FFT基本思想,时间抽选法 DIT: Decimation-In-Time 频率抽选法 DIF: Decimation-In-Frequency,74,DFT系数的性质,75,2.3.1 按时间抽取的FFT,76,按时间抽取的FFT算法原理,77,按时间抽取的FFT算法原理,78,按时间抽取的FFT算法原理,X1（k），X2（k）为N/2点的DFT，周期为N/2,79,按时间抽

15、取的FFT算法原理,80,按时间抽取的FFT蝶形运算,(前一半),(后一半),1 1,1,1,-1,81,按时间抽取的FFT计算量分析,82,按时间抽取的FFT8点FFT例子,83,按时间抽取的FFT8点FFT例子,84,按时间抽取的FFT8点FFT例子,85,按时间抽取的FFT运算量,由上述分析可知,N=8需三级蝶形运算 N=23=8,由此可知,N=2L 共需L级蝶形运算, 而且每级都由N/2个蝶形运算 组成,每个蝶 形运算有一次复乘,两次复加。 因此,N点的FFT的运算量为 复乘: mF =（N/2）L=（N/2） log2N 复加: aF =N L=N log2 N,86,按时间抽取的F

16、FT算法特点,原位计算,输入数据、中间运算结果和最后输出均用同一存储器。,87,按时间抽取的FFT算法特点,蝶形类型随迭代次数成倍增加,第L级共有2L-1个系数,88,按时间抽取的FFT算法特点,蝶形运算规律,第L级共有2L-1个系数,89,按时间抽取的FFT算法特点,序数重排,90,按时间抽取的FFT算法特点,序数重排,n =0,0,n =1,0,n =0,1,n =1,1,n =0,1,n =1,1,0,1,0,1,0,1,0,1,(n2),x(000) 0,x(100) 4,x(010) 2,x(110) 6,x(001) 1,x(101) 5,x(011) 3,x(111) 7,（偶）

17、,（奇）,91,按时间抽取的FFT算法特点,倒位序的实现,0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7,自然顺序n 二进制n n n 倒位序二进制n n n 倒位顺序n,2 1 0 0 1 2,92,时域采样造成频域延拓,93,2.3.2 按频率抽取的FFT,94,按频率抽取的FFT-算法原理,95,按频率抽取的FFT-蝶形运算,先蝶形运算再进行DFT,96,按频率抽取的FFT-8点FF

18、T例子,97,按频率抽取的FFT-8点FFT例子,x(0) X(0) x (1) X(4) x(2) X(2) x(3) X(6) x(4) X(1) x(5) X(5) x(6) X(3) x(7) X(7),-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,98,按频率抽取的FFT-运算特点,蝶形运算,原位运算,99,按频率抽取的FFT-运算特点,蝶形类型随迭代次数成倍减少,第L级共有2M-L个系数,100,按频率抽取的FFT-运算特点,蝶形运算规律,第L级共有2L-1个系数,101,按频率抽取的FFT-运算特点,序数重排,102,DIT法与DIF法的异同,原位运算

19、运算量相同 序数重排 蝶形运算,103,DIT与DIF算法的流图对比,输入变输出 输出变输入 流图反转,104,频域采样造成时域延拓,105,2.3.3 N为组合数的FFT和基四FFT,自学 基本思想是将DFT的运算尽量分小，减少运算量,106,2.3.4 Chrip-z变换线性调频z变换,自学 不需要计算整个单位圆上z变换的取样，如对于窄带信号，只需要对信号所在的一段频带进行分析，这时,希望频谱的采样集中在这一频带内，以获得较高的分辨率，而频带以外的部分可不考虑。 对其它围线上的z变换取样感兴趣，例如语音信号处理中，需要知道z变换的极点所在频率，如极点位置离单位圆较远，则其单位圆上的频谱就很

20、平滑，如果采样不是沿单位圆而是沿一条接近这些极点的弧线进行，则在极点所在频率上的将出现明显的尖峰，由此可较准确地测定极点频率。 要求能有效地计算当N是素数时序列的DFT。,107,2.3 小结,按时间抽取的FFT 按频率抽取的FFT,108,2.4 关于FFT应用的几个问题,用FFT计算IDFT 实数序列的FFT 线性卷积的FFT算法 用FFT计算相关函数 用FFT计算二维离散傅里叶变换,109,2.4.1 用FFT计算IDFT,110,2.4.2 实数序列的FFT,X(k)、 Y(k)复数序列,111,循环卷积与线性卷积的关系,DFT只能计算循环卷积，但实际使用中经常要求的是两个序列的线性卷积，所以有必要讨论一下循环卷积与线性卷积的关系。,112,循环卷积线性卷积的条件,若LN1N21，则L点循环卷积等于线性卷积而不产生混叠。,113,2.4.3 线性卷积的FFT算法,补L-N1 个零点,补L-N2 个零点,IFFT,x,x(n