2.3.6 Fast Fourier transform FFT With the substitution of variables n=2r for n even and n=2r+I for n odd H(k)=∑x(2那3+∑x2r+)WNk =∑x(2)w3y+W∑x(2r+1)Wy (2.237) r=0 r=0 But W=W∠ since W2=e-j(2m/N) e2(M/2)With the substitution of variables n=2r for n even and n=2r+1 for n odd, But since 2.3.6 Fast Fourier transform (FFT) ( ) ( ) ( ) ( )  ( )( )  ( )( )   − = − = − = − = + = + + = + + 1 2 2 1 2 2 1 2 1 2 2 2 1 2 2 1 2 2 1 N r o r k N N r o k N r k N N r o N r o r N r k N x r W W x r W X k x r W x r W k (2.237) 2 2 WN =WN ( ) ( ) 2 2 2 2 2 N j N j N WN = e = e =W −  − 