Connexions

You are here: Home » Content » Spectrum Analysis Using the Discrete Fourier Transform
Content Actions

Spectrum Analysis Using the Discrete Fourier Transform

Module by: Douglas L. Jones

Summary: The discrete Fourier transform (DFT) maps a finite number of discrete time-domain samples to the same number of discrete Fourier-domain samples. Being practical to compute, it is the primary transform applied to real-world sampled data in digital signal processing. The DFT has special relationships with the discrete-time Fourier transform and the continuous-time Fourier transform that let it be used as a practical approximation of them through truncation and windowing of an infinite-length signal. Different window functions make various tradeoffs in the spectral distortions and artifacts introduced by DFT-based spectrum analysis.

Discrete-Time Fourier Transform

The Discrete-Time Fourier Transform (DTFT) is the primary theoretical tool for understanding the frequency content of a discrete-time (sampled) signal. The DTFT is defined as
Xω=n=-xn-ωn X ω n x n ω n (1)
The inverse DTFT (IDTFT) is defined by an integral formula, because it operates on a continuous-frequency DTFT spectrum:
xn=12π-ππXkωndω x n 1 2 ω X k ω n (2)
The DTFT is very useful for theory and analysis, but is not practical for numerically computing a spectrum digitally, because
  1. infinite time samples means
    • infinite computation
    • infinite delay
  2. The transform is continuous in the discrete-time frequency, ω
For practical computation of the frequency content of real-world signals, the Discrete Fourier Transform (DFT) is used.

Discrete Fourier Transform

The DFT transforms NN samples of a discrete-time signal to the same number of discrete frequency samples, and is defined as
Xk=n=0N-1xn-2πnkN X k n 0 N 1 x n 2 π n k N (3)
The DFT is invertible by the inverse discrete Fourier transform (IDFT):
xn=1Nk=0N-1Xk+2πnkN x n 1 N k N 1 0 X k 2 n k N (4)
The DFT and IDFT are a self-contained, one-to-one transform pair for a length-NN discrete-time signal. (That is, the DFT is not merely an approximation to the DTFT as discussed next.) However, the DFT is very often used as a practical approximation to the DTFT.

Relationships Between DFT and DTFT

DFT and Discrete Fourier Series

The DFT gives the discrete-time Fourier series coefficients of a periodic sequence ( xn=xn+N x n x n N ) of period NN samples, or
Xω=2πNXkδω-2πkN X ω 2 N X k δ ω 2 k N (5)
as can easily be confirmed by computing the inverse DTFT of the corresponding line spectrum:
xn=12π-ππ2πNXkδω-2πkNωndω=1Nk=0N-1Xk+2πnkN=IDFTXk=xn x n 1 2 ω 2 N X k δ ω 2 k N ω n 1 N k N 1 0 X k 2 n k N IDFT X k x n (6)
The DFT can thus be used to exactly compute the relative values of the NN line spectral components of the DTFT of any periodic discrete-time sequence with an integer-length period.

DFT and DTFT of finite-length data

When a discrete-time sequence happens to equal zero for all samples except for those between 00 and N-1N1, the infinite sum in the DTFT equation becomes the same as the finite sum from 00 to N-1N1 in the DFT equation. By matching the arguments in the exponential terms, we observe that the DFT values exactly equal the DTFT for specific DTFT frequencies ω k =2πkN ω k 2 k N . That is, the DFT computes exact samples of the DTFT at NN equally spaced frequencies ω k =2πkN ω k 2 k N , or
X ω k =2πkN=n=-xn- ω k n=n=0N-1xn-2πnkN=Xk X ω k 2 k N n x n ω k n n 0 N 1 x n 2 π n k N X k

DFT as a DTFT approximation

In most cases, the signal is neither exactly periodic nor truly of finite length; in such cases, the DFT of a finite block of NN consecutive discrete-time samples does not exactly equal samples of the DTFT at specific frequencies. Instead, the DFT gives frequency samples of a windowed (truncated) DTFT X ^ ω k =2πkN=n=0N-1xn- ω k n=n=-xnwn- ω k n=Xk X ^ ω k 2 k N n N 1 0 x n ω k n n x n w n ω k n X k where wn=1if0n<N0ifelse w n 1 0 n N 0 else Once again, Xk X k exactly equals X ω k X ω k a DTFT frequency sample only when n,n0N-1:xn=0 n n 0 N 1 x n 0

Relationship between continuous-time FT and DFT

The goal of spectrum analysis is often to determine the frequency content of an analog (continuous-time) signal; very often, as in most modern spectrum analyzers, this is actually accomplished by sampling the analog signal, windowing (truncating) the data, and computing and plotting the magnitude of its DFT. It is thus essential to relate the DFT frequency samples back to the original analog frequency. Assuming that the analog signal is bandlimited and the sampling frequency exceeds twice that limit so that no frequency aliasing occurs, the relationship between the continuous-time Fourier frequency ΩΩ (in radians) and the DTFT frequency ωω imposed by sampling is ω=ΩT ω Ω T where TT is the sampling period. Through the relationship ω k =2πkN ω k 2 k N between the DTFT frequency ωω and the DFT frequency index kk, the correspondence between the DFT frequency index and the original analog frequency can be found: Ω=2πkNT Ω 2 k N T or in terms of analog frequency ff in Hertz (cycles per second rather than radians) f=kNT f k N T for kk in the range kk between 00 and N2 N 2 . It is important to note that k N2+1N-1 k N 2 1 N 1 correspond to negative frequencies due to the periodicity of the DTFT and the DFT.
Problem 1
In general, will DFT frequency values Xk X k exactly equal samples of the analog Fourier transform X a X a at the corresponding frequencies? That is, will Xk= X a 2πkNT X k X a 2 k N T ?
[ Click for Solution 1 ]
Solution 1
In general, NO. The DTFT exactly corresponds to the continuous-time Fourier transform only when the signal is bandlimited and sampled at more than twice its highest frequency. The DFT frequency values exactly correspond to frequency samples of the DTFT only when the discrete-time signal is time-limited. However, a bandlimited continuous-time signal cannot be time-limited, so in general these conditions cannot both be satisfied.
It can, however, be true for a small class of analog signals which are not time-limited but happen to exactly equal zero at all sample times outside of the interval n 0N-1 n 0 N 1 . The sinc function with a bandwidth equal to the Nyquist frequency and centered at t=0 t 0 is an example.
[ Hide Solution 1 ]

Zero-Padding

If more than NN equally spaced frequency samples of a length-NN signal are desired, they can easily be obtained by zero-padding the discrete-time signal and computing a DFT of the longer length. In particular, if LN LN DTFT samples are desired of a length-NN sequence, one can compute the length- LN LN DFT of a length- LN LN zero-padded sequence zn=xnif0nN-10ifNnLN-1 z n x n 0 n N 1 0 N n L N 1 X w k =2πkLN=n=0N-1xn-2πknLN=n=0LN-1zn-2πknLN= DFT L N zn X w k 2 k L N n N 1 0 x n 2 k n L N n L N 1 0 z n 2 k n L N DFT L N z n Note that zero-padding interpolates the spectrum. One should always zero-pad (by about at least a factor of 4) when using the DFT to approximate the DTFT to get a clear picture of the DTFT. While performing computations on zeros may at first seem inefficient, using FFT algorithms, which generally expect the same number of input and output samples, actually makes this approach very efficient.
Figure 1 shows the magnitude of the DFT values corresponding to the non-negative frequencies of a real-valued length-64 DFT of a length-64 signal, both in a "stem" format to emphasize the discrete nature of the DFT frequency samples, and as a line plot to emphasize its use as an approximation to the continuous-in-frequency DTFT. From this figure, it appears that the signal has a single dominant frequency component.
Spectrum without zero-padding
Stem plotzpstem64.png
Subfigure 1.1
Line Plotzpline64.png
Subfigure 1.2
Figure 1: Magnitude DFT spectrum of 64 samples of a signal with a length-64 DFT (no zero padding)
Zero-padding by a factor of two by appending 64 zero values to the signal and computing a length-128 DFT yields Figure 2. It can now be seen that the signal consists of at least two narrowband frequency components; the gap between them fell between DFT samples in Figure 1, resulting in a misleading picture of the signal's spectral content. This is sometimes called the picket-fence effect, and is a result of insufficient sampling in frequency. While zero-padding by a factor of two has revealed more structure, it is unclear whether the peak magnitudes are reliably rendered, and the jagged linear interpolation in the line graph does not yet reflect the smooth, continuously-differentiable spectrum of the DTFT of a finite-length truncated signal. Errors in the apparent peak magnitude due to insufficient frequency sampling is sometimes referred to as scalloping loss.
Spectrum with factor-of-two zero-padding
Stem plotzpstem128.png
Subfigure 2.1
Line Plotzpline128.png
Subfigure 2.2
Figure 2: Magnitude DFT spectrum of 64 samples of a signal with a length-128 DFT (double-length zero-padding)
Zero-padding to four times the length of the signal, as shown in Figure 3, clearly shows the spectral structure and reveals that the magnitude of the two spectral lines are nearly identical. The line graph is still a bit rough and the peak magnitudes and frequencies may not be precisely captured, but the spectral characteristics of the truncated signal are now clear.
Spectrum with factor-of-four zero-padding
Stem plotzpstem256.png
Subfigure 3.1
Line Plotzpline256.png
Subfigure 3.2
Figure 3: Magnitude DFT spectrum of 64 samples of a signal with a length-256 zero-padded DFT (four times zero-padding)
Zero-padding to a length of 1024, as shown in Figure 4 yields a spectrum that is smooth and continuous to the resolution of the computer screen, and produces a very accurate rendition of the DTFT of the truncated signal.
Spectrum with factor-of-sixteen zero-padding
Stem plotzpstem1024.png
Subfigure 4.1
Line Plotzpline1024.png
Subfigure 4.2
Figure 4: Magnitude DFT spectrum of 64 samples of a signal with a length-1024 zero-padded DFT. The spectrum now looks smooth and continuous and reveals all the structure of the DTFT of a truncated signal.
The signal used in this example actually consisted of two pure sinusoids of equal magnitude. The slight difference in magnitude of the two dominant peaks, the breadth of the peaks, and the sinc-like lesser side lobe peaks throughout frequency are artifacts of the truncation, or windowing, process used to practically approximate the DFT. These problems and partial solutions to them are discussed in the following section.

Effects of Windowing

Applying the DTFT multiplication property X ω k ̂=n=-xnwn- ω k n=12πX ω k *W ω k X ω k n x n w n ω k n 1 2 X ω k W ω k we find that the DFT of the windowed (truncated) signal produces samples not of the true (desired) DTFT spectrum Xω X ω , but of a smoothed verson Xω*Wω X ω W ω . We want this to resemble Xω X ω as closely as possible, so Wω W ω should be as close to an impulse as possible. The window wn w n need not be a simple truncation (or rectangle, or boxcar) window; other shapes can also be used as long as they limit the sequence to at most NN consecutive nonzero samples. All good windows are impulse-like, and represent various tradeoffs between three criteria:
  1. main lobe width: (limits resolution of closely-spaced peaks of equal height)
  2. height of first sidelobe: (limits ability to see a small peak near a big peak)
  3. slope of sidelobe drop-off: (limits ability to see small peaks further away from a big peak)
Many different window functions have been developed for truncating and shaping a length-NN signal segment for spectral analysis. The simple truncation window has a periodic sinc DTFT, as shown in Figure 5. It has the narrowest main-lobe width, 2πN 2 N at the -3 dB level and 4πN 4 N between the two zeros surrounding the main lobe, of the common window functions, but also the largest side-lobe peak, at about -13 dB. The side-lobes also taper off relatively slowly.
Rectangular windowboxcar64.png
Subfigure 5.1
Magnitude of boxcar window spectrumboxcarfreq.png
Subfigure 5.2
Figure 5: Length-64 truncation (boxcar) window and its magnitude DFT spectrum
The Hann window (sometimes also called the hanning window), illustrated in Figure 6, takes the form wn=0.5-0.5cos2πnN-1 w n 0.5 0.5 2 n N 1 for nn between 00 and N-1 N 1 . It has a main-lobe width (about 3πN 3 N at the -3 dB level and 8πN 8 N between the two zeros surrounding the main lobe) considerably larger than the rectangular window, but the largest side-lobe peak is much lower, at about -31.5 dB. The side-lobes also taper off much faster. For a given length, this window is worse than the boxcar window at separating closely-spaced spectral components of similar magnitude, but better for identifying smaller-magnitude components at a greater distance from the larger components.
Hann windowhann64.png
Subfigure 6.1
Magnitude of Hann window spectrumhannfreq.png
Subfigure 6.2
Figure 6: Length-64 Hann window and its magnitude DFT spectrum
The Hamming window, illustrated in Figure 7, has a form similar to the Hann window but with slightly different constants: wn=0.538-0.462cos2πnN-1 w n 0.538 0.462 2 n N 1 for nn between 00 and N-1 N 1 . Since it is composed of the same Fourier series harmonics as the Hann window, it has a similar main-lobe width (a bit less than 3πN 3 N at the -3 dB level and 8πN 8 N between the two zeros surrounding the main lobe), but the largest side-lobe peak is much lower, at about -42.5 dB. However, the side-lobes also taper off much more slowly than with the Hann window. For a given length, the Hamming window is better than the Hann (and of course the boxcar) windows at separating a small component relatively near to a large component, but worse than the Hann for identifying very small components at considerable frequency separation. Due to their shape and form, the Hann and Hamming windows are also known as raised-cosine windows.
Hamming windowhamming64.png
Subfigure 7.1
Magnitude of Hamming window spectrumhammingfreq.png
Subfigure 7.2
Figure 7: Length-64 Hamming window and its magnitude DFT spectrum
Note: Standard even-length windows are symmetric around a point halfway between the window samples N2-1 N 2 1 and N2 N 2 . For some applications such as time-frequency analysis, it may be important to align the window perfectly to a sample. In such cases, a DFT-symmetric window that is symmetric around the N2 N 2 -th sample can be used. For example, the DFT-symmetric Hamming window is wn=0.538-0.462cos2πnN w n 0.538 0.462 2 n N . A DFT-symmetric window has a purely real-valued DFT and DTFT. DFT-symmetric versions of windows, such as the Hamming and Hann windows, composed of few discrete Fourier series terms of period NN, have few non-zero DFT terms (only when not zero-padded) and can be used efficiently in running FFTs.
The main-lobe width of a window is an inverse function of the window-length N N; for any type of window, a longer window will always provide better resolution.
Many other windows exist that make various other tradeoffs between main-lobe width, height of largest side-lobe, and side-lobe rolloff rate. The Kaiser window family, based on a modified Bessel function, has an adjustable parameter that allows the user to tune the tradeoff over a continuous range. The Kaiser window has near-optimal time-frequency resolution and is widely used. A list of many different windows can be found here.
Example 1 
Figure 8 shows 64 samples of a real-valued signal composed of several sinusoids of various frequencies and amplitudes.
examplesig.png
Figure 8: 64 samples of an unknown signal
Figure 9 shows the magnitude (in dB) of the positive frequencies of a length-1024 zero-padded DFT of this signal (that is, using a simple truncation, or rectangular, window).
boxcarspec.png
Figure 9: Magnitude (in dB) of the zero-padded DFT spectrum of the signal in Figure 8 using a simple length-64 rectangular window
From this spectrum, it is clear that the signal has two large, nearby frequency components with frequencies near 1 radian of essentially the same magnitude.
Figure 10 shows the spectral estimate produced using a length-64 Hamming window applied to the same signal shown in Figure 8.
hammingspec.png
Figure 10: Magnitude (in dB) of the zero-padded DFT spectrum of the signal in Figure 8 using a length-64 Hamming window
The two large spectral peaks can no longer be resolved; they blur into a single broad peak due to the reduced spectral resolution of the broader main lobe of the Hamming window. However, the lower side-lobes reveal a third component at a frequency of about 0.7 radians at about 35 dB lower magnitude than the larger components. This component was entirely buried under the side-lobes when the rectangular window was used, but now stands out well above the much lower nearby side-lobes of the Hamming window.
Figure 11 shows the spectral estimate produced using a length-64 Hann window applied to the same signal shown in Figure 8.
hannspec.png
Figure 11: Magnitude (in dB) of the zero-padded DFT spectrum of the signal in Figure 8 using a length-64 Hann window
The two large components again merge into a single peak, and the smaller component observed with the Hamming window is largely lost under the higher nearby side-lobes of the Hann window. However, due to the much faster side-lobe rolloff of the Hann window's spectrum, a fourth component at a frequency of about 2.5 radians with a magnitude about 65 dB below that of the main peaks is now clearly visible.
This example illustrates that no single window is best for all spectrum analyses. The best window depends on the nature of the signal, and different windows may be better for different components of the same signal. A skilled spectrum analysist may apply several different windows to a signal to gain a fuller understanding of the data.

Comments, questions, feedback, criticisms?

Send feedback