数字信号处理（西电版）第三章快速傅里叶变换复习.ppt

1、数字信号处理Digital Signal Processing(DSP,信息学院电子系,3.1 引 言,DFT实现了时域序列的频域离散化, 因此在数字信号处理中用途很广 但是DFT的计算量太大，不适于实时处理，所以没有得到真正的运用 快速傅里叶变换(FFT)就是为了缩短DFT运算时间而产生的, 运算时间一般可缩短一二个数量级 FFT并不是一种新的变换,而是DFT的一种快速算法,3.2 直接计算DFT的问题及改进的途径,3.2.1 直接计算DFT的运算量问题,k=0, 1, , N-1,设x(n)为N点有限长序列，其DFT为,通常x(n)和WNnk都是复数，因此一个X(k)需要N次复数乘法和N-

2、1次复数加法 完成整个DFT运算则需要N2次复数乘法及N(N-1)次复数加法 由于DFT的运算次数与N2成正比, N较大时, 运算量非常可观,例对一幅NN点的二维图像进行DFT变换，当N=1024时, 直接计算DFT所需复乘次数为1012次，用每秒可做10万次复数乘法的计算机计算需要近3000小时,3.2.2 改善途径,把长序列的DFT分解成短序列的DFT运算,利用系数Wnk的特性,3.3 按时间抽取（DIT）的基 -2 FFT算法,设序列x(n)长度为N，且满足N=2M，M为正整数。按n的奇偶把x(n)分解为两个N/2点的子序列,FFT分为两大类: 按时间抽取法(Decimation in

3、Time) 和按频率抽取法(Decimation in Frequency) ,本节先介绍第一种算法,3.3.1 算法原理,一个N点DFT的分解,将DFT x (n)分解为DFTx1(r) 与DFTx2(r)的线性组合,代入,重写DFT,上式为X(k)的前一半值,而后一半值可表示为,化简,得到,分解后运算工作量节省了近一半,N点DFT的一次时域抽取分解过程见下图（N=8,两个N/2点DFT的分解,X1(k)的分解,由于N=2M仍是偶数，可以把每个N/2点子序列再进行分解,X1(k)分解图示,X2(k)的分解图示,N点DFT的第二次时域抽取分解图（N=8,N点DFT的第二次时域抽取分解图（N=8

4、,上式不需要乘法, 类似可求出X4(k)，X5(k)，X6(k,四个N/4点DFT的计算,X3(k)的分解,完整的N=8 DIT-FFT运算流图,由于输入序列在时域上进行奇偶分解，故称为“按时间抽取法,N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成,3.3.2 DIT-FFT算法与直接计算DFT运算量的比较,直接计算DFT与FFT算法的计算量之比为,N越大，FFT的优点越为明显,例3-2 P109 3000h-2m,3.3.3 按时间抽取的FFT算法的特点,1. 原位运算（同址运算,定义：利用同一存贮单元存贮蝶形运算输入、输出数据的方法,DIT-FFT的运算规律,同一级中，每个蝶

5、形的两个输入数据只对计算本蝶形有用，可采用原位运算，则全部运算过程只需要N个存储单元,2. 倒位序规律 （ N=2M,输入序列的排序为N的二进制倒位序，输出序列则为自然顺序,N8时的输入输出值,3. 蝶形运算两节点的“距离,对N=2M点FFT，当输入为倒位序， 输出为正常顺序时，其第m级运算，每个蝶形的两节点“距离”为2m-1,3.3.4 按时间抽取的FFT算法的其他形式流图,对于任何流图，只要保持各节点所连的支路及传输系数不变，则不论节点位置怎么排列所得流图总是等效的,将左图x(4)与 x(1) , x(6)与x(3)对调,时间抽取、 输入自然顺序、 输出倒位序的FFT流图特点,数据存放的方

6、式不同,取用系数的顺序不同,3.4 按频率抽取（DIF）的基 -2 FFT算法,3.4.1 算法原理,将长度为N=2M的序列x(n)前后对半分开, 其N点DFT可表示为,k=0, 1, , N-1,统一求和区间,按k的奇偶可将X(k)分为两部分,k=0, 1, , N-1,k取偶数时,x(n)前后两部分和的N/2点DFT,k取奇数时,x(n)前后两部分差再乘以WNn后的N/2点DFT,k取偶数时,上式表明, X(k)按k的奇偶分为两组,其偶(奇)数组是x1(n)(x2(n)的N/2点DFT. x1(n), x2(n)与x(n)间的关系也可用下面蝶形运算流图表示,式中,得到,按频率抽取的N点DF

7、T第一次分解(N=8,式中,与DIT-FFT一样，由于N/2仍为偶数，继续将每个N/2点DFT输出再分解为偶数组与奇数组,直到第M次（N=2M,按频率抽取完整的N点DFT运算流图 (N=8,3.4.2 DIF-FFT与DIT-FFT的联系,DIF的基本蝶形与DIT的基本蝶形互为转置,DIT蝶形运算流图,DIF蝶形运算流图,两种FFT运算方法等价,DIT-FFT,DIF-FFT,3.4.3 IDFT的高效算法,FFT算法同样可以用于 IDFT，称为快速傅里叶反变换(IFFT,比较DFT和IDFT的运算公式,左图为在DIF-FFT流图上改动后，得到的DIT-IFFT运算流图,3.4.3 IDFT的

8、高效算法,上述IFFT算法需要改动FFT的程序和参数才能实现。也可以利用DFT的性质，直接用FFT程序来完成IDFT的运算,已知,两边取共轭,两边再取共轭,3.5 N为复合数的FFT算法,3.6 线性调频Z变换（Chirp-Z变换）算法,FFT算法用于计算有限长序列的z变换X(z)在z平面单位圆上N个等间隔抽样点zk上的采样值 实际应用中在很多情况下并不一定需要计算全部频谱值,而仅需对某一频带内的信号频谱作较密集的分析 另外，采样也不一定局限于单位圆上，而需要计算出某一螺旋线上的等角度间隔的采样值 例如语音信号分析时，往往在靠近语音信号序列z变换的极点的螺旋线上进行采样，可以使语音信号的共振峰

9、变得更尖锐，便于精确确定共振峰频率,3.6 线性调频Z变换（Chirp-Z变换）算法,线性调频z变换就是利用FFT快速计算螺旋线采样的算法,3.6.1 算法基本原理,为适应z可以沿Z平面更一般的路径取值，沿Z平面上的一段螺线作等分角的采样，采样点zk为,设有限长序列x(n)的Z变换为,式中: A和W都是任意复数, 设,综合上式得到,zk参数的物理意义,螺线采样,A0: 起始采样点z0的矢量半径 0: 起始采样点z0的相角 0: 两相邻采样点之间的角度差 W0: 表示螺线的伸展率,序列的DFT是Chirp-Z变换的特例,0kM-1,将zk=AW-k代入x(n)的Z变换变换表达式中,得到,Chir

10、p-Z变换公式,Chirp-Z变换的FFT 算法,直接计算Chirp-Z变换公式的计算量很大, 但可以将其转换为卷积形式, 从而利用FFT算法, 提高运算速度,将公式中的nk做一变换,Chirp-Z变换公式的卷积形式,0kM-1,代入公式, 整理后得到,卷积形式,与卷积公式比较,k=0, 1, , M-1,卷积形式的Chirp-Z公式可采用FFT算法，从而提高运算速度,Chirp-Z变换的计算框图如下,3.6.2 Chirp-Z变换的特点,输入序列和输出序列长度不需要相等, 且二者均可为素数 分析频率点zk的起始点z0及相邻两点的夹角0是任意的(即频率分辨率是任意的)， 因此可从任意频率上开始

11、， 对输入数据进行窄带高分辨率的谱分析 谱分析路径可以是螺旋形的 Chirp-Z变换在一定条件下就是序列的DFT,与标准DFT(FFT)算法相比较， Chirp-Z变换有以下特点,3.7 利用FFT分析时域连续信号频谱,3.7.1 基本步骤,时域连续信号离散傅里叶分析的处理步骤如下图示,频谱分析是指计算信号各个频率的幅值, 相位和功率,处理过程分析,LPF : 避免在模拟信号转换成序列时, 可能出现的频谱混叠现象,A/D: 时域离散化,得到采样序列x(n)，其频谱用X(ej)表示,w(n): 窗函数.为进行FFT，须对x(n)加窗处理，即v(n)=x(n)w(n,对连续信号进行谱分析时，主要关

12、心两个问题：即谱分析范围与频率分辨率,谱分析范围与频率分辨率,谱分析范围(所能分析的最高频率)受采样频率的限制 频率分辨率用频率采样间隔F描述，表示谱分析中能够分辨的两个频谱分量最小间隔。F较小时，称频率分辨率较高,有限长序列v(n)=x(n)w(n)的DFT相当于v(n)FT的等间隔采样,V(k)是sc(t)的离散频率函数， V(k)的第k点对应的模拟频率为,谱分析范围与频率分辨率,显然，数字域频率间隔=2/N 对应的模拟域谱线间距应为,fs 为采样频率,谱线间距: 即频谱分辨率，指可分辨两频率的最小间距,fs 为采样频率,T为采样时间间隔(s) fs为采样频率(Hz) F为谱线间距,频谱分

13、辨率(Hz) tp为截取连续时间信号的样本长度, 又称记录长度(s,DFT对连续信号谱分析时，参数间的关系及选择原则,例 时间序列v(n)=(1.1)nR16(n)与16点的DFT 的如下图所示,参数间的关系,参数的选择(T、tp和N,实际应用中, 根据信号最高频率fh和频谱分辨率F的要求来确定三个参数,DFT对连续信号谱分析时，参数间的关系及选择原则,采样周期T的选择,为保证采样信号不失真应满足，fs2fh，即周期T,说明：信号的谱分析范围 fh与频率分辨率F存在矛盾关系,解释：如果保持采样点数N不变，而提高谱的分辨率(F减小)， 必须降低采样速率fs ，从而引起谱分析范围 fh 减少 解决

14、方法：如维持fs不变, 为提高分辨率，可以考虑增加采样点数N与观察时间Tp,N的选择（由频谱分辨率F和T确定,最小记录长度tp的选择（由N, T确定,例 一频谱分析器，其采样点数必须是2的整数幂，已知 频率分辨率10 Hz; 信号最高频率4kHz。试求 (1) 最小记录长度tp；(2) 最大采样间隔T（即最小采样频率)；(3) 在一个记录中的最少点数N,解题思路,已知 F=10 Hz, fh=4 kHz,1,2,由信号的时域波形图估计最高频率 最高频率1/(2*相邻峰谷间的最小距离,信号最高频率fh的估计,例：如下图示,3.7.2 利用FFT对连续信号进行傅里叶分析时可能造成的误差,1. 频谱

15、混叠失真,当时域采样频率不满足fs2fh 时，会产生频谱混叠失真,对于FFT，频率函数也要采样成离散序列，因此为兼顾fh与F，必要时需增加记录长度的点数N,一般取 fs=(2.53.0) fh,3.7.2 利用FFT对连续信号进行傅里叶分析时可能造成的误差,2. 栅栏效应,利用FFT计算频谱，只能得到有限点的频谱采样值，而采样点间的频谱函数是不知道的，这就像通过一个“栅栏”观看信号频谱,只能在离散点上看到信号频谱，称之为“栅栏效应”。由于栅栏效应，有可能漏掉(挡住)大的频谱分量,减小栅栏效应的方法： 增加频域采样点数N，通过在时域数据末端添加零点，使一个周期内的点数增加，但并不改变原有的记录数

16、据 说明：补零不能提高频率分辨率,2. 栅栏效应,cos(n/4) 频谱,3. 由截断效应引起的频谱泄漏与谱间干扰,实际中的序列x(n)有可能是无限长的，为进行DFT运算，x(n)需要进行加窗处理变成有限长序列，截断后序列的频谱与原序列频谱必然有差别, 主要表现为泄漏与谱间干扰,矩形窗函数的幅度谱,加矩形窗后的频谱,泄漏：截断后的序列不再是单一谱线，而是向附近展宽。泄漏使频谱变模糊，使谱分辨率降低 谱间干扰：主谱线两边形成很多旁瓣，将引起不同频率分量间的干扰。特别是强信号谱的旁瓣可能湮没弱信号的主谱线,加矩形窗后的频谱,减小两种影响的措施,cos(n/4) 频谱,增加窗的时域宽度N 可使频域主

17、瓣变窄 采用其它缓变的窗代替矩阵窗，可使旁瓣能量更小，从而减少谱间干扰,N一定时，旁瓣越小的窗函数，其主瓣就越宽。因此只能以降低谱分辨率为代价，换取谱间干扰的减小,3.7.3 频谱分析的应用,实信号x(n)的频谱是共轭偶对称的，故只要求出k在0, 1, N/2上的X(k)即可。 将X(k)写成极坐标形式,式中，|X(k)|称为幅频谱，argX(k)称为相频谱,频谱图,一个长度为N的时域离散序列x(n)，其DFT可表示为,由上式绘成的图形称为频谱图。从图中可以知道信号存在哪些频率分量,实际也常用功率谱表示，主要用于分析带有噪声干扰的信号,功率谱,频率轴几种定标方式的对应关系,例 用频谱分析下列时

18、域信号的组成( fs=32 Hz,对序列作32点DFT，|X(k)|如右图示。频率分辨率 F=fs/N=1Hz,3.8 FFT的其它应用,3.8.1 线性卷积的FFT算法快速卷积,1. FFT的快速卷积法（利用圆周卷积的FFT计算线性卷积,FFT计算y(n)的步骤,求H(k)=DFTh(n) 求X(k)=DFTx(n) 计算Y(k)=X(k)H(k); 求y(n)=IDFTY(k,运算量的比较（直接线性卷积和FFT法计算线性卷积,x(n)与h(n)点数差不多时, 有如下结果(KM为两种卷积运算量比值,当M=L且M超过32以后，M越长， FFT法的优势越明显,x(n)与h(n)点数相差很大时,采

19、用FFT运算时，要求长序列全部输入，短序列补充很多零点，这样既不经济，运算时间也长。解决的方法是将长序列分段计算，即重叠相加法与重叠保留法,设h(n)的点数为M，长序列x(n)可被分成为若干长度为L点的段,输入序列表示,2. 重叠相加法,x(n)和h(n)的线性卷积等于,计算N点FFT， H(k)=DFTh(n) （ N=2mL+M-1 ） 计算N点FFT，Xi(k)=DFTxi(n) （ N=2mL+M-1 ） 相乘，Yi(k)=Xi(k)H(k) 计算N点IFFT，yi(n)=IDFTYi(k,计算步骤,将各段yi(n)（包括重叠部分）相加,xi(n)与yi(n)序列长度不同, 导致相邻两段输出有若干点重叠，应该将重叠部分相加后再和不重叠的部分共同组成输出y(n,重叠相加法卷积图示,将x(n)分段，每段L=N