数 理 着考处 由式(742)及式(74.3)可知,A(k)及B(k)均是N/2点 的DFT,利用式(744)计算得到的只是X(k)前半部分的结果, 为了利用Ak)及B(k)表达整个的X(k)值,考虑到WM因子的周 期性,即W,=W+N2,则有 AN2+k)=∑x2)m21)=∑x(2r)W2=4k) 745) N/2-1 B(N2+k)=∑x2r+1)形m2=∑x(2r+1)WM=B(k)(746) 式(745)及式(74.6)表明,后半部分的A(N2+k)值及 B(N/2+k)值分别等于前半部分的所对应的A(k)值及B(k)值
2 ( 2) 2 2 21 21 (2) 2 2 0 0 7.4.2 7.4.3 ( ) ( ) 2 7.4.4 ( ) () () () ( 2 ) (2 ) (2 ) ( ) (7.4.5) ( 2 rk N rk r k N N N N N rN k rk N N r r Ak Bk N X k Ak Bk X k W W W AN k x rW x rW Ak B N + − − + = = = + = = = + ∑ ∑ DFT 由式（ ）及式（ ）可知， 及 均是 点 的 ，利用式（ ）计算得到的只是 前半部分的结果， 为了利用 及 表达整个的 值，考虑到 因子的周 期性，即 ，则有 2 1 2 1 (2) 2 2 0 0 ) (2 1) (2 1) ( ) (7.4.6) 7.4.5 7.4.6 ( 2 ) (2 ) () () N N rN k rk N N r r k x r W x r W Bk AN k BN k Ak Bk − − + = = = + = += + + ∑ ∑ 式（ ）及式（ ）表明，后半部分的 值及 值分别等于前半部分的所对应的 值及 值
数 理 着考处 考虑到的对称性,即 W(N/2+k)=WN/Wk=-Wk 74.7) 将式(74.5)至式(7.47)代入式(744),可得后半 部分的X(k)(k=N/2,…N-1)值,即 X(k+N/2)=A(k+N/2)+W2B(k+N2) A(k)-WNB(k) (748) 这样,若求出k∈[O,N/2-1]区间的所有A(k)值和B(k)值, 则可求出k∈[O,N-1间的(k)值,因此大大节省了运算。 N=8时,A(k),B(k)及X(k的关系,如图741所示,其中, 输出值X(0)到X(3)式(744)给出,输出值X(4到X(7) 由式(74.8)给出
(2) 2 2 (7.4.7) 7.4.5 7.4.7 7.4.4 ( )( 2, , 1) ( 2) ( 2) ( 2) ( ) ( ) (7.4.8) [0 2 1] ( Nk N k k N NN N k N N k N W WW W Xk k N N X k N Ak N W Bk N Ak W Bk k N A + + = =− = − + =+ + + = − ∈ − " 考虑到的对称性，即 将式（ ）至式（ ）代入式（ ），可得后半 部分的 值，即 这样，若求出 ， 区间的所有 ) () [0 1] ( ) 8 ( ) ( ) ( ) 7.4.1 (0) (3) 7.4.4 (4) (7) 7.4.8 k Bk k N Xk N Ak Bk X k X X X X ∈ − = 值和 值， 则可求出 ， 区间的 值，因此大大节省了运算。 时， ， 及 的关系，如图 所示，其中， 输出值 到 由式（ ）给出，输出值 到 由式（ ）给出
数 理 着考处 A(0) X(O A(1) x(2) 点 X(1) A(2) DFT X(2 x(6) A(3) X(3) (1) B(O) X(4) 点 X(5) B(2)W DFT X(6 乃(3) X(7) 图7.41N=8时A(k,B(k)及X(k)的关系图
数 理 着考处 由于N=2,因而N/2仍是偶数,可进一步按序号的奇 偶将每个N2点子序列分成两个点的N/4子序列,即令r=2l 及r=2l+1,l=0,1,2…,N4-1,则4(k)可表示为 k)=∑x(2r)WW2 2x4)m2+x4+2)m=2m =0 ∑x(4)W4+W2∑x(41+2)W(4 (74.9) =0 令C(k l k=0,1,2…,N/4 1=0 D(k)=∑x(4+2)4,k=0,2…,N/4-1(74) =0 则A(k)=X3(k)+W2X4(k),k=0,1,2,…,N4-1(7412)
2 1 2 0 4 1 4 1 2 (2 1) 2 2 0 0 4 1 4 2 0 2 2 2 42 2 1 0,1,2 4 1 ( ) ( ) (2 ) (4 ) (4 2) (4 ) (4 2) M N rk N r N N lk l k N N l l N lk k N N l N N r N Nr l r l l N Ak Ak x rW x lW x l W x lW W x l W − = − − + = = − = = = =+ = − = = ++ = ++ ∑ ∑ ∑ ∑ " 由于 ，因而 仍是偶数，可进一步按序号 的奇 偶将每个 点子序列分成两个点的 子序列，即令 及 ， ， ， ，则 可表示为 4 1 4 0 4 1 4 0 4 1 4 0 3 24 (7.4.9) ( ) (4 ) , 0,1,2, , 4 1 (7.4.10) ( ) (4 2) , 0,1,2, , 4 1 (7.4.11) ( ) ( ) ( ) , 0,1,2, , 4 1 (7.4.12) N lk N l N lk N l N lk N l k N Ck x lW k N Dk x l W k N Ak X k W X k k N − = − = − = = =− =+ = − =+ = − ∑ ∑ ∑ " " " 令 则
数 理 着考处 由式(74.10)及式(741)可知,C(k)及Dk)均是N/4点的DFT, 利用式(7412)计算得到的只是4(k)前半部分的结果,为了利用C(k) 及D(k)表达整个的A(k)值,考虑到因子W的周期性,即WA4=WA4 则有 C(N/4+k) x(4)4+) /4 (4)WM4=C(k (74.13) D(N4+k)=∑x(4+2A+=∑x(4+2Mk4=Dk)(7414) 式(7413)及式(7414)表明后半部分的C(N4+k)值及D(N/4+k) 值分别等于前半部分所对应的C(k)值及D(k)值
( 4) 4 4 4 4 1 4 1 (4) 4 4 0 0 7.4.10 7.4.11 ( ) ( ) 4 7.4.12 ( ) ( ) ( ) ( ) ( 4 ) (4 ) (4 ) ( ) (7.4.13) (4 ) lk k l k N N N N N N lN k lk N N l l Ck Dk N Ak Ck Dk Ak W W W C N k x lW x lW Ck DN k + − − + = = = + = = = + ∑ ∑ 由式（ ）及式（ ）可知， 及 均是 点的 ， DFT 利用式（ ）计算得到的只是 前半部分的结果，为了利用 及 表达整个的 值，考虑到因子 的周期性，即 ， 则有 4 1 4 1 (4) 4 4 0 0 (4 2) (4 2) ( ) (7.4.14) 7.4.13 7.4.14 , ( 4 ) ( 4 ) () () N N lN k lk N N l l x l W x l W Dk CN k DN k Ck Dk − − + = = = + = += + + ∑ ∑ 式（ ）及式（ ）表明 后半部分的 值及 值分别等于前半部分所对应的 值及 值