computational complexity X[k=G[k+Hk ◆TwoN/2-point DFTs 2(N/2)2 complex multiplications eactly2-l） 2(N/2)2 complex additions xo一 W G[1川 x2I0→ Combining the DFT outputs 2-point WN G[2] x[4]0→ DFT w G[3] 4 N complex multiplications x句o→ w x[1]o→ X[4] 6 ◆N complex additions HIO] x[3]o+ X[5 2-point H1] Total complexity N=8 N=210 DFT H2] 40N2/+N complex multiplicati H 40N2/2+N complex additions. xactly:2+- More efficient than direct DFT when N>2 19◆Two N/2-point DFTs ◆2(N/2)2 complex multiplications 18 computational complexity ◆Combining the DFT outputs ◆N complex multiplications ◆N complex additions ◆Total complexity ◆N2/2+N complex multiplications ◆N2/2+N complex additions. ◆More efficient than direct DFT when N>2 ◆2(N/2)2 complex additions ( ) 2 exactly: 2 1 2 2 2 N N N − + = N exactly: 2 1 ( ) 2 2 N N −       k X k G k W H k N = + N-point DFT computational complexity: ; N=8 40 64 56 40 N=210 32