n为复合数的fft算法课件

1、第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法14.5 N为复合数的为复合数的FFT算法算法 第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法24.6 线性调频线性调频Z变换（变换（Chirp-Z变换）算法变换）算法 vFFT算法用于计算有限长序列的算法用于计算有限长序列的z变换变换X(z)在在z平面单位圆上平面单位圆上N个等间隔抽样点个等间隔抽样点zk上的采样值上的采样值v实际应用中在很多情况下并不一定需要计算全部频谱值实际应用中在很多情况下并不一定需要计算全部频谱值,而仅而仅需对某一频带内的信号频谱作较密集的分析需对某一频带内的信号频谱作较密集的分析v

2、另外，采样也不一定局限于单位圆上，而需要计算出某一螺另外，采样也不一定局限于单位圆上，而需要计算出某一螺旋线上的等角度间隔的采样值旋线上的等角度间隔的采样值 例如语音信号分析时，往往在靠近语音信号序列例如语音信号分析时，往往在靠近语音信号序列z变换的变换的极点的螺旋线上进行采样，可以使语音信号的共振峰变得极点的螺旋线上进行采样，可以使语音信号的共振峰变得更尖锐，便于精确确定共振峰频率更尖锐，便于精确确定共振峰频率第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法34.6 线性调频线性调频Z变换（变换（Chirp-Z变换）算法变换）算法 v线性调频线性调频z变换就是利用变换就是利

3、用FFT快速计算螺旋线采样的算法快速计算螺旋线采样的算法ooooABX(ej)RezRezjImzjImzAB(a)(b)X(ej) 沿单位圆采样沿单位圆采样 沿沿AB弧采样弧采样 第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法44.6.1 算法基本原理算法基本原理为适应为适应z可以沿可以沿Z平面更一般的路径取值，沿平面更一般的路径取值，沿Z平面上的一段螺线平面上的一段螺线作等分角的采样，采样点作等分角的采样，采样点zk为为 10)()(NnnznxzX设有限长序列设有限长序列x(n)的的Z变换为变换为 式中式中: A和和W都是任意复数都是任意复数, 设设0000jjAA

4、eWW ezk=AW-k k=0, 1, , M-1 M为采样点的总数为采样点的总数0000jjkkkzA eWe综合上式得到综合上式得到 00()00jkkAWe第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法5)(00000000kjkjkkjkeWAeWeAz zk参数的物理意义参数的物理意义 0jImzRezo0A01.0zM1A0W01z0(M I)0螺线采样螺线采样 A0: 起始采样点起始采样点z0的矢量半径的矢量半径0: 起始采样点起始采样点z0的相角的相角0: 两相邻采样点之间的角度差两相邻采样点之间的角度差 W0: 表示螺线的伸展率表示螺线的伸展率序列的序列

5、的DFT是是Chirp-Z变换的特例变换的特例第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法61100()( )( )NNnnnkkknnX zx n zx n A W 0kM-1 将将zk=AW-k代入代入x(n)的的Z变换变换表达式中变换变换表达式中,得到得到 Chirp-Z变换公式变换公式 Chirp-Z变换的变换的FFT 算法算法直接计算直接计算Chirp-Z变换公式的计算量很大变换公式的计算量很大, 但可以将其转换为但可以将其转换为卷卷积形式积形式, 从而利用从而利用FFT算法算法, 提高运算速度提高运算速度 第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数

6、的fft算法7将公式中的将公式中的nk做一变换做一变换2221() 2nknkkn Chirp-Z变换公式的卷积形式变换公式的卷积形式1100()( )( )NNnnnkkknnX zx n zx n A W 0kM-1 代入公式代入公式, 整理后得到整理后得到222()12220() ( )knk nNnknX zWx n A WW(卷积形式卷积形式 )与卷积公式比较与卷积公式比较 10( )( )( ) ()Nng kh kg n h kn2222( )( )( )nnng nx n A Wh nW当当X(zk)可表示成卷积形式可表示成卷积形式第第10讲讲 快速傅里叶变换快速傅里叶变换 n

7、为复合数的fft算法8)()()(22khkgWzXkkk=0, 1, , M-1 卷积形式的卷积形式的Chirp-Z公式可采用公式可采用FFT算法，从而提高运算速度算法，从而提高运算速度x(n)2/ 2 )(nWnh2/ 2nnWAg(n)h(n)1 / h(n)X(zn) Chirp-Z变换的计算框图如下变换的计算框图如下第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法94.6.2 Chirp-Z变换的特点变换的特点输入序列和输出序列长度不需要相等输入序列和输出序列长度不需要相等, 且二者均可为素数且二者均可为素数 分析频率点分析频率点zk的起始点的起始点z0及相邻两点的

8、夹角及相邻两点的夹角0是任意的是任意的(即即频率分辨率是任意的频率分辨率是任意的)， 因此可从任意频率上开始，因此可从任意频率上开始， 对输对输入数据进行窄带高分辨率的谱分析入数据进行窄带高分辨率的谱分析 谱分析路径可以是螺旋形的谱分析路径可以是螺旋形的 Chirp-Z变换在一定条件下就是序列的变换在一定条件下就是序列的DFT 与标准与标准DFT(FFT)算法相比较，算法相比较， Chirp-Z变换有以下特点变换有以下特点:第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法104.7 利用利用FFT分析时域连续信号频谱分析时域连续信号频谱 4.7.1 基本步骤基本步骤 时域连续

9、信号离散傅里叶分析的处理步骤如下图示时域连续信号离散傅里叶分析的处理步骤如下图示 LPFsc(t)Ha(j)xc(t)A / Dx(n)w(n)v(n)DFTV(k)频谱分析是指计算信号各个频率的幅值频谱分析是指计算信号各个频率的幅值, 相位和功率相位和功率 处理过程分析处理过程分析第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法11LPF : 避免在模拟信号转换成序列时避免在模拟信号转换成序列时, 可能出现的频谱混叠现象可能出现的频谱混叠现象TmjTjXTeXmcj21)(LPFsc(t)Ha(j)xc(t)A / Dx(n)w(n)v(n)DFTV(k)A/D: 时域离散

10、化时域离散化,得到采样序列得到采样序列x(n)，其频谱用，其频谱用X(ej)表示表示第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法12 DFT(FFT)运算运算: 加窗后的加窗后的DFT是是 102)()(NnnkNjenvkV0kN-1 LPFsc(t)Ha(j)xc(t)A / Dx(n)w(n)v(n)DFTV(k)w(n): 窗函数窗函数.为进行为进行FFT，须对，须对x(n)加窗处理，即加窗处理，即v(n)=x(n)w(n)第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法13对连续信号进行谱分析时，主要关心两个问题：即谱分析范围对连续信号进行谱分

11、析时，主要关心两个问题：即谱分析范围与频率分辨率与频率分辨率 谱分析范围与频率分辨率谱分析范围与频率分辨率 谱分析范围谱分析范围(所能分析的最高频率所能分析的最高频率)受采样频率的限制受采样频率的限制 频率分辨率用频率采样间隔频率分辨率用频率采样间隔F描述，表示谱分析中能够分辨的描述，表示谱分析中能够分辨的两个频谱分量最小间隔。两个频谱分量最小间隔。F较小时，称频率分辨率较高较小时，称频率分辨率较高第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法14有限长序列有限长序列v(n)=x(n)w(n)的的DFT相当于相当于v(n)FT的等间隔采样的等间隔采样 kNjeVkV2)()

12、(V(k)是是sc(t)的离散频率函数，的离散频率函数， V(k)的第的第k点对应的模拟频率为点对应的模拟频率为: NTkTk22kkkfNT 谱分析范围与频率分辨率谱分析范围与频率分辨率显然，数字域频率间隔显然，数字域频率间隔=2/N 对应的模拟域对应的模拟域谱线间距谱线间距应为应为 NfNTFs1( fs 为采样频率为采样频率) 谱线间距谱线间距: 即频谱分辨率，指可分辨两频率的最小间距即频谱分辨率，指可分辨两频率的最小间距第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法15NfNTFs1( fs 为采样频率为采样频率) T为采样时间间隔为采样时间间隔(s) fs为采样频

13、率为采样频率(Hz) F为谱线间距为谱线间距,频谱分辨率频谱分辨率(Hz) tp为截取连续时间信号的样本为截取连续时间信号的样本长度长度, 又称记录长度又称记录长度(s) DFT对连续信号谱分析时，参数间的关系及选择原则对连续信号谱分析时，参数间的关系及选择原则例例 时间序列时间序列v(n)=(1.1)nR16(n)与与16点的点的DFT 的如下图所示的如下图所示第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法16 参数间的关系参数间的关系11psptNTfFNNTt 参数的选择参数的选择(T、tp和和N)实际应用中实际应用中, 根据信号最高根据信号最高频率频率fh和频谱分辨

14、率和频谱分辨率F的要的要求来确定三个参数求来确定三个参数 DFT对连续信号谱分析时，参数间的关系及选择原则对连续信号谱分析时，参数间的关系及选择原则第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法17 采样周期采样周期T的选择：的选择：1 2hTf为保证采样信号不失真应满足，为保证采样信号不失真应满足，fs2fh，即周期，即周期T11psptNTfFNNTt说明：信号的谱分析范围说明：信号的谱分析范围 fh与频率分辨率与频率分辨率F存在矛盾关系存在矛盾关系解释解释：如果保持采样点数：如果保持采样点数N不变，而提高谱的分辨率不变，而提高谱的分辨率(F减小减小)， 必须降低采样速

15、率必须降低采样速率fs ，从而引起谱分析范围，从而引起谱分析范围 fh 减少减少解决方法解决方法：如维持：如维持fs不变不变, 为提高分辨率，可以考虑增加采样为提高分辨率，可以考虑增加采样点数点数N与观察时间与观察时间Tp第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法18 N的选择（由频谱分辨率的选择（由频谱分辨率F和和T确定）确定）1sfNFFT11psptNTfFNNTt 最小记录长度最小记录长度Tp的选择（由的选择（由N, T确定）确定）1pTNTF第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法19例例 一频谱分析器，其采样点数必须是一频谱分析器，

16、其采样点数必须是2的整数幂，已知的整数幂，已知 频率分辨率频率分辨率10 Hz; 信号最高频率信号最高频率4kHz。试求。试求(1) 最小记录长度最小记录长度tp；(2) 最大采样间隔最大采样间隔T（即最小采样频率（即最小采样频率)；(3) 在一个记录中的最少点数在一个记录中的最少点数N 1 211hspTffNFFTTNTF解题思路解题思路已知已知 F=10 Hz, fh=4 kHz1pTNTF(1)1 2hTf(2)1sfNFFT(3)取 2mN 第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法20 由信号的时域波形图估计最高频率由信号的时域波形图估计最高频率 最高频率最

17、高频率1/(2*相邻峰谷间的最小距离相邻峰谷间的最小距离) 信号最高频率信号最高频率fh的估计的估计tt3t4ot1t2x(t)例：如下图示例：如下图示)(214Hztfh第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法214.7.2 利用利用FFT对连续信号进行傅里叶分析时可能造成的误差对连续信号进行傅里叶分析时可能造成的误差1. 频谱混叠失真频谱混叠失真 当时域采样频率不满足当时域采样频率不满足fs2fh 时，会产生频谱混叠失真时，会产生频谱混叠失真 对于对于FFT，频率函数也要采样成离散序列，因此为兼顾，频率函数也要采样成离散序列，因此为兼顾fh与与F，必要时需增加记录

18、长度的点数，必要时需增加记录长度的点数N一般取一般取 fs=(2.53.0) fh 第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法224.7.2 利用利用FFT对连续信号进行傅里叶分析时可能造成的误差对连续信号进行傅里叶分析时可能造成的误差2. 栅栏效应栅栏效应利用利用FFT计算频谱，只能得到有限点的频谱采样值，而采样点计算频谱，只能得到有限点的频谱采样值，而采样点间的频谱函数是不知道的，这就像通过一个间的频谱函数是不知道的，这就像通过一个“栅栏栅栏”观看信号观看信号频谱频谱,只能在离散点上看到信号频谱，称之为只能在离散点上看到信号频谱，称之为“栅栏效应栅栏效应”。由。由于

19、栅栏效应，有可能漏掉于栅栏效应，有可能漏掉(挡住挡住)大的频谱分量大的频谱分量第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法23 减小栅栏效应的方法：减小栅栏效应的方法： 增加频域采样点数增加频域采样点数N，通过在时域数据末端添加零点，使通过在时域数据末端添加零点，使一个周期内的点数增加，但并不改变原有的记录数据一个周期内的点数增加，但并不改变原有的记录数据 说明：说明：补零不能提高频率分辨率补零不能提高频率分辨率2. 栅栏效应栅栏效应第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法24cos(n/4) 频谱频谱 3. 由截断效应引起的频谱泄漏与谱间干扰由

20、截断效应引起的频谱泄漏与谱间干扰实际中的序列实际中的序列x(n)有可能是无限长的，为进行有可能是无限长的，为进行DFT运算，运算，x(n)需需要进行加窗处理变成有限长序列，截断后序列的频谱与原序列要进行加窗处理变成有限长序列，截断后序列的频谱与原序列频谱必然有差别频谱必然有差别, 主要表现为泄漏与谱间干扰主要表现为泄漏与谱间干扰矩形窗函数的幅度谱矩形窗函数的幅度谱 加矩形窗后的频谱加矩形窗后的频谱 第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法25 泄漏泄漏：截断后的序列不再是单一谱线，而是向附近展宽。泄：截断后的序列不再是单一谱线，而是向附近展宽。泄漏使频谱变模糊，使谱分

21、辨率降低漏使频谱变模糊，使谱分辨率降低谱间干扰谱间干扰：主谱线两边形成很多旁瓣，将引起不同频率分量：主谱线两边形成很多旁瓣，将引起不同频率分量间的干扰。特别是强信号谱的旁瓣可能湮没弱信号的主谱线间的干扰。特别是强信号谱的旁瓣可能湮没弱信号的主谱线加矩形窗后的频谱 cos(n/4) 频谱 第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法26加矩形窗后的频谱加矩形窗后的频谱 减小两种影响的措施：减小两种影响的措施：cos(n/4) 频谱频谱 增加窗的时域宽度增加窗的时域宽度N 可使频域主瓣变窄可使频域主瓣变窄 采用其它缓变的窗代替矩阵窗，可使旁瓣能量更小，从采用其它缓变的窗代替矩

22、阵窗，可使旁瓣能量更小，从而减少谱间干扰而减少谱间干扰 N一定时，旁瓣越小的窗函数，其主瓣就越宽。因此只能以一定时，旁瓣越小的窗函数，其主瓣就越宽。因此只能以降低谱分辨率为代价，换取谱间干扰的减小降低谱分辨率为代价，换取谱间干扰的减小第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法274.7.3 频谱分析的应用)()()(1kjXkXkXR实信号实信号x(n)的频谱是共轭偶对称的，故只要求出的频谱是共轭偶对称的，故只要求出k在在0, 1, N/2上的上的X(k)即可。即可。 将将X(k)写成极坐标形式写成极坐标形式 )(arg| )(|)(kXjekXkX式中，式中，|X(k

23、)|称为幅频谱，称为幅频谱，argX(k)称为相频谱。称为相频谱。 频谱图频谱图 一个长度为一个长度为N的时域离散序列的时域离散序列x(n)，其，其DFT可表示为可表示为 由上式绘成的图形称为频谱图。从图中可以知道信号存在哪由上式绘成的图形称为频谱图。从图中可以知道信号存在哪些频率分量些频率分量第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法28例例 用频谱分析下列时域信号的组成用频谱分析下列时域信号的组成( fs=32 Hz )对序列作对序列作32点点DFT，|X(k)|如右图示。频率分辨率如右图示。频率分辨率 F=fs/N=1Hz 210120102030(a)(b)00

24、51015816nkx(n)|X(k)|210120102030(a)(b)0051015816nkx(n)|X(k)|第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法294.8 FFT的其它应用的其它应用 4.8.1 线性卷积的线性卷积的FFT算法算法快速卷积快速卷积 1. FFT的快速卷积法的快速卷积法（利用循环卷积的利用循环卷积的FFT计算线性卷积计算线性卷积）补L N个零点L点DFT补L M个零点L点DFTL点IDFTy(n)h(n)x(n) FFT计算计算y(n)的步骤的步骤 求求H(k)=DFTh(n) 求求X(k)=DFTx(n) 计算计算Y(k)=X(k)H(

25、k); 求求y(n)=IDFTY(k) 第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法30设设h(n)的点数为的点数为M，长序列，长序列x(n)可被分成为若干长度为可被分成为若干长度为L点的段点的段0)()(nxnxiiLn(i+1)L-1 其他n i=0, 1, 输入序列表示输入序列表示 0)()(iinxnx 2. 重叠相加法重叠相加法x(n)和和h(n)的线性卷积等于的线性卷积等于00( )( )( )( )( )( )iiiiy nx nh nx nh ny n第第10讲讲 快速傅里叶变换快速傅里叶变换 n为复合数的fft算法31计算计算N点点FFT， H(k)=DFTh