DSPFFT深入浅出详细讲解快速傅里叶变换

DSPFFT深入浅出详细讲解快速傅里叶变换DSPFFT深入浅出详细讲解快速傅里叶变换1第一节

引言第一节

引言2一、快速付里叶变换FFT有限长序列通过离散傅里叶变换(DFT)将其频域离散化成有限长序列.但其计算量太大(与N的平方成正比〕,很难实时地处理问题,因此引出了快速傅里叶变换(FFT).FFT并不是一种新的变换形式,它只是DFT的一种快速算法.并且根据对序列分解与选取方法的不同而产生了FFT的多种算法.FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用.。一、快速付里叶变换FFT有限长序列通过离散傅里叶变换(DF3二、FFT产生故事当时加文(Garwin)在自已的研究中极需要一个计算付里叶变换的快速方法。他注意到图基(J.W.Turkey)正在写有关付里叶变换的文章，因此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文介绍了一种方法，它本质上就是后来的著名的库利(CooleyJ.W)图基算法。在加文的迫切要求下，库利很快设计出一个计算机程序。1965年库利--图基在<计算数学>、MathematicofComputation杂志上发表了著名的“机器计算付里级数的一种算法〞文章，提出一种快速计算DFT的方法和计算机程序--揭开了FFT开展史上的第一页，促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的条件，使DFT的运算大简化了。二、FFT产生故事当时加文(Garwin)在自已4三、本章主要内容1.直接计算DFT算法存在的问题及改进途径。2.多种DFT算法(时间抽取算法DIT算法，频率抽取算法DIF算法，线性调频Z变换即CZT法)三、本章主要内容1.直接计算DFT算法存在的问题及改进途径。5第二节

直接计算DFT算法存在的问题及改进途径第二节

直接计算DFT算法存在的问题及改进途径6一、直接计算DFT计算量

问题提出：设有限长序列x(n),非零值长度为N,计算对x(n)进展一次DFT运算，共需多大的运算工作量?一、直接计算DFT计算量

问题提出：设有限长序列x(n),7其中x(n)为复数，也为复数所以DFT与IDFT二者计算量一样。其中x(n)为复数，82.以DFT为例，计算DFT复数运算量计算一个X(k)(一个频率成分)值，运算量为例k=1那么要进展N次复数乘法+(N-1)次复数加法所以，要完成整个DFT运算，其计算量为：N*N次复数相乘和N*(N-1)次复数加法2.以DFT为例，计算DFT复数运算量计算一个X(k)(一个9复数运算要比加法运算复杂，需要的运算时间长。一个复数乘法包括4个实数乘法和2个实数相法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)

4次实数乘法2次实数加法复数运算要比加法运算复杂，需要的运算时间长。4次实数乘法2次10每运算一个X(k)的值，需要进展4N次实数相乘和2N+2(N-1)=2(2N-1)次实数相加.整个DFT运算量为：4N2次实数相乘和2N(2N-1)次实数相加.由此看出：直接计算DFT时，乘法次数与加法次数都是和N2成比例的。当N很大时，所需工作量非常可观。DSPFFT深入浅出详细讲解快速傅里叶变换11例子例1:当N=1024点时，直接计算DFT需要：N2=220=1048576次，即一百多万次的复乘运算这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有非常苛刻的要求-->迫切需要改进DFT的计算方法，以减少总的运算次数。例2：石油勘探，24道记录，每道波形记录长度5秒，假设每秒抽样500点/秒，每道总抽样点数=500*5=2500点24道总抽样点数=24*2500=6万点DFT运算时间=N2=(60000)2=36*108次例子例1:当N=1024点时，直接计算DFT需要：12作业作业13二、改善DFT运算效率的根本途径利用DFT运算的系数的固有对称性和周期性，改善DFT的运算效率。1.合并法：合并DFT运算中的某些项。3.分解法：将长序列DFT利用对称性和周期性，分解为短序列DFT。二、改善DFT运算效率的根本途径利用DFT运算的系数14利用DFT运算的系数的固有对称性和周期性，改善DFT的运算效率的对称性：的周期性：因为：由此可得出：利用DFT运算的系数的固有对称性和周期性，改15例子例:利用以上特性,得到改进DFT直接算法的方法.例子例:利用以上特性,得到改进DFT直接算法的方法.16(1)合并法：步骤1分解成虚实部合并DFT运算中的有些项对虚实部而言所以带入DFT中：(1)合并法：步骤1分解成虚实部合并DFT运算中的有些项17(1)合并法：步骤2代入DFT中展开：(1)合并法：步骤2代入DFT中展开：18(1)合并法：步骤3合并有些项根据：有：(1)合并法：步骤3合并有些项根据：有：19(1)合并法：步骤4结论由此找出其它各项的类似归并方法：乘法次数可以减少一半。例：(1)合并法：步骤4结论由此找出其它各项的202、将长序列DFT利用对称性和周期性分解为短序列DFT--思路因为DFT的运算量与N2成正比的假设一个大点数N的DFT能分解为假设干小点数DFT的组合，那么显然可以到达减少运算工作量的效果。2、将长序列DFT利用对称性和周期性分解为短序列DFT--思212、将长序列DFT利用对称性和周期性分解为短序列DFT--方法把N点数据分成二半：其运算量为：再分二半：+=+++=这样一直分下去，剩下两点的变换。2、将长序列DFT利用对称性和周期性分解为短序列DFT--方222、将长序列DFT利用对称性和周期性分解为短序列DFT--结论快速付里时变换(FFT)就是在此特性根底上开展起来的，并产生了多种FFT算法，其根本上可分成两大类：按抽取方法分：时间抽取法(DIT);频率抽取法(DIF)按“基数〞分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：线性调频Z变换(CZT法)2、将长序列DFT利用对称性和周期性分解为短序列DFT--结23第三节

基--2按时间抽取的FFT算法Decimation-in-Time(DIT)

(Coolkey-Tukey)第三节

基--2按时间抽取的FFT算法Decimation-24一、算法原理设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。其中基数2----N=2M，M为整数.假设不满足这个条件，可以人为地加上假设干零值〔加零补长〕使其到达N=2M一、算法原理设输入序列长度为N=2M(M为正整数，将该序列按25例子设一序列x(n)的长度为L=9,应加零补长为N=24=16

应补7个零值。0123456789101112131415nx(n)例子设一序列x(n)的长度为L=9,应加零补长为026二、算法步骤

1.分组，变量置换DFT变换：先将x(n)按n的奇偶分为两组，作变量置换:当n=偶数时，令n=2r;当n=奇数时，令n=2r+1;得到：x(2r)=x1(r);x(2r+1)=x2(r);r=0…N/2-1;那么可得其DFT为两局部：前半局部：后半局部：二、算法步骤

1.分组，变量置换DFT变换：先将x(n)按n27生成两个子序列x(0),x(2)…x(2r)偶数点x(1),x(3)…x(2r+1)奇数点代入DFT变换式：生成两个子序列x(0),x(2)…x(2r)偶数点代入DFT28上式得：上式得：29一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：再应用W系数的周期性，求出用X1(k),X2(k)表达的后半部的X(k+N/2)的值。一个N点的DFT被分解为两个N/2点DFT。X1(k),X230看出：后半部的k值所对应的X1(k),X2(k)那么完全重复了前半局部的k值所对应的X1(k),X2(k)的值。看出：后半部的k值所对应的X1(k),X2(k)那么完全重复31频域中的N个点频率成分为：结论：只要求出〔0~N/2-1〕区间内的各个整数k值所对应的X1(k),X2(k)值，即可以求出(0~N-1)整个区间内全部X(k)值，这就是FFT能大量节省计算的关键。频域中的N个点频率成分为：结论：只要求出〔0~N/2-1〕区32由于N=2M，因此N/2仍为偶数，可以按照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算。由于N=2M，因此N/2仍为偶数，可以按照上面方法进一步把每33三、蝶形结即蝶式计算构造也即为蝶式信号流图上面频域中前/后半局部表示式可以用蝶形信号流图表示。X1(k)X2(k)作图要素：(1)左边两路为输入(2)右边两路为输出(3)中间以一个小圆表示加、减运算〔右上路为相加输出、右下路为相减输出)(4)假设在某一支路上信号需要进展相乘运算，那么在该支路上标以箭头，将相乘的系数标在箭头旁。(5)当支路上没有箭头及系数时，那么该支路的传输比为1。三、蝶形结即蝶式计算构造也即为蝶式信号流图X1(k)X2(k34例子：求N=23=8点FFT变换

〔1〕先按N=8-->N/2=4，做4点的DFT：先将N=8DFT分解成2个4点DFT：可知：时域上：x(0),x(2),x(4),x(6)为偶子序列

x(1),x(3),x(5),x(7)为奇子序列频域上：X(0)~X(3)，由X(k)给出X(4)~X(7),由X(k+N/2)给出例子：求N=23=8点FFT变换

〔1〕先按N=8-->35(a)比较N=8点直接DFT与分解2个4点DFT的FFT运算量N=8点的直接DFT的计算量为：N2次(64次〕复数相乘,N(N-1)次(8＊(8-1)=56次)复数相加.共计120次。(a)比较N=8点直接DFT与分解2个4点DFT的FFT运算36〔b)求一个蝶形结需要的运算量要运算一个蝶形结，需要一次乘法，两次加法。〔b)求一个蝶形结需要的运算量要运算一个蝶形结，需要一次乘37〔c〕分解为两个N/2=4点的DFT的运算量分解2个N/2点〔4点〕的DFT：偶数其复数相乘为复数相加为奇数其复数相乘为复数相加为〔c〕分解为两个N/2=4点的DFT的运算量分解2个N/2点38(d)用2个4点来求N=8点的FFT所需的运算量再将N/2点〔4点〕合成N点(8点)DFT时，需要进展N/2个蝶形运算还需N/2次〔4次〕乘法及次(8次〕加法运算。(d)用2个4点来求N=8点的FFT所需的运算量再将N/2点39(e)将N=8点分解成2个4点的DFT的信号流图4点DFTx(0)x(2)x(4)x(6)4点DFTx(1)x(3)x(5)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶数序列奇数序列X(4)~X(7)同学们自已写x1(r)x2(r)(e)将N=8点分解成2个4点的DFT的信号流图4点x(040(2)N/2(4点)-->N/4(2点)FFT

(a)先将4点分解成2点的DFT：因为4点DFT还是比较费事，所以再继续分解。假设将N/2(4点)子序列按奇/偶分解成两个N/4点〔2点〕子序列。即对将x1(r)和x2(r)分解成奇、偶两个N/4点〔2点〕点的子序列。(2)N/2(4点)-->N/4(2点)FFT

(a)先将441(b)求2点的DFT(b)求2点的DFT42〔c)一个2点的DFT蝶形流图2点DFT2点DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)〔c)一个2点的DFT蝶形流图2点DFT2点DFTx(0)x43〔d)另一个2点的DFT蝶形流图2点DFT2点DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)同理：〔d)另一个2点的DFT蝶形流图2点DFT2点DFTx(1)44(3)将N/4〔2点〕DFT再分解成2个1点的DFT

(a)求2个一点的DFT最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。(3)将N/4〔2点〕DFT再分解成2个1点的DFT

(a)45(b)2个1点的DFT蝶形流图1点DFTx(0)1点DFTx(4)X3(0)X3(1)进一步简化为蝶形流图：X3(0)X3(1)x(0)x(4)(b)2个1点的DFT蝶形流图1点DFTx(0)1点DFT46(4)一个完好N=8的按时间抽取FFT的运算流图x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)m=0m=1m=2(4)一个完好N=8的按时间抽取FFT的运算流图x(0)X47四、FFT算法中一些概念

〔1〕“级〞概念将N点DFT先分成两个N/2点DFT，再是四个N/4点DFT…直至N/2个两点DFT.每分一次称为“一〞级运算。因为N=2M所以N点DFT可分成M级如上图所示依次m=0,m=1….M-1共M级四、FFT算法中一些概念

〔1〕“级〞概念将N点DFT先48〔2〕“组〞概念每一级都有N/2个蝶形单元，例如：N=8,那么每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成假设干组，每一组具有一样的构造，一样的因子分布，第m级的组数为：例：N=8=23，分3级。m=0级,分成四组,每组系数为m=1级,分成二组,每组系数为m=2级,分成一组,每组系数为〔2〕“组〞概念每一级都有N/2个蝶形单元，例如：N49(3)因子的分布结论：每由后向前〔m由M-1-->0级〕推进一级，那么此系数为后级系数中偶数序号的那一半。(3)因子的分布结论：每由后向前〔m由M-1-->50〔4〕按时间抽取法2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT两个2点DFT两个2点DFT两个2点DFT两个2点DFT两个4点DFT两个4点DFT两个N/2点DFTX1(k)…...X2(k)X(k)由于每一步分解都是基于在每级按输入时间序列的次序是属于偶数还是奇数来分解为两个更短的序列，所以称为“按时间抽取法〞.x(n)〔4〕按时间抽取法2点DFT2点DFT2点DFT2点DFT251五、按时间抽取的FFT算法与直接计算DFT运算量的比较由前面介绍的按时间抽取的FFT运算流图可见：每级都由N/2个蝶形单元构成，因此每一级运算都需要N/2次复乘和N次复加〔每个结加减各一次〕。这样〔N=2M)M级运算共需要：复乘次数：复加次数：可以得出如下结论：按时间抽取法所需的复乘数和复加数都是与成正比。而直接计算DFT时所需的复乘数与复加数那么都是与N2成正比.(复乘数md=N2,复加数ad=N(N-1)≈N2)五、按时间抽取的FFT算法与直接计算DFT运算量的比较由前面52例子看N=8点和N=1024点时直接计算DFT与用基2-按时间抽取法FFT的运算量。看出：当N较大时，按时间抽取法将比直接法快一、二个数量级之多。例子看N=8点和N=1024点时直接计算DFT与用基2-按时53作业作业54六、按时间抽取FFT算法的特点根据DIT基2-FFT算法原理，能得出任何N=2m点的FFT信号流图，并进而得出FFT计算程序流程图。最后总结出按时间抽取法解过程的规律。1.原位运算〔in-place)六、按时间抽取FFT算法的特点根据DIT基2-FFT算法原理551.原位运算〔in-place)原位运算的构造，可以节省存储单元，降低设备本钱。定义：当数据输入到存储器以后，每一组运算的结果，仍然存放在这同一组存储器中直到最后输出。x(0)x(4)X3(0)X3(1)1.原位运算〔in-place)原位运算的构造，可以节省存储56例子例：N=8FFT运算,输入:x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)=x(0)A(1)=x(1)A(2)=x(2)A(3)=x(3)A(4)=x(4)A(5)=x(5)A(6)=x(6)A(7)=x(7)R1R1R1R1R1R2R1R1R2R2R3R4看出：用原位运算构造运算后，A(0)…A(7)正好顺序存放X(0)…X(7),可以直接顺序输出。例子例：N=8FFT运算,输入:x(0)A(0)A(0)A57我们从输入序列的序号及整序规律得到码位倒读规那么。由N=8蝶形图看出：原位计算时，FFT输出的X(k)的次序正好是顺序排列的，即X(0)…X(7),但输入x(n)都不能按自然顺序存入到存储单元中，而是按x(0),x(4),x(2),x(6)….的顺序存入存储单元即为乱序输入，顺序输出。这种顺序看起来相当杂乱，然而它是有规律的。即码位倒读规那么。我们从输入序列的序号及整序规律得到码位倒读规那么。由N=8蝶58例子以N=8为例：01234567000001010011100101110111自然顺序二进制码表示码位倒读码位倒置顺序00010001011000110101111104261537看出：码位倒读后的顺序刚好是数据送入计算机内的顺序。例子以N=8为例：0000自然顺序二进制码表示码位倒读码位倒59整序重排子程序详细执行时，只须将1与4对调送入，3与6对调送入，而0，2，5，7不变，仅需要一个中间存储单元。n01234567n’04261537在实际运算时，先按自然顺序将输入序列存入存储单元，再通过变址运算将自然顺序变换成按时间抽取的FFT算法要求的顺序。变址的过程可以用程序安排加以实现--称为“整序〞或“重排〞〔采用码位倒读〕且注意：(1)当n=n’时，数据不必调换；(2)当n≠n时，必须将原来存放数据x(n)送入暂存器R，再将x(n’)送入x(n),R中内容送x(n’).进展数据对调。(3)为了防止再次考虑前面已调换过的数据，保证调换只进展一次，否那么又变回原状。n’>n时，调换。整序重排子程序详细执行时，只须将1与4对调送入，3与6对调送60作业编写N=128点的基2--按时间抽取的FFT算法。要求用C语言编写，并将输入数据放在文件inputdata.dat中，输出数据放在outputdata.dat文件中。作业编写N=128点的基2--按时间抽取的FFT算法。要求用61七、按时间抽取的FFT算法的假设干变体

对于任何流图，只要保持各节点所连续的支路及其传输系数不变，那么不管节点位置怎么排列所得流图总是等效的，最后所得结果都是x(n)的离散付里叶变换的正确结果。只是数据的提取和存放的次序不同而已。七、按时间抽取的FFT算法的假设干变体

对于任何流62(2)输入是自然顺序而输出是乱序将原先中与x(4)程度相邻的所有节点跟x(1)程度相邻的所有节点位置对调；将原先中与x(6)程度相邻的所有节点跟x(3)程度相邻的所有节点位置对调，其余诸节点保持不变，那么可得：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(3)X(5)X(7)它与输入是乱序，输出顺序比较，看出：一样点：运算量一样；不同点：第一是数据存入方式不同；第二是取用系数的顺序不同。(2)输入是自然顺序而输出是乱序将原先中与x(4)程度相邻的63(2)输入和输出都是自然顺序对输入自然顺序，输出乱序的第二级，第三级节点作调整，可得输入输出都是顺序，无需数据重排：x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)〔1〕它失掉了“原位运算〞的性质。〔2〕为了变换N点数据，至少需要2N个复数单元。在内存比较紧张时，而对输入数据整序并不困难时一般不用。为了争取速度，才采取这种变体。(2)输入和输出都是自然顺序对输入自然顺序，输出乱序的第二级64第四节

基--2按频率抽取的FFT算法Decimation-in-Frequency(DIF)

(Sander-Tukey)第四节

基--2按频率抽取的FFT算法Decimation-65一、算法原理设输入序列长度为N=2M(M为正整数，将该序列的频域的输出序列X(k)(也是M点序列，按其频域顺序的奇偶分解为越来越短的子序列，称为基2按频率抽取的FFT算法。也称为Sander-Tukey算法。一、算法原理设输入序列长度为N=2M(M为正整数，将该序列的66二、算法步骤

DFT变换：已证明频域上X(k)按k的奇偶分为两组，在时域上x(n)按n的顺序分前后两局部，现将输入x(n)按n的顺序分前后两局部:前半子序列x(n),0≤n≤N/2-1;后半子序列x(n+N/2),0≤n≤N/2-1;例：N=8时，前半序列为：x(0),x(1),x(2),x(3);后半序列为：x(4),x(5),x(6),x(7);那么由定义输出〔求DFT〕二、算法步骤

DFT变换：已证明频域上X(k)按k的奇偶分为67DSPFFT深入浅出详细讲解快速傅里叶变换683.变量置换--13.变量置换--1693.变量置换--23.变量置换--2703.变量置换--33.变量置换--3713.变量置换--43.变量置换--472一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：可见：如此分解，直至分到2点的DFT为止。一个N点的DFT被分解为两个N/2点DFT。X1(k),X273DSPFFT深入浅出详细讲解快速傅里叶变换74三、蝶形流图表示蝶形单元：时域中，前后半部表示式用蝶形结表示。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。三、蝶形流图表示蝶形单元：时域中，前后半部表示式用蝶形结表示75例子：求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)为后半序列产生新的子序列：x1(n)、x2(n)频域上：X(0),X(2),X(4),X(6)由x1(n)给出X(1),X(3),X(5),X(7),由x2(n)给出例子：求N=23=8点DIF

〔1〕先按N=8-->N/76将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)将N=8点分解成2个4点的DIF的信号流图4点x(0)4点77(2)N/2(4点)-->N/4(2点)FFT

(a)先将4点分解成2点的DIF：因为4点DIF还是比较费事，所以再继续分解。(2)N/2(4点)-->N/4(2点)FFT

(a)先将478〔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)〔b)一个2点的DIF蝶形流图2点DFT2点DFTx1(0)79(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)(c)另一个2点的DIF蝶形流图2点DFT2点DFTx2(080(3)将N/4〔2点〕DFT再分解成2个1点的DFT

(a)求2个一点的DFT最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x3(0)、x3(1)为例。(3)将N/4〔2点〕DFT再分解成2个1点的DFT

(a)81(b)2个1点的DFT蝶形流图1点DFTx3(0)1点DFTx3(1)X(0)X(4)进一步简化为蝶形流图：X(0)X(4)x3(0)x3(1)(b)2个1点的DFT蝶形流图1点DFTx3(0)1点DF82(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(4)一个完好N=8的按频率抽取FFT的运算流图x(0)X83(5)DIF的特点(a)输入自然顺序，输出乱序且满足码位倒置规那么。(b)根据时域、频域互换，可知：输入乱序，输出自然顺序。(5)DIF的特点(a)输入自然顺序，输出乱序且满足码位倒置84〔6〕DIF与DIT比较1一样之处：〔1〕DIF与DIT两种算法均为原位运算。〔2〕DIF与DIT运算量一样。它们都需要〔6〕DIF与DIT比较1一样之处：85〔6〕DIF与DIT比较2不同之处：〔1〕DIF与DIT两种算法构造倒过来。DIF为输入顺序，输出乱序。运算完毕再运行“二进制倒读〞程序。DIT为输入乱序，输出顺序。先运行“二进制倒读〞程序，再进展求DFT。〔2〕DIF与DIT根本区别：在于蝶形结不同。DIT的复数相乘出如今减法之前。DIF的复数相乘出如今减法之后。〔6〕DIF与DIT比较2不同之处：86作业作业87第五节IFFT运算方法以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT。即快速付里叶反变换。从IDFT的定义出发，可以导出以下二种利用FFT来计算FFT的方法。第五节IFFT运算方法以上所讨论的FFT的运算方法同样可用于88一、利用FFT计算IFFT的思路1将以下两式进展比较一、利用FFT计算IFFT的思路1将以下两式进展比较89二、利用FFT计算IFFT的思路2利用FFT计算IFFT时在命名上应注意：(1)把FFT的时间抽取法，用于IDFT运算时，由于输入变量由时间序列x(n)改成频率序列X(k),原来按x(n)的奇、偶次序分组的时间抽取法FFT，如今就变成了按X(k)的奇偶次序抽取了。〔2〕同样，频率抽取的FFT运算用于IDFT运算时，也应改变为时间抽取的IFFT。二、利用FFT计算IFFT的思路2利用FFT计算IFFT时在90在IFFT的运算中，常常把1/N分解为(1/2)m，并且在M级运算中每一级运算都分别乘以1/2因子，就可得到IFFT的两种根本蝶形运算构造。〔并不常用此方法〕在IFFT的运算中，常常把1/N分解为(1/2)m，并且在M91ABAB(a)频率抽取IFFT的蝶形运算(b)时间抽取IFFT的蝶形运算ABAB(a)频率抽取IFFT的蝶形运算(b)时间抽取IFF92前面的两种IFFT算法，排程序很方便，但要改变FFT的程序和参数才能实现。现介绍第三种IFFT算法，那么可以完全不必改动FFT程序。前面的两种IFFT算法，排程序很方便，但要改变FFT的程序和93可知：只须将频域成份一个求共轭变换，即〔1〕将X(k)的虚部乘以-1，即先取X(k)的共轭，得X*(k)。(2)将X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再对运算结果取一次共轭变换，并乘以常数1/N，即可以求出IFFT变换的x(n)的值。此为DFT可用FFT程序可知：只须将频域成份一个求共轭变换，即〔1〕将X(k)的虚部94〔1〕FFT与IFFT连接应用时，注意输入输出序列的排列顺序，即应注意是自然顺序还是倒序。〔2〕FFT和IFFT共用同一个程序时，也应注意利用FFT算法输入输出的排列顺序，即应注意自然顺序还是例位序〔3〕当把频率抽取FFT流图用于IDFT时，应改称时间抽取IFFT流图。〔4〕当把时间抽取FFT流图用于IDFT时，应改称频率抽取IFFT流图。〔1〕FFT与IFFT连接应用时，注意输入输出序列的排列顺序95作业用C语言完成N=1024点的IDIT，IDIF。作业用C语言完成N=1024点的IDIT，IDIF。96第六节

线性调频Z变换第六节

线性调频Z变换97一、引入以上提出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个零点。一、引入以上提出FFT算法，可以很快地求出全部DFT值。即求98二、问题提出由上面三个问题提出：为了进步DFT的灵敏性，须用新的方法。线性调频z变换(CZT)就是适用这种更为一般情况下，由x(n)求X(zk)的快速变换CZT：来自于雷达专业的专用词汇。二、问题提出由上面三个问题提出：99Z变换采用螺线抽样,可适用于更一般情况下由x(n)求X(zk)的快速算法,这种变换称为线性调频Z变换(简称CZT).Z变换采用螺线抽样,可适用于更一100为适应z可以沿平面内更一般的途径取值，故：沿z平面上的一段螺线作等分角的抽样，那么z的取样点Zk可表示为：已知x(n)，0≤n≤N-1,那么它的z变换是：其中M：表示欲分析的复频谱的点数。M不一定等于N。A，都为任意复数。为适应z可以沿平面内更一般的途径取值，故：已知x(n)101DSPFFT深入浅出详细讲解快速傅里叶变换102DSPFFT深入浅出详细讲解快速傅里叶变换103DSPFFT深入浅出详细讲解快速傅里叶变换104DSPFFT深入浅出详细讲解快速傅里叶变换1055、图形5、图形1066、说明1〔1〕A为起始样点位置6、说明1〔1〕A为起始样点位置1076、说明2〔2〕zk是z平面一段螺线上的等分角上某一采样点。6、说明2〔2〕zk是z平面一段螺线上的等分角上某一采样点。1086、说明36、说明31096、说明46、说明41106、说明56、说明51117、CZT的实现步骤17、CZT的实现步骤11127、CZT的实现步骤27、CZT的实现步骤21137、CZT的实现步骤37、CZT的实现步骤31147、CZT的实现步骤47、CZT的实现步骤41157、CZT的实现步骤57、CZT的实现步骤51167、CZT的实现步骤67、CZT的实现步骤61177、CZT的实现步骤77、CZT的实现步骤71188、CZT变换运算流程图8、CZT变换运算流程图1199、CZT运算量的估算19、CZT运算量的估算11209、CZT运算量的估算29、CZT运算量的估算212110、CZT运算量与直接运算量比较当M、N足够小时，直接算法运算量少。但M、N值比较大时〔大于50〕，CZT算法比直接算法的运算量少得多。例M=50，N=50，N*M=2500次而CZT<1600次。10、CZT运算量与直接运算量比较当M、N足够小时，直接算法12211、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。11、CZT算法的特点与标准FFT算法相比，CZT算法有以下12312、CZT变换的应用1〔1〕利用CZT变换计算DFT。12、CZT变换的应用1〔1〕利用CZT变换计算DFT。12412、CZT变换的应用2〔2〕对信号的频谱进展细化分析。其中对窄带信号频谱或对局部感兴趣的频谱进展细化分析。这样CZT只对感兴趣的频率区段进展采样。计算量小很多，有利于实时处理。或在保证实时处理的情况下，可大进步频率分辨率。12、CZT变换的应用2〔2〕对信号的频谱进展细化分析。其中12512、CZT变换的应用3〔3〕求解z变换X(z)的零、极点。用于语音信号处理过程中。详细方法：利用不同半径同心圆，进展等间隔的采样。12、CZT变换的应用3〔3〕求解z变换X(z)的零、极点。126作业作业127第七节

分裂基FFT算法第七节

分裂基FFT算法128一、开展史自从基2快速算法出现以来，人们仍在不断寻求更快的算法。基4FFT算法就比最初的基2FFT算法更快。从理论上讲，用较大的基数还可以进一步减少运算次数，但要以程序〔或硬件〕变得更为复杂为代价。甚至得不偿失。1984年，法国的杜梅尔(P.Dohamel)和霍尔曼(H.Hollmann)将基2分解和基4分解糅合在一起，提出了分裂基FFT算法。其运算量比前几种算法都有所减少，运算流图却与基2FFT很接近，运算程序也很短。它是目前一种实用的高效新算法。一、开展史自从基2快速算法出现以来，人们仍在不断寻求更快的算129二、分裂基FFT算法原理二、分裂基FFT算法原理130DSPFFT深入浅出详细讲解快速傅里叶变换131DSPFFT深入浅出详细讲解快速傅里叶变换132DSPFFT深入浅出详细讲解快速傅里叶变换133DSPFFT深入浅出详细讲解快速傅里叶变换134DSPFFT深入浅出详细讲解快速傅里叶变换135结论1结论1136N/2点DFTN/4点DFT...N/4点DFT...........................................-jN/2点N/4.N/4.............-j137结论2结论2138结论3结论3139例子下面以N=16为例，说明完好的分裂基FFT运算流图的画法和排列形式。例子下面以N=16为例，说明完好的分裂基FFT运算流图的画法140DSPFFT深入浅出详细讲解快速傅里叶变换141DSPFFT深入浅出详细讲解快速傅里叶变换142N/2点〔8点〕DFTN/4点〔4点〕DFTN/4点〔4点〕DFT-j-j-j-jN/2点N/4N/4-j-j-j-j143DSPFFT深入浅出详细讲解快速傅里叶变换144DSPFFT深入浅出详细讲解快速傅里叶变换145N/4点〔4点〕DFT-j-jN/4点-j-j146-j同理，用同样方法可以画出4点分裂基FFT算法L形运算流