How to Interpret FFT results – complex DFT, frequency bins and FFTShift

1 Star2 Stars3 Stars4 Stars5 Stars (47 votes, average: 4.70 out of 5)
Loading...

Four types of Fourier Transforms:

Simulation of digital communication systems using Matlab

Often, one is confronted with the problem of converting a time domain signal to frequency domain and vice-versa. Fourier Transform is an excellent tool to achieve this conversion and is ubiquitously used in many applications. In signal processing , a time domain signal can be \(continuous\) or \(discrete\) and it can be \(aperiodic\) or \(periodic\). This gives rise to four types of Fourier transforms.

Table 1: Four types of Fourier Transform
TransformNature of time domain signalNature of frequency spectrum
Fourier Transform (FT),
(a.k.a Continuous Time Fourier Transform (CTFT))
continuous, non-periodicnon-periodic,continuous
Discrete-time Fourier Transform (DTFT)discrete, non-periodicperiodic,continuous
Fourier Series (FS)continuous, periodicnon-periodic, discrete
Discrete Fourier Transform (DFT)discrete, periodicperiodic,discrete

Note that when the signal is discrete in one domain, it will be periodic in other domain. Similarly, if the signal is continuous in one domain, it will be aperiodic (non-periodic) in another domain. For simplicity, let’s not venture into the specific equations for each of the transforms above. We will limit our discussion to DFT, that is widely available as part of software packages like Matlab, Scipy(python) etc.., however we can approximate other transforms using DFT.

Real version and Complex version:

For each of the listed transforms above, there exist a real version and complex version. The real version of the transform, takes in a real numbers and gives two sets of real frequency domain points – one set representing coefficients over \(cosine\) basis function and the other set representing the co-efficient over \(sine\) basis function. The complex version of the transforms represent positive and negative frequencies in a single array. The complex versions are flexible that it can process both complex valued signals and real valued signals. The following figure captures the difference between real DFT and complex DFT

realDFT_complexDFT
Figure 1: Real and complex DFT

Real DFT:

Consider the case of N-point \(real\) DFT , it takes in N  samples of \(real-valued\) time domain waveform \(x[n]\) and gives two arrays of length \(N/2+1\) each set projected on cosine and sine functions respectively.

$$\begin{align} X_{re}[k] &= \frac{2}{N} \sum_{n=0}^{N-1} \displaystyle x[n] cos\left( \frac{2 \pi k n}{N} \right)  \nonumber \\ X_{im}[k] &= -\frac{2}{N} \sum_{n=0}^{N-1} \displaystyle x[n] sin\left( \frac{2 \pi k n}{N} \right)  \nonumber \end{align}$$

Here, the time domain index \(n\) runs from \(0 \rightarrow  N\), the frequency domain index \(k\) runs from \(0 \rightarrow  N/2\)

The real-valued time domain signal \(x[n]\) can be synthesized from the real DFT pairs as

$$ x[n] =\sum_{k=0}^{N/2} \displaystyle X_{re}[K] cos\left( \frac{2 \pi k n}{N} \right)  –   X_{im}[K] sin\left( \frac{2 \pi k n}{N} \right)$$

Caveat: When using the synthesis equation, the values \(X_{re}[0]\) and \(X_{re}[N/2] \) must be divided by two. This problem is due to the fact that we restrict the analysis to real-values only. These type of problems can be avoided by using complex version of DFT.

Complex DFT:

Consider the case of N-point \(complex\) DFT, it takes in N samples of \(complex-valued\) time domain waveform \(x[n]\) and produces an array \(X[k]\) of length \(N\).

$$X[k]=\frac{1}{N} \sum_{n=0}^{N-1} x[n] e^{-j2 \pi k n/N}$$

The arrays values are interpreted as follows

  • \(X[0]\) represents DC frequency component
  • Next \(N/2\) terms are positive frequency components with \(X[N/2]\) being the Nyquist frequency (which is equal to half of sampling frequency)
  • Next \(N/2-1\) terms are negative frequency components (note: negative frequency components are the phasors rotating in opposite direction, they can be optionally omitted depending on the application)

The corresponding synthesis equation (reconstruct \(x[n]\) from frequency domain samples \(X[k]\)) is

$$x[n]=\sum_{k=0}^{N-1} X[k] e^{j2 \pi k n/N} $$

From these equations we can see that the real DFT is computed by projecting the signal on cosine and sine basis functions. However, the complex DFT projects the input signal on exponential basis functions (Euler’s formula connects these two concepts).

When the input signal in the time domain is real valued, the complex DFT zero-fills the imaginary part during computation (That’s its flexibility and avoids the caveat needed for real DFT). The following figure shows how to interpret the raw FFT results in Matlab that computes complex DFT. The specifics will be discussed next with an example.

complexDFT_Matlab_index
Figure 2: Interpretation of frequencies in complex DFT output

Fast Fourier Transform (FFT)

The FFT function in Matlab  is an algorithm published in 1965 by J.W.Cooley and J.W.Tuckey for efficiently calculating the DFT. It exploits the special structure of DFT when the signal length is a power of 2, when this happens, the computation complexity is significantly reduced.  FFT length is generally considered as power of 2 – this is called \(radix-2\) FFT which exploits the twiddle factors. The FFT length can be odd as used in this particular FFT implementation – Prime-factor FFT algorithm where the FFT length factors into two co-primes.

FFT is widely available in software packages like Matlab, Scipy etc.., FFT in Matlab/Scipy implements the complex version of DFT. Matlab’s FFT implementation computes the complex DFT that is very similar to above equations except for the scaling factor. For comparison, the Matlab’s FFT implementation computes the complex DFT and its inverse as

$$X[k]=\sum_{n=0}^{N-1} x[n] e^{-j2 \pi k n/N}$$
$$x[n]=\frac{1}{N}  \sum_{k=0}^{N-1} X[k] e^{j2 \pi k n/N} $$

The Matlab commands that implement the above equations are \(FFT\) and \(IFFT\) respectively. The corresponding syntax is as follows

Interpreting the FFT results

Lets assume that the \(x[n]\) is the time domain cosine signal of frequency \(f_c=10Hz\) that is sampled at a frequency \(f_s=32*fc\) for representing it in the computer memory.

fft_1
Figure 3: A 2 seconds record of 10 Hz cosine wave

Lets consider taking a \(N=256\) point FFT, which is the \(8^{th}\) power of \(2\).

Note: The FFT length should be sufficient to cover the entire length of the input signal. If \(N\) is less than the length of the input signal, the input signal will be truncated when computing the FFT. In our case, the cosine wave is of 2 seconds duration and it will have 640 points (a \(10Hz\) frequency wave sampled at 32 times oversampling factor will have \(2 \times 32 \times 10 = 640\) samples in 2 seconds of the record). Since our input signal is periodic, we can safely use \(N=256\) point FFT, anyways the FFT will extend the signal when computing the FFT (see additional topic on spectral leakage that explains this extension concept).

Due to Matlab’s index starting at 1, the DC component of the FFT decomposition is present at index 1.

That’s pretty easy. Note that the index for the raw FFT are integers from \(1 \rightarrow N\). We need to process it to convert these integers to \(frequencies\). That is where the \(sampling\) frequency counts.

Each point/bin in the FFT output array is spaced by the frequency resolution \(\Delta f\), that is calculated as
$$ \Delta f = \frac{f_s}{N} $$
where, \(f_s\) is the sampling frequency and \(N\) is the FFT size that is considered. Thus, for our example, each point in the array is spaced by the frequency resolution
$$ \Delta f = \frac{f_s}{N} = \frac{32*f_c}{256} = \frac{320}{256} = 1.25 Hz$$

Now, the \(10 Hz\) cosine signal will leave a spike at the 8th sample (10/1.25=8), which is located at index 9 (See next figure).

Therefore, from the frequency resolution, the entire frequency axis can be computed as

Now we can plot the absolute value of the FFT against frequencies as

The following plot shows the frequency axis and the sample index as it is for the complex FFT output.

fft_2
Figure 4: Magnitude response from FFT output plotted against sample index (top) and computed frequencies (bottom)

After the frequency axis is properly transformed with respect to the sampling frequency, we note that the cosine signal has registered a spike at \(10 Hz\). In addition to that, it has also registered a spike at \(256-8=248^{th}\) sample that belongs to negative frequency portion. Since we know the nature of the signal, we can optionally ignore the negative frequencies. The sample at the Nyquist frequency (\(f_s/2 \)) mark the boundary between the positive and negative frequencies.

Note that the complex numbers surrounding the Nyquist index are complex conjugates and they represent positive and negative frequencies respectively.

FFTShift

From the plot we see that the frequency axis starts with DC, followed by positive frequency terms which is in turn followed by the negative frequency terms. To introduce proper order in the x-axis, one can use \(FFTshift\) function Matlab, which arranges the frequencies in order: negative frequencies \(\rightarrow\) DC \(\rightarrow\) positive frequencies. The fftshift function need to be carefully used when \(N\) is odd.

For even N, the original order returned by FFT  is as follows (note: all indices below corresponds to Matlab’s index)

  • \(X[1]\) represents DC frequency component
  • \(X[2]\) to \(X[N/2]\) terms are positive frequency components
  • \(X[N/2+1]\) is the Nyquist frequency (\(F_s/2\)) that is common to both positive and negative frequencies. We will consider it as part of negative frequencies to have the same equivalence with the fftshift function.
  • \(X[N/2+1]\) to \(X[N]\) terms are considered as negative frequency components

FFTshift shifts the DC component to the center of the spectrum. It is important to remember that the Nyquist frequency at the (N/2+1)th Matlab index is common to both positive and negative frequency sides. FFTshift command puts the Nyquist frequency in the negative frequency side. This is captured in the following illustration.

FFTshift_Matlab_index
Figure 5: Role of FFTShift in ordering the frequencies

Therefore, when \(N\) is even, ordered frequency axis is set as
$$f = \Delta f \left[ -\frac{N}{2}:1:\frac{N}{2}-1 \right] = \frac{f_s}{N} \left[ -\frac{N}{2}:1:\frac{N}{2}-1 \right] $$

When \(N\) is odd, the ordered frequency axis should be set as
$$f = \Delta f \left[ -\frac{N+1}{2}:1:\frac{N+1}{2}-1 \right] = \frac{f_s}{N} \left[ -\frac{N+1}{2}:1:\frac{N+1}{2}-1 \right] $$

The following code snippet, computes the fftshift using both the manual method and using the Matlab’s in-build command. The results are plotted by superimposing them on each other. The plot shows that both the manual method and fftshift method are in good agreement.

fft_3
Figure 6: Magnitude response of FFT result after applying FFTShift : plotted against sample index (top) and against computed frequencies (bottom)

Comparing the bottom figures in the Figure 4 and Figure 6, we see that the ordered frequency axis is more meaningful to interpret.

IFFTShift

One can undo the effect of fftshift by employing \(ifftshift\) function. The \(ifftshift\) function restores the raw frequency order. If the FFT output is ordered using \(fftshift\) function, then one must restore the frequency components back to original order BEFORE taking \(IFFT\). Following statements are equivalent.

Some observations on FFTShift and IFFTShift

When \(N\) is odd and for an arbitrary sequence, the fftshift and ifftshift functions will produce different results. However, when they are used in tandem, it restores the original sequence.

When \(N\) is even and for an arbitrary sequence, the fftshift and ifftshift functions will produce the same result. When they are used in tandem, it restores the original sequence.

Rate this article: 1 Star2 Stars3 Stars4 Stars5 Stars (47 votes, average: 4.70 out of 5)

Loading...

Recommended Signal Processing Books

Articles in this series:
How to Interpret FFT results – complex DFT, frequency bins and FFTShift
How to Interpret FFT results – obtaining Magnitude and Phase information
FFT and Spectral Leakage
How to plot FFT using Matlab – FFT of basic signals : Sine and Cosine waves
Generating Basic signals – Square Wave and Power Spectral Density using FFT
Generating Basic signals – Rectangular Pulse and Power Spectral Density using FFT
Generating Basic Signals – Gaussian Pulse and Power Spectral Density using FFT
Chirp Signal – Frequency Sweeping – FFT and power spectral density
Constructing the Auto Correlation Matrix using FFT

  • Niraj Maddy

    Hii Mathuranathan….can u explain what is 50 percent overlapping in window function?

    • I would suggest you to take a look at the following research. It has lots of details on window function and optimizing them for spectral analysis.

      Spectrum and spectral density estimation by the Discrete Fourier transform (DFT), including a comprehensive list of window functions and some new at-top windows
      Authors: Heinzel, Gerhard; Rüdiger, Albrecht; Schilling, Roland
      Link: http://edoc.mpg.de/395068

  • michaelwfogle

    Very good article. I thought your treatment of the fftshift MATLAB function was good, but perhaps giving a brief example of a signal where the output of the complex FFT is not symmetric about DC would allow those new to signal processing to understand the “why” behind the fftshift function; an OFDM signal perhaps that is quadrature sampled? Perhaps this would muddy the elegance in the articles simplicity. Just a suggestion. Keep up the good work!

    • Thanks for your valuable feedback. I will try to incorporate your suggestions to further improve the article.

  • Feng Zhang

    Awsome!