(12 intermediate revisions by one other user not shown)
Line 1: Line 1:
 
[[Category:ECE438Fall2009mboutin]]
 
[[Category:ECE438Fall2009mboutin]]
 +
[[Category:discrete Fourier transform]]
  
 
== DFT ( Discrete Fourier Transform ) ==
 
== 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.
+
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 calculateSignals 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.
  
 
----
 
----
Line 11: Line 12:
  
 
'''DFT'''  
 
'''DFT'''  
*<math>X(k) = \sum_{n=0}^{N-1}{x[n]e^{-j \frac{2{\pi}}{N}kn}},  k = 0, 1, 2, ..., N-1</math>
+
*<math>X[k] = \sum_{n=0}^{N-1}{x[n]e^{-j \frac{2{\pi}}{N}kn}}, \mbox{ }k = 0, 1, 2, ..., N-1</math>
  
 
'''Inverse DFT (IDFT)'''  
 
'''Inverse DFT (IDFT)'''  
*<math>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</math>
+
*<math>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</math>
  
 
----
 
----
Line 22: Line 23:
  
 
'''Linearity'''
 
'''Linearity'''
 +
 
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] \longleftarrow zX_1[k] + bX_2[k]</math>
+
<math>ax_1[n] + bx_2[n] \longleftrightarrow aX_1[k] + bX_2[k]</math>
 +
 
 +
 
 +
'''Time-Shifting'''
 +
 
 +
For all <math>n_0</math> , and all x[n] with period N
 +
 
 +
<math>x[n - n_0] \longleftrightarrow X[k]e^{-j \frac{2{\pi}}{N} n_0 k}</math>
 +
 
 +
 
 +
'''Modulation'''
 +
 
 +
<math>x[n]e^{j \frac{2 \pi}{N}k_0n} \longleftrightarrow X[k-k_0]</math>
 +
 
 +
 
 +
'''Duality'''
 +
 
 +
<math>X[n] \longleftrightarrow Nx[-k]</math>, where X[n] is the DFT of a DFT
 +
 
 +
 
 +
'''Parseval's Relation'''
 +
 
 +
<math>\sum_{n=0}^{N-1} |x[n]|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X[k]|^2</math>
 +
 
 +
 
 +
'''Initial Value'''
 +
 
 +
<math>\sum_{n=0}^{N-1} x[n] = X[0]</math>
 +
 
 +
 
 +
'''Periodicity'''
 +
 
 +
<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'''
 +
 
 +
<math>X[k] = Y(k \frac{ 2 \pi}{N})</math> where Y(w) is the DTFT of signal
 +
<math>y[n] = \left\{
 +
\begin{array}{c l}
 +
  x[n] & n=0,...,N-1 \\
 +
  0 & \mbox{ else}
 +
\end{array}
 +
\right.</math>
 +
 
 +
----
 +
 
 +
== Important DFT Pairs ==
 +
 
 +
* <math>x[n] = \delta [n],\mbox{  }0 \le n < N \longleftrightarrow X[k] = 1,\mbox{  } 0 \le k < N</math> both repeat with period N
 +
 
 +
* <math>x[n] = 1,\mbox{  } 0 \le n < N \longleftrightarrow X[k] = N \delta [n],\mbox{  } 0 \le k < N</math> both repeat with period N
 +
 
 +
* <math>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</math> both repeat with period N
 +
 
 +
* <math>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</math> 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 [[ECE_438_Fall_2009_mboutin_DFT_lecture_material|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 <math>x_p[n]</math> is the periodic repetition (with period N, the duration of x[n]) of x[n].  The formula is <math>X_{tr}(w) = \sum_{k=0}^{N-1} X[k]P(w - \frac{2 \pi}{N}k)</math>, where
 +
<math>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.</math>
 +
 
 +
 
 
[[ECE438_(BoutinFall2009)|Back to ECE438 course page]]
 
[[ECE438_(BoutinFall2009)|Back to ECE438 course page]]

Latest revision as of 05:46, 23 September 2011


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. $


Back to ECE438 course page

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett