Indexing and shifting of Discrete Fourier Transform

Contents
Introduction
In the previous section we got equations for the direct discrete Fourier transform (DFT) and inverse DFT (IDFT):
 (1)
(1)
Calculating the DFT and IDFT is carried out on the basis of temporal and frequency sample indexes without frequency sampling.
Thus, it is possible to use the DFT and IDFT in case of any sampling frequency without changing the computing procedure.
In this section we will consider how to assign the DFT indexes to frequency values , stated in Hertz, or to values of the angular frequency rad/s.
Indexing of DFT spectrum samples
Upon considering the DFT we said that the spectrum of the discrete signal , , is a periodic function with the period rad/s where is the samplerate (Hz) of a pickup signal .
Respectively the repetition period of the spectrum of the discrete signal , , for the frequency , stated in Hertz, is equal to the sampling frequency Hz.
The DFT is got by sampling of the periodic function in one repetition period with the step :
 (2)
(2)
Thus, the -th spectrum sample corresponds to the frequency
 (3)
(3)
or
 (4)
(4)
Example 1. Under the sampling frequency , under , the first spectrum sample corresponds to the frequency .
Example 2. Under the sampling frequency , under , the spectrum sample with the number , corresponds to the frequency .
DFT shifting
Let the input signal , , be a complex one and consist of one complex exponent with the frequency Hz:
 (5)
(5)
Set the sampling frequency which is equal to Hz and take pickup signal samples.
Calculate the DFT , , of this signal and get the amplitude spectrum as it is shown in Figure 1.
Figure 1. Amplitude signal spectrum
As it is possible to note in Figure 1, there is only one component with the index that corresponds to the frequency according to (4) in the signal spectrum
 (6)
(6)
that can seem strange because we set the pickup signal frequency Hz.
However there is nothing special in it if we remember that the spectrum of our discrete signal is the periodic function with the period Hz, i.e. for our discrete signal the spectrum consists of the infinite number of harmonicas with frequencies , , as it is shown in Figure 2.
Figure 2. Periodic spectrum of the signal
The figure shows that when the spectrum sampling in one repetition period is from 0 to Hz (in Figure 2 it is set as the DFT period) the periodic harmonica with 100 Hz frequency occurs in the sample capture. At the same time the spectrum in the frequency range from Hz to Hz periodically repeats the spectrum in the frequency range from Hz to Hz.
Thus, we can perform the DFT shifting for the signal spectrum analysis in the range of frequencies from to Hz.
Let’s state an important remark. The frequency component corresponding to the frequency Hz in view of the discrete signal spectrum periodicity also corresponds to the frequency Hz. Upon shifting we will refer this component to the frequency Hz.
DFT shifting for even
Under even the spectrum sample corresponds to the frequency Hz in accordance with (4). As we noted above, the same sample corresponds to the frequency Hz. hen it is possible to write the spectrum after shifting for even as follows:
 (7)
(7)
The -th spectrum sample after shifting corresponds to the frequency
 (8)
(8)
or
 (9)
(9)
Thus, the sample corresponds to the frequency Hz, the sample corresponds to the frequency Hz and the sample corresponds to the frequency Hz.
DFT shifting for even is shown in Figure 3.

Figure 3. DFT shifting for even
DFT shifting for odd
Under odd the spectrum sample corresponds to the frequency Hz in accordance with (4), and the spectrum sample corresponds to the frequency Hz.
The spectrum after shifting for odd :
 (10)
(10)
The spectrum sample after shifting corresponds to the frequency
 (11)
(11)
or
 (12)
(12)
After DFT shifting under odd , the spectrum sample corresponds to the frequency Hz in accordance with (12), the spectrum sample corresponds to the frequency Hz and the last sample corresponds to the frequency Hz.
DFT shifting for odd is shown in Figure 4.

Figure 4. DFT shifting for odd
DFT shifting example
Perform DFT shifting for correct presenting negative frequencies for the example given above (Figure 1).
The number of samples in the given example is , therefore we can use (7) for getting . Then after shifting spectrum samples will correspond to frequencies (9).
In Figure 4 there is given the amplitude spectrum after shifting and frequency values (Hz). Spectrum samples correspond to this frequency .
Figure 5. Amplitude spectrum
after shifting and corresponding
frequency values
As it is possible to see in Figure 5, after shifting of spectrum samples the component corresponds to the frequency Hz that we set for the pickup signal.
Conclusions
In this section we considered the question of indexing and shifting of spectrum samples in the DFT output.
The equations for DFT shifting for even and odd for correct presenting negative frequencies after the DFT were given.
The DFT properties will be considered in more detail in the following sections.
Reference
[1] Bracewell R.N. The Fourier Transform and its Applications. McGraw Hill, 2000.

[2] Oppenheim Alan V. and Schafer Ronald W. Discrete-Time Signal Processing. Second Edition. Prentice-Hall, New Jersey, 1999.

[3] Robert J. Marks II The Joy of Fourier: Analysis, Sampling Theory, Systems, Multidimensions, Stochastic Processes, Random Variables, Signal Recovery, Pocs, Time Scales, & Applications. Baylor University, 2006.

[4] Nussbaumer Henri J. Fast Fourier Transform and Convolution Algorithms. Second Corrected and Updated Edition. Springer-Verlag, 1982.
Appendix
                
# -*- coding: utf-8 -*-
"""
Images 1 and 4 data calculation script.
DFT frequency indexation and shifting
@author: Sergey Bakhurin
www.dsplib.org
"""
import numpy as np

# DFT size
N = 30

# Signal frequency Hz
f0 = -20.0

# Sample-rate Hz
Fs = 120.0

n = np.linspace(0, N, N, endpoint = False, dtype = 'float64')
f = n / N * Fs

# Input signal
s = np.exp(2j * np.pi * n * f0 / Fs)

# DFT
S = np.abs(np.fft.fft(s))

# DFT shifting
S_sh = np.fft.fftshift( S )
f_sh = f - Fs/2.0

# Save data to files for plotting
np.savetxt('dat/dft_freq_fig1.txt', np.transpose([n, S]))
np.savetxt('dat/dft_freq_fig4.txt', np.transpose([n, S_sh]))

# Data plotting.
# Please uncomment this block if you want to plot data.
"""
import matplotlib.pyplot as plt

plt.figure(1)
plt.stem(f, np.abs(S))
plt.xlabel('f, Hz')
plt.ylabel('|S(f)|')

plt.figure(2)
plt.stem(f_sh, np.abs(S_sh))
plt.xlabel('fsh, Hz')
plt.ylabel('|Ssh(fsh)|')

plt.show()

"""