快速计算离散傅里叶变换

《快速计算离散傅里叶变换》由会员分享，可在线阅读，更多相关《快速计算离散傅里叶变换（56页珍藏版）》请在装配图网上搜索。

1、第 4章 快 速 傅 里 叶 变 换 (FFT) 第 4章 快 速 计 算 离 散 傅 里 叶 变 换 4.1 引 言4.2 基 2FFT算 法4.3 进 一 步 减 少 运 算 量 的 措 施4.4 分 裂 基 FFT算 法4.5 离 散 哈 特 莱 变 换 (DHT) 第 4章 快 速 傅 里 叶 变 换 (FFT) 4.1 引 言 与 序 列 的 傅 里 叶 变 换 相 比 ， 离 散 傅 里 叶 变 换 有 实用 价 值 。 但 是 按 定 义 直 接 计 算 DFT有 实 用 价 值 吗 ？ 只有 一 些 。 因 为 这 种 算 法 的 计 算 数 度 太 慢 了 。 特 别 是 与

2、后 人 发 明 的 算 法 相 比 ， 它 的 慢 更 显 突 出 。 1965年 ， J. W. Cooley 和 J. W. Tukey在Mathematics of Computation上 发 表 了 An algorithm for the machine calculation of complex Fourier series。 它 极 大 的 提 高 了 计 算 离 散 傅 里 叶 变 换 的 速 度 。 第 4章 快 速 傅 里 叶 变 换 (FFT) 从 定 义 来 看 N点 长 的 DFT的 运 算 量 。 1 直 接 计 算 DFT需 ： 复 乘 N2次 ， 复 加 (

3、N-1)N次 。 因为 1个 k需 复 乘 N次 ， 复 加 (N-1)次 。 对 于 复 乘 1次 需 50s， 复 加 1次 需 10s的 计 算 机 ， 用 直接 法 做 N=1024点 长 的 DFT共 需 多 少 时 间 ？ 1024 2 50 10-6 1023 1024 10 10-6=63(s) 2 Cooley和 Tukey发 明 的 方 法 计 算 DFT需 ： 复 乘(N/2)log2N次 ， 复 加 Nlog2N次 。 用 来 计 算 上 面 的 DFT共需 多 少 时 间 ？ 512 10 50 10-6 1024 10 10 10-6=0.36(s) 10 )()(

4、 Nn knNWnxkX 第 4章 快 速 傅 里 叶 变 换 (FFT) 4.2 基 2(radix2)FFT算 法 4.2.1 直 接 计 算 DFT的 特 点 及 减 少 运 算 量 的 方 法 直 接 计 算 N个 采 样 值 的 DFT 需 要 有 N2次 复 数 乘 法 和N(N-1)次 复 数 加 法 。 如 果 把 N分 成 几 小 段 ， 降 低 DFT的 规 模 ， 是 不 是 可 以 大幅 度 地 减 少 乘 法 和 加 法 的 运 算 次 数 ？ 还 有 ， W Nkn具 有 对 称 性 和 周 期 性 ， 是 不 是 可 以 巧 妙 地利 用 ？ 第 4章 快 速 傅

5、 里 叶 变 换 (FFT) 例 如 ， 当 N=8时 ， 从 形 式 上 看 ， W8kn共 有 64个 值 。 但从 图 来 看 ， Wkn实 际 上 只 有 W0W7这 8个 值 是 独 立 的 ； 而且 ， 其 中 有 一 半 是 对 称 的 。 科 学 家 Cooley和 Tukey正 是 巧妙 地 利 用 这 些 特 性 加 快 了 DFT的 运 算 速 度 。周 期 性 ：对 称 性 ： 0mNNmN mNlNmN WW WW 2 第 4章 快 速 傅 里 叶 变 换 (FFT) 4.2.2 时 域 抽 取 法 基 2FFT基 本 原 理 设 序 列 x(n)的 长 度 N=2M

6、， M为 自 然 数 。 (1) 缩 短 DFT， 把 x(n)按 n的 奇 偶 顺 序 分 成 两 半 。 则 x(n)的 DFT为1 2( ) (2 ), 0,1, 12( ) (2 1), 0,1, 12Nx r x r r Nx r x r r 点有 N,)()( )()( )(,)()( )12()2()( 21 120 120 2221120 222120 2221 120 120 )12(2 kkXWkX WrxWWrx eWWrxWWrx WrxWrxkX k NNr Nr krNkNkrNNr krNjkrNNr krNkNkrN Nr Nr rkNkrN 第 4章 快 速

7、傅 里 叶 变 换 (FFT) (2) 重 组 DFT， 按 DFT的 定 义 重 新 组 合 变 短 的 DFT。 变短 后 的 DFT中 X1(k)和 X2(k)分 别 为 x1(r)和 x2(r)的 N/2点DFT， 周 期 为 N/2； 对 称 性 WNk+N/2 = WNk。 X(k)又可 表 示 为 经 过 这 两 步 骤 处 理 后 ， 1个 N点 的 DFT就 变 成 了 2个N/2点 的 DFT。 运 算 量 变 成 ：复 乘 (N/2) 2 2+(N/2)N2/2次 ，复 加 (N/2) (N/2-1) 2 +(N/2) 2=N2/2次 。比 原 来 多 了 还 是 少 了

8、 ？1 21 2( ) ( ) ( ) 0,1, 12( ) ( ) ( ) 0,1, 12 2kN kN NX k X k W X k kN NX k X k W X k k (4.2.7) (4.2.8) 第 4章 快 速 傅 里 叶 变 换 (FFT) C A B A BC A BC 将 式 (4.2.7)和 式 (4.2.8)用 流 图 符 号 表 示 ， 称 为 蝶 形 运 算 符号 。采 用 蝶 形 符 号 可 以 表 示 N=8 点 的 DFT运 算 ， 下 面 是 经 过 1次 分 解 的 DFT的 示 意 图 。注 意 ： 上 半 部 份 有 4点 ， 用 “ ” 的 公 式

9、 做 ； 下 半 部 份 有 4点 ， 用 “ ” 的 公 式 做 。 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.2.2 8点 DFT的 一 次 时 域 抽 取 分 解 图N/2点DFT WN0N/2点DFT W N1WN2WN3 x(0) X1(0) x(2) x(4) x(6) x(1) x(3) x(5) x(7) X1(1) X1(2) X1(3) X2(0) X2(1) X2(2) X2(3) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 第 4章 快 速 傅 里 叶 变 换 (FFT) 2次 分 解 x(n)的 DFT: (1) 缩

10、 短 x1(r)和 x2(r)的 DFT， 与 第 一 次 分 解 相 同 ， 将 x1(r)按 奇 偶 分 解 成 两 个 N/22长 的 子 序 列 x3(l)和 x4(l)， 即则 x1(r)的 DFT为 12,.,1,0,)12()( )2()( 214 13 Nllxlx lxlx (4.2.9) 点有 2N,)()( )()( )12()2()( 423 140 140 44243140 140 )12(212 211 kkXWkX WlxWWlx WlxWlxkX kNNl Nl klNkNklNNl Nl lkNklN 第 4章 快 速 傅 里 叶 变 换 (FFT) (2)重

11、 组 DFT， 按 DFT的 定 义 重 新 组 合 变 短 的 DFT。 变短 后 的 DFT中 X3(k)和 X4(k)分 别 为 x3(l)和 x4(l)的 N/4点 DFT，周 期 为 N/22； 对 称 性 WN/2k+N/4 = WN/2k。 X1(k)也 可表 示 为用 同 样 的 方 法 可 以 计 算 出如 果 是 8点 的 DFT， 经 两 次 分 解 ， DFT的 长 度 是 多 少 ？ 有几 个 这 种 长 度 的 DFT？ 1 3 /2 4 1 3 /2 4( ) ( ) ( ) , 0,1, , /4 1( /4) ( ) ( )kN kNX k X k W X k

12、 k NX k N X k W X k )()()4/( 4N,)()()( 6252 6252 kXWkXNkX kkXWkXkX kNkN 点有 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.2.3 8点 DFT的 第 二 次 时 域 抽 取 分 解 图N/4点DFT WN1 2WN1 2 WN0W N1WN2WN3X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3) X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0) X3(0)X3(1)X4(0)X4(1)x(4)x(2)x(6)x(1)x(5)x(3)x(7) N/4点DF

13、TN/4点DFTN/4点DFT WN0 2WN0 2 第 4章 快 速 傅 里 叶 变 换 (FFT) 3次 分 解 DFT， ， 长 度 为 N/23， 8点 DITFFT运 算 流 图 需 要 几 次 分 解 DFT， 才 会 使 DFT变 为 1点 的 DFT？W N0W N1W N2W N3W N0W N2W N0W N2W N0W N0W N0W N0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7) A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7) A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7) A(0)A(7) X(0)X(1)X

14、(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7) 第 4章 快 速 傅 里 叶 变 换 (FFT) 4.2.3 时 域 抽 取 法 快 速 傅 里 叶 变 换 的 运 算 量从 分 解 的 级 来 看 每 级 需 复 乘 N/2次 ， ？ 复 加 N次 ； ？ M=log2N级 需 复 乘 N/2 M次 ， ？ 复 加 N M次 。 ？对 于 复 乘 1次 需 50s， 复 加 1次 需 10s的 计 算 机 ， 现 在 做N=1024点 的 DFT运 算 。按 定 义 直 接 运 算 需 要 1024 2 50 10-6 1023

15、 1024 10 10-6=63(s)按 DIT-FFT运 算 需 要 512 10 50 10-6 1024 10 10 10-6=0.36(s) 它 们 的 速 度 相 差 63 0.36=175 （ 倍 ） ！ 第 4章 快 速 傅 里 叶 变 换 (FFT) 例 如 ： 分 析 序 列 x(n)=sin(1.8n)+cos(1.8n)的 频 谱 。clear,close all %用 两 种 方 法 计 算 DFTn=0:1023;w=1.8;x=sin(w*n)+cos(w*n);subplot(2,1,1),stem(n,x,.);%axis(250,350,-1.5,1.5)w=

16、linspace(0,2*pi,1024);tic;X1=x*exp(-j*n*w);toc;%时 间 约 1.36秒 ， 复 加 0.2微 秒tic;X2=fft(x);toc;%时 间 约 0秒subplot(2,1,2),plot(n,abs(X1),.,n,abs(X2),r); %axis(250,350,0,800);%算 出 角 频 率 1.798弧 度 第 4章 快 速 傅 里 叶 变 换 (FFT) 4.2.4 DITFFT的 运 算 规 律 及 编 程 思 想 1. 运 算 规 律 原 位 计 算从 蝶 形 来 看 这 种 运 算 的 好 处 ； 有 M级从 每 次 分 解

17、 DFT次 数 和 DFT变 短 的 规 律 来 看 ； 旋 转 因 子 ， L指 第 几 级 ， J是 序 号 ， 从 后 往 前 看 ； 各 级 蝶 形 的 点 距 ， 从 后 往 前 看 。 10 22 MJLW2 第 4章 快 速 傅 里 叶 变 换 (FFT) 2. 编 程 思 想 循 环 1 一 级 一 级 地 计 算 蝶 形 ， 给 出 每 个 蝶 的 两 点 距 离 2L-1； 循 环 2一 种 一 种 蝶 形 地 计 算 ， 给 出 旋 转 因 子 的 指 数 J， 每 级有 2L-1种 不 同 的 蝶 ；循 环 3 同 一 种 蝶 里 一 个 一 个 蝶 形 地 计 算 ，

18、 给 出 同 一 种 蝶 形 里 各蝶 形 的 间 隔 距 离 2 L。看 图 说 明 JLW2 第 4章 快 速 傅 里 叶 变 换 (FFT) 3. 程 序 框 图 图 4.2.6 DITFFT运 算 程 序 框 图 开 始 送 入 x(n)，M N2 M 倒 序 L1 , M 0 , B 1 P2 M LJ k J , N1 , 2L pNpN WBkXkXBkX WBkXkXkX )()()( )()()( 输 出 结 束 B 2 L1 第 4章 快 速 傅 里 叶 变 换 (FFT) 4. 倒 序 的 意 思 因 为 DIT-FFT是 对 x(n)的 序 列 按 偶 奇 不 断 地

19、分 解 ， 使得 N=2M的 序 号 按 2倍 不 断 地 变 短 ； 造 成 了 在 蝶 形 运 算 时的 输 入 信 号 排 列 顺 序 与 原 来 的 顺 序 不 一 样 。 所 以 倒 序 就 是 从 序 号 的 2进 制 的 低 位 向 高 位 不 断 地 把 0（ 代 表 偶 数 ） 和 1（ 代 表 奇 数 ） 分 开 。 图 4.2.7 N=23时 的 倒 序 图01010101 0101 01 (n2n1n0)2 000 04261537100010110001101011111 第 4章 快 速 傅 里 叶 变 换 (FFT) 表 4.2.1 顺 序 和 倒 序 二 进 制

20、 数 对 照 表 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.2.8 倒 序 规 律 x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7)A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7)x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.2.9 倒 序 程 序 框 图 221 NN LHJ NLH I1 , N1 I JTJA JXIA IXT )( )()( )

21、( J K LHK KJJ 2KK KJJ N N Y 第 4章 快 速 傅 里 叶 变 换 (FFT) 习 题 1和 2的 解clear;N=1024;A=N2,N*(N-1); N/2*log2(N),N*log2(N); N*log2(N)+N,2*N*log2(N)b=5e-6,1e-6;T=A*bf=N/T(3)/2 第 4章 快 速 傅 里 叶 变 换 (FFT) 4.2.5 频 域 抽 取 法 基 2FFT基 本 原 理 设 序 列 x(n)的 长 度 为 N=2M， M为 自 然 数 。 (1) 缩 短 DFT， 将 x(n)按 前 后 对 半 分 开 。 其 DFT可 表 示

22、 为如 下 形 式 ： 点有 N,)2()( )2()( )()( )()()( 120 2/120 120 )2/(120 1210 kWNnxWnx WNnxWnx WlxWnx WnxnxDFTkX Nn knNkNNNn Nn NnkNknNNn NNn knNknN Nn knN 第 4章 快 速 傅 里 叶 变 换 (FFT) （ 2） 重 组 DFT， 按 DFT的 定 义 重 新 组 合 变 短 的 DFT。 将X(k)分 解 成 偶 数 组 与 奇 数 组 ， 变 成 N/2点 的 DFT。当 k取 偶 数 时当 k取 奇 数 时 该 运 算 结 构 中 方 括 号 部 份

23、可 以 用 蝶 形 图 表 示点有 2N,)2()( )2()()12( 120 2120 )12( rWWNnxnx WNnxnxrX Nn rnNnNNn nrN 点有 2N,)2()( )2()()2( 120 2120 2 rWNnxnx WNnxnxrX Nn rnNNn rnN 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.2.10 DIFFFT蝶 形 运 算 流 图 符 号 采 用 蝶 形 符 号 可 以 表 示 N=8 点 的 DFT运 算 ， 下 面 是 经 过 1次 分 解 的 DFT的 示 意 图 。注 意 ： 上 半 部 份 有 4点 ， 用 “ ” 的 公

24、 式 做 ； 下 半 部 份 有 4点 ， 用 “ ” 的 公 式 做 。 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.2.11 N=8的 DIFFFT一 次 分 解 运 算 流 图N/2点DFTWN0 N/2点DFTW N1WN2WN3 X(0)x1(0) X(2)X(4)X(6)X(1)X(3)X(5)X(7)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7) 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.2.12 N=8的 DIFFFT二 次 分 解 运 算 流 图N/4点DFT

25、WN0W N1WN2WN3x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7) X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)WN0W N2W N0WN2 N/4点DFTN/4点DFTN/4点DFT 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.2.13 N=8的 DIFFFT运 算 流 图WN0W N1WN2WN3 WN0W N2WN0W N2 W N0W N0WN0WN0 X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7) 第 4章 快 速 傅 里 叶 变 换 (FFT)

26、 图 4.2.14 DITFFT的 一 种 变 形 运 算 流 图WN0 WN0W N2 W N0 X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7) WN0 W N2WN1WN3WN2WN0WN0W N0 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.2.15 DITFFT的 一 种 变 形 运算 流 图WN0 WN0WN2 WN0 X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7) WN0 W N2WN1WN3WN2WN0W

27、N0WN0 第 4章 快 速 傅 里 叶 变 换 (FFT) 4.2.6 IDFT的 快 速 算 法 方 法 1： 按 照 FFT的 方 法 编 造 IDFT的 快 速 算 法 程 序 。 那 么 将 产 生 时 域 抽 取 法 和 频 域 抽 取 法 两 种 。 好 处 是 ？ 坏 处 是 ？方 法 2： 利 用 FFT的 程 序 计 算 IDFT。 将 FFT中 的 WNkn改 为 WN-kn， 并 且 输 出 乘 上 1/N。 比 较 DFT和 IDFT的 运 算 公 式 就 明 白 ： 这 么 做 产 生 哪 两 种 方 法 ？ 好 处 是 ？ 坏 处 是 ？ 1010 )(1)()(

28、 )()()( Nk knNNn knN WkXNkXIDFTnx WnxnxDFTkX 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.2.16 是 DITIFFT运 算 流 图 。它 是 从 哪 种 FFT方 法 转 变 过 来 的 ？为 什 么 称 它 为 DITIFFT运 算 流 图 ？ WN0WN1W N2WN3 WN0W N0 N1 x(0)x(4)x(2)x(6) x(4) x(5) x(3) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) WN2WN2 N1N1 N1 N1 N1 N1 N1 第 4章 快 速 傅 里 叶 变

29、换 (FFT) 有 时 ， 为 了 防 止 运 算 过 程 中 发 生 溢 出 ， 将 1/N分 配到 每 一 级 的 蝶 形 运 算 中 。 下 图 是 DITIFFT 防 止 溢 出的 运 算 流 图 这 种 做 法 的 乘 法 次 数 比 前 面 的 增 加 次 。)1(2 MNW N02121 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7) 21 21 21 W N121 W N221 W N321 21 21 WN021W N221 21 21 WN021W N221 21W N021 21W N021

30、 21 21W N021WN021 第 4章 快 速 傅 里 叶 变 换 (FFT) 方 法 3： 先 对 X(k)取 共 轭 ， 然 后 直 接 利 用 FFT程 序 计 算 x*(n)， 最 后 输 出 再 取 共 轭 和 乘 上 1/N。 怎 么 知 道 呢 ？ 根 据 是 ， 对 某 序 列 两 次 取 共 轭 等 于 没 有 取 共 轭 。 好 处 是 ？ 坏 处 是 ？ )(1 )(1( )(1)( 101010Nk knNNk knNNk knNWkXN WkXN WkXNnx 第 4章 快 速 傅 里 叶 变 换 (FFT) 4.3 实 序 列 的 FFT算 法 1 直 接 利

31、 用 FFT程 序 。 好 处 是 ？ 坏 处 是 ？2 编 一 个 专 用 于 实 序 列 的 FFT程 序 。 好 处 是 ？ 坏 处 是 ？3 用 一 个 FFT程 序 算 两 个 实 序 列 的 FFT。 根 据 是 DFT的 共 轭 对 称 性 ： 若 x(n)=x 1(n)+jx2(n)， 则 X1(k)=X(k)+X*(N-k)/2 X2(k)= -jX(k)-X*(N-k)/2 好 处 是 ？ 坏 处 是 ？ 第 4章 快 速 傅 里 叶 变 换 (FFT) 4 用 一 个 N/2点 的 FFT程 序 算 一 个 N点 实 序 列 的 FFT 。 将 N点 实 序 列 x(n)

32、分 成 偶 数 点 和 奇 数 点 两 个 序 列 x1(r)和 x2(r) ， 然 后 造 出 一 个 N/2点 的 复 序 列 ， y(r)= x1(r)+jx2(r) ， r=0, 1, , (N/2-1) 对 y(r)利 用 N/2点 的 FFT程 序 可 以 算 出 Y(k)=DFTy(r)， k=0, 1, , (N/2-1) 这 时 ， 利 用 方 法 3得 X1(k)=Y(k)+Y*(N/2-k)/2 X2(k)= -jY(k)-Y*(N/2-k)/2 最 后 ， 利 用 时 域 抽 取 法 快 速 傅 里 叶 变 换 的 原 理 得 X(k)=X 1(k) +WNkX2(k)

33、， k=0, 1, , (N-1) 好 处 是 ？ 坏 处 是 ？ 第 4章 快 速 傅 里 叶 变 换 (FFT) 4.4 分 裂 基 FFT算 法 从 理 论 上 讲 ， 用 较 大 的 基 数 可 以 进 一 部 减 少 DFT的 运算 次 数 ， 但 要 使 程 序 变 得 更 复 杂 为 代 价 。分 裂 基 FFT算 法 原 理 是 这 样 ：它 和 基 2FFT的 基 本 原 理 大 体 相 同 ；不 同 的 是 分 裂 基 FFT的 做 法 是 把 N点 长 的 时 序 分 成 4段 ，再 按 基 2FFT的 频 域 抽 取 法 的 组 合 方 法 把 这 4段 变 成 1个(

34、N/2-1)长 的 DFT和 2个 (N/4-1)长 的 DFT。 第 4章 快 速 傅 里 叶 变 换 (FFT) /2 1 20 /4 1 40 /4 1 3 40(2 ) ( ) ( ) ,0 12 2 3(4 1) ( ) ( ) ( ) ( )4 2 40 14 3(4 3) ( ) ( ) ( ) ( )4 2 40 14N knNn N n knN NnN n knN Nn N NX k x n x n W kN N NX k x n jx n x n jx n W WNk N N NX k x n jx n x n jx n W WNk (4.4.2) 第 4章 快 速 傅 里

35、 叶 变 换 (FFT) 214 2 34( ) ( ) ( ), 0 12 2 3( ) ( ) ( ) ( ) ( )4 2 43( ) ( ) ( ) ( ) ( )4 2 40 14 nN nNN Nx n x n x n nN N Nx n x n jx n x n jx n WN N Nx n x n jx n x n jx n WNn (4.4.3) 令 第 4章 快 速 傅 里 叶 变 换 (FFT) 则 (4.4.2)式 可 写 成 如 下 更 简 明 的 形 式 ：/2 1 22 20 /4 1 1 4 1 4 40/4 1 2 4 24 40(2 ) ( ) ( ), 0

36、 12(4 1) ( ) ( ), 0 14(4 3) ( ) ( ), 0 14N knNn N knNnN knNn NX k x n W DFT x n k NX k x n W DFT x n k NX k x n W DFT x n k (4.4.4) 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.4.1 分 裂 基 第 一 次 分 解 L形 流 图 点 DFT 点 DFT 点 DFT x2(1) x2(1N/4) 2N 4N 4N)1(14x )1(24x1NW 3NW x(1) 41 Nx 21 Nx 431 Nx 1 1 1 j 第 4章 快 速 傅 里 叶 变 换

37、 (FFT) 例 如 ， N=16， 第 一 次 抽 选 分 解 时 ， 由 式 (4.4.3)得 x2(n)=x(n)+x(n+8), 0n7x14(n)= x(n)-x(n+8) -j x(n+4)-x(n+12) Wn16, 0n3x24(n)= x(n)-x(n+8) +j x(n+4)-x(n+12) W3n16, 0n3 把 上 式 代 入 式 (4.4.4)， 可 得 X(2k)=DFT x 2(n) , 0k7 X(4k+1)=DFT x14(n) , 0k3 X(4k+3)=DFT x24(n) , 0k3 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.4.2 分

38、 裂 基 FFT算 法 L形 排 列 示 意 图 与 结 构 示 意 图(a)分 裂 基 FFT算 法 L形 排 列 示 意 图 ；(b)分 裂 基 FFT算 法 运 算 流 图 结 构 示 意 图 ( a ) ( b ) 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.4.3 16点 分 裂 基 第 一 次 分 解 L形 流 图 (图 中 省 去 箭 头 ) (8)点DFT x2(0) x2(1) x2(2) x2(3) x2(4) x2(5) x2(6) x2(7) 点 DFT 点 DFT )0(14x )1(14x )2(14x )3(14x )0(24x )1(24x )2(

39、24x )3(2 4x 44 N 44 N 2Nx(0)x(1)x(2) x(3) x(4) x(5) x(6) x(7) x(8) x(9) x(10) x(11) x(12) x(13) x(14) x(15) 0NW1NW 3NW 2NW 0NW 3NW 6NW j j j X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X(8) X(9) X(10) X(11) X(12) X(13) X(14) X(15) X(2k) X(4k1) X(4k3) 1 1 1 1 1 1 1 1 1 1 第 4章 快 速 傅 里 叶 变 换 (FFT) 第 二 次 分

40、解 ： 先 对 图 4.4.3中 N/2点 DFT进 行 分 解 。 令 X1(l)=X(2l)， 则 有 X1(2l)=DFT y2(n) , 0l3 X1(4l+1)=DFT y14(n) , 0l1 X1(4l+3)=DFT y24(n) , 0l1 第 4章 快 速 傅 里 叶 变 换 (FFT) 其 中y2(n)=x2(n)+x2(n+4), 0n3y14(n)= x2(n)-x2(n+4) - x2(n+2)x(n+6) Wn8,n=0,1y24(n)= x2(n)-x2(n+4) +j x2(n+2)x2(n+6) W3n8,n=0,1 第 4章 快 速 傅 里 叶 变 换 (F

41、FT) 图 4.4.4 图 4.4.4中 N/2点 DFT的 分 解 L形 流 图 (4)点DFTx2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7) y2(0)y2(1)y2(2)y2(3) X1(0) X(0)X1(2) X(4)X1(4) X(8)X1(6) X(12)X1(1) X(2)X1(5) X(10)X1(3) X(6)X1(7) X(14) X1(2l)X1(4l1 )X1(4l3 )4N )0(14y )1(14y )1(24y )0(24y1 2NW3 2NW j j 11 111111 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4

42、.4.5 4点 分 裂 基 L形 运 算 流 图 v(0)v(1)v(2)v(3) V(0)V(2)V(1)V(3) j11 11 第 4章 快 速 傅 里 叶 变 换 (FFT) 图 4.4.6 16点 分 裂 基 FFT运 算 流 图 x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) x(8) x(9) x(10) x(11) x(12) x(13) x(14) x(15) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X(8) X(9) X(10) X(11) X(12) X(13) X(14) X(15) j 1 1 1

43、1 j j 1 1 1 1 j j 1 1 1 1 1 1 1 1 1 1 1 1 j j j j W 1 W 2 W 3 W 3 W 6 W 9 W 2 W 6 1 1 1 1 1 1 1 1 1 1 1 1 N N N N N N N N 第 4章 快 速 傅 里 叶 变 换 (FFT) 4.5 离 散 哈 特 莱 变 换 (DHT) 4.5.1 离 散 哈 特 莱 变 换 定 义 设 x(n),n=0,1,N-1， 为 一 实 序 列 ， 其 DHT定 义 为 10 2( ) ( ) ( )cos( ), 0,1, , 1NH nX k DHT x n x n kn k NN 式 中 ，

44、 cas()=cos+sin。 其 逆 变 换 (IDHT)为101 2( ) ( ) ( )cos( ), 0,1, , 1NH Hkx n IDHT X k X k kn n NN N (4.5.3) 第 4章 快 速 傅 里 叶 变 换 (FFT) 4.5.2 DHT与 DFT之 间 的 关 系x(n)的 DFT可 表 示 为同 理 ， x(n)的 DHT可 表 示 为XH(k)=ReX(k)-ImX(k) 1 1( ) ( ) ( ) ( ) ( )2 2H H H HX k X k X N k j X k X N k 第 4章 快 速 傅 里 叶 变 换 (FFT) 4.5.3 DH

45、T的 主 要 优 点 (1)DHT是 实 值 变 换 ， 在 对 实 信 号 或 实 数 据 进 行 谱分 析 时 避 免 了 复 数 运 算 ， 从 而 提 高 了 运 算 效 率 ， 相 应的 硬 件 也 更 简 单 、 更 经 济 ； (2)DHT的 正 、 反 变 换 (除 因 子 1/N外 )具 有 相 同 的 形式 ， 因 而 ， 实 现 DHT的 硬 件 或 软 件 既 能 进 行 DHT， 也能 进 行 IDHT； (3)DHT与 DFT间 的 关 系 简 单 ， 容 易 实 现 两 种 谱 之间 的 相 互 转 换 。 第 4章 快 速 傅 里 叶 变 换 (FFT) clf

46、;%双 音 频 信 号 的 检 测d=input(type in the telephone digit=,s);symbol=abs(d);tm=49,50,51,65;52,53,54,66;55,56,57,67;42,48,35,68;for p=1:4; for q=1:4; if tm(p,q)=abs(d);break,end end if tm(p,q)=abs(d);break,endendf1=697,770,852,941; f2=1209,1336,1477,1633;figure(1);n=0:204;x=sin(2*pi*n*f1(p)/8000)+sin(2*pi

47、*n*f2(q)/8000);subplot(2,1,1);stem(n,x,.);xlabel(n);X=fft(x); ylabel(双 音 频 信 号 );subplot(2,1,2);stem(n,abs(X),.);xlabel(k,w=2*pi*k/205(弧 度 ),f=8000*k/205(Hz);ylabel(按 键 对 应 双 音 频 信 号 的 频 谱 ); 第 4章 快 速 傅 里 叶 变 换 (FFT) k=18,20,22,24,31,34,38,42;val=zeros(1,8);for m=1:8; Fx(m)=X(k(m)+1);endfigure(2);va

48、l=abs(Fx);stem(k,val);grid;xlabel(k);limit=80; ylabel(|X(k)|);for s=5:8;if val(s)limit,break,endend for r=1:4;if val(r)limit,break,endenddisp(按 键 符 号 是 ,setstr(tm(r,s-4),) 第 4章 快 速 傅 里 叶 变 换 (FFT) Problems1 已 知 两 个 序 列 为 x1=0.95nR64(n)和 x2=sin(0.5n)R48(n)， 它们 的 卷 积 是 y=x1*x2。 求 直 接 计 算 方 法 和 快 速 圏 积 计 算方 法 的 运 算 量 。2 已 知 数 字 振 荡 器 的 采 样 频 率 是 2500Hz， 它 能 输 出 频 率为 150Hz， 375Hz， 620Hz或 850Hz的 正 弦 波 信 号 。 当接 收 到 该 振 荡 器 传 来 的 信 号 时 ， 采 用 DFT检 测 出 信 号的 频 率 。 请 确 定 DFT的 最 小 点 数 N 。