Download presentation
Presentation is loading. Please wait.
1
第四章 快速傅里叶变换 §4-1 引言 频域分析：一种有效的工具 DFT: △ 问题：
2
第四章 快速傅里叶变换 §4-2 直接计算DFT的起源和改善DFT运算效率的途径
设
3
第四章 快速傅里叶变换 §4-2 直接计算DFT的起源和改善DFT运算效率的途径
4
第四章 快速傅里叶变换 §4-2 直接计算DFT的起源和改善DFT运算效率的途径
2．长序列分解 Decimation-in-Time (DIT) Decimation-in-Frequency (DIF)
5
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
一、算法原理 ?
6
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
△ 代入(4-4)式
7
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
? 可见： 由(4-7)式
8
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
利用 的周期性， (4-10) 同理有， (4-11) 代入(4-7)式，有:
9
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
归纳起来有 可见，
10
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
上述运算可用下列蝶形信号流图表示: 图 4-1 蝶形运算流图符号
11
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
例：N=8 N/2-DFT
12
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
计算量分析： 相比N-DFT的 运算量减小了一半。
13
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
2-DFT： 可见仅需计算“+/-”运算。
14
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
例：N=8 (P129) 图4-5 N=8时的按频率抽取FFT运算流图
15
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
例：N=2v _(P130) 图4-5 N点基-2FFT的ν级迭代过程
16
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
二、运算量比较 1.DIT-FFT：N=2ν 由图4-6可见， 2. DFT
17
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
1. 原位运算(In-place)
18
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
3. 输入序列的序号及整序规律 由图4-5可见， 输入x(n)：乱序的 如何做到？ 整序 输出X(k)：顺序的
19
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
(1) 乱序的原因 例：N=8 正好为DIT-FFT的输入 正序 反序
20
第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
(2) 整序的规律 四、DIT-FFT算法的若干变体 [详见P :图4-11~图4-14]
21
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
一、算法原理 将X(n)，0 ≤ n ≤N-1 按顺序分为前后两半 k=0,1,…,N-1 (4-23) 注意： ∴两个∑和式并不是 N/2-DFT
22
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
所以，式(4-23)可改写为 (4-24) ∴可按k的奇偶取值将X(k)分为两部分：
23
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
(4-25) (4-26)
24
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
显然，若令 则有（式(4-25)(4-26)分别变为）
25
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
可见， 按k为奇偶分解 按频率抽取
26
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
例：N=8，DIF的分解过程（见图4-16）[P.137] N/2点 DFT ∴上述分解过程可继续下去， 直至分解ν次/步后变成求 N/2 个 2-DFT 为止。 DIF-FFT算法 （显然与DIT-FFT算法的分解类似）
27
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
例：N=8，DIF-FFT算法流图 [图4-18，P.138] 注意: ① ② 依然保留 （为了算法结构上的统一）
28
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
二、DIF-FFT与DIT-FFT的比较 图4-18 N=8,DIF-FFT算法流图
29
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
图4-5 N=8,DIT-FFT算法流图
30
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
1. 二者的区别 (1) 输入与输出 DIF：顺序 反序 DIT：反序 顺序 (2) 蝶形运算 DIF：先加减，后相乘 DIT：先相乘，后加减
31
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
2. 二者的相似之处 (1)分解过程 DIF：ν列 每列N/2个蝶形运算 DIT：ν列 同上 同上 (2)原位运算（∵所有运算均由蝶形运算构成） 3. 二者关系 DIF-FFT DIT-FFT 转置
32
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
三、逆DFT的快速算法(IFFT) 1. 算法一： FFT IFFT 比较IDFT与DFT，可见 DIT-FFT DIF-IFFT DIF-FFT DIT-IFFT (1) (2)
33
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
例：N=8，DIT-IFFT算法流图[图4-19，P.138]
34
第四章 快速傅里叶变换 §4-4 按频率抽取(DIF)的FFT算法(Sande-Tukey算法)
2. 算法二 优点： 四、DIF-FFT算法的若干变体 DIF-FFT DIT-FFT 转置 ∵ 变体 转置 ∴
35
第四章 快速傅里叶变换 §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 减少了运算
36
第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法
为此，令 n=Mn1+n0 , n0=0,1,…,M-1 —— 列号 n1=0,1,…,L-1 —— 行号 x(n) x( n1 , n0 )
37
第四章 快速傅里叶变换 §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 )
38
第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法
x(Mn1+n0) 1 n k L W = 1 n k M W = =1
39
第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法
式中 一列一列求DFT 旋转因子 一行一行求DFT
40
第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法
二、运算步骤
41
第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法——统一的FFT算法
例：N=12=4×3, M=4 , L=3 算法流图：图4-20,P.144 详见(4-38) P.142
42
第四章 快速傅里叶变换 §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
43
第四章 快速傅里叶变换 §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)
44
第四章 快速傅里叶变换 §4-6 分裂基FFT算法
一、背景 对更快速算法的需求 1984年，杜梅尔（P.Douhamel） 霍尔曼（H.Hollman） 基-2 FFT 基-4 FFT
45
第四章 快速傅里叶变换 §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 n n1 k=4k1+k0 , 0≤k1≤(N/4)-1 , 0≤ k0≤ 3 行号 列号
46
第四章 快速傅里叶变换 §4-6 分裂基FFT算法
(4-43)
47
第四章 快速傅里叶变换 §4-6 分裂基FFT算法
(4-44)
48
第四章 快速傅里叶变换 §4-6 分裂基FFT算法
L形蝶形运算：×— 2次 ＋— 5次
49
第四章 快速傅里叶变换 §4-6 分裂基FFT算法
则(4-44)式变为:
50
第四章 快速傅里叶变换 §4-6 分裂基FFT算法
可见： L形蝶形(流图) 图4-21/P.146
51
第四章 快速傅里叶变换 §4-6 分裂基FFT算法
例：N=16 分裂基第一次分解L形流图：图4-22 P.147 分解1： 分解2：
52
第四章 快速傅里叶变换 §4-6 分裂基FFT算法
分解3： 4点分裂基 L形运算流图 图4-24/P.148 图4-24 → 图4-23 → 图 图4-25 P.148 16点分裂基DIF-FFT算法流图
53
第四章 快速傅里叶变换 §4-6 分裂基FFT算法
三、运算量分析 L形分解：共M-1级 M~N=2M 每级L形碟形个数： 每个L形碟形：×— 2次 总的复数乘法次数： (4-48) 相比 ，下降33% 相同（∵ 个数相同）
54
第四章 快速傅里叶变换 §4-7 实序列的FFT算法
一、问题的提出 可能的办法： ① ② 能否有更好的方法吗？ ③
55
第四章 快速傅里叶变换 §4-7 实序列的FFT算法
二、算法一：用一个N-FFT同时计算两个N点时序的DFT DFT的性质：[P.91]
56
第四章 快速傅里叶变换 §4-7 实序列的FFT算法
即： (4-51) (4-52)
57
第四章 快速傅里叶变换 §4-7 实序列的FFT算法
三、算法二：用一个N-FFT计算一个2N-FFT 令：
58
第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform)
一、问题的提出 i) N=ML/2ν → FFT算法 （基-2，统一，分裂基） ii) （X(z)在 |z|=1 上等间隔取样值） 问题： Chirp-Z 变换
59
第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform)
二、算法原理 图4-26(P.152) 令
60
第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform)
…… ……
61
第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform)
参数几何意义
62
第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform)
可见， ∴DFT也可视为CZT的一种特例 一般情况： (4-62) 利用公式：
63
第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform)
式(4-62)变为： (4-65) 式中：
64
第四章 快速傅里叶变换 §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的运算流程图
65
第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform)
三、运算/实现步骤： (1)要求[X(zk)] (2)计算 f(n)*h(n)， n=0,1,…,M-1
66
第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform)
(3)计算 f(k)*h(k) 四、运算量估算 (M,N>50→CZT优于直接计算)
67
第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform)
五、CZT算法的特点 2) N,M均可为质数 → 任意情况 3) 取样起始点z0任选： 进行窄带学分辨分析 4) 可任意取值 的角间隔（频率）任意 频率分辨率可变
68
第四章 快速傅里叶变换 §4-8 线性调频 Z 变换 (Chirp-Z Transform)
DFT的推广
69
第四章 快速傅里叶变换 §4-9 细化FFT算法 (Zoom FFT or ZFFT)
一、问题提出 1) FFT/DFT：分辨率 ΔfN=fs/N ， (0 ~ fs)
70
第四章 快速傅里叶变换 §4-9 细化FFT算法 (Zoom FFT or ZFFT)
二、算法原理 (详见图4-30/P157) Zoom FFT
71
第四章 快速傅里叶变换 §4-10 FFT的应用 一、利用FFT求卷积——快速卷积
72
第四章 快速傅里叶变换 §4-10 FFT的应用 二、利用FFT求相关——快速相关
73
第四章 快速傅里叶变换 §4-11 FFT的其它形式
Winograd Fourier Transform Algorithm (WFTA):
74
第四章 快速傅里叶变换 §4-12 2-D DFT/FFT 算法
75
第四章 快速傅里叶变换 §4-12 2-D DFT/FFT 算法
二、2-D FFT
76
第四章 快速傅里叶变换 §4-12 2-D DFT/FFT 算法
三、运算量估算 1、2-D FFT 2、2-D DFT (与统一 1-D FFT算法比较)
77
第四章 快速傅里叶变换 小结
Similar presentations
