ine@mit software and mathematics

Deriving the DT Fourier Transform

In 18.03, we learned that any function can be written as a sum of sines and cosines of different frequencies.

where

This is the definition of a continuous time fourier series. The interesting thing is that there is another definition that can be reached for discrete time, and that Euler's formula e^iθ = cos θ + i sin θ can be used to make the math simpler. Using Euler's formula will also result in the possibility of having complex Fourier coefficients (the a's and b's in the formula). So (using Wikipedia's image):

gives the Fourier coefficients as T increases. In discrete time, we write it like this:

Where omega sub k is 2πk/N, and x[n] is the original input. So these expressions are expressing the same thing. This is how the DTFS (discrete time fourier transform) derives from the Fourier series. Read Wikipedia if you want a fuller explanation; I've glossed over some details on the restrictions on the functions and such.

Plotting X[k] gives the spectrum - a frequency sweep that shows how much of each frequency is present in any input function/signal. The original signal itself can also be written in terms of Fourier coefficients:

Nice, huh? Basically this is just the DT equivalent, saying that we can write an input signal as a weighted sum of exponentials, just as in CT we can write any input function as a sum of weighted sines and cosines (Euler's formula provides the relationship between sin/cos and e, of course). So, given this information, let's look at how to plot the spectrum for any input signal using Python (this is from my 6.02 lab 6.1):

1 # Return two numpy arrays, one containing frequencies, one containing
2 # magnitudes of frequency responses.
3 def freq_res_usr(usr, num_freqs):
4     freqs, mags = [], []
5     #we choose arbitrary frequencies and calulate the magnitude of the resp
6     for f in range(num_freqs):
7         freq = 2.0*math.pi * (float(f)/float(num_freqs)) - math.pi
8         sum = complex(0, 0)
9         #for this freq, what is the magnitude of the usr?
10         for m in range(len(usr)):
11            sum += usr[m] * (math.e**(-complex(0, 1)*freq*m))
12        mags.append(abs(sum))
13        freqs.append(freq)
14    return (freqs, mags)

In line 7, we choose what frequency we are going to calculate (omega sub k). In lines 10-11, for all of the items in the input signal, we sum the individual item multiplied by e^(-i * freqency * index). Really simple actually, but a very powerful result. I'll go over why this actually useful in the next post.