《按时间抽取的fft算法讲义》由会员分享，可在线阅读，更多相关《按时间抽取的fft算法讲义（28页珍藏版）》请在金锄头文库上搜索。
1、FFT算法分类:,时间抽选法 DIT: Decimation-In-Time 频率抽选法 DIF: Decimation-In-Frequency,7-2 按时间抽取的FFT算法,7-2 按时间抽取的FFT算法,一、按时间抽取的算法原理 二、按时间抽取的算法特点 三、按时间抽取FFT算法的其他形式,2,2019/8/18,一、按时间抽取的算法原理,设序列点数 N = 2L，L 为整数。 若不满足，则补零 N为2的整数幂的FFT算法称基-2FFT算法。 将序列x(n)按n的奇偶分成两组：,3,2019/8/18,4,则x(n)的DFT:,2019/8/18,5,再利用周期性求X(k)的后半部分,
2、2019/8/18,6,一个“蝶形运算”包含1次乘法，2次加法,2019/8/18,7,2019/8/18,8,分解后的运算量：,运算量减少了近一半,2019/8/18,N / 2仍为偶数，进一步分解：N / 2 N / 4,9,2019/8/18,10,同理：,其中：,这样逐级分解，直到2点DFT,基2时间抽取FFT算法流图,11,N=2,xk=x0, x1,2019/8/18,4点基2时间抽取FFT算法流图,12,X10,X11,X20,X21,-1,-1,-1,-1,X 0,X 1,X 2,X 3,2019/8/18,13,2019/8/18,4点基2时间抽取FFT算法流图,8点基2时间
3、抽取FFT算法流图,14,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,2019/8/18,15,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,8点基2时间抽取FFT算法流图,2019/8/18,基2时间抽取FFT算法,16,第一级,第二级,第三级,2019/8/18,二、按时间抽取的算法特点,17,1.计算速度 当N = 2L时，共有L级蝶形，每级N / 2个蝶形，每个蝶形有1次复数
4、乘法2次复数加法。,复数乘法：,复数加法：,比较DFT,2019/8/18,18,2019/8/18,算法的计算复杂度,19,2019/8/18,例 .如果一台通用计算机的速度为平均每次复乘 ，每次复加 ，用它来计算512点的 ，问直接计算需要多少时间，用 运算需要多少时间。,复乘所需时间,复加所需时间,所以直接利用DFT 计算所需时间：,2019/8/18,20,复乘所需时间,复加所需时间,所以用 FFT 计算所需时间,(2) 利用 计算： 复乘次数为 ，复加次数为 。,2019/8/18,21,2.倒序排列,22,23,倒序,k,0,k,1,k,2,2019/8/18,3.同址运算 在同一级蝶形运算中，两信号只参与一次运算。 4.蝶距规律,24,三、按时间抽取FFT算法的其它形式,25,2019/8/18,26,2019/8/18,27,2019/8/18,28,2019/8/18,
