2.3.6 Fast Fourier transform FFT 1. Decimation-in-Time FFt algorithms Assuming: N=2M separating x(n)into two N/2-point sequence consisting of the even-numbered points in x(n) and the odd-numbered points in x(n). With X(k) given by X(k)=∑x(n)x,k=01…N then X(k)=∑x(nx+∑xn)W n old1. Decimation-in-Time FFT Algorithms Assuming: separating x(n) into two N/2-point sequence consisting of the even-numbered points in x(n) and the odd-numbered points in x(n). With X(k) given by then 2.3.6 Fast Fourier transform (FFT) M N = 2 ( ) ( ) , 0,1, 1 1 0 =  = − − = X k x n W k N N n n k N  ( ) =  ( ) +  ( ) n old nk N n even nk X k x n WN x n W