× 之 十 十
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