- The Discrete Fourier Transform (DFT)
is given by:

- The operation of the DFT can be reversed to recover a time-domain signal from its frequency representation. This is done with the Inverse Discrete Fourier Transform (IDFT).
- The IDFT is given by:

- The DFT specifies the relationship between a time-domain signal and its frequency-domain representation.
- Many general relationships between these two representations can be derived from Eq. (1).
- For example, if a time-domain signal
*x*[*n*] is time-shifted by an amount (resulting in a signal ), its frequency-domain representation is simply multiplied by a phase shift term of :

= = =

- This result is referred to as the ``Shift Theorem'', given by a corresponding ``transform pair'':

(3) - Note that the phase shift term has unity magnitude ( ) and so, a time-shift produces no change in the magnitude response of the corresponding frequency-domain representation.

- Convolution is the operation ``performed'' by digital filters. We can say that the filter convolves an input signal
*x*[*n*] with its impulse response*h*[*n*] to produce an output*y*[*n*]. - Convolution is described mathematically as:

(4) - Convolution can be interpreted as a sample-by-sample multiplication and sum of the signal
*x*[*n*] and a time ''flipped'' and delayed version of the signal*h*[*n*]. - We can derive the time/frequency transform pair for the convolution process as follows:

= = *X*[*k*]*H*[*k*]

- We have just derived the very important result that convolution in the time domain corresponds to multiplication in the frequency domain:

(5) - For long signal lengths (
*N*> 100 or so), it is much faster to transform signals with the FFT (and IFFT) and to perform the convolution as a frequency-domain multiplication.

- We have already noted the trade-off between time- and frequency-resolution using the DFT. Larger DFT sizes provide better spectral resolution but less time-resolution and vice-versa.
- It turns out that we can add zeros to the end of a signal in order to achieve a longer DFT length without modifying the spectral content of the signal. Because the zero-padded signal is longer (though no new energy has been added), the resulting DFT provides better frequency resolution.
- For example, a length
*N*=1024 DFT provides a frequency resolution of 43 Hertz at a sample rate of 44.1 kHz. If we add*N*more zeros to the signal and perform a length 2048 DFT, we double the frequency resolution (to 21.5 Hz). - Stated another way, zero-padding in the time-domain results in interpolation in the frequency-domain.
- Figure 1 illustrates the effect of zero padding on the resulting DFT.

©2004-2017 McGill University. All Rights Reserved. Maintained by Gary P. Scavone. |