第四章 快速傅里叶变换 §4-1 引言 频域分析：一种有效的工具 DFT: △ 问题：

第四章 快速傅里叶变换 §4-2 直接计算DFT的起源和改善DFT运算效率的途径 设

第四章 快速傅里叶变换 §4-2 直接计算DFT的起源和改善DFT运算效率的途径

第四章 快速傅里叶变换 §4-2 直接计算DFT的起源和改善DFT运算效率的途径 2．长序列分解 Decimation-in-Time (DIT) Decimation-in-Frequency (DIF)

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 一、算法原理 ?

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) △ 代入(4-4)式

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) ? 可见： 由(4-7)式

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 利用 的周期性， (4-10) 同理有， (4-11) 代入(4-7)式，有:

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 归纳起来有 可见，

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 上述运算可用下列蝶形信号流图表示: 图 4-1 蝶形运算流图符号

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 例：N=8 N/2-DFT

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 计算量分析： 相比N-DFT的 运算量减小了一半。

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 2-DFT： 可见仅需计算“+/-”运算。

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 例：N=8 (P129) 图4-5 N=8时的按频率抽取FFT运算流图

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 例：N=2v _(P130) 图4-5 N点基-2FFT的ν级迭代过程

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 二、运算量比较 1.DIT-FFT：N=2ν 由图4-6可见， 2. DFT

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 1. 原位运算(In-place)

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 3. 输入序列的序号及整序规律 由图4-5可见， 输入x(n)：乱序的 如何做到？ 整序 输出X(k)：顺序的

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) (1) 乱序的原因 例：N=8 正好为DIT-FFT的输入 正序 反序

第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) (2) 整序的规律 四、DIT-FFT算法的若干变体 [详见P.134-135:图4-11~图4-14]

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 一、算法原理 将X(n)，0 ≤ n ≤N-1 按顺序分为前后两半 k=0,1,…,N-1 (4-23) 注意： ∴两个∑和式并不是 N/2-DFT

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 所以，式(4-23)可改写为 (4-24) ∴可按k的奇偶取值将X(k)分为两部分：

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) (4-25) (4-26)

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 显然，若令 则有（式(4-25)(4-26)分别变为）

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 可见， 按k为奇偶分解 按频率抽取

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 例：N=8，DIF的分解过程（见图4-16）[P.137] N/2点 DFT ∴上述分解过程可继续下去， 直至分解ν次/步后变成求 N/2 个 2-DFT 为止。 DIF-FFT算法 （显然与DIT-FFT算法的分解类似）

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 例：N=8，DIF-FFT算法流图 [图4-18，P.138] 注意: ① ② 依然保留 （为了算法结构上的统一）

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 二、DIF-FFT与DIT-FFT的比较 图4-18 N=8,DIF-FFT算法流图

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 图4-5 N=8,DIT-FFT算法流图

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 1. 二者的区别 (1) 输入与输出 DIF：顺序 反序 DIT：反序 顺序 (2) 蝶形运算 DIF：先加减，后相乘 DIT：先相乘，后加减

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 2. 二者的相似之处 (1)分解过程 DIF：ν列 每列N/2个蝶形运算 DIT：ν列 同上 同上 (2)原位运算（∵所有运算均由蝶形运算构成） 3. 二者关系 DIF-FFT DIT-FFT 转置

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 三、逆DFT的快速算法(IFFT) 1. 算法一： FFT IFFT 比较IDFT与DFT，可见 DIT-FFT DIF-IFFT DIF-FFT DIT-IFFT (1) (2)

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 例：N=8，DIT-IFFT算法流图[图4-19，P.138]

第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法) 2. 算法二 优点： 四、DIF-FFT算法的若干变体 DIF-FFT DIT-FFT 转置 ∵ 变体 转置 ∴

第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法 处理方法： (1)通过补零，使序列长度=2ν→ 基-2 FFT (2)N=ML（复合数） → 统一的FFT算法 (3)N≠ML（素数） → Chirp-Z 变换(CZT) 一、算法原理 ∵N-DFT~N ∴如果N-DFT M个L-DFT~M×L2 L个M-DFT~L×M2 减少了运算

第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法 为此，令 n=Mn1+n0 , n0=0,1,…,M-1 —— 列号 n1=0,1,…,L-1 —— 行号 x(n) x( n1 , n0 )

第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法 同理，对DFT的输出X(k)做类似的处理： 令 k=Lk1+k0 k0=0,1,…,L-1 ~ n1 k1=0,1,…,M-1~ n0 X(k) X( k1 , k0 )

第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法 x(Mn1+n0) 1 n k L W = 1 n k M W = =1

第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法 式中 一列一列求DFT 旋转因子 一行一行求DFT

第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法 二、运算步骤

第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法 例：N=12=4×3, M=4 , L=3 算法流图：图4-20,P.144 详见(4-38) P.142

第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法 三、基数（指特定的分解） 1. N=2ν→基2 FFT算法 2. N≠2ν N=r1,r2,…,rM M级r1,r2,…, rM点DFT →混合基算法 r1=r2=…=rM →N= rM M级r-DFT → 基-r FFT算法 比如：a) N=2M →基-2 FFT b) N=4M →基-4 FFT

第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法 四、运算量估算 N=ML (1) M个L-DFT：×— M×L2=N×L ＋— M×L(L-1)=N(L-1) (2) 乘N个 因子： ×— N (3) L个M-DFT：×—L×M2=N×M ＋— L×M(M-1)=N(M-1) 总运算量：×— NL+N+NM=N(L+M+1) < N2 ＋— N(L-1)+N(M-1)=N(L+M-2) < N(N-1)

第四章 快速傅里叶变换 §4-6 分裂基FFT算法 一、背景 对更快速算法的需求 1984年，杜梅尔（P.Douhamel） 霍尔曼（H.Hollman） 基-2 FFT 基-4 FFT

第四章 快速傅里叶变换 §4-6 分裂基FFT算法 二、算法原理 DFT[x(n)] → 更快的FFT算法 设 N=Pq, P=N/4, q=4 (=ML, M=N/4, L=4) 令 n=Pn1+n0 , 0≤n1 ≤3, 0≤ n0≤(N/4)-1 n0 n1 k=4k1+k0 , 0≤k1≤(N/4)-1 , 0≤ k0≤ 3 行号 列号

第四章 快速傅里叶变换 §4-6 分裂基FFT算法 (4-43)

第四章 快速傅里叶变换 §4-6 分裂基FFT算法 (4-44)

第四章 快速傅里叶变换 §4-6 分裂基FFT算法 L形蝶形运算：×— 2次 ＋— 5次

第四章 快速傅里叶变换 §4-6 分裂基FFT算法 则(4-44)式变为:

第四章 快速傅里叶变换 §4-6 分裂基FFT算法 可见： L形蝶形(流图) 图4-21/P.146

第四章 快速傅里叶变换 §4-6 分裂基FFT算法 例：N=16 分裂基第一次分解L形流图：图4-22 P.147 分解1： 分解2：

第四章 快速傅里叶变换 §4-6 分裂基FFT算法 分解3： 4点分裂基 L形运算流图 图4-24/P.148 图4-24 → 图4-23 → 图4-22 图4-25 P.148 16点分裂基DIF-FFT算法流图

第四章 快速傅里叶变换 §4-6 分裂基FFT算法 三、运算量分析 L形分解：共M-1级 M~N=2M 每级L形碟形个数： 每个L形碟形：×— 2次 总的复数乘法次数： (4-48) 相比 ，下降33% 相同（∵ 个数相同）

第四章 快速傅里叶变换 §4-7 实序列的FFT算法 一、问题的提出 可能的办法： ① ② 能否有更好的方法吗？ ③

第四章 快速傅里叶变换 §4-7 实序列的FFT算法 二、算法一：用一个N-FFT同时计算两个N点时序的DFT DFT的性质：[P.91]

第四章 快速傅里叶变换 §4-7 实序列的FFT算法 即： (4-51) (4-52)

第四章 快速傅里叶变换 §4-7 实序列的FFT算法 三、算法二：用一个N-FFT计算一个2N-FFT 令：

第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform) 一、问题的提出 i) N=ML/2ν → FFT算法 （基-2，统一，分裂基） ii) （X(z)在 |z|=1 上等间隔取样值） 问题： Chirp-Z 变换

第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform) 二、算法原理 图4-26(P.152) 令

第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform) …… ……

第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform) 参数几何意义

第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform) 可见， ∴DFT也可视为CZT的一种特例 一般情况： (4-62) 利用公式：

第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform) 式(4-62)变为： (4-65) 式中：

第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform) h(n) X(zn), n=0,1,…,M-1 x(n), n=0,1,…,N-1 f(n) 图4-27 CZT的运算流程图

第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform) 三、运算/实现步骤： (1)要求[X(zk)] (2)计算 f(n)*h(n)， n=0,1,…,M-1

第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform) (3)计算 f(k)*h(k) 四、运算量估算 (M,N>50→CZT优于直接计算)

第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform) 五、CZT算法的特点 2) N,M均可为质数 → 任意情况 3) 取样起始点z0任选： 进行窄带学分辨分析 4) 可任意取值 的角间隔（频率）任意 频率分辨率可变

第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform) DFT的推广

第四章 快速傅里叶变换 §4-9 细化FFT算法 (Zoom FFT or ZFFT) 一、问题提出 1) FFT/DFT：分辨率 ΔfN=fs/N ， (0 ~ fs)

第四章 快速傅里叶变换 §4-9 细化FFT算法 (Zoom FFT or ZFFT) 二、算法原理 (详见图4-30/P157) Zoom FFT

第四章 快速傅里叶变换 §4-10 FFT的应用 一、利用FFT求卷积——快速卷积

第四章 快速傅里叶变换 §4-10 FFT的应用 二、利用FFT求相关——快速相关

第四章 快速傅里叶变换 §4-11 FFT的其它形式 Winograd Fourier Transform Algorithm (WFTA):

第四章 快速傅里叶变换 §4-12 2-D DFT/FFT 算法

第四章 快速傅里叶变换 §4-12 2-D DFT/FFT 算法 二、2-D FFT

第四章 快速傅里叶变换 §4-12 2-D DFT/FFT 算法 三、运算量估算 1、2-D FFT 2、2-D DFT (与统一 1-D FFT算法比较)

第四章 快速傅里叶变换 小结