Discrete Fourier Transforms .
To be continued....
Useful Related Links
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
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.
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
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 cn and sn ....
cn [ k ] = cos( 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.
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 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.
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 + ej2πn/N /2
sin(2πn/N) = je-j2πn/N /2 - jej2π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
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
To be continued....
Useful Related Links