9.2 Decimation-in-Time FFT Algorithms Makes use of periodicity and symmetry ofW Consider special case of N=2v:integer v power of 2 Separatexn]into two sequences of length N/2 Even-numbered sequence N:Length of x[n] Odd-numbered sequences. N-point DFT X[k-∑nke/NKn ejexlN)=W n=( =∑n]W+∑]W收 n even n odd 1414 9.2 Decimation-in-Time FFT Algorithms ◆Makes use of periodicity and symmetry of ◆Consider special case of N=2ν : integer ν power of 2 ◆Separate x[n] into two sequences of length N/2 ◆Even-numbered sequence ; ◆Odd-numbered sequences .   ( ) 1 0 2 / [ ] , N n j kn N X k x n e  − = − = n even [ ] kn = +  x nWN =WN j(2 /N) e −  kn WN n odd [ ] kn x nWN N: Length of x[n] N-point DFT