\documentstyle{article}

\newcommand{\nl}{\vspace{10 mm}}

\begin{document}

\section{Homework Assignment \# 0:  Wire World!}

For this assignment, you will program in Wire World, an idealized 
environment of wires and transistor logic.  Here's how it all works:

\begin{itemize}
\item First, there are wires.  Wires are assumed to have just two states
(in real wires, corresponding to two different voltage levels) which we
will call ``0'' and ``1''.  Wires propagate their state instantaneously
from left to right.

Wires are allowed to cross without affecting each other.  Draw that like
this:

\nl

\item Next, there are {\em not-gates}, which look like this:

\nl

A not-gate reverses the state of a wire, or more precisely, if the wire on
the left of a not-gate is 0, then the wire on the right will be 1 and if
the wire on the life of a not-gate is 1, then the wire on the right will be
0.  Logicians and electricians find it convenient to summarize the affect of
a not-gate in the following ``truth table'':

\begin{tabular}{c|c}
left wire & right wire = NOT left wire \\
\hline
0 & 1 \\
1 & 0
\end{tabular}

\item The most important element of Wire World is the {\em and-gate}.  They
look like this:

\nl

As you can see, and-gates take two input wires on the left and output one
wire on the right.  The basic idea is that the right wire will be 1 if both
of the two left wires are 1, and 0 otherwise.  This is summarized in the
truth table

\begin{tabular}{cc|c}
left wire 1 & left wire 2 & right wire = left wire 1 AND left wire 2 \\
\hline
0 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1
\end{tabular}

[In real life, and-gates are computed by transistors (and before that, vacuum
tubes!)]

\item Finally, there are splits:

\nl

All splits do is copy the state of the left wire into the states of the
two right wires.

\item Actually, I lied.  There is one last thing to know about Wire World,
something which doesn't actually {\em do} anything but is extremely useful
none the less.  It is called {\em abstraction}, and is merely the convention
that whenever you have created a bunch of wires and gates that you think
does something useful, you are allowed to draw dotted lines around it
and give it a name.  Then, in future drawings, you don't have to draw it all
over but instead can just a box (representing an integrated circuit or
``chip'') with the right number of input and output wires sticking out and
its name in the middle:

\nl

Abstraction makes your wire diagrams easier to understand, easier to draw,
and easier to create!   Use it!

\end{itemize}

\section{Problems}

\begin{enumerate}

\item  Draw a wire diagram that implements OR:

\begin{tabular}{cc|c}
left wire 1 & left wire 2 & right wire = left wire 1 OR left wire 2 \\
\hline
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 1 
\end{tabular}

[OR is used so often that it is convenient to give it its own shape:

\nl

\item Draw a wire diagram that implements XOR:

\begin{tabular}{cc|c}
left wire 1 & left wire 2 & right wire = left wire 1 XOR left wire 2 \\
\hline
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 
\end{tabular}

\item Draw a wire diagram that implements 1:

\begin{tabular}{c|c}
left wire & right wire = 1 \\
\hline
0 & 1 \\
1 & 1 
\end{tabular}

\item Draw a wire diagram that implements the Fredkin gate:

\begin{tabular}{ccc|ccc}
left wire 1 & left wire 2 & left wire 3 & right wire 1 & right wire 2 & right wire 3  \\
\hline
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 1 & 0 \\
1 & 1 & 0 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 \\
\end{tabular}

Intuitively, a Fredkin gate copies the top wire from input to output, and
switches the bottom two wires if the top wire is 1 and copies them otherwise.
Its importance lies in the fact that it is reversible -- if you put two 
Fredkin gates in a row, it is the same as if you just had three straight
wires -- and that all other reversible functions can be built up from it
and not.

\item Describe how to draw a wire diagram that implements ``$= (b_1, \ldots,
b_n )$'' where each of $b_1, \ldots, b_n$ is either 0 or 1, ($n > 0$).  That is, describe
how to draw a wire diagram with $n$ input wires on the left and one final
output wire on the right which is 1 if and only if the first wire is in 
state $b_1$, the second wire is in state $b_2$, ..., and the last wire is 
in state $b_n$.

\item Describe how to draw a wire diagram that implements any truth table
with $n$ input wires and 1 output wire ($n> 0 $ ).

\item Describe how to draw a wire diagram that implements any truth table
with $n$ input wires and $m$ output wires ($n > 0$, $m > 0$).

\item Paul Hacker wants to add a new feature to Wire World called {\em
sinks}.  He proposes that sinks look like this:

\nl

and says, ``Sinks take in one input wire and output zero wires.  They are
a great way to get rid of wires that you don't need!''

Show Paul that sinks are unnecessary by giving a procedure by which a wire
diagram with sinks can be transformed into a wire diagram without sinks.
You can assume that the wire diagram has at least 1 output wire.

\item This problem involves binary numbers.  To paraphrase Tom Lehrer, 
binary numbers are just like decimal numbers with eight of your fingers
chopped off.  That is, in the binary system of describing numbers, there
are only two digits, 0 and 1, and instead of having a ``ones place'',
a ``tens place'', a ``hundreds places'', etc. you have a ``ones place'', 
a ``twos place'', a ``fours place'', a ``eights place'', and so forth
for all of the powers of 2.  For example, here is how you count up to 
decimal 10 (binary 1010) in binary, starting at 0:  0, 1, 10, 11, 100, 
101, 110, 111, 1000, 1001, 1010.  For more information about binary 
numbers, see Appendix E of your text.

Computer scientists and programmers like to use binary numbers a lot because
they map well to the logic of Wire World.  In particular, it is convenient
to group $n$ wires together and to consider them as the $n$ binary digits
(or {\em bits}) of a binary number.  The following problems all use that
representation, so when they say ``$n$ bit binary number'' it means exactly
the same as ``$n$ wires''.
 
\begin{enumerate}
\item Draw a wire diagram that multiplies two 1 bit binary numbers.
\item Draw a wire diagram that adds two 1 bit binary numbers.  (Warning:
just like adding two 1 digit decimal numbers can result in a two digit
decimal number, adding two 1 bit binary numbers can result in a two bit
binary number.)
\item Draw a wire diagram that adds two 2 bit binary numbers.
\item Draw a wire diagram that multiplies two 2 bit binary numbers.
\item Draw a wire diagram that implements the following truth table:

\begin{tabular}{cc|cccc}
left wire 1 & left wire 2 & right wire 0 & right wire 1 &
                            right wire 2 & right wire 3 \\
\hline
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 1 
\end{tabular}

[This is called a two-bit multiplexer because if we interpret the input
as a two-bit binary number $m$ and if we label our output wires from 0 to 3, 
it sends a 1 on the $m$-th output wire and 0 on the others.  Multiplexers
are essential for decoding memory addresses in computers, among other things.]
\end{enumerate} 

\item {\em Extra Credit}:  Is it possible to make a wire diagram emulate
a wire cross without containing a wire cross?  To put it another way, can
any wire diagram with wire crossings be transformed into a wire diagram
without wire crossings?  Assume that your wire diagram is restricted to
a two dimensional piece of paper with all input wires starting on the left
edge and all output wires ending on the right edge.
 
\end{enumerate}

\end{document}