Oct 31
The Discrete Fourier Transform
Or "putting it all together".
The formulas are
\[ A_k = \sum\limits_{n=0}^{N-1} x_n \, e^{\frac{2 \pi i}{N} n \, k } \]
\[ x_n = \frac{1}{N} \sum\limits_{k=0}^{N-1}{} A_k \, e^{- \frac{2 \pi i}{N} n \, k } \]
There are several variations depending on how you
define the normalization of A, which changes where the \( 1/N \) goes.
(Some people put \(\sqrt{\frac{1}{N}}\) on both equations to make them symmetric.)
N number of points, typically a power of 2 (8, 128, 1024)
x[n] [x0, x1, ...] time (or distance) samples, 0 <= n < N
A[k] [A0, A1, ...] frequency amplitudes, 0 <= k < N
(I will use A[k]=\( A_k \) instead of the wikipedia article's X[k],
since I think trying to keep "x" vs "X" as different variables
in the same equation is too confusing.)
Both \(x_n\) = x[n] and \(A_k\) = A[k] are cyclic in (n,k),
wrapping around at n=N and k=N.
For example x[0]=x[N], x[-1]=x[N-1], A[0]=A[N], A[-1]=A[N-1].
The frequencies go from a low at k=0 to a high at k=N/2,
with two (cos,sin) phases packed into the two complex
amplitudes on either side of N/2. For example with N=8
the frequency indices are
--- N = 8 ---
k = 0 (DC component, corresponds to x=[1,1,1,1,...]
k = 1 one full cycle from x[n=0] to x[n=N]
k = 2 two cycles
k = 3 three cycles
k = 4 (N/2, highest frequency, corresponds to x=[1,-1,1,-1,...])
k = 5 (k=-3, other phase of k=3)
k = 6 (k=-2, other phase of k=2)
k = 7 (k=-1, other phase of k=1)
Both x and A can be complex in these formulas. If x is real,
then the complex numbers in A have a particular symmetry,
namely \(A_k = A_{-k}^*\) where the * means "complex conjugate",
and where (-k) is (N-k).
- If A is real and \(A_k = A_{-k}\) then the complex exponentials add to give real cosines.
- If A is imaginary and \(A_k = - A_{-k}\) then the complex exponentials add to give real sines.
homework
Your mission for next week:
- implement these formulas in iPython, for some small values of N
- something like N = 4, N = 8, N = 16
- either explicitly with "for" loops, or implicitly with built-ins like the dot() function
- and some simple understandable functions like
- x[n] = 1 for all n (constant)
- x[n] = 0 except for one where (say) x[3] = 1 (spike or delta-function)
- x = [1, 1, 1, 1, 0 , 0, 0, 1, 1, 1, 1, ...] (square wave)
- ... or whatever you like.
- draw some plots of x, A, and the rows or columns of the transform matrix (the basis functions) to get some intuition.
This should give some notebooks like those we did in the first few weeks
of the term, but this time the transform matrix is coming from the formula,
with the complex exponentials giving the basis functions oscillating at different rates.
