快速付里叶变换.pptx

第四节基-2按频率抽取的FFT算法Decimation-in-Frequency(DIF)(Sander-Tukey)一、算法原理设输入序列长度为N=2M(M为正整数，将该序列的频域的输出序列X(k)(也是M点序列，按其频域顺序的奇偶分解为越来越短的子序列，称为基2按频率抽取的FFT算法。也称为Sander-Tukey算法。二、算法步骤1.分组分组DFT变换：已证明频域上X(k)按k的奇偶分为两组，在时域上x(n)按n的顺序分前后两部分，现将输入x(n)按n的顺序分前后两部分:前半子序列x(n),0nN/2-1;后半子序列x(n+N/2),0nN/2-1;例：N=8时，前半序列为：x(0),x(1),x(2),x(3);后半序列为：x(4),x(5),x(6),x(7);则由定义输出（求DFT）2.代入DFT中3.变量置换变量置换-13.变量置换变量置换-23.变量置换变量置换-33.变量置换变量置换-44.结论1一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：可见：如此分解，直至分到2点的DFT为止。4.结论2三、蝶形流图表示蝶形单元：时域时域中，前后半部表示式用蝶形结表示。x(n)x(n+N/2)与时间抽取法的推演过程一样，由于N=2L,N/2仍为偶数，所以可以将N/2点DFT的输出X(k)再分为偶数组和奇数组，这样就将一个N/2点的DFT分成两个N/4点DFT的输入，也是将N/2点的DFT的输入上、下对半分后通过蝶形运算而形成，直至最后为2点DFT。例子：求 N=23=8点DIF（1）先按）先按N=8-N/2=4，做做4点的点的DIF：先将N=8DFT分解成2个4点DFT：可知：时域上：x(0),x(1),x(2),x(3)为偶子序列 x(4),x(5),x(6),x(7)为奇子序列 频域上：X(0),X(2),X(4),X(6)由x1(n)给出 X(1),X(3),X(5),X(7),由x2(n)给出将N=8点分解成2个4点的DIF的信号流图 4点DFTx(0)x(1)x(2)x(3)4点DFTx(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)X1(k)前半部分序列后半部分序列x1(n)x2(n)X2(k)(2)N/2(4点)-N/4(2点)FFT(a)先将先将4点分解成点分解成2点的点的DIF：因为4点DIF还是比较麻烦，所以再继续分解。（b)一个2点的DIF蝶形流图2点DFT2点DFTx1(0)x1(1)x1(2)x1(3)x3(0)x3(1)x4(0)x4(1)X(0)X(4)X(2)X(6)(c)另一个2点的DIF蝶形流图2点DFT2点DFTx2(0)x2(1)x2(2)x2(3)x5(0)x5(1)x6(0)x6(1)X(1)X(5)X(3)X(7)(3)将N/4（2点）DFT再分解成2个1点的DFT(a)求2个一点的DFT 最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x3(0)、x3(1)为例。(b)2个1点的DFT蝶形流图 1点DFTx3(0)1点DFTx3(1)X(0)X(4)进一步简化为蝶形流图：X(0)X(4)x3(0)x3(1)(4)一个完整N=8的按频率抽取FFT的运算流图 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)m=0m=1m=2(5)DIF的特点(a)输入自然顺序，输出乱序且满足码位输入自然顺序，输出乱序且满足码位倒置规则。倒置规则。(b)根据时域、频域互换，可知：根据时域、频域互换，可知：输入乱序，输出自然顺序。输入乱序，输出自然顺序。（6）DIF与DIT比较1相同之处：（1）DIF与DIT两种算法均为原位运算。（2）DIF与DIT运算量相同。它们都需要（6）DIF与DIT比较2不同之处：（1）DIF与DIT两种算法结构倒过来。DIF为输入顺序，输出乱序。运算完毕再运行“二进制倒读”程序。DIT为输入乱序，输出顺序。先运行“二进制倒读”程序，再进行求DFT。（2）DIF与DIT根本区别：在于蝶形结不同。DIT的复数相乘出现在减法之前。DIF的复数相乘出现在减法之后。作业试画出N=16点的基-2按频率抽取的FFT流图（DIF）。第五节IFFT运算方法以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT。即快速付里叶反变换。从IDFT的定义出发，可以导出下列二种利用FFT来计算FFT的方法。一、利用FFT计算IFFT的思路1将下列两式进行比较二、利用FFT计算IFFT的思路2利用FFT计算IFFT时在命名上应注意：(1)把FFT的时间抽取法，用于IDFT运算时，由于输入变量由时间序列x(n)改成频率序列X(k),原来按x(n)的奇、偶次序分组的时间抽取法FFT，现在就变成了按X(k)的奇偶次序抽取了。（2）同样，频率抽取的FFT运算用于IDFT运算时，也应改变为时间抽取的IFFT。三、改变FFT流图系数的方法1.思路在IFFT的运算中，常常把1/N分解为(1/2)m，并且在M级运算中每一级运算都分别乘以1/2因子，就可得到IFFT的两种基本蝶形运算结构。（并不常用此方法）2.IFFT的基本蝶形运算ABAB(a)频率抽取IFFT的蝶形运算(b)时间抽取IFFT的蝶形运算四.直接利用FFT流图的方法1.思路前面的两种IFFT算法，排程序很方便，但要改变FFT的程序和参数才能实现。现介绍第三种IFFT算法，则可以完全不必改动FFT程序。2.直接利用FFT流图方法的推导可知：只须将频域成份一个求共轭变换，即（1）将X(k)的虚部乘以-1，即先取X(k)的共轭，得X*(k)。(2)将X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再对运算结果取一次共轭变换，并乘以常数1/N，即可以求出IFFT变换的x(n)的值。此为DFT可用FFT程序3.直接利用FFT流图方法的注意点（1）FFT与IFFT连接应用时，注意输入输出序列的排列顺序，即应注意是自然顺序还是倒序。（2）FFT和IFFT共用同一个程序时，也应注意利用FFT算法输入输出的排列顺序，即应注意自然顺序还是例位序（3）当把频率抽取FFT流图用于IDFT时，应改称时间抽取IFFT流图。（4）当把时间抽取FFT流图用于IDFT时，应改称频率抽取IFFT流图。作业用C语言完成N=128点的DIT，DIF及IDIT，IDIF。第六节线性调频Z变换一、引入以上提出FFT算法，可以很快地求出全部DFT值。即求出有限长序列x(n)的z变换X(z)在单位园上N个等间隔抽样点zk处的抽样值。它要求N为高度复合数。即N可以分解成一些因子的乘积。例N=2L实际上：（1）也许对其它围线上z变换取样发生兴趣。如语音处理中，常常需要知道某一围线z变换的极点所处的复频率。（2）只需要计算单位圆上某一段的频谱。如窄带信号，希望在窄带频率内频率抽样能够非常密集，提高分辨率，带外则不考虑。（3）若N是大素数时，不能加以分解，又如何有效计算这种序列DFT。例N=311，若用基2则须补N=28=512点，要补211个零点。二、问题提出由上面三个问题提出：为了提高DFT的灵活性，须用新的方法。线性调频z变换(CZT)就是适用这种更为一般情况下，由x(n)求X(zk)的快速变换CZT：来自于雷达专业的专用词汇。三、算法原理1.定义Z 变 换 采 用 螺螺 线线 抽抽 样样,可 适 用 于 更 一 般 情 况 下 由 x(n)求X(zk)的 快 速 算 法,这 种 变 换 称 为 线 性 调 频 Z 变 换(简 称 CZT).2.CZT公式推导1 已 知 x(n)，0nN-1,则它的z变换是：为适应z可以沿平面内更一般的路径取值，故：沿z平面上的一段螺线作等分角的抽样，则z的取样点Zk可表示为：其中M：表示欲分析的复频谱的点数。M不一定等于N。A，都为任意复数。2.CZT公式推导22.CZT公式推导33.用CZT求解DFT的流图4.CZT变换各点的值5、图形6、说明1（1）A为起始样点位置6、说明2（2）zk是z平面一段螺线上的等分角上某一采样点。6、说明36、说明46、说明57、CZT的实现步骤17、CZT的实现步骤27、CZT的实现步骤37、CZT的实现步骤47、CZT的实现步骤57、CZT的实现步骤67、CZT的实现步骤78、CZT变换运算流程图9、CZT运算量的估算19、CZT运算量的估算210、CZT运算量与直接运算量比较当M、N足够小时，直接算法运算量少。但M、N值比较大时（大于50），CZT算法比直接算法的运算量少得多。例M=50，N=50，N*M=2500次而CZT1600次。11、CZT算法的特点与标准FFT算法相比，CZT算法有以下特点：（1）输入序列长N及输出序列长M不需要相等。（2）N及M不必是高度合成数，二者均可为素数。（3）Zk的角间隔 是任意的，其频率分辨率也是任意的。（4）周线不必是z平面上的圆，在语音分析中螺旋周线具有某些优点。（5）起始点z0可任意选定，因此可以从任意频率上开始对输入数据进行窄带高分辨率的分析。（6）若A=1,M=N,可用CZT来计算DFT，即使N为素数时，也可以。总之，CZT算法具有很大的灵活性，在某种意义上说，它是一个一般化的DFT。12、CZT变换的应用1（1）利用CZT变换计算DFT。12、CZT变换的应用2（2）对信号的频谱进行细化分析。其中对窄带信号频谱或对部分感兴趣的频谱进行细化分析。这样CZT只对感兴趣的频率区段进行采样。计算量小很多，有利于实时处理。或在保证实时处理的情况下，可大提高频率分辨率。12、CZT变换的应用3（3）求解z变换X(z)的零、极点。用于语音信号处理过程中。具体方法：利用不同半径同心圆，进行等间隔的采样。作业第七节FFT的应用凡是利用付里叶变换来进行分析、综合、变换的地方，都可以利用FFT算法来减少其计算量。FFT主要应用在（1）快速卷积（2）快速相关（3）频谱分析一、快速卷积设x(n)的长度为N点，h(n)的长度为M点，则：y(n)的长度为N+M-1点。所以直接计算y(n)线性卷积运算量为NM。1.利用圆周卷积代替线卷积用圆周卷积（FFT）代替线卷积的必要条件：x(n)、h(n)补零加长至L=N+M-1.然后计算圆卷积。求出y(n)代表线卷积。2、用FFT计算y(n)的步骤(1)求H(k)=DFTh(n)(L点）(2)求X(k)=DFTx(n)(L点）(3)计算Y(k)=X(k)H(k)(L点）(4)求y(n)=IDFTY(k)(L点）2、用FFT计算y(n)与直接计算y(n)的运算量比较3、分段卷积的方法（1）重叠相加法（2）重叠保留法设x(n)的长度为长序列N，h(n)为短序列列M。（1）重叠相加法1（1）x(n)为分段，每段长为p点，p选择与M数量组相同。用xi(n)表示x(n)的第i段.（1）重叠相加法2（1）重叠相加法例子（2）重叠保留法1（2）重叠保留法2（2）重叠保留法例子二、快速相关1.方法2.步骤三、频谱分析这里我们仅介绍FFT的仪器设备：快速付里叶分析仪。其功能为：（1）能分析确定性信号的频谱。（2）估计随机信号的功率谱（3）并对信号进行快速卷积滤波（4）计算相关函数1.频谱分析仪的框图数据选择器A/D保护滤波器输入电路输入数据存储器运算器数据选择器控制器变址单元函数发生器输出缓冲器D/A输出2.部件说明（1）保护滤波器：对输入信号进行模拟滤波，滤掉噪声，提取感兴趣的有用信号，以便分析频谱。（2）运算器：完成时间抽取FFT或Chirp-Z变换所要求运算。（3）RAM:存储输入数据。（4）ROM(函数发生器）。以表格形式存放蝶形运算因子W.(5)变址单元：根据输入数据，进行码位倒置排序。