9.1 Direct Computation of the Discrete Fourier Transform Most fast methods are based on Periodicity properties Periodicity of W in n and k; ej2z/N)kn_e-j(2z/N)k(n+N)-e j(2zlN)(k+N)n W农=WN+m=W+m, e2πN=W Complex conjugate symmetry W收N-w=W-()*, (WN-）*-(W）*=WW ej2π/Nk(N-m=ej2m/N)kNe-j(2π/Wk(m三e/2π/WMkm (e2x1M）( ) n N Wk N− 5 9.1 Direct Computation of the Discrete Fourier Transform ◆Most fast methods are based on Periodicity properties ◆Periodicity of in n and k; j(2 /N k N n ) ( ) e −  − j(2 / 2 / N)kn k j( N) (n N) e e − −   + = ( ) ( ) , kn N N k k n n W W W N N N + + = = ( ) ( )* ( )* N N N N W W W k k k −n n − n = = ◆Complex conjugate symmetry j(2 /N)(k n N) e −  + = j(2 /N) e WN −  = j(2 /N k) n e  = ( )*, kn = WN j(2 / 2 / N k )kN N n j( ) ( ) e e − −   − = kn WN − = ( ) ( ) 2 / * = j N nk e −  n N Wk