2.15 Lecture 15, Wed March 17, 2010

HW4 key solution handed in.

Handout D handed in (4th handout). This lecture was mainly about 2 things: Periodic convolution, and DFT.

If we have a sequence of numbers, we can find the DFT (Discrete Fourier Transform) of this sequence. We assume the sequence of numbers repeat (just for convenience). Write little delta over \(x\) to indicate periodic. These are the definitions to know

\begin{align*} \tilde{x}(n) & = \frac{1}{N} \sum \limits _{k=0}^{N-1} \tilde{X}(k) e^{j\left ( \frac{2\pi }{N} \right ) n k} \qquad n=0\cdots N-1\\ \tilde{X}\left ( k\right ) & = \sum \limits _{n=0}^{N-1} \tilde{x}\left ( n\right ) e^{-j\left ( \frac{2\pi }{N}\right ) nk} \qquad k=0\cdots N-1 \end{align*}

\(N\) is the length of the sequence \(\tilde{x}(n)\) and \(\tilde{X}(k)\) is the DFT of \(\tilde{x}(n)\).

One important thing to know: If we find the \(Z\) transform of \(\tilde{x}(n)\), then sampling the Z transform around the unit circle, we get the values of each \(\tilde{X}(k)\).

How to sample the Z transform? start from zero angle and move anticlockwise for an angle \(\theta \) where \(\theta =\frac{2\pi }{N}\) and read the Z transform at that polar coordinate. This gives values of \(\tilde{X}(k)\). So \(\tilde{X}(0)\) is Z transform of \(\tilde{x}(n)\) at angle zero, and \(\tilde{X}(1)\) is Z transform of \(\tilde{x}(n)\) at angle \(\frac{2\pi }{N}\) and \(\tilde{X}(2)\) is Z transform at the angle \(2 \frac{2\pi }{N}\) and so on

Then went over properties of \(\tilde{x}(n)\), but we are really more interested in properties of \(\tilde{X}(k)\).

Went over example of periodic convolution (might be on second midterm).

It is easier than linear convolution, since both sequences will always start at \(n=0\) and have the same period. So, just flip one, and remember to only look at one period.

FFT is just an implementation to determine DFT.

Most use of FFT is for doing fast convolution. We studies FFT is details in EE 518 that I took last year.

This was the end of this lecture.