北京交通大学：《数字信号处理》课程教学课件（PPT讲稿）第3章 快速傅里叶算法FFT 3.1 FFT引入

离散傅单叶变换快速算法为什么研究FFT算法FFT算法的历史沿革解决问题的基本思想

◆ 为什么研究FFT算法 ◆ FFT算法的历史沿革 ◆ 解决问题的基本思想 离散傅里叶变换快速算法

为什么研究FFT算法x(t)X(jo)理论上FTX(ej?)x[k]？方法上x[k]X[m]DFT

x k[ ] j X(e )  x k[ ] X m[ ] 理论上 方法上 FT DFT x t( ) X ( j )  为什么研究FFT算法

为什么研究FFT算法4点序列2，3，3，2?DFT的计算复杂度N-X[m]-2x[kJW", m=0,],, N-1Wkm=ek=0X[0]= 2W +3W +3W +2W=10复数加法N(N-1)X[1]= 2W +3W +3W+2W = -1- jN2复数乘法X[2] =2W +3W+3W4 +2W = 0随着N的增大，DFT的X[3] = 2W +3W +3W° +2W = -1+ j计算复杂度急剧增加

4点序列{2，3，3，2} DFT的计算复杂度 1 0 [ ] [ ] , 0,1, , 1 − = = = −  N km N k X m x k W m N 0 0 0 0 X W W W W [0] 2 3 3 2 10 = + + + = N N N N 0 1 2 3 X W W W W [1] 2 3 3 2 1 j = + + + = − − N N N N 0 2 4 6 X W W W W [2] 2 3 3 2 0 = + + + = N N N N 0 3 6 9 X W W W W [3] 2 3 3 2 1 j = + + + = − + N N N N 复数加法 N(N-1) 复数乘法 N 2 随着N的增大，DFT的 计算复杂度急剧增加。 2π j e km km N WN − = 为什么研究FFT算法

为什么研究FFT算法序列DFT点数N复数乘法复数加法N28645616256240329921024644096403212816384162562566553665280512262144261632102410485761047552204841943044192256N4096167772161677312081926710886467100672

为什么研究FFT算法 序列 DFT 点数N 复数乘法 复数加法 8 16 32 64 128 256 512 1024 2048 4096 8192 64 256 1024 4096 16384 65536 262144 1048576 4194304 16777216 67108864 56 240 992 4032 16256 65280 261632 1047552 4192256 16773120 67100672 复乘次数 N N 2

为什么研究FFT算法DFT在数字信号处理中的重要意义早已被人们所认识，但其得到广泛应用却经历了较长时间，原因就是其计算量太大而难以实用。二十世纪中叶以来，信号处理快速算法研究取得长足进展，其中包括DFT的快速算法，即快速傅里叶变换(FastFourierTransform，简称FFT），FFT是各种DFT快速算法的统称

二十世纪中叶以来，信号处理快速算法研究取得长足进展， 其中包括DFT的快速算法，即快速傅里叶变换（Fast Fourier Transform，简称FFT），FFT是各种DFT快速算法的统称。 DFT在数字信号处理中的重要意义早已被人们所认识，但 其得到广泛应用却经历了较长时间，原因就是其计算量太大而 难以实用。 为什么研究FFT算法

为什么研究FFT算法频域分析的工程应用x(t)X(jo)理论上FTX(ej?)x[k]方法上x[k]X[m]DFT技术上x[k]* X[m]FFT方法从提出到实际应用要经过理论--方法--技术三个阶段，同时也会受制于其他技术（如硬件等）的发展

为什么研究FFT算法 x k[ ] j X(e )  x k[ ] x k[ ] X m[ ] X m[ ] 理论上 方法上 技术上 FT DFT FFT x t( ) X ( j )  方法从提出到实际应用要经过理论-方法-技术三个阶段，同时也会受 制于其他技术（如硬件等）的发展。 频域分析的工程应用

FFT算法的历史沿革1965年，库利和图基的快速算法几儿经改进，形成了一套高效运算方法，这就是现在的FFT。这种算法使DFT的运算效率得到了极大的提高，并降低了DFT运算带来的累计量化误差杜哈梅和霍尔库利和图基提出了一种DFTBergland提出曼提出分裂基算法基-4算法的快速算法196519691984

1965年，库利和图基的快速算法几经改进，形成了一套高效运算方 法，这就是现在的FFT。这种算法使DFT的运算效率得到了极大的提高， 并降低了DFT运算带来的累计量化误差。 库利和图基提 出了一种DFT 的快速算法 1965 1969 Bergland提出 基-4算法 杜哈梅和霍尔 曼提出分裂基 算法 1984 FFT算法的历史沿革

FFT算法的历史沿革库利，JamesWilliamCooley(1926-)，美国数学家，哥伦比亚大学的数学博士，提出的快速傅里叶变换(FFT)使得数字信号处理技术取得了突破性进展，对于现在网络通信，图形图像处理等领域的发展奠定了基础。多年来在IBM研究中心中主要从事数字信号处理的研究，1980年获得ASSPSociety以及MeritoriousServiceAward,1984年获得SocietyAward以及IEEECentennialMedal

库利，James William Cooley(1926-)，美国 数学家，哥伦比亚大学的数学博士，提出的快 速傅里叶变换(FFT)使得数字信号处理技术取得 了突破性进展，对于现在网络通信，图形图像 处理等领域的发展奠定了基础。 多年来在IBM研究中心中主要从事数字信 号处理的研究，1980年获得ASSP Society以及 Meritorious Service Award,1984年获得Society Award以及IEEE Centennial Medal。 FFT算法的历史沿革

FFT算法的历史沿革图基，JohnWilderTukey（1915~2000），美国著名数学家，普林斯顿大学数学博士，他与库利共同提出了一种快速傅里叶变换算法。1973年被授予美国国家科学奖章，1982年被授予IEEE荣誉勋章和皇家科学院外籍院士。以他的名字命名的图基范围测试，图基拉姆达分布，图基加性试验和图基引理都是他一生的科学贡献

图基，John Wilder Tukey (1915~2000)，美 国著名数学家，普林斯顿大学数学博士，他与 库利共同提出了一种快速傅里叶变换算法。 1973年被授予美国国家科学奖章，1982年 被授予IEEE荣誉勋章和皇家科学院外籍院士。 以他的名字命名的图基范围测试，图基拉姆达 分布，图基加性试验和图基引理都是他一生的 科学贡献。 FFT算法的历史沿革

解决问题的基本思想Cooley-Tukey提出的FFT算法的基本思想：※将长序列DFT分解为短序列的DFT※利用旋转因子 Wkm 的周期性、对称性、可约性

※将长序列DFT分解为短序列的DFT ※利用旋转因子 WN km 的周期性、对称性、可约性 解决问题的基本思想 Cooley-Tukey 提出的FFT算法的基本思想：