The Discrete Fourier Transform (DFT)

The DFT is the Fourier Transform we will use all the time !!
The DFT is defined over a finite number N of samples and the DFT itself is a discrete sequence (not a continuous variable).
The DFT definition :

So the DFT has the same number of elements as the time series from which it is calculated.
k is a frequency index and we will see below how k corresponds to frequency in Hertz in the case of a sampled analogue signal.

The inverse transform (IDFT) :

We use the familiar transform pair notation .

Note that the factor that appears in the DFT definition represents a complex exponential that rotates clockwise in the complex plane with an angular velocity of radians/sample .

Some interesting properties of the DFT (and the DTFT)

1. While the DTFT exists for an indefinite continuous range of digital frequencies , the DFT is generated by a finite sum and is defined for a finite set of frequency values (equal to the number of time domain sample values).
2. The DFT X(k) is periodic in k with period N . If we compute X(k) for values of k outside the range the resulting values of X(k) simply repeat the values within the interval .
3. The IDFT representation of x(n) is periodic in n with period N . If we use the IDFT to calculate x(n) for values of n outside the range the x(n) would simply repeat the values from within the interval . Thus from the DFT point of view, x(n) is but one period of a periodic sequence :

   

   We normally restrict ourselves to the case m=0 .

4. The X(k) derived from the DFT are the values that would be obtained by sampling the continuous function DTFT at values of

Example

Find the DFT of the sequence x(0)=1,x(1)=2,x(2)=3,x(3)=4 (N=4)

Note that X(0) will always be just the sum of the samples in the sequence. It is the zero frequency or `DC' term.

Similarly and .
When X(k) is written in the form then and are interpreted as the amplitude and phase respectively of the frequency component indexed k .

DFT using MATLAB

In MATLAB a DFT is computed with the function fft

%  Solution of the previous example with MATLAB
m=[0 1 2 3];  % vector of time samples
xn=[1 2 3 4]; % x(n) vector
Xk=fft(xn);   % call fft to get X(k)
%
% Convert X(k) to get the amplitude and phase
Xmag=abs(X(k);
Xphase=angle(Xk);
%

Note on MATLAB fft

MATLAB fft uses a Fast Fourier Transform algorithm to compute the DFT.
FFT is a computationally efficient method of computing a DFT.
In a straightforward computation of a DFT of N samples the number of computational operations . FFT methods require a number of operations which is for large N.
(See S&K pp562-566 for a discussion of the principle of FFT algorithms)

The difference between typical applications of z-transforms and DFT

The typical application of z-transforms is to the solution of difference equations (DE's). We do the z-transform in to the complex plane (z-domain), we do some algebraic manipulation and finally return to the time domain via the inverse z-transform. The complex variable z itself has no particular physical significance (though particular values of z such as poles of the transfer function do).
The typical application of DFT is to spectral analysis. Note again that a DFT is still a transform in to the z-plane but with z restricted to the unit circle . But now the values of have a particular physical significance - frequency . In spectral analysis we typically do the transform in to the z-plane and never return.