\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{3}

% title command
\newcommand{\mytitle}[1]{\begin{center} {\Large Computation Structures -- 
6.004 Problem Set \psnum \\ Juliet Bourne -- #1} \\ \vspace{-.1in} 
\rule{6in}{.5mm} \end{center}}
% problem command
\newcommand{\prob}[1]{\vspace{.15in}\noindent{\fbox{\large\bf Problem #1}}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}
% newpage setup command 
\newcommand{\mynewpage}{\newpage\noindent
\begin{center}
{\Large 6.004 Problem Set \psnum -- Juliet Bourne -- {\bf Page \thepg}}
\rule{6in}{.5mm}
\end{center}
\addtocounter{pg}{1}}
% see-page command
\newcommand{\seepage}{\noindent See page \rule{.2in}{.1mm} for the
computer output.}

\begin{document}

\mytitle{10/03/90}

\prob{1: {\em Clock Skew}}

\subprob{A}

\vspace{3in}
\special{psfile=sketch1.ps}

\subprob{B} $T \geq t_{cq} + t_{su} + t_{pd}$

\subprob{C} $T \geq t_{cq} + t_{su} + t_{pd}$ \hspace{.1in} $
t_{skew} \leq t_{cq} + t_{pd} - t_{cd-inv}$

\subprob{D}

\vspace{3in}
\special{psfile=sketch2.ps}

\mynewpage

\prob{2: {\em Metastability}}

There are three stable output voltage points and two metastable ones.

\vspace{5in}

\prob{3: {\em State-Transition Diagram}}

\subprob{A}

\begin{center}
\begin{tabular}{c|c|c} \hline
State & Output & Input $\rightarrow$ State \\ \hline
A & 0 & 0 $\rightarrow$ C \\
C & 1 & 0 $\rightarrow$ D \\
D & 1 & 1 $\rightarrow$ B \\
B & 0 & 1 $\rightarrow$ C \\
C & 1 & 0 $\rightarrow$ D \\
D & 1 & \mbox{} \\ \hline
\end{tabular}
\end{center}

\subprob{B} Only a string of all 1's will result in an output string
of all 0's, when starting in state A.

\subprob{C} There are 4 (or $2^2$) states. Therefore, 2 state
variables are needed.

\mynewpage 

\subprob{D} A = 00, B = 01, C = 10, D = 11

\begin{center}
\begin{tabular}{cc|cc||cc|cc} \hline
\multicolumn{2}{c|}{Input} & \multicolumn{2}{c||}{Output} & 
\multicolumn{2}{c|}{Input} & \multicolumn{2}{c}{Output} \\ \hline
$l$ & $S_1 S_0$ & $O$ & $S^{'}_1 S^{'}_0$ & 
$l$ & $S_1 S_0$ & $O$ & $S^{'}_1 S^{'}_0$ \\ \hline
0 & 0 0 & 0 & 1 0 & 0 & 1 0 & 1 & 1 1 \\
1 & 0 0 & 0 & 0 0 & 1 & 1 0 & 1 & 0 0 \\
0 & 0 1 & 0 & 0 0 & 0 & 1 1 & 1 & 0 1 \\
1 & 0 1 & 0 & 1 0 & 1 & 1 1 & 1 & 0 1 \\ \hline
\end{tabular}
\end{center}

\subprob{E}

\vspace{2.5in}
\special{psfile=sketch3.ps}

\subprob{F}

\vspace{4in}
\special{psfile=flops.ps}

\mynewpage

\prob{4: {\em Mobile Robots}}

\subprob{A}

\vspace{1.5in}
\special{psfile=fsm1.ps}

\subprob{B}

\vspace{2.5in}
\special{psfile=fsm2.ps}

\subprob{C}

\begin{center}
\begin{tabular}{ccc|cc||ccc|cc}\hline
\multicolumn{3}{c|}{Input} & \multicolumn{2}{c||}{Output} & 
\multicolumn{3}{c|}{Input} & \multicolumn{2}{c}{Output} \\ \hline
$L$ & $T$ & $S_1 S_0$ & $M_1 M_0$ & $S^{'}_1 S^{'}_0$ & 
$L$ & $T$ & $S_1 S_0$ & $M_1 M_0$ & $S^{'}_1 S^{'}_0$ \\ \hline
0 & 0 & 0 0 & 0 0 & 0 0 & 0 & 0 & 1 0 & 1 0 & 0 0 \\
0 & 1 & 0 0 & 0 0 & 0 0 & 0 & 1 & 1 0 & 1 0 & 0 0 \\
1 & 0 & 0 0 & 0 0 & 0 1 & 1 & 0 & 1 0 & 1 0 & 0 1 \\
1 & 1 & 0 0 & 0 0 & 0 1 & 1 & 1 & 1 0 & 1 0 & 1 0 \\ \hline
0 & 0 & 0 1 & 1 1 & 0 0 & 0 & 0 & 1 1 & 0 1 & 0 0 \\
0 & 1 & 0 1 & 1 1 & 0 0 & 0 & 1 & 1 1 & 0 1 & 0 0 \\
1 & 0 & 0 1 & 1 1 & 0 1 & 1 & 0 & 1 1 & 0 1 & 0 1 \\
1 & 1 & 0 1 & 1 1 & 1 0 & 1 & 1 & 1 1 & 0 1 & 1 0 \\ \hline
\end{tabular}
\end{center}

\subprob{D} $2^2$ bits for the Light and Touch inputs. $2^2$ bits for
the current state. $2^2$ bits for the Motion outputs. $2^2$ bits for
the next state. Therefore, the ROM must have a total of $4 \cdot 2^2 =
16$ bits of storage.

\subprob{E} Previously labelled state 0 remains the same; both outputs
are 0. Previously labelled state 1 is now state 3 or 11 in binary.
Previously labelled state 2 remains the same; its outputs are 10 in
binary. Previously labelled state 3 is now state 1 or 01 in binary.

\mynewpage

\begin{center}
\begin{tabular}{cc|c|c||cc|c|c}\hline
\multicolumn{2}{c|}{Input} & State/Output & Next State & 
\multicolumn{2}{c|}{Input} & State/Output & Next State \\ \hline
$L$ & $T$ & $M_1 M_0$ & $S^{'}_1 S^{'}_0$ & 
$L$ & $T$ & $M_1 M_0$ & $S^{'}_1 S^{'}_0$ \\ \hline
0 & 0 & 0 0 & 0 0 & 0 & 0 & 1 0 & 1 1 \\
0 & 1 & 0 0 & 1 0 & 0 & 1 & 1 0 & 1 0 \\
1 & 0 & 0 0 & 0 1 & 1 & 0 & 1 0 & 1 1 \\
1 & 1 & 0 0 & 1 0 & 1 & 1 & 1 0 & 1 0 \\ \hline
0 & 0 & 0 1 & 0 0 & 0 & 0 & 1 1 & 0 0 \\
0 & 1 & 0 1 & 1 0 & 0 & 1 & 1 1 & 1 0 \\
1 & 0 & 0 1 & 0 1 & 1 & 0 & 1 1 & 0 1 \\
1 & 1 & 0 1 & 1 0 & 1 & 1 & 1 1 & 1 0 \\ \hline
\end{tabular}
\end{center}

This only requires $2^2 + 2^2 + 2^2 = 12$ bits of storage.

\subprob{F} The state-transition diagram for the restless cockroach
should look like this:

\vspace{5in}

\subprob{G} Applications could include be obstacle avoidance,
shadow-detection, and light-detection. The cockroach might be able to
cross an area (with obstacles and dark and light areas) with the least
detection (or time spent in the light).

\end{document}
