implementing the DFT go by the generic name of fast Fourier transforms FFTs . This chapter describes the DFT and its properties, and its relationship to DTFT.
2. Definition of DFT and its Inverse Lest us consider a discrete time signal x n having a finite duration, say in the range 0 n N-1. The DTFT of the signal is N-1 X
-jwn x n e
n-0 Let us sample X using a total of N equally spaced samples in the range 0,2 , sampling interval is 2 That is, we sample X using the frequencies. N k 2 k , 0 k N-1. N-1 -jwn Thus X k x n e n-0
- j2 kn x n e N
The result is, by definition the DFT. That is ,