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:

where

is the signal

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:

The DFT associates

samples of the signal

,

, to

samples of
the complex spectrum

,

. Hereinafter in this section the
variable

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

as result
of multiplying the continuous signal

by the sampling function:

where

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.

Complex exponents

in (7) are periodic functions with the period

where

is the signal sampling frequency (Hz).

It is necessary to note that

is excluded from (8)
as under

the complex exponent is equal to unit.
The maximum spectrum repetition period

will be under

and it is equal to

rad/s.

Thus, the spectrum

of the discrete
signal

is

,
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

Hz.
As a result of the DTFT we get the

periodic
function

of
the normalized angular frequency

.

As the discrete signal spectrum is a periodic function,
it is possible to consider only one period of the spectrum
repetition

under

rad/s
or

under

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

.
Then the periodic signal spectrum will contain
discrete multiple harmonicas

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

are red.

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

spectrum samples.

Consider the mentioned above things in (7):

If we omit the time sampling step

and frequency sampling step

in (13),
we will get the final DFT equation:

The DFT associates

samples of the discrete signal

to

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:

where

are discrete spectrum samples

in one repetition period

rad/s.

Plug (15) into Inverse Fourier Transform (1):

where

is the proportionality coefficient which task
is to provide equality in the pickup discrete signal
amplitude and the IDFT result.
The proportionality coefficient

considers
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

sec,
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
coefficient

is unknown:

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.

Under

we get:

Now consider the same sum under

.

Let it be

, then:

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:

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

of the discrete signal is the periodic function with the period

rad/s or

Hz.

There is introduced the concept of Discrete-Time Fourier Transform

as the

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

sec.

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.