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

1第4章快速傅立叶变换( FFT ) 概述 时间抽取基 2 算法 频率抽取基 2 算法 减少运算量的措施 分裂基算法 线性调频 Z 变换 其它算法 概述 120120 ) ( ) 0,1, 1 1 ( ) ( ) 0,1, 1 N j nk N nN j nk N k X k x n e k N x n X k e n N N ???????? ??? ??????( 2 ( ) ( ) DFT 1 x n N x n N X k N N N ?若 是点序列, 实现的, 即求出个( )需要: 次复数乘法,( )次复数加法! 3 2 4 2 1, 2 1 2 ( ) : 1024 1048576 ( ) : 512, 262144 ! x n N N x n n N N N ? ? ?=,= 解决耗时的乘法问题是将数字信号处理理论用于实际的关键问题。特别是 30年前,计算机的速度相当慢。因此,很多学者对解决 DFT 的快速计算问题产生了极大的兴趣。 Cooley J W, Tukey J W. An algorithm for the putation plex Fourier series. Mathematics putation, 1965, pp297~301 4 2 1024 1048576 N N =,= Cooley 和 Tukey 提出的解决 DFT 的快速傅立叶变换算法( Fast Fourier Transform, FFT ),使计算量由 N 2 降为 2 log 2 NN 2 log 5120 2 NN? 5120 % 1048576 ? 5 FFT 的思路: 10 ) ( ) 0,1, 1 Nnk n X k x n W k N ??? ????( 2 / j N W e ??= 0 1. 1 W? 2. 1, 1 N mN W W ? ? 3. N r r W W ?? 2 4. 1 NW ?? 25. Nrr W W ???如何充分利用这些关系 6 DFT : 0 0 0 0 0 1 2 1 0 2 4 2( 1) 0 1 2( 1) ( 1)( 1) (0) (0) (1) (1) (2) (2) ( 1) ( 1) ??? ? ??? ?? ? ??? ?? ? ??? ?? ? ??? ?? ? ???? ?? ? ??? ?? ? ??? ?? ? ??? ?? ? ??? ????? ?? ????? N N N N N N N N N N N N N N N N N N N N N N X x W W W W X x W W W W X x W W W W X N x N