What is the Discrete Fourier Transform

	In systems, it is often necessary to analyze data across a
certain domain. In the analog world, this domain is represented in the
voltage versus time. In the digital world it may often become necessary
to measure the signal’s spectral components, meaning the amplitude
versus its frequency. The applications of such spectral measurements can
be seen in testing communications system’s modulators to determine
proper functioning; data and voice, and video compression for faster
transmission. In particular, MPEG is a video compression algorithm using
discrete cosine transforms to compress images and send them enabling
real-time quality. You can also see its applications in radar signal
processing, and pattern recognition. 
	The science of the Discrete Fourier Transform stems from the
publications of Fourier Analysis published in 1822. Fourier classifies
signals as a sum of sine waves. The sine wave is considered the most
basic signal of which other shaped signals can be developed. A square
wave consists of one sine wave of one amplitude and frequency, and many
other sine waves of higher frequencies and smaller amplitudes. The
smaller sine waves are called Harmonics which are smaller
representations of the sine wave but at different amplitudes. These
signals are added together to produce the pulsed wave. To prove that the
sine wave is the most basic of signals, construct an LC circuit and tune
it to a particular frequency. Attach a signal generator outputting a
square wave, triangle wave, or any other type of wave to the input of
the LC circuit. Measure the output and you will see a sine wave at the
frequency of the tuned LC circuit. The equation of the Fourier Series is
represented below.

f(t) = A0 + {[summation]|n=1 to infinity} An cos (nwt) +
{[summation]|n=1 to infinity} Bn sin (nwt)

where:

A0 = 1/Tp {[integral]-Tp/2 to Tp/2} f(t) dt

An = 2/Tp {[integral]-Tp/2 to Tp/2 f(t) cos (nwt) dt
and 
Bn = 2/Tp {[integral]-Tp/2 to Tp/2 f(t) sin (nwt) dt

A0  = amplitude of the main signal
An = amplitude of the odd harmonic
Bn = amplitude of the even harmonic
nw = nth. Harmonic frequencies

The series can be manipulated mathematically to become:

f(t) = {[summation]n=-infinity to infinity} = Dn{[exp]-jwt}

where:

	Dn = 1/Tp {[integral]-Tp/2 to Tp/2} f(t){[exp]-jnwt}dt

The Fourier Transform for analog data  is defined as:

F(jw) = {[integral]-infinity to infinity} f(t){[exp]-jwt}

The digital world uses discrete data rather than continuous data. To
represent data in discrete form, a sample and hold circuit is used to
capture continuous waveforms at specific time periods, known as sampling
periods. These voltage impulses are then quantized and encoded into bit
representations of 1’s and 0’s. This is now a digital representation
of the signal where the discrete fourier transform can now analyze the
frequency aspects of the discrete data. The formula for DFT is listed
below.

X(k) = Fd[x(nT)] = {[summation]n=0 to N-1}x(nT)[exp]-jk(Omega)nT 

		= {[summation]n=0 to N-1}x(nT)[exp]-jk2[pi]n/N
(simplified form)

where:  k=0,1,…N-1

The magnitude and phase angle is calculated as: 
    
|X(k)| = SQRT([R**2(k) + I**2(k)])
PHI(k) = [inverse]tan [I(k)/R(k)]

(Omega) = 2[pi]/NT
N = number of samples
T sampling period

Sometimes it is necessary to convert from the frequency domain to
discrete time domain. To do this we implement the Inverse DFT which is
listed below:

X(k) = Fd(inverse)[x(nT)] = 1/N{[summation]n=0 to N-1}x(k)[exp]
jk(Omega)nT

where:	n=0,1,…..,N-1

Here is an example of the DFT

Using the sampled interval [1001] we will compute the Discrete fourier
transform and its phase angle.

X(0) = {[summation] n=0 to 3}x(nT) [exp] -j0 = {[summation] n=0 to
3}x(nT)

= x(0) + x(T) + x(2T) + x(3T) = 1+0+0+1 = 2

X(1) = {[summation] n=0 to 3}x(nT) [exp] -j2[pi]n/N =
1+0+0+1[exp]-2[pi]3/4

 = 1+[exp]-j3[pi]/2 = 1+cos (3[pi]/2) - jsin(3[pi]/2) = 1+j

X(1) is complex with a magnitude of SQRT(2) and phase angle of
(inverse)tan(1) = 45 degrees

X(2) = {[summation] n=0 to 3}x(nT) [exp]-2n2[pi]/N =
1+0+0+1[exp]-j4[pi]3/4 = 1-1 = 0

X(3) = {[summation] n=0 to 3}x(nT) [exp] -j3n[pi]/N =
1+0+0+[exp]-j9[pi]/2 = 1-j

X(3) is complex with a magnitude of SQRT(2) and phase angle of
(inverse)tan(-1) = -45 degrees

There fore, the time series is {1,0,0,1} and the DFT frequency series
is: {2,1+j,0,1-j}.
To plot the magnitude versus the angular frequency, (Omega) we first
find Omega. To do this we must know the sampling rate and N. N  = 4 in
this case. Assuming a voice signal and sampled at 8KHz = 1/T, we have
the frequencies where the magnitudes are placed.

(Omega) = 12.57 kHz
2(Omega) = 25.14 kHz
3(Omega) = 37.71 kHz
4(Omega)  = 50.28 kHz

We also use these frequencies to plot the phase versus frequency as
well.

References

  1. Title: Digital Signal Processing A Practical Approach