| Line 25: | Line 25: | ||
For all <math>a,b</math> in the complex plane, and all <math>x_1[n],x_2[n]</math> with the same period N | For all <math>a,b</math> in the complex plane, and all <math>x_1[n],x_2[n]</math> with the same period N | ||
| − | <math>ax_1[n] + bx_2[n] \ | + | <math>ax_1[n] + bx_2[n] \longleftrightarrow aX_1[k] + bX_2[k]</math> |
| + | |||
'''Time-Shifting''' | '''Time-Shifting''' | ||
| Line 31: | Line 32: | ||
For all <math>n_0</math> included in Z, and all x[n] with period N | For all <math>n_0</math> included in Z, and all x[n] with period N | ||
| − | <math>x[n - n_0] \ | + | <math>x[n - n_0] \longleftrightarrow X[k]e^{-j \frac{2{\pi}}{N} n_0 k}</math> |
| + | |||
'''Modulation''' | '''Modulation''' | ||
| − | <math>x[n]e^{j \frac{2 \pi}{N}k_0n} \ | + | <math>x[n]e^{j \frac{2 \pi}{N}k_0n} \longleftrightarrow X[k-k_0]</math> |
| + | |||
'''Duality''' | '''Duality''' | ||
| − | <math>X[n] \ | + | <math>X[n] \longleftrightarrow Nx[-k]</math>, where X[n] is the DFT of a DFT |
| + | |||
'''Parseval's Relation''' | '''Parseval's Relation''' | ||
<math>\sum_{n=0}^{N-1} |x[n]|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X[k]|^2</math> | <math>\sum_{n=0}^{N-1} |x[n]|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X[k]|^2</math> | ||
| + | |||
'''Initial Value''' | '''Initial Value''' | ||
<math>\sum_{n=0}^{N-1} x[n] = X[0]</math> | <math>\sum_{n=0}^{N-1} x[n] = X[0]</math> | ||
| + | |||
'''Periodicity''' | '''Periodicity''' | ||
<math>X[k + N] = X[k]</math> for all k. X[k] is periodic with the same period N as x[n]. | <math>X[k + N] = X[k]</math> for all k. X[k] is periodic with the same period N as x[n]. | ||
| + | |||
'''Relation to DTFT''' | '''Relation to DTFT''' | ||
| Line 61: | Line 68: | ||
== Important DFT Pairs == | == Important DFT Pairs == | ||
| + | * <math>x[n] = \delta [n], 0 \le n < N \longleftrightarrow X[k] = 1, 0 \le k \le N</math> both repeat with period N | ||
| + | |||
| + | * <math>x[n] = 1, 0 \le n < N \longleftrightarrow X[k] = N \delta [n], 0 \le k < N</math> both repeat with period N | ||
| + | </math> | ||
| + | |||
| + | * <math>x[n] = e^{j2 \pi k_0n}, 0 \le n < N \longleftrightarrow X[k] = N \delta [k-k_0], 0 \le k < N</math> both repeat with period N | ||
| + | |||
| + | * <math>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</math> both repeat with period N | ||
Revision as of 07:37, 28 September 2009
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}}, 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}}, 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 $ included in Z, 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] = (^{x[n], n=0,...,N-1}_{0, else} $
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
</math>
- $ 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
