\documentclass[11pt]{article}

\usepackage{precalc}
\usepackage{graphicx}

\begin{document}

\assigntitle{6}{Interlude: Logic Circuits}

In the previous assignment, I mentioned how Boolean logic is the
foundation of modern digital computers. This week, we'll explore what
that actually means.

One of the central insights which makes digital computers possible is
that it is possible to represent any information you want using only
two different symbols---usually referred to as $0$ and $1$, or $F$ and
$T$.  (Sound familiar?)  In a computer, these are physically
represented by \emph{voltages} (you can think of voltage in a wire as
the electrical equivalent of \emph{pressure}, like air pressure or
water pressure in a hose).  A zero is represented by a voltage of 0V,
and a one is represented by some positive voltage (generally around
1.5V nowadays, although it has been getting smaller over time).  First
we'll talk about how to use these zeros and ones to represent
informaion, and then we'll explore how a computer actually computes
things with them!

\section{Binary numbers}
\label{sec:binary}

\topic{encoding information}
So, how is it possible to represent any information you want (such as
this document, a recording of Miles Davis's ``So What'', or that
picture of your family at the beach where your little sister isn't
looking at the camera and your uncle has his finger up his nose) using
only ones and zeros, that is, ``true'' and ``false''?  It's obvious
that you can't represent any information at all with only \emph{one}
symbol---if all you had was zeros, the only thing you could do would
be to write down ``0000000000000000\dots''---but it seems incredible
that by adding just \emph{one more symbol}, we can now encode anything
we want!  Adding a third, fourth, or fifth symbol doesn't give us any
extra power.

\topic{binary}
The key is that we can encode any integer we want using only ones and
zeros, by writing it in \emph{base two}, also known as \emph{binary}.
For this reason, a single zero or one is also called a \emph{b}inary
dig\emph{it}, or \emph{bit}.  Once we can encode any integer we like,
it's not hard to see how to make the jump to encoding images or text
files or any other sort of information; we just have to agree on a way
to represent the information using numbers.

As you probably recall from elementary school, the system we normally
use for writing numbers is \emph{base 10}, which means that the places
in a number are given values based on successive powers of ten.  For
example, the number ``$452$'' has a $2$ in the ones ($10^0$) place, a
$5$ in the tens ($10^1$) place, and a $4$ in the hundreds ($10^2$)
place, so it represents the number $4\times 10^2 + 5 \times 10^1 + 2
\times 10^0$.  The fact that we use a base 10 system also means that
we use ten symbols to write numbers: $0$, $1$, $2$, \dots, $9$.

Likewise, a base two system uses only two symbols ($0$ and $1$, of
course) and determines place values based on powers of $2$ rather than
powers of $10$.  For example, the number $1101_2$ (the subscript $2$
indicates that it is the number ``one one zero one'' in base two, rather
than one thousand one hundred one) represents $1 \times 2^3 + 1 \times 2^2 + 0
\times 2^1 + 1 \times 2^0 = 8 + 4 + 1 = 13_{10}$.  

\begin{problem}
  What base ten number does $1001101011_2$ represent?  
\end{problem}

\begin{problem}
  Write $698_{10}$ in binary.
\end{problem}

\begin{problem} \label{prob:binary-facts}
  Compute each of the following.  Write your answers in binary.
  \begin{subproblems}
    \item $0_2 + 0_2$
    \item $0_2 + 1_2$
    \item $1_2 + 0_2$
    \item $1_2 + 1_2$
    \item $1_2 + 1_2 + 1_2$
  \end{subproblems}
\end{problem}

\topic{binary addition}
Remember how in elementary school you had to memorize all the
``addition facts'' (like $3 + 5 = 8$ or $9 + 7 = 16$), and once you
had memorized those you could use them to do addition of bigger
numbers place-by-place? (For example, if there is a $3$ on top of a
$5$, write ``$8$'' underneath; if there is a $9$ on top of a $7$,
write ``$6$'' underneath and carry a $1$, and so on.)  Well, after
doing \pref{prob:binary-facts}, you now know all your binary addition
facts! You can now add longer binary numbers in just the same way that
you can add longer numbers in base ten.  

\begin{problem} \label{prob:binary-add}
  Add:
  \begin{tabular}{cr}
      & $1011001_2$ \\
  $+$ &  $111100_2$ \\
  \hline
  \end{tabular}
\end{problem}

\begin{problem}
  Multiply:
  \begin{tabular}{cr}
            & $10010_2$ \\
   $\times$ & $11_2$ \\
   \hline
  \end{tabular}
\end{problem}

\section{Logic gates}
\label{sec:logic-gates}

So, now we see how computers can represent data using only ones and
zeros.  But there's still something missing.  How do computers
actually \emph{compute} things with ones and zeros?  After all, if
computers were only good at \emph{storing} data, they would be called
``storers,'' not ``computers.''

\topic{computing with logic gates}
The answer is that computers are built out of primitive physical
components called \emph{logic gates} which can perform logical
operations on the one/zero (true/false) values which are represented
as voltages.  I won't go into the details of how they actually
work---you can look up ``logic gates'' and ``transistors'' if you want
to read about it.  But for now, you can just take my word for
it---there are particular configurations of silicon and metal which
can transform voltages in a way that implements logical operations.

So, what are some of these logical operations which can be performed?
We'll look at four (although there are others as well)---AND, OR, NOT,
and XOR.  Sound familiar?

\topic{AND gate}
\pref{fig:and-gate} shows the symbol we use to draw an AND gate.  An
AND gate takes two voltages as input, and makes its output $1$ (high
voltage) if both its inputs are $1$, and zero (low voltage)
otherwise.  This should not be surprising---it's exactly the $A \land
B$ operation that you learned about in a previous week!

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/and-gate.eps}
  \caption{An AND gate}
  \label{fig:and-gate}
\end{figure}

\topic{OR gate}
\pref{fig:or-gate} shows the symbol used for an OR gate, which
implements $A \lor B$.  Its output is $0$ if both its inputs are $0$,
and $1$ otherwise.

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/or-gate.eps}
  \caption{An OR gate}
  \label{fig:or-gate}
\end{figure}

\topic{NOT and XOR gates}
\pref{fig:not-gate} and \pref{fig:xor-gate} show the symbols used for
NOT and XOR gates, respectively.  A NOT gate simply inverts its input,
like $\neg$.  An XOR gate implements the ``exclusive or'' operation $A
\oplus B$---its output is $1$ if exactly one of its inputs is $1$, and
$0$ if the inputs are both $0$ or both $1$.  In other words, it
implements ``not equal to.''

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/not-gate.eps}
  \caption{A NOT gate (inverter)}
  \label{fig:not-gate}
\end{figure}

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/xor-gate.eps}
  \caption{An XOR gate}
  \label{fig:xor-gate}
\end{figure}

\section{Logic circuits}
\label{sec:logic-circuits}

\topic{circuits}
The cool thing is that these gates can be wired together to form
circuits which compute useful things.  \pref{fig:example-circuit}
shows a simple example.

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/example-circuit.eps}
  \caption{An example circuit}
  \label{fig:example-circuit}
\end{figure}

$A$ and $B$ are inputs to an AND gate.  The output of the AND gate is
an input to an OR gate, along with another input $C$.  Finally, the
output of the OR gate is an input to a NOT gate, and the output of the
NOT gate is the output of the entire circuit.

\begin{problem}
  Write down an equation defining $X$ in terms of $A$, $B$, and
  $C$.
\end{problem}

\topic{Mystery circuit 1}
\pref{fig:mystery-1} shows another example circuit.  By the way, wires
only connect at a dot; if two wires cross each other without a fat dot
at their intersection (as happens in one place in
\pref{fig:mystery-1}, for example), you should assume that they are
not connected and have no effect on each other.  (On a physical
computer chip, there are several different ``layers'' for wires to
travel through, so you can imagine the wires passing over or under
each other in different layers.)

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/half-adder.eps}
  \caption{Mystery circuit \#1}
  \label{fig:mystery-1}
\end{figure}

\begin{problem}
  Fill in the following table showing the operation of the circuit in
  \pref{fig:mystery-1}.  That is, make a row for each of the
  possible values of inputs $A$ and $B$, and show what outputs $C$ and
  $D$ the circuit computes.

  \begin{center}
  \begin{tabular}{cc|cc}
    $A$ & $B$ & $C$ & $D$ \\
    \hline
    & & & \\
    & & & \\
    & & &
  \end{tabular}
  \end{center}
\end{problem}

\begin{problem}
  Can you describe in words what the circuit in
  \pref{fig:mystery-1} does? (\emph{Hint}: look at
  \pref{prob:binary-facts}.)
\end{problem}

\begin{problem}
  \pref{fig:mystery-2} shows another circuit.  You might
  notice that it contains two copies of mystery circuit \#1, and an
  extra OR gate.  Make a table, like the one you made for mystery
  circuit \#1, showing the operation of this circuit. (Hint: the table
  should have five columns and eight rows.)
\end{problem}

\begin{problem}
  Can you describe in words what mystery circuit \#2 does?
\end{problem}

\begin{figure}[htp]
  \centering
  \includegraphics[scale=0.8]{diagrams/full-adder.eps}
  \caption{Mystery circuit \#2}
  \label{fig:mystery-2}
\end{figure}

\topic{encapsulating circuits}
We'd like to be able to use multiple copies of mystery circuit \#2 in
bigger circuits, but drawing out all the individual gates would get
tedious, not to mention that it would clutter the diagram and make it
hard to understand at a high level.  So we can imagine putting a box
around the circuit, as shown in \pref{fig:encapsulate-2}. Now that we
know what mystery circuit \#2 does, we can forget about its internal
details and just think of it as a ``black box'' which takes some
inputs and somehow computes some outputs.  With this perspective, we
can use \pref{fig:m2-box} as an abbreviation for the entire circuit.
The ``M2'' in the center stands for ``Mystery circuit 2.''  Figures
\ref{fig:encapsulate-2} and \ref{fig:m2-box} show exactly the same
circuit, but with different levels of detail.

\begin{figure}[htp]
  \centering
  \includegraphics[scale=0.8]{diagrams/full-adder-boxed.eps}
  \caption{Encapsulating mystery circuit \#2}
  \label{fig:encapsulate-2}
\end{figure}

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/adder-box.eps}
  \caption{Mystery circuit \#2 as a ``black box''}
  \label{fig:m2-box}
\end{figure}

\topic{Mystery circuit 3}
Now that we have a compact symbol for mystery circuit \#2, we can use
it to draw larger circuit diagrams.  \pref{fig:mystery-3} shows such a
circuit. 

\begin{figure}[htp]
  \centering
  \includegraphics[scale=0.9]{diagrams/ripple-carry.eps}
  \caption{Mystery circuit \#3}
  \label{fig:mystery-3}
\end{figure}

\begin{problem}
  In words, what does the circuit in \pref{fig:mystery-3} do?  (\emph{Hint}:
  look at \pref{prob:binary-add}.)
\end{problem}

You may be interested to know that there is a circuit very much like
mystery circuit \#3 in your computer!  It is probably much
bigger (featuring perhaps 32 or 64 copies of M2) and much more
complicated (in order to make it faster), but the basic idea is still
the same.

\topic{SR-latch}
One final circuit for you to consider: \pref{fig:sr-latch} shows a
circuit known as an ``SR-latch''.  As you may notice, the strange
thing about this circuit is that it takes some of its own outputs as
inputs!

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/sr-latch.eps}
  \caption{An SR-latch}
  \label{fig:sr-latch}
\end{figure}

\topic{feedback}
Feeding the output of a circuit back into itself as input could cause
one of several things to happen. First, it could cause an inconsistent
or oscillatory state, where the voltages in the circuit switch back and
forth very rapidly between $0$ and $1$.  For example,
\pref{fig:not-loop} shows such a circuit: if a $1$ is fed into the NOT
gate, it outputs a $0$, which becomes the new input to the NOT gate,
so it outputs a $1$, so it outputs a $0$, so it outputs a $1$\dots and
so on, billions of times per second!  Circuits like this are not very
useful.

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/not-loop.eps}
  \caption{An oscillatory feedback loop}
  \label{fig:not-loop}
\end{figure}

However, sometimes feedback can be useful, and can lead to a
consistent, non-oscillating state where the feedback from the output
reinforces the input. 

\begin{problem}
  Suppose the SR-latch circuit shown in \pref{fig:sr-latch} starts out
  with $R = S = Q = 0$ and $\overline{Q} = 1$.  Is the whole circuit
  in a consistent state, or will some of the wires oscillate between
  $0$ and $1$?  Justify your answer.
\end{problem}

\begin{problem}
  Now suppose that $S$ changes to $1$.  What happens to $Q$ and
  $\overline{Q}$?
\end{problem}

\begin{problem}
  Now suppose that after being set to $1$, $S$ returns to being $0$
  again.  Now what happens to $Q$ and $\overline{Q}$?  (Think
  carefully about this one!)
\end{problem}

\begin{problem}
  What would happen now if $R$ was set to $1$?
\end{problem}

\begin{problem}
  Why do you think $Q$ and $\overline{Q}$ are called $Q$ and
  $\overline{Q}$ instead of, say, $Q$ and $P$?
\end{problem}

\begin{problem}
  What could you use an SR-latch for in a computer?
\end{problem}

\end{document}