Next  |  Prev  |  Top  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

Linear Convolution of Short Signals

\begin{center}
\epsfig{file=eps/blackbox.eps,width=\textwidth } \\
\end{center}

Convolution theorem for DFTs:

$\displaystyle (h*x) \leftrightarrow H \cdot X
$

or

   DFT$\displaystyle _k(h*x)=H(\omega_k)X(\omega_k)
$

where $ h,x\in \mathbb{C}^N$ , and $ H$ and $ X$ are the $ N$ -point DFTs of $ h$ and $ x$ , respectively.

DFT performs circular (or cyclic) convolution:

$\displaystyle y(n) \;\mathrel{\stackrel{\mathrm{\Delta}}{=}}\;(x*h)(n) \;\mathrel{\stackrel{\mathrm{\Delta}}{=}}\;\sum_{m=0}^{N-1} x(m)h(n-m)_N
$

where $ (n-m)_N$ means ``$ (n-m)$ modulo $ N$ ''

Another way to look at this is as the inner product of $ x$ , and $ \hbox{\sc Shift}_n[\hbox{\sc Flip}(\overline{h})]$ , i.e.,

$\displaystyle y(n) = \langle x, \hbox{\sc Shift}_n[\hbox{\sc Flip}(\overline{h})] \rangle %
$



Subsections
Next  |  Prev  |  Top  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

Download ReviewFourier.pdf
Download ReviewFourier_2up.pdf
Download ReviewFourier_4up.pdf
[Comment on this page via email]

``Review of the Discrete Fourier Transform (DFT)'', by Julius O. Smith III, (From Lecture Overheads, Music 421).
Copyright © 2018-04-10 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA  [Automatic-links disclaimer]