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 non-periodic 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 (normally-time 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

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

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 N-1.    The parameter n, determines the frequency of the wave.    In an N point DFT, n takes on values between 0 and N/2.

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).   

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 N-1, 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.

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 N-1

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

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