啊
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
× 之 十 十
6 ∑ ∑ − = − = + = 1 2 0 2 2 1 2 0 2 1 ) ( ) ( N r rk N k N N r rk N Wr x W Wr x ) ( ) ( 2 1 k X W k X k N + = 1 0 − ≤ ≤ N k X1(k),X2(k)分别为偶数号序列和奇数号序列的N/2点 DFT,其周期均为N/2. = + = + ) ( ) 2 ( ) ( ) 2 ( 2 2 1 1 k X N k X k X N k X k N N k N W W − = + 2 Q又
之 。丑e 之 × 乙 田叵水
7 上式又可写为 ∴ − = + ⋅ + = ) ( ) ( ) 2 ( ) ( ) ( ) ( 2 1 2 1 k X W k X N k X k X W k X k X k N k N 1 2 0 − ≤ ≤ N k 这样N点X(k)，可由两个N/2点DFT求出。上述算 法可用蝶形运算表示： ) (1 k X ) (2 k X k N W ) ( ) ( 2 1 k X W k X k N + ) (k X ) 2 ( N k X + ) ( ) ( 2 1 k X W k X k N −
尽以以以 4 最
8 那么求一个N点DFT的流图可如下实现(以N=8为例）： ) 0( ) 0(1 x x = ) 2( ) 1(1 x x = ) 4( ) 2(1 x x = ) 6( ) 3(1 x x = ) 1( ) 0(2 x x = ) 3( ) 1(2 x x = ) 5( ) 2(2 x x = ) 7( ) 3(2 x x = ) 0( X ) 1( X ) 2( X ) 3( X ) 4( X ) 5( X ) 6( X ) 7( X ) 0(1 X ) 1(1 X ) 2(1 X ) 3(1 X ) 0(2 X ) 1(2 X ) 2(2 X ) 3(2 X 0 N W 1 N W 2 N W 3 N W DFT N 点2/ DFT N 点2/
Q 之"三 十 之"… 段 段 尔啊鲥 鲥← 嶇z←图 上之鲥
9 运算量分析： N/2次复乘 1次复乘 每个蝶形运算 N/2个蝶形： N次复加 2次复加 而两个N/2点DFT:共需 ) 1 2 ( ) 1 2 ( 2 2 − = − × N N N N 次复乘， 2 ) 2 ( 2 2 2 N N = × 次复加 = + − ≈ + = + 2 ) 1 2 ( 2 2 ) 1 ( 2 2 2 2 2 N N N N N N N N N 复乘： 复加： 分解一次后，共需 =≈ 22 NN 复加： 复乘： 而直接运算N点DFT需：
之 之 汁1细锔嘔鲥Ⅳ瞄尔1的品 版过z←图餐尔尿尔令×× 十 十 尔繁 小
10 即经过一次分解，运算量就节省一半。 继续分解： 将 X1(k)、X2(k)分别分解成两个N/4点子序列的DFT。 + == ) 1 2( ) ( ) 2( ) ( 1 4 1 3 l x l x l x l x 令： 1 4 0 − ≤ ≤ N l 则有 ∑ ∑ − = + − = + + = 1 4 0 ) 1 2( 2 1 1 4 0 2 2 1 1 ) 1 2( ) 2( ) ( N l k l N N l lk N W l x Wl x k X ∑ ∑ − = − = + = 1 4 0 4 4 2 1 4 0 4 3 ) ( ) ( N l lk N k N N l lk N Wl x W Wl x 1 2 0 − ≤ ≤ N k