Discrete Fourier Transform (DFT)

Contents
Introduction
The Discrete Fourier Transform (DFT) is one of widespread signal spectrum analysis tools which is widely used in the most different branches of science and technology. At the same time the set of fast algorithms for extra computational DFT performance is developed.
In this section special attention will be paid to transition from the continuous Fourier integral to the Discrete-Time Fourier Transform (DTFT) and then to the Discrete Fourier Transform. The comprehension of this transition will allow to understand better the DFT properties and essence of the digital spectrum analysis in the whole.
The couple of continuous Fourier transform (the Fourier integral) is as follows:
$$ S(\omega) = \int \limits_{-\infty}^{\infty} s(t) \cdot \exp \left( -j \cdot \omega \cdot t\right) d t; \nonumber $$ $$ s(t) = \frac{1}{2 \pi} \cdot \int \limits_{-\infty}^{\infty} S(\omega) \cdot \exp \left( j \cdot \omega \cdot t\right) d \omega, $$
(1)
where $ S(\omega) $ is the signal $s(t)$ spectrum (in general the signal and the spectrum are complex ones).
The direct DFT and the Inverse Discrete Fourier Transform (IDFT) equations are as follows:
$$ S_{\textrm{d}}(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_{\textrm{d}}(k) \cdot \exp \left( j \cdot \frac{2\pi}{N} \cdot n \cdot k\right), \text{ } n=0 \ldots N-1. $$
(2)
The DFT associates $N$ samples of the signal $s(n)$, $n = 0\ldots N-1$, to $N$ samples of the complex spectrum $S_{\textrm{d}}(k)$, $k = 0 \ldots N-1$. Hereinafter in this section the variable $n$ indexes time signal samples, and the variable $k$ indexes DFT spectrum samples.
There is a normalizing coefficient in equations for the inverse transform either in the continuous case or in the discrete one. In case of the Fourier integral it is $\frac{1}{2 \pi}$, in case of the IDFT it is $\frac{1}{N}$.
The normalizing coefficient is necessary for correct signal scaling from the frequency domain to the time one. The normalizing coefficient reduces the signal amplitude at the output of the inverse transform for it to be coincided with the pickup signal amplitude. If the direct Fourier transform of some signal is calculated in sequence, and then the inverse Fourier transform is considered, then the result of the inverse transform shall coincide with the pickup signal completely.
Signal time sampling. Discrete-Time Fourier Transform.
Consider the discrete signal $s_{\text{d}} (t)$ as result of multiplying the continuous signal $s(t)$ by the sampling function:
$$ s_\text{d} (t) = s(t) \cdot \sum_{n=0}^{N-1} \delta(t - n \cdot \Delta t) = \sum_{n=0}^{N-1} s(t) \cdot \delta(t - n \cdot \Delta t), $$
(3)
where $\delta(t)$ is the delta function:
$$ \delta(t) = \begin{cases} \infty &\text{if $t = 0$;}\\ 0 &\text{if $t \neq 0$,} \end{cases} $$
(4)
$\Delta t$ is the sampling interval. Graphically the sampling process can be presented as it is shown in Figure 1.
Figure 1. Signal Sampling Process
Calculate the Fourier transform of the discrete signal $s_{\textrm{d}}(t)$, for this purpose plug (3) into the Fourier transform (1):
$$ S_{\textrm{d}}(\omega) = \int \limits_{-\infty}^{\infty} s_{\text{d}}(t) \cdot \exp \left( -j \cdot \omega\ \cdot t \right) dt = \int \limits_{-\infty}^{\infty} \sum_{n=0}^{N-1} s(t) \cdot \delta(t - n \cdot \Delta t) \cdot \exp \left( -j \cdot \omega\ \cdot t \right) dt. $$
(5)
Interchange the position of summing and integrating operations and use the filtering property of the delta function:
$$ \int \limits_{-\infty}^{\infty}s(t) \cdot \delta(t-\tau) dt = s(\tau). $$
(6)
Then (5) taking into account (6) is as follows:
$$ S_{\textrm{d}}( \omega) = \sum_{n=0}^{N-1} {\int \limits_{-\infty}^{\infty} s(t) \cdot \delta(t - n \cdot \Delta t) \cdot \exp \left( -j \cdot \omega\ \cdot t \right) dt} = \sum_{n=0}^{N-1} s(n \cdot \Delta t) \cdot \exp \left( -j \cdot \omega\ \cdot n \cdot \Delta t \right). $$
(7)
Thus, we got rid of integration in infinite limits, having replaced it with the final summing of complex exponents.
Complex exponents $\exp \left( -j \cdot \omega\ \cdot n \cdot \Delta t \right)$ in (7) are periodic functions with the period
$$ \Omega(n) = \frac{2 \pi}{n \cdot \Delta t} = \frac{2 \pi \cdot F_{\textrm{s}}}{n} , \text{ rad/s, } n = 1 \ldots N-1, $$
(8)
where $F_{\rm{s}} = \frac{1}{\Delta t}$ is the signal sampling frequency (Hz).
It is necessary to note that $n=0$ is excluded from (8) as under $n=0$ the complex exponent is equal to unit. The maximum spectrum repetition period $S_{\textrm{d}}(\omega)$ will be under $n=1$ and it is equal to $\Omega_{\text{max}} = \Omega(1) = \frac{2 \pi}{\Delta t} = 2\pi \cdot F_{\rm{s}}$ rad/s.
Thus, the spectrum $S_{\textrm{d}}(\omega)$ of the discrete signal $s_{\textrm{d}}(t)$ is $2\pi \cdot F_{\textrm{s}}$, i.e. the periodic function of the angular frequency $\omega$ defined as (7). If we introduce frequency sampling normalization $F_{\textrm{s}} = 1$ Hz, then (7) passes to the Discrete-Time Fourier Transform (DTFT):
$$ S(\omega_{\textrm{n}}) = \sum_{n=0}^{N-1} s(n) \cdot \exp \left( -j \cdot \omega_{\textrm{n}} \cdot n \right). $$
(9)
The DTFT uses only indexes of input signal samples $s(n)$ if the frequency sampling is $F_{\textrm{s}} = 1$ Hz. As a result of the DTFT we get the $2\pi$ periodic function $S_{\textrm{d}}(\omega_{\textrm{n}})$ of the normalized angular frequency $\omega_{\textrm{n}} = \frac{\omega}{F_{\textrm{s}}}$.
As the discrete signal spectrum is a periodic function, it is possible to consider only one period of the spectrum repetition $S_{\textrm{d}}(\omega)$ under $\omega = \big[0, \: 2\pi \cdot F_{\textrm{s}} \big]$ rad/s or $S_{\textrm{d}}(f)$ under $f = \big[0, \: F_{\rm{s}} \big]$ Hz.

Signal time repetition. Discrete Fourier Transform
Either discrete signal samples or discrete spectrum samples are required for the software implementation of digital processing algorithms. It is known that periodic signals possess the discrete spectrum or line one as it is also called. At the same time the discrete spectrum is got by periodic signal expansion in a Fourier series. It means that to get a discrete spectrum, it is necessary to turn the pickup discrete signal to a periodic one by means of this time signal repetition an infinite number of times with some period $T$. Then the periodic signal spectrum will contain discrete multiple harmonicas $\Delta \omega = \frac{2\pi}{T}$ rad/s.
Graphically the time signal repetition process is presented in Figure 2.
Figure 2. Time Signal Repetition
The pickup signal is black, its repetitions via the period $T$ are red.
It is possible to repeat a signal with the various period $T$, however the repetition period shall be more or equal to the signal duration $T \ge N \cdot \Delta t$ for the signal and its periodic repetitions to be not covered in time. At the same time the minimum signal repetition period $T_{\text{min}}$ when the signal and its repetitions do not cover each other is equal to
$$ T_{\text{min}} = N \cdot \Delta t, {\textrm{ sec}}. $$
(10)
The signal repetition with the minimum period $T_{\text{min}} = N \cdot \Delta t$ is shown in Figure 3.
Figure 3. Signal Repetition with the Minimum Period
Upon repeating the signal with the minimum period $T_{\text{min}}$ we will get the line signal spectrum consisting of multiple harmonicas:
$$ \Delta \omega = \frac{2\pi}{T_{\text{min}}} = \frac{2\pi}{N \cdot \Delta t} \text{ (rad/s)}. $$
(11)
Thus, we can sample the spectrum $S_{\textrm{d}}(\omega)$ of the discrete signal $s(n)$ in one repetition period $2\pi \cdot F_{\textrm{s}}$ with the step $\Delta \omega = \frac{2\pi}{N \cdot \Delta t}$ and thereby we get
$$ \frac{ 2\pi \cdot F_{\textrm{s}} }{\Delta \omega} = \frac{ \frac{ 2 \pi }{ \Delta t } } { \frac{ 2\pi }{ N \cdot \Delta t} } = N $$
(12)
spectrum samples.
Consider the mentioned above things in (7):
$$ S_{\textrm{d}}( k \cdot \Delta \omega) = \sum_{n=0}^{N-1} s(n \cdot \Delta t) \exp \left( -j \cdot n \cdot \Delta t \cdot k \cdot \Delta \omega \right) = $$ $$ = \sum_{n=0}^{N-1} s(n \cdot \Delta t) \exp \left( -j \cdot n \cdot \Delta t \cdot k \cdot \frac{2\pi}{N \cdot \Delta t} \right) = $$ $$ = \sum_{n=0}^{N-1} s(n \cdot \Delta t) \exp \left( -j \cdot \frac{2\pi}{N} \cdot n \cdot k \right), \text{ } k = 0 \ldots N-1. $$
(13)
If we omit the time sampling step $\Delta t$ and frequency sampling step $\Delta \omega$ in (13), we will get the final DFT equation:
$$ S_{\textrm{d}}(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. $$
(14)
The DFT associates $N$ samples of the discrete signal $s(n)$ to $N$ samples of the discrete spectrum $S_{\textrm{d}}(k)$, at the same time it is supposed that the signal and spectrum are periodic, and they are analyzed in one repetition period.
The DFT properties will be considered in details in the following sections.
Inverse discrete Fourier transform
Similarly (3) it is possible to write down the discrete spectrum via the sampling function:
$$ S_{\textrm{D}}(\omega) = \sum_{k=0}^{N-1}S_{\textrm{d}}(\omega) \cdot \delta(\omega - k \cdot \Delta \omega), $$
(15)
where $S_{\textrm{D}}(\omega)$ are discrete spectrum samples $S_{\textrm{d}}(\omega)$ in one repetition period $2 \pi \cdot F_{\textrm{s}}$ rad/s.
Plug (15) into Inverse Fourier Transform (1):
$$ s(t) = C \cdot \int \limits_{-\infty}^{\infty}S_{\textrm{D}}(\omega) \cdot \exp(j \cdot \omega \cdot t) d \omega = C \cdot \int \limits_{-\infty}^{\infty}\sum_{k=0}^{N-1}S_{\textrm{d}}(\omega) \cdot \delta(\omega - k \cdot \Delta \omega) \cdot \exp(j \cdot \omega \cdot t) d \omega , $$
(16)
where $C$ is the proportionality coefficient which task is to provide equality in the pickup discrete signal amplitude and the IDFT result. The proportionality coefficient $C$ considers the Inverse Fourier Transform coefficient $\frac{1}{2\pi}$.
Interchange the position of summing and integrating operations and consider the filtering property of the delta function:
$$ s(t)= C \cdot \sum_{k=0}^{N-1}\int \limits_{-\infty}^{\infty}S_{\textrm{d}}(\omega) \cdot \delta(\omega - k\cdot \Delta \omega) \cdot \exp(j \cdot \omega \cdot t) d \omega = C \cdot \sum_{k=0}^{N-1}S_{\textrm{d}}(k\cdot \Delta\omega) \cdot \exp(j \cdot k \cdot \Delta \omega \cdot t). $$
(17)
Take discrete samples $s(t)$ via the interval $\Delta t = \frac{1}{F_{\textrm{s}}}$ sec, then it is possible to write down (17) as follows:
$$ s(n \cdot \Delta t) = C \cdot \sum_{k=0}^{N-1}S_{\textrm{d}}(k\cdot \Delta\omega) \cdot \exp(j \cdot k \cdot \Delta \omega \cdot n \cdot \Delta t), \text{ } n = 0 \ldots N-1. $$
(18)
Consider (11) and get:
$$ s(n \cdot \Delta t) = C \cdot \sum_{k=0}^{N-1}S_{\textrm{d}}(k\cdot \Delta\omega) \cdot \exp \left(j \cdot \frac{2\pi}{N} \cdot n \cdot k \right), \text{ } n = 0\ldots N-1. $$
(19)
Having omitted frequency and time sampling intervals in (19), we will get the IDFT formulation in which the proportionality coefficient $C$ is unknown:
$$ s(n) = C \cdot \sum_{k=0}^{N-1}S_{\textrm{d}}(k) \cdot \exp \left(j \cdot \frac{2\pi}{N} \cdot n \cdot k \right), \text{ } n = 0 \ldots N-1. $$
(20)
To calculate the coefficient $C$ it is necessary to plug (14) into IDFT (20):
$$ s(n) = C \cdot \sum_{k=0}^{N-1} \sum_{m=0}^{N-1} s(m) \cdot \exp \left(-j \cdot \frac{2\pi}{N} \cdot m \cdot k \right) \cdot \exp \left(j \cdot \frac{2\pi}{N} \cdot n \cdot k \right), \text{ } n = 0 \ldots N-1. $$
(21)
Interchange the position of summing in (21) and combine exponents:
$$ s(n) = C \cdot \sum_{m=0}^{N-1} \cdot s(m) \cdot \sum_{k=0}^{N-1} \exp \left(j \cdot \frac{2\pi}{N} \cdot (n-m) \cdot k \right), \text{ } n = 0 \ldots N-1. $$
(22)
Consider the sum of complex exponents (22) in more detail.
Under $m=n$ we get:
$$ \sum_{k=0}^{N-1} \exp \left(j \cdot \frac{2\pi}{N} \cdot (n-n) \cdot k \right) = \sum_{k=0}^{N-1} 1 = N. $$
(23)
Now consider the same sum under $m \neq n$.
Let it be $L=n-m$, then:
$$ \sum_{k=0}^{N-1} \exp \left(j \cdot \frac{2\pi}{N} \cdot (n-m) \cdot k \right) = \sum_{k=0}^{N-1} \exp \left(j \cdot \frac{2\pi}{N} \cdot L \cdot k \right). $$
(24)
Each complex exponent being in sum (24) is a vector in the complex plane of unit length rotated by an angle:
$$ \phi(k) = \frac{2\pi \cdot L}{N} \cdot k, \text{ } k = 0 \ldots N-1. $$
(25)
There will be such $N$ vectors, and they are rotated by the same angles $\Delta\phi$ relative to one another.
As all vectors come out of the same point (out of the 0 complex plane) and are rotated by the same angles $\Delta\phi$ relative to one another, their sum is equal to zero. It is illustrated in Figure 4 for $N=4$.
Figure 4. Sum of Complex Exponents
According to Figure 4 it is possible to conclude that the sums of complex exponents (24) are equal to zero for all $L=n-m$, $n=0\ldots N-1$, $m=0\ldots N-1$, $m \neq n$.
Then only the summand under $n=m$ will be left in (22) off the sum according to $m=0 \ldots N-1$. Then it is possible to present (22) as follows:
$$ s(n) = C \cdot \sum_{m=0}^{N-1} \cdot s(m) \cdot \sum_{k=0}^{N-1} \exp \left(j \cdot \frac{2\pi}{N} \cdot (n-m) \cdot k \right) = C \cdot s(n) \cdot N, \text{ } n = 0 \ldots N-1. $$
(26)
According to (26) it is possible to conclude that $C = \frac{1}{N}$.
Thus, the final IDFT formulation is as follows:
$$ s(n) = \frac{1}{N} \cdot \sum_{k=0}^{N-1} S_{\textrm{d}}(k) \cdot \exp \left( j \cdot \frac{2 \pi}{N} \cdot n \cdot k\right), \text{ } n = 0 \ldots N-1. $$
(27)
Conclusions
In this section we carried out the transition from the Fourier integral to the direct and Inverse Discrete Fourier Transform by either the time or frequency signal sampling.
It was shown that the spectrum $S_{\textrm{d}}(\omega)$ of the discrete signal is the periodic function with the period $2 \pi \cdot F_{\textrm{s}}$ rad/s or $F_{\textrm{s}}$ Hz.
There is introduced the concept of Discrete-Time Fourier Transform $S(\omega_ {\textrm{n}})$ as the $2\pi$ periodic function which is normalized to the sampling frequency of the angular frequency $\omega_{\textrm{n}}$.
The DFT is got by the continuous function sampling $S_{\textrm{d}}(\omega)$ in one repetition period that is equivalent to the periodic repetition of the time discrete signal with the period $\frac{N}{F_{\textrm{s}}}$ sec.

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, Singapor, 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 Система Orphus