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:
is the signal
(in general the signal and the spectrum are complex ones).
The direct DFT and the Inverse Discrete Fourier
Transform (IDFT) equations are as follows:
The DFT associates
samples of the signal
the complex spectrum
. Hereinafter in this section the
indexes time signal samples,
and the variable
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
in case of the IDFT it is
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
of multiplying the continuous signal
by the sampling function:
is the delta function:
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
, for this purpose plug (3)
into the Fourier transform (1):
Interchange the position of summing and integrating operations
and use the filtering property of the delta function:
Then (5) taking into account (6) is as follows:
Thus, we got rid of integration in infinite limits,
having replaced it with the final summing of complex exponents.
in (7) are periodic functions with the period
is the signal sampling frequency (Hz).
It is necessary to note that
is excluded from (8)
the complex exponent is equal to unit.
The maximum spectrum repetition period
will be under
and it is equal to
Thus, the spectrum
of the discrete
i.e. the periodic function of the angular frequency
defined as (7).
If we introduce frequency sampling normalization
Hz, then (7) passes to the
Discrete-Time Fourier Transform (DTFT):
The DTFT uses only indexes of input signal samples
if the frequency sampling is
As a result of the DTFT we get the
the normalized angular frequency
As the discrete signal spectrum is a periodic function,
it is possible to consider only one period of the spectrum
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
Then the periodic signal spectrum will contain
discrete multiple harmonicas
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
It is possible to repeat a signal with the various period
however the repetition period shall be more or equal to the signal duration
for the signal and its periodic
repetitions to be not covered in time.
At the same time the minimum signal repetition period
when the signal and its repetitions
do not cover each other is equal to
The signal repetition with the minimum period
is shown in Figure 3.
Figure 3. Signal Repetition with the Minimum Period
Upon repeating the signal with the minimum period
we will get the line signal spectrum consisting of multiple harmonicas:
Thus, we can sample the spectrum
of the discrete signal
in one repetition period
with the step
and thereby we get
Consider the mentioned above things in (7):
If we omit the time sampling step
and frequency sampling step
we will get the final DFT equation:
The DFT associates
samples of the discrete signal
samples of the discrete spectrum
at the same time it is supposed that the signal and
spectrum are periodic, and they are analyzed in one repetition period.
Inverse discrete Fourier transform
Similarly (3) it is possible to write down the discrete
spectrum via the sampling function:
are discrete spectrum samples
in one repetition period
Plug (15) into Inverse Fourier Transform (1):
is the proportionality coefficient which task
is to provide equality in the pickup discrete signal
amplitude and the IDFT result.
The proportionality coefficient
the Inverse Fourier Transform coefficient
Interchange the position of summing and integrating
operations and consider the filtering property of the delta function:
Take discrete samples
via the interval
then it is possible to write down (17) as follows:
Consider (11) and get:
Having omitted frequency and time sampling intervals in (19),
we will get the IDFT formulation in which the proportionality
To calculate the coefficient
it is necessary to plug (14) into IDFT (20):
Interchange the position of summing in (21) and combine exponents:
Consider the sum of complex exponents (22) in more detail.
Now consider the same sum under
Let it be
Each complex exponent being in sum (24) is a vector in
the complex plane of unit length rotated by an angle:
There will be such
vectors, and they are rotated by the same angles
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
relative to one another,
their sum is equal to zero. It is illustrated in Figure 4 for
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
Then only the summand under
will be left in (22)
off the sum according to
Then it is possible to present (22) as follows:
According to (26) it is possible to conclude that
Thus, the final IDFT formulation is as follows:
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
of the discrete signal is the periodic function with the period
There is introduced the concept of Discrete-Time Fourier Transform
periodic function which is normalized to the sampling frequency of the angular frequency
The DFT is got by the continuous function sampling
in one repetition period that is equivalent to the periodic repetition of the time discrete signal with the period
The Fourier Transform and its Applications.
McGraw Hill, Singapor, 2000.
Oppenheim Alan V. and Schafer Ronald W.
Discrete-Time Signal Processing
Prentice-Hall, New Jersey, 1999.
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.
Nussbaumer Henri J.
Fast Fourier Transform and Convolution Algorithms.
Second Corrected and Updated Edition.