啊
1 第四章 FFT---DFT的快速算法
要煦长水 之V Z寸 新水 实本 之
2 §1 FFT 算法的基本思想 ∑ − = = 1 0 ) ( ) ( : N n kn N W n x k X DFT 1 0 − ≤ ≤ N k Nj N e W π2 − = 1、直接计算DFT存在的问题： 设 x(n) 为复数 对每个k，计算 X(k)，共需N次复乘及N-1次复加。 N个k，则共需 N2 次复乘及N(N-1)次复加。 4N2 次实乘及 2N(2N-1)次实加
之 进煥 之 之 之 之 R水沉≤糕 三田采 之 之 鸭
3 如N=1024 复乘次数约为100万次。 2、提高DFT的运算效率的途径 kn N W （1）利用 的对称性 ∗ − − = = ) ( ) ( kn N kn N n N k N W W W k N N N k N N k N W W W W − = ⋅ = + 2 2 ( ) ( ∗) − − = = kn N kn N n k N N W W W
之 乙?乙 新氓≤餐尔长实
4 的周期性 ） kn N W 2 （ n N k N N n k N kn N W W W ) ( ) ( + + = = k N k N W W 2 2 = 2 2 k N k N W W = 1 2/ −= NN W 1 = N N W (3) 将大点数DFT分解成小点数DFT
+C 的什NZ←图餐尔 三+ 盛密 之 鲥丫1 密实 E囚
5 §2 时域抽取基—2 FFT算法 ) 2 ( — 基 一、算法原理： γ2 = N 思想：将 x(n) 在时域按序号n的奇偶性分成两个N/2点子序列， 然后再计算DFT. + == ) 1 2( ) ( ) 2( ) (12 r x r x r x r x 设 1 2 0 − ≤ ≤ N r ∑ ∑ ∑ − = + − = − = + + = = 1 2 0 ) 1 2( 1 2 0 2 1 0 ) 1 2( ) 2( ) ( ) ( N r k r N N r rk N N n nk N W r x Wr x Wn x k X 则 ∑ ∑ − = − = ⋅ + = 1 2 0 2 2 1 2 0 2 1 ) ( ) ( N r k N rk N N r rk N W Wr x Wr x