Introduction
The notes on the webpages on Fourier series and Fourier Transforms
provide some background to the derivation and the application of the subject.
Fourier Transforms are largely theoretical concepts using integral calculus of
some complexity. In experimental work the integrand may be
large quantities of measured ( sampled ) data. Discrete Fourier
Transforms are the only practical transforms which can be used for analysing the
sampled information.
Discrete Fourier Transforms (DFT) are periodic in both the time domain and the
frequency domain. The DFT provides a practical method of analysing continuous
functions which may not be periodic. A single period of the DFT is used as a very accurate
approximation of the nonperiodic Fourier tranform
By far the most efficient method of obtaining Discrete Fourier Transform (DFT) and
the inverse transforms is by use of the Fast Fourier transform alogorithm.(FFT) The notes below do not cover in detail
the Fast Fourier algorithm.
The sampled data is read into a file or array and
using a relatively simply computation based on the FFT algorithm the data
is transformed to Discrete Fourier Transform data consisting of digital frequency /amplitude
information, and the results are available as output. This can be achieved using software or
it can be achieved  on the run using integrated circuits.
Note: The process of transforming the input data (normallytime domain)
into the frequency domain is called analysis. The reverse process is called synthesis.
These notes are outline in nature and cover only the basic concepts without delving too much into the
details benefits and limitations. I shall try to expand the content over the coming weeks
The Discrete Fourier Transforms
Equations for Discrete Fourier Transforms, in exponential form,are provided below without proof.
Notes are provided below to attempt to clarify these equations and their application.
The Discrete Fourier Transform function generally relates to sampled
data .
The symbol k is simply the sample number in the time domain. The symbol n is the frequency
over the sampling period e.g. n = 1 is one cycle
over the period N
N is the number of samples. The sampling interval is represented by T. The number of samples
comprising one period T_{o} equal to NT. In the frequency domain the
Period is represented by a period of 1/T is equal to N/T_{o}.
N is normally a number such as 32, 64, 128, 256, 512, 1024........The larger the value of N
the more accurate is the Discrete Fourier Transform
Real Discrete Fourier Transforms
The above equations defining Discrete Fourier Transforms are defined using complex variables.
Discrete Fourier Transforms can be expressed as real or
complex versions. The real version is the simplest, using ordinary numbers and algebra for the synthesis and
decomposition. The two figure below show the difference btween complex versions and real number versions
Complex Number Version
Real Number Version
Re X() are cosine amplitudes and Im x() are sine amplitudes.
This is based on the following relationship
The basis functions are a set of sine and cosine
waves with unity amplitude. Assigning an amplitude, in the frequency
domain, to the proper sine or cosine wave ( the basis functions ) results in
a set of scaled sine and cosine waves that can be added to form the time
domain signals c_{n} and s_{n} .... c_{n} is the
cosine wave for the amplitude held ReX [ n ] and s_{n} is the sine wave for
the amplitude held in ImX [ n ] c_{n} [ k ] = cos( 2πnk /N)
s_{n} [ k ] = sin( 2πnk /N)
c _{n} and s _{n} are cosine and sine waves each N
points in length, running from k = 0 to N1. The
parameter n, determines the frequency of the wave.
In an N point DFT, n takes on values between 0 and N/2.
Calculating the Inverse DFT ( Synthesis )
The equation below is a simplified version of the above equations.
..
The spectral density value indicates how much frequency signal (amplitude)
is present per unit of bandwidth. The sinusoidal amplitudes are converting
into spectral density values by dividing each amplitude i.e Re[n] by the bandwidth
represented by each amplitude i.e (N/2).
Calculating the DFT ( Analysis Decomposition )
Various methods are used to obtain DFT for time domain samples including use of
Simultaneous Equations using Gaussian elimination, correlation, and using the Fast
Fourier Transform algorithm. The first
option requires massive work even for a comparitively small number of samples.
In actual practice, correlation is the preferred method if the DFT has less than
about 32 points. FFT algorithms are used for all applications if the number of points exceed 32.
The equations for determining the Discrete Fourier Transforms, using the principles of correlation, from the time domain signals are listed below
The index k runs from 0 to N1, while the index n runs from 0 to N/2.
Considering a signal of N points. To
detect a specific waveform contained in this signal, multiply the
signal amplitude by the waveform amplitude at each time interval and
add all the points in the resulting signal. The result of
this operation will be zero if the signal does not contain the
specific waveform. If the signal contains waveform
then a positive value will result. For example: if the signal has an amplitude of
4 and includes 4 cycles over N= 64 points and the specific waveform also completes 4 cycles
over N = 64 points then the result is as shown below. For all other signal frequencies
the result will be zero.
Now if the signal includes a constant value offset (say 4). The result of the
above operation will be the same. Also if the signal includes other waveforms
of different amplitudes and frequencies the result still be unchanged only the content with
the same frequency as the specific waveform will be added in the sum for ReX(n).
Signal Waveform ..x(k) = 4 + 4cos(2π4k/N) + 2.cos(2πk/N) + sin(2π2k/N)  5sin(2π3k/N)
The signal includes a sine wave with 3 cycles over N = 64 points.
If the signal is multiplied with a specific sine waveform which completes 3 cycles over N = 64 points the follow results.
The results of the operation of detecting other waveforms are shown below.
The complex Discrete Fourier Transform
These notes attempt to show relationship between the Real DFTs based on cosines and sines are
and more elegant, but more difficult to comprehend complex DFTs.
1)First looking at determining the time function from the frequency domain  Synthesis..
The following identities show exponential  trigonometric relationship
The following relationships are easilty defined
cos(2πn/N) = e^{j2πn/N} /2 + e^{j2πn/N} /2
sin(2πn/N) = je^{j2πn/N} /2  je^{j2πn/N} /2
It is clear each expression consists two terms one based on
exponential with a negative frequency term and one with a positive
frequency term. The complete waveform
consists of half of each term..
Now n (cycles over the period N) for the sine /cosine DFT version
is from 0 to N/2. For the complex DFT version n is from
0 to N1
The sine /cosine version of the Fourier transform only
deals with positive frequencies i.e the frequency domain index, n, only runs
from 0 to N/2. The complex Fourier transform includes both positive and
negative frequencies for N/2 to N/2.
For even functions the amplitudes X(N/2 to 0) = X(N/2 to N) and for odd functions
X(N/2 to 0) = X(N/2 to N ) . This results from the frequency domain
being periodic about zero frequency and for a period N the frequencies from 0 to N/2 are mirror images of
the frequencies of 0 to N/2. The frequencies from N/2 to 0 have equal
magnitude as the the frequencies from N/2 to N.
This is illustrated by the figure below
A inverse Discrete Fourier Transofrm f(k) is expressed in complex DFT form as shown below
This equation is related to those applicable to the real variation of the Discrete Fourier Transform
as follows.
2) Now looking at the determination of the Discrete Fourier Transform  Analysis
The Discrete Fourier Transform Properties
Note: In this table for convenience F( n ) has
been used for F( n /NT) and f( k ) for f( kT ).
A table of the properties of Discrete Fourier Transforms is provided below. This table also include
the equivalent Fourier Transforms properties for comparison
Property  Discrete Fourier Transform  Fourier Transform 
Linearity   
Symmetry   
Time Shifting   
Frequency Shifting   
Even functions   
Odd Functions   
Decomposition   
Convolution   
Time Convolution Theorem   
Correlations   
Frequency Convolution Theorem   
