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):
$$S(k) = \sum_{n=0}^{N-1} s(n) \cdot \exp \left( -j \cdot \frac{2\pi}{N} \cdot n \cdot k \right),\text{ } k=0 \ldots N-1;$$ $$s(n) = \frac{1}{N} \cdot \sum_{k=0}^{N-1} S(k) \cdot \exp \left( j \cdot \frac{2\pi}{N} \cdot n \cdot k\right), \text{ } n=0 \ldots N-1.$$
(1)
Calculating the DFT and IDFT is carried out on the basis of temporal $n=0 \ldots N-1$ and frequency $k = 0 \ldots N-1$ 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 $f$, stated in Hertz, or to values of the angular frequency $\omega = 2 \pi \cdot f$ rad/s.
Indexing of DFT spectrum samples
Upon considering the DFT we said that the spectrum $S(\omega)$ of the discrete signal $s(n)$, $n = 0 \ldots N-1$, is a periodic function with the period $\Omega_{\textrm{max}} = 2 \pi \cdot F_{\textrm{s}}$ rad/s where $F_{\textrm{s}}$ is the samplerate (Hz) of a pickup signal $s(n)$ .
Respectively the repetition period of the spectrum $S(f)$ of the discrete signal $s(n)$, $n = 0 \ldots N-1$, for the frequency $f$, stated in Hertz, is equal to the sampling frequency $F_{\textrm{max}} = F_{\textrm{s}}$ Hz.
The DFT is got by sampling of the periodic function $S(\omega)$ in one repetition period with the step $\Delta \omega$:
$$\Delta \omega = \frac{\Omega_{\textrm{max}}}{N} = 2 \pi \cdot \frac{F_{\textrm{s}}}{N} \textrm{, rad/s}.$$
(2)
Thus, the $k$-th spectrum sample $S(k)$ corresponds to the frequency
$$\omega(k) = k \cdot \Delta \omega = 2 \pi \cdot \frac{F_{\textrm{s}}}{N} \cdot k \textrm{, rad/s},$$
(3)
or
$$f(k) = k \cdot \Delta f = \frac{F_{\textrm{s}}}{N} \cdot k \textrm{, Hz}.$$
(4)
Example 1. Under the sampling frequency $F_{\text{s}} = 120 \text{ kHz}$, under $N = 1024$, the first spectrum sample $S(0)$ corresponds to the frequency $f = \frac{0}{1024} \cdot 120 = 0 \text{ Hz}$.
Example 2. Under the sampling frequency $F_{\text{s}} = 120 \text{ kHz}$, under $N = 1024$, the spectrum sample with the number $k = 128$, $S(128)$ corresponds to the frequency $f = \frac{128}{1024} \cdot 120 = 15 \text{ kHz}$.
DFT shifting
Figure 1. Amplitude signal spectrum $s(n)$
Let the input signal $s(n)$, $n = 0 \ldots N-1$, be a complex one and consist of one complex exponent with the frequency $f_0 = -20$ Hz:
$$s(n) = \exp\left( j \cdot 2\pi \cdot n \cdot \frac{f_0}{F_{\textrm{s}}}\right) .$$
(5)
Set the sampling frequency which is equal to $F_{\textrm{s}} = 120$ Hz and take $N = 30$ pickup signal samples.
Calculate the DFT $S(k)$, $k = 0 \ldots N-1$, of this signal and get the amplitude spectrum as it is shown in Figure 1.
As it is possible to note in Figure 1, there is only one component with the index $k = 25,$ that corresponds to the frequency according to (4) in the signal spectrum
$$f(25) = \frac{120}{30} \cdot 25 = 100 \textrm{, Hz},$$
(6)
that can seem strange because we set the pickup signal frequency $f_0 = -20$ Hz.
However there is nothing special in it if we remember that the spectrum $S(f)$ of our discrete signal $s(n)$ is the periodic function with the period $F_{\textrm{s}} = 120$ Hz, i.e. for our discrete signal the spectrum $S(f)$ consists of the infinite number of harmonicas with frequencies $f(m) = f_0 + m \cdot F_{\textrm{s}}$ , $m = 0, \pm 1, \pm 2, \ldots$, as it is shown in Figure 2.
Figure 2. Periodic spectrum $S(f)$ of the signal $s(n)$
The figure shows that when the spectrum sampling $S(f)$ in one repetition period is from 0 to $F_{\textrm{s}}$ 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 $S(f)$ in the frequency range from $\frac{F_{\textrm{s}}}{2}$ Hz to $F_{\textrm{s}}$ Hz periodically repeats the spectrum $S(f)$ in the frequency range from $-\frac{F_{\textrm{s}}}{2}$ Hz to $0$ Hz.
Thus, we can perform the DFT shifting for the signal spectrum analysis in the range of frequencies from $-\frac{F_{\textrm{s}}}{2}$ to $\frac{F_{\textrm{s}}}{2}$ Hz.
Let’s state an important remark. The frequency component corresponding to the frequency $\frac{F_{\textrm{s}}}{2}$ Hz in view of the discrete signal spectrum periodicity also corresponds to the frequency $-\frac{F_{\textrm{s}}}{2}$ Hz. Upon shifting we will refer this component to the frequency $-\frac{F_{\textrm{s}}}{2}$ Hz.
DFT shifting for even $N$
Under even $N$ the spectrum sample $S\left( \frac{N}{2}\right)$corresponds to the frequency $\frac{F_{\textrm{s}}}{2}$ Hz in accordance with (4). As we noted above, the same sample corresponds to the frequency $-\frac{F_{\textrm{s}}}{2}$ Hz. Then it is possible to write the spectrum $S_\textrm{sh}(k)$ after shifting for even $N$ as follows:
$$S_\textrm{sh}(k) = \begin{cases} S \left( k + \frac{N}{2}\right) &\text{if k = 0 \ldots \frac{N}{2}-1};\\ S \left( k - \frac{N}{2}\right) &\text{if k = \frac{N}{2} \ldots N-1}. \end{cases}$$
(7)
The $k$-th spectrum sample after shifting $S_\textrm{sh}(k)$ corresponds to the frequency
$$\omega_\textrm{sh}(k) = - 2 \pi \cdot \frac{F_{\textrm{s}}}{2} + k \cdot \Delta \omega =2 \pi \cdot \left( - \frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{N} \cdot k \right) \textrm{, rad/s},$$
(8)
or
$$f_\textrm{sh}(k) = -\frac{F_{\textrm{s}}}{2} + k \cdot \Delta f = -\frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{N} \cdot k \textrm{, Hz}.$$
(9)
Thus, the sample $S_\textrm{sh}(0)$ corresponds to the frequency $f_\textrm{sh}(0) = -\frac{F_{\textrm{s}}}{2}$ Hz, the sample $S_\textrm{sh} \left( \frac{N}{2} \right)$ corresponds to the frequency $f_\textrm{sh}\left( \frac{N}{2} \right) = 0$ Hz and the sample $S_\textrm{sh}(N-1)$ corresponds to the frequency $f_\textrm{sh}\left( N-1\right) = \frac{F_{\textrm{s}}}{2} - \frac{F_{\textrm{s}}}{N}$ Hz.
DFT shifting for even $N$ is shown in Figure 3a.

Figure 3. DFT shifting a) for even $N$, b) for odd $N$
DFT shifting for odd $N$
Under odd $N$ the spectrum sample $S\left( \frac{N-1}{2}\right)$ corresponds to the frequency $\frac{F_{\textrm{s}}}{2} - \frac{F_{\textrm{s}}}{2 \cdot N}$ Hz in accordance with (4), and the spectrum sample $S\left( \frac{N+1}{2}\right)$ corresponds to the frequency $\frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{2 \cdot N}$ Hz.
The spectrum $S_\textrm{sh}(k)$ after shifting for odd $N$:
$$S_\textrm{sh}(k) = \begin{cases} S \left( k + \frac{N+1}{2}\right) &\text{if k = 0 \ldots \frac{N-1}{2}-1};\\ S \left( k - \frac{N-1}{2}\right) &\text{if k = \frac{N-1}{2} \ldots N-1}. \end{cases}$$
(10)
The $k$ spectrum sample after shifting $S_\textrm{sh}(k)$ corresponds to the frequency
$$\omega_\textrm{sh}(k) = 2 \pi \cdot \left(- \frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{2 \cdot N} \right)+ k \cdot \Delta \omega = 2 \pi \cdot \left(-\frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{2 \cdot N} + \frac{F_{\textrm{s}}}{N} \cdot k \right) \textrm{, rad/s},$$
(11)
or
$$f_\textrm{sh}(k) = -\frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{2 \cdot N} + k \cdot \Delta f = -\frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{2 \cdot N} + \frac{F_{\textrm{s}}}{N} \cdot k \textrm{, Hz}.$$
(12)
Figure 4. Amplitude spectrum $|S_\textrm{sh}(k)|$
after shifting and corresponding
frequency values $f_\textrm{sh}(k)$
After DFT shifting under odd $N$, the spectrum sample $S_\textrm{sh}(0)$ corresponds to the frequency $f_\textrm{sh}(0) = -\frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{2 \cdot N}$ Hz in accordance with (12), the spectrum sample $S_\textrm{sh} \left(\frac{N-1}{2} \right)$ corresponds to the frequency $f_\textrm{sh}\left(\frac{N-1}{2} \right) = 0$ Hz and the last sample $S_\textrm{sh}(N-1)$ corresponds to the frequency $f_\textrm{sh}(N-1) = \frac{F_{\textrm{s}}}{2} - \frac{F_{\textrm{s}}}{2 \cdot N}$ Hz.
DFT shifting for odd $N$ is shown in Figure 3b.
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 $N = 30$, therefore we can use (7) for getting $S_\textrm{sh}(k)$. Then after shifting spectrum samples will correspond to frequencies (9).
In Figure 4 there is given the amplitude spectrum $|S_\textrm{sh}(k)|$ after shifting and frequency values $f_\textrm{sh}(k)$ (Hz). Spectrum samples correspond to this frequency $S_\textrm{sh}(k)$.
As it is possible to see in Figure 4, after shifting of spectrum samples the component $S_\textrm{sh}(10)$ corresponds to the frequency $f_\textrm{sh}(10) = -20$ Hz that we set for the pickup signal.
In the DSPL library the dspl_fft_shift function for shifting of DFT spectrum samples is implemented. This function was used for calculating the data upon plotting Figures 1 and 4.
GNU Octave and Matlab can repeat the experiments above by dft_indexation.m script.


clear all;
close all;
clc;

N = 30; 	% DFT size
f0 = -20; %Hz
Fs = 120; %Hz

n = 0 : N-1;

f = (0 : N-1)/N * Fs;

% input signal
s = exp(2i*pi*n*f0/Fs);

% Input signal DFT
S = abs(fft(s));

% Input signal magnitude (figure 1)
figure; h = stem(f,S,'.');
set (h(1), 'markersize', 8);
xlabel ('f(k), Hz');
ylabel ('|S(k)|');

% DFT shifting
Ssh = fftshift(S);
fsh = f - Fs/2;

% Spectrum magnitude after DFT shifting (figure 4)
figure; h = stem(fsh,Ssh,'.');
set (h(1), 'markersize', 8);
xlabel ('f_{sh}(k), Hz');
ylabel ('|S_{sh}(k)|');


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 $N$ for correct presenting negative frequencies after the DFT were given.
The DFT properties will be considered in more detail in the following sections.

You can provide your any feedbacks, questions and wishes in the message board or guestbook.
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.

 Select spelling error with your mouse and press