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


Downsampling Theorem (Aliasing Theorem)



Theorem: For all $ x\in{\bf C}^N$ ,

$\displaystyle \zbox {\hbox{\sc Downsample}_L(x) \;\longleftrightarrow\;\frac{1}{L}\hbox{\sc Alias}_L(X).}
$



Proof: Let $ k^\prime \in[0,M-1]$ denote the frequency index in the aliased spectrum, and let $ Y(k^\prime )\isdef \hbox{\sc Alias}_{L,k^\prime }(X)$ . Then $ Y$ is length $ M=N/L$ , where $ L$ is the downsampling factor. We have

\begin{eqnarray*}
Y(k^\prime ) &\isdef & \hbox{\sc Alias}_{L,k^\prime }(X)
\isdef \sum_{l=0}^{L-1}X(k^\prime +lM), \quad k^\prime =0,1,2,\ldots,M-1 \\ [5pt]
&\isdef & \sum_{l=0}^{L-1}\sum_{n=0}^{N-1}x(n) e^{-j2\pi(k^\prime +lM)n/N} \\ [5pt]
&\isdef & \sum_{n=0}^{N-1}x(n) e^{-j2\pi k^\prime n/N}
\sum_{l=0}^{L-1}e^{-j2\pi l n M/N}.
\end{eqnarray*}

Since $ M/N=1/L$ , the sum over $ l$ becomes

$\displaystyle \sum_{l=0}^{L-1}\left[e^{-j2\pi n/L}\right]^l =
\frac{1-e^{-j2\pi n}}{1-e^{-j2\pi n/L}}
= \left\{\begin{array}{ll}
L, & n=0 \left(\mbox{mod}\;L\right) \\ [5pt]
0, & n\neq 0 \left(\mbox{mod}\;L\right) \\
\end{array} \right.
$

using the closed form expression for a geometric series derived in §6.1. We see that the sum over $ L$ effectively samples $ x$ every $ L$ samples. This can be expressed in the previous formula by defining $ m\isdeftext n/L$ which ranges only over the nonzero samples:

\begin{eqnarray*}
\hbox{\sc Alias}_{L,k^\prime }(X) &=& \sum_{n=0}^{N-1}x(n) e^{-j2\pi k^\prime n/N} \sum_{l=0}^{L-1}e^{-j2\pi l n /L} \\
&=& L\sum_{m=0}^{N/L-1} x(mL) e^{-j2\pi k^\prime (m L) /N}\qquad(m\isdef n/L) \\
&\isdef & L\sum_{m=0}^{M-1}x(mL) e^{-j2\pi k^\prime m /M}\\
&\isdef & L\sum_{m=0}^{M-1}\hbox{\sc Downsample}_{L,m}(x) e^{-j2\pi k^\prime m /M} \\
&\isdef & L\cdot \hbox{\sc DFT}_{k^\prime }(\hbox{\sc Downsample}_L(x))
\end{eqnarray*}

Since the above derivation also works in reverse, the theorem is proved.

An illustration of aliasing in the frequency domain is shown in Fig.7.12.



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

[How to cite this work]  [Order a printed hardcopy]  [Comment on this page via email]

``Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications --- Second Edition'', by Julius O. Smith III, W3K Publishing, 2007, ISBN 978-0-9745607-4-8.
Copyright © 2014-04-06 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA