Skip to content Skip to navigation

Connexions

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

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

In these lenses

  • Lens for Engineering

    This module is included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.
 

Spectrum Analysis Using the Discrete Fourier Transform

Module by: Douglas L. Jones. E-mail the author

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 =−∞∞x⁢n⁢e−(i⁢ω⁢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:
x⁢n=12⁢π⁢∫−ππX⁢k⁢ei⁢ω⁢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

X⁢k=∑ n =0N−1x⁢n⁢e−i⁢2⁢π⁢n⁢kN X k n 0 N 1 x n 2 π n k N
(3)
The DFT is invertible by the inverse discrete Fourier transform (IDFT):
x⁢n=1N⁢∑ k =0N−1X⁢k⁢ei⁢2⁢π⁢n⁢kN 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 ( x⁢n=x⁢n+N x n x n N ) of period NN samples, or

X⁢ω=2⁢πN⁢∑X⁢k⁢δ⁢ω−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:

x⁢n=12⁢π⁢∫−ππ(2⁢πN⁢∑X⁢k⁢δ⁢ω−2⁢π⁢kN)⁢ei⁢ω⁢nd ω =1N⁢∑ k =0N−1X⁢k⁢ei⁢2⁢π⁢n⁢kN=IDFT⁢X⁢k=x⁢n 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 =−∞∞x⁢n⁢e−(i⁢ ω k ⁢n)=∑ n =0N−1x⁢n⁢e−i⁢2⁢π⁢n⁢kN=X⁢k 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−1x⁢n⁢e−(i⁢ ω k ⁢n)=∑ n =−∞∞x⁢n⁢w⁢n⁢e−(i⁢ ω k ⁢n)=X⁢k X ^ ω k 2 k N n N 1 0 x n ω k n n ∞ ∞ x n w n ω k n X k where w⁢n={1  if  0≤n<N0  if  else w n 1 0 n N 0 else Once again, X⁢k X k exactly equals X⁢ ω k X ω k a DTFT frequency sample only when ∀ n ,n∉ 0 N−1 :x⁢n=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⁢π⁢kN⁢T Ω 2 k N T or in terms of analog frequency ff in Hertz (cycles per second rather than radians) f=kN⁢T f k N T for kk in the range kk between 00 and N2 N 2 . It is important to note that k∈ N2+1 N−1 k N 2 1 N 1 correspond to negative frequencies due to the periodicity of the DTFT and the DFT.

Exercise 1

In general, will DFT frequency values X⁢k X k exactly equal samples of the analog Fourier transform X a X a at the corresponding frequencies? That is, will X⁢k= X a ⁢2⁢π⁢kN⁢T X k X a 2 k N T ?

Solution

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∈ 0 N−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.

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 L⁢N LN DTFT samples are desired of a length-NN sequence, one can compute the length- L⁢N LN DFT of a length- L⁢N LN zero-padded sequence z⁢n={x⁢n  if  0≤n≤N−10  if  N≤n≤L⁢N−1 z n x n 0 n N 1 0 N n L N 1 X⁢ w k =2⁢π⁢kL⁢N=∑ n =0N−1x⁢n⁢e−(i⁢2⁢π⁢k⁢nL⁢N)=∑ n =0L⁢N−1z⁢n⁢e−(i⁢2⁢π⁢k⁢nL⁢N)= DFT L N ⁢z⁢n 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.

Figure 1: Magnitude DFT spectrum of 64 samples of a signal with a length-64 DFT (no zero padding)
Spectrum without zero-padding
Stem plot
(a)
Stem plot (zpstem64.png)
Line Plot
(b)
Line Plot (zpline64.png)
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.
Figure 2: Magnitude DFT spectrum of 64 samples of a signal with a length-128 DFT (double-length zero-padding)
Spectrum with factor-of-two zero-padding
Stem plot
(a)
Stem plot (zpstem128.png)
Line Plot
(b)
Line Plot (zpline128.png)
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.
Figure 3: Magnitude DFT spectrum of 64 samples of a signal with a length-256 zero-padded DFT (four times zero-padding)
Spectrum with factor-of-four zero-padding
Stem plot
(a)
Stem plot (zpstem256.png)
Line Plot
(b)
Line Plot (zpline256.png)
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.
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.
Spectrum with factor-of-sixteen zero-padding
Stem plot
(a)
Stem plot (zpstem1024.png)
Line Plot
(b)
Line Plot (zpline1024.png)
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 =−∞∞x⁢n⁢w⁢n⁢e−(i⁢ ω 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 w⁢n 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.

Figure 5: Length-64 truncation (boxcar) window and its magnitude DFT spectrum
Rectangular window
(a)
Rectangular window (boxcar64.png)
Magnitude of boxcar window spectrum
(b)
Magnitude of boxcar window spectrum (boxcarfreq.png)

The Hann window (sometimes also called the hanning window), illustrated in Figure 6, takes the form w⁢n=0.5−0.5⁢cos2⁢π⁢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.

Figure 6: Length-64 Hann window and its magnitude DFT spectrum
Hann window
(a)
Hann window (hann64.png)
Magnitude of Hann window spectrum
(b)
Magnitude of Hann window spectrum (hannfreq.png)

The Hamming window, illustrated in Figure 7, has a form similar to the Hann window but with slightly different constants: w⁢n=0.538−0.462⁢cos2⁢π⁢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.

Figure 7: Length-64 Hamming window and its magnitude DFT spectrum
Hamming window
(a)
Hamming window (hamming64.png)
Magnitude of Hamming window spectrum
(b)
Magnitude of Hamming window spectrum (hammingfreq.png)

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 w⁢n=0.538−0.462⁢cos2⁢π⁢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.

Figure 8: 64 samples of an unknown signal
(examplesig.png)
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).
Figure 9: Magnitude (in dB) of the zero-padded DFT spectrum of the signal in Figure 8 using a simple length-64 rectangular window
(boxcarspec.png)
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.

Figure 10: Magnitude (in dB) of the zero-padded DFT spectrum of the signal in Figure 8 using a length-64 Hamming window
(hammingspec.png)
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.

Figure 11: Magnitude (in dB) of the zero-padded DFT spectrum of the signal in Figure 8 using a length-64 Hann window
(hannspec.png)
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.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks