快速傅里叶变换(FFT).ppt

第四章

快速傅里叶变换

（FFT）主要内容DIT-FFT算法DIF-FFT算法IFFT算法Chirp-FFT算法线性卷积的FFT算法§4.1引言FFT:FastFourierTransform1965年，Cooley-Turky发表文章《机器计算傅里叶级数的一种算法》，提出FFT算法，解决DFT运算量太大，在实际使用中受限制的问题。FFT的应用。频谱分析、滤波器实现、实时信号处理等。DSP芯片实现。TI公司的TMS320c30，10MHz时钟，基2-FFT1024点FFT时间15ms。典型应用：信号频谱计算、系统分析等§4.2直接计算DFT的问题及改进途径3、降低DFT运算量的考虑§4.3按时间抽取（DIT）的FFT算法1、算法原理 设序列点数N=2L，L为整数。若不满足，则补零将N点DFT定义式分解为两个长度为N/2的DFT将上式表达的运算用一个专用“蝶形”信流图表示。用“蝶形结”表示上面运算的分解： N点DFT分解为四个N/4点的DFT类似进一步分解类似的分解一直继续下去，直到分解为最后的两类蝶形运算为止(2点DFT).如上述N=8=23，N/4=2点中：FFT运算量与运算特点1．N=2L时，共有L=log2N级运算；每一级有N/2个蝶形结。2．每一级有N个数据(中间数据），且每级只用到本级的转入中间数据，适合于迭代运算。3．计算量：每级N/2次复乘法，N次复加。（每蝶形只乘一次，加减各一次）。共有L*N/2=N/2log2N次复乘法；复加法L*N=Nlog2N次。与直接DFT定义式运算量相比(倍数)N2/(Nlog2N)。当N大时，此倍数很大。按时间抽取FFT蝶形运算特点1、关于FFT运算的混序与顺序处理（位倒序处理）由于输入序列按时间序位的奇偶抽取，故输入序列是混序的，为此需要先进行混序处理。混序规律：x(n)按n位置进行码位（二进制）倒置规律输入，而非自然排序，即得到混序排列。所以称为位倒序处理。位倒序实现：（1）DSP实现采用位倒序寻址（2）通用计算机实现可以有两个方法：一是严格按照位倒序含义进行；二是倒进位的加N/2。例 计算，。计算 点FFT。用时间抽取输入倒序算法，问倒序前寄存器的数和倒序后的数据值？DITFFT中最主要的蝶形运算实现（1）参与蝶形运算的两类结点（信号）间“距离”（码地址）与其所处的第几级蝶形有关；第m级的“结距离”为(即原位计算迭代）（2）每级迭形结构为DIT算法的其他形式流图输入倒位序输出自然序输入自然序输出倒位序输入输出均自然序相同几何形状输入倒位序输出自然序输入自然序输出倒位序§4.4按频率抽取（DIF）的FFT算法与DIT-FFT算法类似分解，但是抽取的是X(k)。即分解X(k)成奇数与偶数序号的两个序列。设：N=2L，L为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半：下面讨论二、按频率抽取FFT蝶形运算特点1）原位计算§4.6线性调频Z变换（Chirp-Z变换）算法

（FFT应用二）§4.7线性卷积的FFT算法

（FFT应用三）2、重叠保存法此方法与上述方法稍有不同。先将x(n)分段，每段L=N-M+1个点，这是相同的。不同之处是，序列中补零处不补零，而在每一段的前边补上前一段保留下来的（M-1）个输入序列值，组成L+M-1点序列xi(n)。如果L+M-1<2m，则可在每段序列末端补零值点，补到长度为2m，这时如果用DFT实现h(n)和xi(n)圆周卷积，则其每段圆周卷积结果的前（M-1）个点的值不等于线性卷积值，必须舍去。例用FFT算法处理一幅N×N点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解当N=1024点时，FFT算法处理一幅二维图像所需复数乘法约为 次，仅为直接计算DFT所需时间的10万分之一。即原需要3000小时，现在只需要2分钟。（DecimationInFrequency)一、算法原理按k的奇偶将X(k)分成两部分：显然：令：用蝶型结构图表示为：x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)