DFT的快速算法【有戈泽尔算法】.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：0.78M 资料格式：pdf 举报版权申诉

55a26a1b-8eb5-44ff-acec-912720c471f7.pdf-第1页.png

第1页 / 共56页

55a26a1b-8eb5-44ff-acec-912720c471f7.pdf-第2页.png

第2页 / 共56页

55a26a1b-8eb5-44ff-acec-912720c471f7.pdf-第3页.png

第3页 / 共56页

55a26a1b-8eb5-44ff-acec-912720c471f7.pdf-第4页.png

第4页 / 共56页

55a26a1b-8eb5-44ff-acec-912720c471f7.pdf-第5页.png

第5页 / 共56页

55a26a1b-8eb5-44ff-acec-912720c471f7.pdf-第6页.png

第6页 / 共56页

55a26a1b-8eb5-44ff-acec-912720c471f7.pdf-第7页.png

第7页 / 共56页

55a26a1b-8eb5-44ff-acec-912720c471f7.pdf-第8页.png

第8页 / 共56页

文本预览

第1章 DFT的快速算法 1. 1 FFT算法（基于抽选） 1．1．1 基2FFT：DIT和DIF 1．1．2 混合基（包括任意基）FFT 1．1．3 分裂基（组合基，SRFFT） 1．2 GOERTZEL（戈泽尔）算法适用于计算部分X[k]，是直接法的一半运算量 1．3 CHIRPZ（线性调频）变换算法（CTA，CZT）适用于任意个X[k]，任意频率点开始，任意频域取样间隔

第1章 DFT的快速算法 X k [ ] = x n W [ ] kn N 0 ≤ ≤ k N − 1 x n [ ] = X k W − N [ ] kn 0 ≤ ≤ n N − 1 kn N / − j n ω = = e e | ω π = 2 k N / , k N / j n ω | ω π = 2 N k 1 0,..., , − = N k 1 0,..., − = （4实乘+2实加）（2实加） N 1 − 0 N = ∑ n 1 N j 2 − π k 1 − ∑ = 0 j 2 π kn N / W kn N W − N e = e kn = 直接计算运算量：复数乘法：N2 复数加法：N（N-1）实数乘法：4N2 实数加法：4N2-2N

1.1 FFT算法（基于抽选） 1.1.1 基2FFT：DIT和DIF 1.1.1 1.DIT N = 2m 第一次分解 kn N 0 ≤ k N ≤ − 1 则 X k [ ] = g m W [ ] h m W [ ] km N / 2 = G k W H k [ ] [ ] + k N G[k]和H[k]长度为N/2，所以X[k]分成两段表示 X k [ ] X k [ + G k W H k [ ], 0 = N W ] ] + 2 / 2 1 − N ] + 2 k N ≤ H k [ / 2 G k W H k + G k [ ≤ k N + N [ ] = k N + N 2 [ ] k N − = [ ], 0 ≤ k N ≤ / 2 1 − X k [ ] = x n W [ ] 1 − N ∑ n N 0 = / 2 1 − = ∑ m 0 = g m ] [ = 令 h m [ ] = x m W [2 ] k m 2 N + N / 2 1 − ∑ m = 0 x m W [2 1] + + 1) k m (2 N m N ≤ ≤ ≤ m N / 2 1 − / 2 1 − x m [2 ] x m [2 + N / 2 1 − 1] ∑ m = 0 0 km N / 2 + W ≤ 0 N k N / 2 1 − ∑ m = 0

x m [2 ], 0 x m [2 + ≤ 1], 0 m N ≤ ≤ ≤ m N = = g m [ ] h m [ ] 第一次分解后流图 / 2 1 − / 2 1 − X k [ ] = X k [ + [ ] ] = [ ], 0 k N + ≤ ≤ G k W H k [ ], 0 ≤ G k W H k N 2 k N [ ] k N − / 2 1 − k N ≤ / 2 1 − x[0] x[2] x[4] x[6] x[1] x[3] x[5] x[7] N/2 点 DFT N/2 点 DFT G[0] G[1] G[2] G[3] H[0] 0 WN H[1] 1 WN H[2] 2 WN H[3] 3 WN X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7] -1 -1 -1 -1

第二次分解 h m W [ ] , k = 0,..., N / 2 1 − N / 2 1 − ∑ m = 0 + ) 1 ] km N / 2 0 ≤ m N ≤ ≤ 0 / 4 1 − m N ≤ / 4 1 − N / 2 1 − G k [ ] = , g m W [ ∑ H k [ ] ] km = N / 2 m 0 = ) ( ( ) x m g m [2 ] 2 [ 2 ] = ⋅ ) ( ( x m g m 1 ] 2 [2 [ 2 ⋅ = + ) ) ( ( x m h m 2 [2 [ 2 ] = ⋅ + ) ( ( m h m x [2 1 ] 2 [ 2 + ⋅ = G k W G k [ ] [ ] + k N / 2 1 2 令 g m [ ] 1 g m [ ] 2 = = h m ] [ = 1 h m ] [ = 2 G k [ ] 则 = N 4 = G k [ + H k [ ] H k [ + ] = G k W G k [ ] [ ] − k N / 2 1 2 1 / 2 + k N [ ] H k W H k [ ] N 4 H k W H k [ ] [ ] k N = − ] / 2 1 2 2 1] 1 + ) + 1] 0 0 ≤ ≤ m N / 4 1 − ≤ m N 0 ≤ ≤ k N / 4 1 − ≤ / 4 1 − 0 ≤ k N ≤ / 4 1 − 0 ≤ k N ≤ / 4 1 − 0 ≤ k N ≤ / 4 1 −

g m ] 1 g m ] 2 [ [ = = g m [2 ], 0 g m [2 + ≤ 1], 0 第二次分解后信号流图 m N / 4 1 ≤ − m N / 4 1 − ≤ ≤ G k [ ] [ ] = + 1 G k [ 2 / 2 k N G k W G k N ] + 4 G[0] [ ] k N = / 2 1 [ ], 0 ≤ k N ≤ / 4 1 − G k W G k [ ], 0 − ≤ k N ≤ / 4 1 − 2 X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7] -1 -1 -1 -1 x[0] x[4] x[2] x[6] x[1] x[5] x[3] x[7] N/4point DFT N/4point DFT N/4point DFT N/4point DFT G1[0] G1[1] G2[0] 0 WN G2[1] 2 WN H1[0] H1[0] G[1] G[2] G[3] -1 -1 H[0] 0 WN H[1] 1 WN H2[0] 0 WN H[2] 2 WN -1 H2[0] 2 WN H[3] 3 WN -1

完全分解后完整流图（N=8） DFT G k 0 [ ] [ ] g n W 1 kn 2 = : 1 ∴ G 1 [0] = g 1 [0] + G 1 [1] = g 1 [0] − g 1 [1] 2 点 ≤ k ≤ 1 1 ∑ 0 = g [1], n 1

复乘次数：次蝶形 ( 1 / 复加次数：次蝶形 ( 2 / 蝶形级 / 运算量 N 2 ⎛ ⎜ ⎝ N 2 蝶形级 / ⎞ ⎟ ⎠ ( * log ⎞ ⎟ ⎠ ) * ⎛ ⎜ ⎝ * ) N 级 ) = 2 N 2 log 2 N ( * log N ) 级 = N 2 log 2 N

分享到：

赞收藏

资料库

DFT的快速算法【有戈泽尔算法】.pdf

相关推荐

课程资源

热门标签

最新资料