Page MenuHomec4science

90-examples.tex
No OneTemporary

File Metadata

Created
Thu, Mar 13, 14:15

90-examples.tex

\section{Examples}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{example}[Discrete time in the Far West]
\label{sed:dt:wagonwheel}\index{wagonwheel effect|mie}
\index{wagon wheel effect} \index{complex exponential!aliasing}
The fact that the ``fastest'' digital frequency is $2\pi$ can be readily appreciated when watching an old movie, and in particular a good old western. Consider the classic scene of a stagecoach leaving town: the wagon's spoked wheels start to turn forward, faster and faster as the coach gains speed, but then they appear to stop and to start turning backwards. The phenomenon is known as ``the wagonwheel effect'' and it is an instance of a digital angular frequency wrapping around its possible maximum value.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[t]
\center
\def\wheel#1#2{
\pscircle(#1,50){#2}
}
\def\spokes#1#2#3#4{
\def\a{#3}
\def\c{#1}
\def\r{#2}
\FPupn\xa{\r{} \a{} sin mul \c{} add}
\FPupn\xb{-\r{} \a{} sin mul \c{} add}
\FPupn\ya{\r{} \a{} cos mul 50 add}
\FPupn\yb{-\r{} \a{} cos mul 50 add}
\psline[#4](\xa, \ya)(\xb, \yb)
\FPupn\xa{-\r{} \a{} cos mul \c{} add}
\FPupn\xb{\r{} \a{} cos mul \c{} add}
\FPupn\ya{\r{} \a{} sin mul 50 add}
\FPupn\yb{-\r{} \a{} sin mul 50 add}
\psline[#4](\xa, \ya)(\xb, \yb)
\ifx&#4&
\qdisk(\xb, \yb){2pt}
\else
\relax
\fi
}
\psset{unit=0.4mm, linewidth=1pt}
\framebox{
\begin{pspicture}(0, 0)(300, 100)
\wheel{50}{30}
\spokes{50}{30}{0}{}
\wheel{150}{30}
\spokes{150}{30}{0}{linecolor=gray}
\spokes{150}{30}{-0.2}{}
\wheel{250}{30}
\spokes{250}{30}{0}{linecolor=lightgray}
\spokes{250}{30}{-0.2}{linecolor=gray}
\spokes{250}{30}{-0.4}{}
\end{pspicture}}
\vspace{2em}
\framebox{
\begin{pspicture}(0, 0)(300, 100)
\wheel{50}{30}
\spokes{50}{30}{0}{}
\wheel{150}{30}
\spokes{150}{30}{0}{linecolor=gray}
\spokes{150}{30}{-1.4}{}
\wheel{250}{30}
\spokes{250}{30}{0}{linecolor=lightgray}
\spokes{250}{30}{-1.4}{linecolor=gray}
\spokes{250}{30}{-2.8}{}
\end{pspicture}}
\caption{Forward motion (top panel, $\omega_0 = \pi/15$) and apparent backward motion (bottom panel, $\omega_0 = 0.9\,\pi/2$).}
\label{fig:dt:wagonwheel}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
To better understand the phenomenon, remember that each frame in the film is a static snapshot of a rotating wheel. In stationary conditions (i.e., the wheel's motion is constant) if the angular speed of the wheel is $\omega_0$ radians per second, and if the frame rate of the movie is $F$ frames per second, the angular displacement between two successive frames is $\Delta = \omega_0/F$.
If the wheel has $K$ spokes (and has perfect circular symmetry), two wheel positions $2\pi/K$ radians apart will be undistinguishable. That gives us a first upper limit on the maximum angular speed of
\[
\omega_1 < 2\pi \frac{F}{K} \quad \mbox{rad/sec}
\]
Things are however slightly more complicated because of the perceptual mechanisms of the human visual system. The illusion of movement in motion pictures relies on the brain's ability to ``fill in the gaps'' between successive static images provided that the images come fast enough: anything below approximately~12 frames per second will not create the illusion of motion. The full mechanism at work is very complex but one of the underlying principles is that the brain will apply a ``plausibility test'' to the virtual motion and go with the most realistic hypothesis. When looking at a revolving spoked wheel, the brain will perceive a rotation in the direction that minimizes the apparent motion of the spokes between successive frames. So, for small angular displacements as in the top panel of Figure~\ref{fig:dt:wagonwheel} the motion will appear counterclockwise; for displacements larger than $\omega_1/2$, on the other hand, the motion will appear clockwise as in the bottom panel of Figure~\ref{fig:dt:wagonwheel}. In both figures, the current position is drawn in black and previous position are drawn in progressively lighter shades of gray; the current position for the reference spoke is indicated by a dot. This observation gives us a second upper limit on the maximum angular speed for ``forward'' motion:
\[
\omega_1 < \pi \frac{F}{K} \quad \mbox{rad/sec}
\]
In practice things are actually a bit more complicated still. For instance, when the angular speed is equal to $\omega_1$ above, the perceived image may be that of a stationary wheel with twice the number of spokes, i.e., the preferred interpretation on the part of the brain is to superimpose two successive frames into a slightly blurred but still image rather than postulating such a wide motion. The net effect is that, at speeds close to $\omega_1$, the wheel appears to have twice the number of spokes and therefore the maximum forward speed is $\omega_2 = \omega_1/2$.
Finally, consider a ``real'' wheel with a diameter of $d$ meters. The linear speed of the wagon for an angular speed of $\omega_2$ is
\[
v = \frac{d}{2}\, \frac{\pi}{2}\, \frac{F}{K}
\]
For an 8-spoke wheel with a diameter of one meter in a movie shot at 24fps, the maximum forward velocity is reached when the wagon travels at approximately 8~Km/h. Since the apparent forward/backward switch in rotation takes place each time the angular velocity reaches a multiple of $\omega_2$, by the time the stagecoach reaches full speed the wagonwheel effect has happened several times.
\end{example}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{example}{Building periodic signals}\label{sec:dt:periodization}\index{periodization|mie}
Given an infinite sequence $\mathbf{x}$ and an integer $N > 0$ we can always formally write
\begin{equation}\label{eq:dt:periodization}
\tilde{\mathbf{y}} = \sum_{k=-\infty}^{\infty} \mathcal{D}_{kN} \bigl\{\mathbf{x}\bigr\}
\end{equation}
or, explicitly,
\[
\tilde{y}[n] = \sum_{k=-\infty}^{\infty} x[n - kN]
\]
The signal $\tilde{\mathbf{y}}$, if it exists, is an $N$-periodic sequence, {}``manufactured''{} by superimposing infinite copies of the original signal spaced $N$~samples apart. We can distinguish three cases:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[p]
\center
\begin{dspPlot}[height=\dspHeightCol,xticks=10]{-40,40}{0,1.2}
\dspSignal[linecolor=ColorDT]{x \dspTri{0}{10}}
\end{dspPlot}
\begin{dspPlot}[height=\dspHeightCol,xticks=10]{-40,40}{0,1.2}
\dspSignalOpt[linecolor=ColorDT]{/S 35 def}{0 -5 1 5 {S mul x add \dspTri{0}{10} add} for}
\end{dspPlot}
\begin{dspPlot}[height=\dspHeightCol,xticks=10]{-40,40}{0,1.2}
\dspSignalOpt[linecolor=ColorDT]{/S 19 def}{0 -5 1 5 {S mul x add \dspTri{0}{10} add} for}
\end{dspPlot}
\begin{dspPlot}[height=\dspHeightCol,xticks=10]{-40,40}{0,1.2}
\dspSignalOpt[linecolor=ColorDT]{/S 15 def}{0 -5 1 5 {S mul x add \dspTri{0}{10} add} for}
\end{dspPlot}
\caption{Periodization of a simple finite-support signal (support length $L=19$); original signal (top panel) and
periodized versions with $N = 35 > L$, $N = 19 = L$, $N = 15 < L$ respectively.}\label{fig:dt:periodization}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}
\item If $\mathbf{x}$ is finite-support and $N$ is larger than the size of the support, then the copies in the sum do not overlap, as illustrated in the second panel of Figure~\ref{fig:dt:periodization}; when $N$ is exactly equal to the size of the support, then $\tilde{\mathbf{y}}$ corresponds to the periodic extension of the nonzero part of the signal, as shown in the third panel of Figure~\ref{fig:dt:periodization}.
\item If $\mathbf{x}$ is finite-support and $N$ is smaller than the size of the support then the copies in the sum do overlap and the shape of the periodized signal will no longer match the shape of the original, as illustrated in the last panel of Figure~\ref{fig:dt:periodization}; since, for each $n$, the value of $\tilde{y}[n]$ is the sum of a finite number of terms, the periodized signal always exists.
\item If $\mathbf{x}$ has infinite support, then each value of $\tilde{\mathbf{y}}$ is the sum of an infinite number of terms and therefore the periodized signal only exists if the sum converges; a sufficient condition for this to happen is that the original sequence be absolutely summable. An example is shown in Figure~\ref{fig:dt:periodizationExp} for an exponential decay of the form $x[n] = \alpha^{-n}\, u[n]$. The periodization formula yields
\[
\tilde{y}[n] = \sum_{k=-\infty}^{\infty} \alpha^{-(n - kN)}u[n-kN] = \sum_{k=-\infty}^{\lfloor n/N \rfloor} \alpha^{-(n - kN)}
\]
since $u[n-kN] = 0$ for $k \geq \lfloor n/N \rfloor$. Now write $n = mN + i$ with $m = \lfloor n/N \rfloor$ and $i = n \mod N$ to obtain
\[
\tilde{y}[n] = \sum_{k=-\infty}^{m} \alpha^{-(m - k)N -i} = \alpha^{-i} \sum_{h=0}^{\infty} \alpha^{-hN};
\]
for $|\alpha|>1$ the sum converges to
\[
\tilde{y}[n] = \frac{ \alpha^{-(n \mod N)}}{1 - \alpha^{-N}}
\]
which is indeed $N$-periodic.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[t]
\center
\def\period{21 }
\def\alphaVal{1.1 }
\begin{dspPlot}[height=\dspHeightCol,xticks=10]{-40,40}{0,1.4}
\dspSignal[linecolor=ColorDT]{x 0 ge {\alphaVal x neg exp} {0} ifelse}
\end{dspPlot}
\begin{dspPlot}[height=\dspHeightCol,xticks=10]{-40,40}{0,1.4}
\dspSignal[linecolor=ColorDT]{\alphaVal x x \period div floor \period mul sub neg exp
1 \alphaVal -\period exp sub
div}
\end{dspPlot}
\caption{Periodization of $x[n] = (\alphaVal)^{-n}\,u[n]$ with $N = \period$; original signal (top panel) and
periodized version (bottom panel).}\label{fig:dt:periodizationExp}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{example}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Further Reading}
\textit{The} reference on discrete-time signals is undoubtedly the classic \textit{Discrete-Time Signal Processing\/},
by A.\ V.\ Oppenheim and R.\ W.\ Schafer (Prentice-Hall, last edition in 1999). Other books of interest for an introductory overview include: B. Porat, \textit{A Course in Digital Signal Processing\/} (Wiley, 1997) and R. L. Allen and D. W. Mills' \textit{Signal Analysis\/} (IEEE Press, 2004).

Event Timeline