23-24-快速傅里叶变换精读.ppt

时间抽取、 输入自然顺序、 输出倒位序的FFT流图 例 用FFT算法处理一幅N×N点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？ 例 用FFT算法处理一幅N×N点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？ 解 当N=1024点时，FFT算法处理一幅二维图像所需复数乘法约为 次，仅为直接计算DFT所需时间的10万分之一。 即原需要3000小时，现在只需要2 分钟。 - DIT-FFT算法 - IFFT算法 IDFT的FFT算法 一、从定义比较分析 与DFT的比较： 1）、旋转因子WN-kn 的不同； 2）、结果还要乘 1/N。 二、实现算法——直接使用FFT程序的算法 共轭 FFT 共轭 乘1/ N 直接调用FFT子程序计算IFFT的方法： - DIT-FFT算法 - IFFT算法 1 引言 FFT: Fast Fourier Transform 1965年，Cooley-Turky 发表文章《机器计算傅里叶级数的一种算法》，提出FFT算法，解决DFT运算量太大，在实际使用中受限制的问题。 FFT的应用。频谱分析、滤波器实现、实时信号处理等。 DSP芯片实现。TI公司的TMS 320c30，10MHz时钟，基2-FFT1024点FFT时间15ms。 典型应用：信号频谱计算、系统分析等 系统分析 频谱分析与功率谱计算 2 直接计算DFT的问题及改进途径 2.1、 DFT与IDFT 2.2、DFT与IDFT运算特点 复数乘法 复数加法 一个X(k) N N – 1 N个X(k) (N点DFT) N 2 N (N – 1) 实数乘法 实数加法 一次复乘 4 2 一次复加 2 一个X (k) 4N 2N+2 (N – 1)=2 (2N – 1) N个X (k) (N点DFT) 4N 2 2N (2N – 1) 同理：IDFT运算量与DFT相同 2.3、降低DFT运算量的考虑 FFT算法分类: 时间抽选法 DIT: Decimation-In-Time 频率抽选法 DIF: Decimation-In-Frequency 3 按时间抽取（DIT）的FFT算法 （Decimation In Time） 3.1、算法原理 设序列点数 N = 2L，L 为整数。 若不满足，则补零 将序列x(n)按n的奇偶分成两组： N为2的整数幂的FFT算法称基-2FFT算法。 将N点DFT定义式分解为两个长度为N/2的DFT 记： ………（1） （这一步利用： ） 再利用周期性求X(k)的后半部分 将上式表达的运算用一个专用“蝶形”信流图表示。 注：a. 上支路为加法，下支路为减法； b. 乘法运算的支路标箭头和系数。 用“蝶形结”表示上面运算的分解： 分解后的运算量： 复数乘法 复数加法 一个N/2点DFT (N/2)2 N/2 (N/2 –1) 两个N/2点DFT N2/2 N (N/2 –1) 一个蝶形 1 2 N/2个蝶形 N/2 N 总计 运算量减少了近一半 进一步分解 由于 ， 仍为偶数，因此，两个 点 DFT又可同样进一步分解为4个 点的DFT。 “蝶形”信流图表示 N点DFT分解为四个N/4点的DFT 类似的分解一直继续下去，直到分解为最后的两类蝶形运算为止(2点DFT). 如上述N=8=23，N/4=2点中： 类似进一步分解 1点DFT x(0) 1点DFT x(4) X3(0) X3(1) 进一步简化为蝶形流图： X3(0) X3(1) x(0) x(4) 因此8点FFT时间抽取方法的信流图如下—— 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大时，此倍数很大。 与DFT