Contents
DFT ( Discrete Fourier Transform )
The DFT is a finite sum, so it can be computed using a computer. Used for discrete, time-limited signals, or discrete periodic signals. The DFT of a signal will be discrete and have a finite duration.
Definition
DFT
- $ X(k) = \sum_{n=0}^{N-1}{x[n]e^{-j \frac{2{\pi}}{N}kn}}, \mbox{ }k = 0, 1, 2, ..., N-1 $
Inverse DFT (IDFT)
- $ x[n] = \frac{1}{N}\sum_{k=0}^{N-1}{X(k)e^{j \frac{2{\pi}}{N}kn}}, \mbox{ }n = 0, 1, 2, ..., N-1 $
Properties
Linearity
For all $ a,b $ in the complex plane, and all $ x_1[n],x_2[n] $ with the same period N
$ ax_1[n] + bx_2[n] \longleftrightarrow aX_1[k] + bX_2[k] $
Time-Shifting
For all $ n_0 $ , and all x[n] with period N
$ x[n - n_0] \longleftrightarrow X[k]e^{-j \frac{2{\pi}}{N} n_0 k} $
Modulation
$ x[n]e^{j \frac{2 \pi}{N}k_0n} \longleftrightarrow X[k-k_0] $
Duality
$ X[n] \longleftrightarrow Nx[-k] $, where X[n] is the DFT of a DFT
Parseval's Relation
$ \sum_{n=0}^{N-1} |x[n]|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X[k]|^2 $
Initial Value
$ \sum_{n=0}^{N-1} x[n] = X[0] $
Periodicity
$ X[k + N] = X[k] $ for all k. X[k] is periodic with the same period N as x[n].
Relation to DTFT
$ X[k] = Y(k \frac{ 2 \pi}{N}) $ where Y(w) is the DTFT of signal $ y[n] = \left\{ \begin{array}{c l} x[n] & n=0,...,N-1 \\ 0 & \mbox{ else} \end{array} \right. $
Important DFT Pairs
- $ x[n] = \delta [n], 0 \le n < N \longleftrightarrow X[k] = 1, 0 \le k \le N $ both repeat with period N
- $ x[n] = 1, 0 \le n < N \longleftrightarrow X[k] = N \delta [n], 0 \le k < N $ both repeat with period N
- $ x[n] = e^{j2 \pi k_0n}, 0 \le n < N \longleftrightarrow X[k] = N \delta [k-k_0], 0 \le k < N $ both repeat with period N
- $ x[n] = cos( \frac{2 \pi}{N} k_0n) \longleftrightarrow \frac{N}{N}(\delta [k-k_0] + \delta[l-(N-k_0)], 0 \le k < N $ both repeat with period N
Spectral Analysis via DFT
There are two sources of inaccuracies in the spectral analysis of a DFT signal. These are leakage, which is caused by signal truncation, and the picket fence effect, which is caused by frequency sampling.
Leakage is caused by the convolution by the DTFT of a window function, which is a sinc. This causes copies of the original spectrum with decreasing amplitude to be placed next to the original spectrum. A graphic analysis of this can be seen in Some material for the lecture on DFT (re:leakage effect).
The picket fence effect is caused by samples of a signal not necessarily occurring at important points, such as local maximums and minimums. Only the points that are sampled are available for data.
There is a reconstruction formula to obtain the DTFT of the truncated x[n] from the DFT. It assumes $ x_p[n] $ is the periodic repetition (with period N, the duration of x[n]) of x[n]. The formula is $ X_{tr}(w) = \sum_{k=0}^{N-1} X[k]P(w - \frac{2 \pi}{N}k) $, where $ P(w) = \left\{ \begin{array}{c l} 1 & \mbox{if }w \mbox{ a multiple of 2}\pi \\ \frac{sin(w \frac{N}{2})}{Nsin( \frac{N}{2})} & \mbox{ else} \end{array} \right. $
