Discrete Fourier Transform

Fourier theorem stated that any waveform can be made from combining series of sine waves.

This deals with infinite repeating waves.

In real world, we only deal with discrete values and have limited duration signals.

Mostly these inputs came from an ADC and sampled at fixed intervals.

Thus the Discrete Fourier Transform is derived from the orignal Fourier Transform and only deals with finite data.

DFT is the function in DSP to convert time-domain signals to its frequency-domain representation.

FFT (fast fourier transform) in the other hand is still DFT but using an alternate computation method that reduces the number of math operations and runs much faster.

I will discuss DFT first and FFT later.

If you remembered our lesson on CORRELATION, and the example to detect radar chirp, DFT is doing the same process.

It is just a multiple correlation for each frequency bin.

Thus, the resulting values corresponds to the signal level of each frequency composing the orignal signal.

The formula for DFT is:

In Python, it is done this way:

`########################################`

#DSP Tutorial

#DFT - Discrete Fourier Transform

#by: Regulus Berdin rberdin@gmail.com

########################################

from numpy import *

def my_dft(x):

N = len(x)

y = zeros(N) + 0j # y = [0,0,0....,0] N number of elements

k = arange(N) # k = [0,1,2,...,N-1]

for n in range(N):

#compute correlating factor

W = exp(-2j*pi*k*n/N)

#correlate with signal

y[n] = sum(x * W)

return y

The returned results from the DFT function will be the frequency spectrum where half of number of input samples correspond to half of the sampling frequency.

For example for a 64 samples at 8KHz, the 32nd output corresponds to 4KHz frequency bin and the 16th sample is the 2KHz bin.

The upper half of the results is just a mirrored image of the lower half.

The results also is a complex number that defines the amplitude and phase of the single sine wave component of the signal of this frequency.

---

Example, we would want to get the spectrum of 2 signals, 1Khz and 300 Hz.

`########################################`

#DSP Tutorial

#DFT - Discrete Fourier Transform

#by: Regulus Berdin rberdin@gmail.com

########################################

from numpy import *

from pylab import *

def my_dft(x):

N = len(x)

y = zeros(N) + 0j # y = [0,0,0....,0] N number of elements

k = arange(N) # k = [0,1,2,...,N-1]

for n in range(N):

#compute correlating factor

W = exp(-2j*pi*k*n/N)

#correlate with signal

y[n] = sum(x * W)

return y

#####

fs = 8000.0

N = 80

y = range(N)

t = arange(0,N/fs,1.0/fs)

f1 = 300

f2 = 1000

signal = 0.5*sin(2*pi*f1*t) + 0.25*sin(2*pi*f2*t)

spectrum = my_dft(signal)

#graph results

clf()

subplot(211)

plot(y, signal)

subplot(212)

plot(y, abs(spectrum))

show()

The graphed results are shown below:

The top graph shows the time-domain signals of the added 2 sine waves.

The lower portion is the resulting spectrum with half is mirrored.

If you have noticed, frequency bin 10 represents the 1KHz level while frequency bin 3 the 300Hz.

Frequency bin 40 is the Nyquist limit (sampling_freq/2) which is the mirror line of the frequency domain results.

Take note also of the levels of the two frequency bins. They are proportional to the levels of each respective added sine waves.

---

If you have questions or need clarification on the Python code or the DFT process, please post it here and I will answer it as I can.