Decimation in Time
The DFT is defined by
![$\displaystyle X(k) = \sum_{n=0}^{N-1} x(n) W_N^{kn}, \quad k=0,1,2,\ldots,N-1,
$](http://www.dsprelated.com/josimages_new/mdft/img1624.png)
![$ x(n)$](http://www.dsprelated.com/josimages_new/mdft/img45.png)
![$ n$](http://www.dsprelated.com/josimages_new/mdft/img80.png)
![$\displaystyle W_N \isdef e^{-j\frac{2\pi}{N}}.\quad \hbox{(primitive $N$th root of unity)}
$](http://www.dsprelated.com/josimages_new/mdft/img1625.png)
![$ W_N^N=1$](http://www.dsprelated.com/josimages_new/mdft/img1626.png)
When is even, the DFT summation can be split into sums over the
odd and even indexes of the input signal:
where
![$ x_e(n)\isdef x(2n)$](http://www.dsprelated.com/josimages_new/mdft/img1634.png)
![$ x_o(n)\isdef x(2n+1)$](http://www.dsprelated.com/josimages_new/mdft/img1635.png)
![$ x$](http://www.dsprelated.com/josimages_new/mdft/img25.png)
![$ N$](http://www.dsprelated.com/josimages_new/mdft/img35.png)
![$ N/2$](http://www.dsprelated.com/josimages_new/mdft/img1293.png)
![$ W_N^k=e^{-j\omega_k}=\exp(-j2\pi k/N)$](http://www.dsprelated.com/josimages_new/mdft/img1636.png)
![$ X(\omega_k)$](http://www.dsprelated.com/josimages_new/mdft/img680.png)
![$ k$](http://www.dsprelated.com/josimages_new/mdft/img20.png)
Next Section:
Radix 2 FFT
Previous Section:
Coherence Function in Matlab
The DFT is defined by
When is even, the DFT summation can be split into sums over the
odd and even indexes of the input signal: