Contents
DFT ( Discrete Fourier Transform )
The Discrete Time Fourier Tranform is a good way to analyze discrete time signals in the frequency domain in theory, but in application the infinite range of time and frequency in the conversion formulas can make analysis difficult, especially on the computer. The Discrete Fourier Transform is very similar to the DFT, but uses a finite time signal, allowing its formulas to be finite sums which a computer can easily calculate. Signals must be discrete and time-limited (or truncated) for use with the DFT. A discrete periodic signal can be used when only one period of the signal is analyzed. 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],\mbox{ }0 \le n < N \longleftrightarrow X[k] = 1,\mbox{ } 0 \le k < N $ both repeat with period N
- $ x[n] = 1,\mbox{ } 0 \le n < N \longleftrightarrow X[k] = N \delta [n],\mbox{ } 0 \le k < N $ both repeat with period N
- $ x[n] = e^{j2 \pi k_0n}, \mbox{ }0 \le n < N \longleftrightarrow X[k] = N \delta [k-k_0],\mbox{ } 0 \le k < N $ both repeat with period N
- $ x[n] = cos( \frac{2 \pi}{N} k_0n) \longleftrightarrow \frac{N}{2}(\delta [k-k_0] + \delta[k-(N-k_0)],\mbox{ } 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, which can cause some problems and inaccuracies.
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. $
