第三章 离散傅里叶变换快速

第三章离散傅里叶变换快速第1页，课件共32页，创作于2023年2月问题的提出例：4点序列{2，3，3，2}DFT的计算复杂度共需：复数加法N(N-1)次复数乘法N

2次∴如果N↑→运算次数↑↑；那么如何提高DFT的运算效率?第2页，课件共32页，创作于2023年2月快速傅里叶变换(FastFourierTransform，简称FFT),FFT是计算DFT的各种快速算法的统称。DFT在信号处理中得到广泛应用，一个非常重要的原因就是其存在高效算法。◆直接计算N点序列的DFT，对每一频率分量X[m]，需计算N次复数乘法，N—1次复数加法。因此，计算N个不同频率分量X[m]，共需N2次复数乘法，(N－1)N次复数加法。◆IDFT的直接计算与DFT的直接计算具有相同的运算量。显然，随着N的增大，DFT和IDFT的运算量将急剧增加。◆FFT的出现以及数字计算系统的问世极大地推动了DFT应用，并可以满足许多工程实际中实时处理需求。FFT算法的复乘运算量只是直接计算DFT的约0．27％左右。解决问题的思路与方法第3页，课件共32页，创作于2023年2月3.1基2时间抽取FFT算法3．3．1算法原理DIT的基本思想:◆基2时间抽取(DecimationinTime，简称DIT)算法原理是利用旋转因子WmkN的特性，通过在时域将序列逐次分解为一组子序列，然后利用子序列的DFT来实现整个序列的DFT，从而提高DFT的运算效率。◆旋转因子WmkN＝ｅ﹣ｊ（２π／Ｎ）ｍｋ旋转因子具有周期性——WmkN以N为周期WmkN＝Wm（k+N）N＝Wk（m+N）N旋转因子具有对称性：旋转因子具有可约性：第4页，课件共32页，创作于2023年2月

计算方法：设序列ｘ［ｋ］的长度为N＝2M，M为正整数：◆将序列ｘ［ｋ］补零以满足该条件；◆将ｘ［ｋ］分解为两个长度N／2点的短序列：ｘ1［ｋ］＝ｘ［2ｋ］（ｋ＝0，1，…N/2－1）——偶数点ｘ2［ｋ］＝ｘ［2ｋ＋1］（ｋ＝0，1，…N/2－1）——奇数点◆将长序列分解为短序列，通过短序列的DFT来实现长序列的DFT，以减少运算量。◆利用旋转因子的周期性、对称性、可约性，将两个短序列的DFT合成为对应的长序列DFT。◆基2频率抽取(Decimationinfrequency)FFT算法：第5页，课件共32页，创作于2023年2月◆基2时间抽取FFT算法流图N=2x[k]={x[0],x[1]}

由于这个图形呈蝶形，故称为蝶形计算结构，这是基2时间抽取FFT运算的基本单元。蝶形图左边的两个节点叫输入节点，右边的两个节点叫输出节点，支路中的箭头表示信号流的方向，支路旁的数字表示该支路的传输函数，未标数字的支路其传输函数为1。由图可见，完成一个蝶形运算需要一次复数乘法和两次复数加法。第6页，课件共32页，创作于2023年2月4点基2时间抽取FFT算法流图x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2点DFT2点DFT-1-1-1-1X

[0]X

[1]X

[2]X

[3]第7页，课件共32页，创作于2023年2月4点基2时间抽取FFT算法流图第8页，课件共32页，创作于2023年2月8点基2时间抽取FFT算法流图4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]-1-1-1-1第9页，课件共32页，创作于2023年2月4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]-1-1-1-18点基2时间抽取FFT算法流图第10页，课件共32页，创作于2023年2月基2时间抽取FFT算法第一级第二级第三级第11页，课件共32页，创作于2023年2月3．1．2算法的计算复杂度复数乘法次数：复乘次数NN2◆

N=8时基2时间抽取FFT的信号流图由3级构成。◆第一级包含N/2=4个蝶形，一般情况下，N=2M点，则基2时间抽取FFT的信号流图应有M级，每一级有M／2个蝶形，所以总共有M×N/2个蝶形；每个蝶形需要一次复数乘法和二次复数加法，因此总共需要：复数加法次数：N第12页，课件共32页，创作于2023年2月FFT算法流图旋转因子规律第二级的蝶形系数为，蝶形节点的距离为2。第一级的蝶形系数均为，蝶形节点的距离为1。第三级的蝶形系数为，蝶形节点的距离为4。第M级的蝶形系数为，蝶形节点的距离为N/2。第13页，课件共32页，创作于2023年2月倒序k0k1k2x[k2k1k0]x[000]x[100]x[010]01011]12x[kk0]x[k2k101x[110]x[001]x[101]x[011]x[111]01010101第14页，课件共32页，创作于2023年2月

3.2基2频率抽取FFT算法第15页，课件共32页，创作于2023年2月3NW-12NW-11NW-10NW-1x[0]x[4]x[1]x[5]x[2]x[6]x[3]x[7]4点DFTX[0]X[6]X[2]X[4]4点DFTX[1]X[3]X[5]X[7]第16页，课件共32页，创作于2023年2月X[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2点DFT-1-12NW0NW-1-12点DFT2点DFT2点DFT第17页，课件共32页，创作于2023年2月0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2NW0NWX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW0NW0NW0NW-1-1-1-1-1-1-1-1第18页，课件共32页，创作于2023年2月FFT算法应用利用N点复序列的FFT计算两个N点实序列FFT利用N点复序列的FFT，计算2N点序列的FFT利用FFT计算IFFT第19页，课件共32页，创作于2023年2月利用N点复序列的FFT算法计算两个N点实序列FFTx1[k],x2[k]是实序列，将其构成复序列y[k]=x1[k]+j

x2[k]DFT{x1[k]+j

x2[k]}=YR[m]+jYI[m]第20页，课件共32页，创作于2023年2月利用N点复序列的FFT，计算2N点序列的FFTy[k]是一个长度为2N的序列问题：如何利用N点FFT，计算4N点序列的FFT？第21页，课件共32页，创作于2023年2月利用FFT实现IFFT步骤：A)将X[m]取共轭C)对B)中结果取共轭并除以N第22页，课件共32页，创作于2023年2月3.3

线性调频z变换算法

线性调频z变换(ChirpZTransform，简称CZT)CZT的基本思想:◆在z平面上采用螺旋曲线抽样，以解决离散傅立叶变换在单位圆等间隔抽样与输出、输入序列长度必须相等的局限。◆CZT的特点：可以求解序列z变换在z平面单位圆上某一段频谱的样点，也可以求解在z平面上非单位圆上的样点；旋转因子WmkN＝ｅ﹣ｊ（２π／Ｎ）ｍｋ输入序列的点数N和输出序列的点数M可以不等。第23页，课件共32页，创作于2023年2月

CZT定义有限长序列的z变换定义为:◆其中：A0、W0为任意的正实数；θ0为起始抽样点的相角，可以为正也可以为负；φ0表示两相邻样点之间的间隔。◆

给定A0、W0、θ0

、φ0

，当m＝0，1，…，M—1时，可得到z平面上的一系列离散点z0，z1，…，zM－1：，取这些点的z变换，即得有限长序列x[k]的M点CZT：第24页，课件共32页，创作于2023年2月

CZT变换的轨迹CZT变换的轨迹通常为一条螺旋曲线(如图3—18所示)：◆

(1)当A0＞1时，螺旋曲线在z平面的单位圆外，A0＜1时，在单位圆内；(2)当W0＞1时，A0W0-1＜A0，螺旋曲线内旋，反之，则外旋；(3)当A0＝W0＝1时，CZT变换的轨迹为单位圆上的一段圆弧；(4)当A0＝1，W＝e﹣j2π/N，M＝N时，CZT变为DFT。CZT变换的轨迹曲线的特点：第25页，课件共32页，创作于2023年2月序列CZT的算法CZT算法框图(如图3—19所示)：◆计算序列CZT的关键是实现序列g[k]与h[k]的线性卷积，可以通过FFT来实现。

◆中间序列变量的取值范围：由于序列x[k]的长度是N，因而序列g[k]的长度也是N点，序列h[k]有用值的范围是[﹣（N－1），M－1]；经线性卷积所得序列y[k]的长度应为2N+M－2。◆由于只需要卷积结果的一部分，所以用循环卷积g[k]㈩h[k]实现时允许有混叠，这时循环卷积点数只要≥N+M－1即可。序列CZT的计算公式：第26页，课件共32页，创作于2023年2月保证y[k]在[0，M—1)区间上不混叠的措施第27页，课件共32页，创作于2023年2月CZT计算量统计：

(1)计算g[k]需N次乘法；(2)计算G[m]＝DFT｛g[k]｝需1/2L㏒2L乘法。(3)一般H[m]＝DFT｛h[k]｝可以事先计算；(4)计算Y[m]＝G[m]·H[m]需L＝N+M－1次乘法；(5)计算g[k]＝IDFTY[m]需1/2(N+M－1)㏒2L(N+M－1)次乘法(6)计算

需M次乘法(7)总共需乘法的次数Count＝（N+M-1）[㏒2L(N+M－1)+2]第28页，课件共32页，创作于2023年2月CZT与DFT比较CZT与DFT比较，具有以下特点：◆输入序列长度与输出序列长度不必相等；◆M和N可以不是组合数，甚至可为素数；◆zk相邻点的间隔φ0是任意的，因此频率分辨率可以任意设定；◆变换轨迹不必是圆，这对分析在单位圆内的极点有利；◆起始点z0不必在z＝1处，可以在任意频率开始计算，因而适用于窄带高分辨率的计算；◆若A＝1、M＝N、W＝ej2π/N，则C