9.1 Direct Computation of the Discrete Fourier Transform The DFT pair was given as X∑meRx,XT个eR 0≤k,n≤W-1 DFTcomputational complexity: Each DFT coefficientrequires N complex multiplications; N-1 complex additions All N DFT coefficients require N2 complex multiplications; N(N-1)complex additions D4 9.1 Direct Computation of the Discrete Fourier Transform ◆The DFT pair was given as   ( ) 1 0 1 2 / [ ] N k j N kn x n X k N e  − =   =  ( ) 1 0 2 / [ ] , N n j N kn X k x n e  − = − = ◆DFTcomputational complexity: ◆Each DFT coefficient requires ◆N complex multiplications; ◆N-1 complex additions ◆All N DFT coefficients require ◆N2 complex multiplications; ◆N(N-1) complex additions 0 1   − k n, N