第四章快速傅里叶变换 41引言 DFT的计算量与N的平方成正比 DFT是信号分析与处理中的一种重要变换。但因直接计算DFT的计算量与 变换区间长度N的平方成正比,当N较大时,计算量很大,所以在快速傅里叶 变换出现以前,直接用DFT算法进行谱分析和信号实时处理是不切实际的。 直到1965年发现了DFT的一种快速算法,情况才发生了根本变化。 快速傅立叶变换发展 令1965年,图基(JW.Tuky)和库力(TW. Coody)在 Math. Computation 杂志发表著名的“机器计算傅立叶级数的一种算法”一文。桑德图 基快速算法出现,经改进,形成一套高效运算方法,这就是快速傅里 叶变换。 ◇1984年,杜哈梅尔和霍尔曼提出分裂基快速算法,使运算效率进 步提高。 42基2FFT算法 本章主要讨论基2FFT算法及其编程思想 42.1直接计算DFT的特点及减少运算量的基本途径 1、按DFT定义计算DFT的计算量 根据前面知识,长度为N的有限长序列x(m)的DFT为 (k)=∑x(n)W,k=01…,N 考虑x(n)为复数序列的一般情况,对某一个k值,直接按(1)式计算X(k)值 需要N次复数乘法、(N-1)次复数加法。因此剧所有N个k值共需N2次复数第四章 快速傅里叶变换 4.1 引言  DFT 的计算量与 N 的平方成正比 DFT 是信号分析与处理中的一种重要变换。但因直接计算 DFT 的计算量与 变换区间长度 N 的平方成正比，当 N 较大时，计算量很大，所以在快速傅里叶 变换出现以前，直接用 DFT 算法进行谱分析和信号实时处理是不切实际的。  直到 1965 年发现了 DFT 的一种快速算法，情况才发生了根本变化。  快速傅立叶变换发展  1965 年，图基（J. W. Tuky）和库力（T.W. Coody）在 Math.Computation 杂志发表著名的“机器计算傅立叶级数的一种算法”一文。桑德-图 基快速算法出现，经改进，形成一套高效运算方法，这就是快速傅里 叶变换。  1984 年，杜哈梅尔和霍尔曼提出分裂基快速算法，使运算效率进一 步提高。 4.2 基 2FFT 算法 ——本章主要讨论基 2FFT 算法及其编程思想 4.2.1 直接计算 DFT 的特点及减少运算量的基本途径 1、按 DFT 定义计算 DFT 的计算量 根据前面知识，长度为 N 的有限长序列 x n  的 DFT 为     1 0 , 0,1, , 1 N kn N n X k x n W k N        (1) 考虑 x n  为复数序列的一般情况，对某一个 k 值，直接按(1)式计算 X k  值 需要 N 次复数乘法、（N-1）次复数加法。因此对所有 N 个 k 值，共需 2 N 次复数