\documentstyle[epsf,6.111-lab,12pt]{article}

\name{Marc Horowitz}
\labnum{3 -- Static RAMs and Finite State Machines}
\recitation{John Piscitello \\ Tuesday 2pm}

\begin{document}
\begin{abstract}
A simple circuit is constructed which allows the user to perform
operations on an SRAM.  The operations include several tests and a
bubble sort.  Switches are used to provide a function and data to a
control circuit which implements an FSM.  The control circuit drives
an SRAM controller, which reads and writes the SRAM, and provides
output on LEDs.
\end{abstract}
\coverpage

\tableofcontents

\listoffigures

\listoftables

\newpage

\section{Overview}

In this lab, a simple circuit is constructed which allows the user to
perform some basic operations on a block of Static RAM (SRAM).  The
user can set the value in the Memory Address Register (MAR), read a
memory location, write a memory location, find the highest value in
the SRAM, and bubble sort the contents of the SRAM.  The first four
are tests of the operation of the hardware and the circuit.  The sort
is the main operation which the circuit implements.

The circuit is divided into two parts.  The first is the the SRAM
Controller, which consists of a Memory Address Register (MAR), an SRAM
chip, several buffers and registers, a comparator, and LEDs for
output.  The second is the control circuitry, which takes as input a
function and data from switches and input from the SRAM Controller,
and generates control signals to read and write the SRAM.

The switches are used to set the function and any data for the
function.  When the GO button is pressed, the function is executed,
leaving any output on the LEDs.  

\section{Description}

\subsection{The SRAM Controller}

The SRAM Controller consists of the following components:
\begin{itemize}
\item sixteen 4-bit words of SRAM
\item a 4-bit MAR which can be loaded, incremented, or decremented
\item two 4-bit registers which are loaded simultaneously
\item a 4-bit comparator
\item two 4-bit buffers
\end{itemize}

The SRAMs address lines are driven by a MAR, which can be loaded from
the switches, incremented, or decremented.  The value of the MAR is
displayed on four LEDs.

The controller has a ``bus'' which can be loaded by the SRAM, a buffer
driven by four switches, or a register.  The ``bus'' can drive the
SRAM, the other register, or a comparator.  The latter register also
drives the former register, the comparator, and four LEDs.  The SRAM
/CS/ (chip select) is wired to the clock, so that the SRAM will only
be selected in the latter half of the clock cycle.  This avoids bus
contention, and allows the value on the bus to settle down before the
SRAM tries to read it.

\begin{figure}
\epsfbox{sram_logic.ps}
\caption{SRAM Controller Logic Diagram}
\label{sram:logic}
\end{figure}

The controller is intended to be used in several different ways.  The
memory can be loaded from the switches, or the registers can be used
to read a value from one location and write it back in another.  The
output of the comparator is used by the control circuit to determine
what operations to take on the memory.  

Tables \ref{sram:in} and \ref{sram:out} describe the inputs and
outputs provided by the SRAM controller.

\begin{table}
\begin{description}
\item[/MARCNT/] Increments or decrements MAR on the rising clock edge.
\item[/DOWNCNT/] When asserted, /MARCNT/ will decrement the MAR
instead of incrementing it.
\item[/MARLOAD/] Loads the MAR from the switches.
\item[/WE/] Writes the SRAM from the bus.  If this
is not asserted, the SRAM will drive the bus.
\item[/SWTTORAM/] Drives the bus from the switches.
\item[/REGTORAM/] Drives the bus from REG2.
\item[/REGLOAD/] Loads REG1 from the bus, and loads REG2 from REG1.
Both happen on the rising edge.
\end{description}
\caption{SRAM Controller Inputs}
\label{sram:in}
\end{table}

\begin{table}
\begin{description}
\item[/MARCAR/] Asserted by the RCO of the counter
\item[RAMLREG] Asserted when the value of the bus is less than the
value of REG1
\end{description}
\caption{SRAM Controller Outputs}
\label{sram:out}
\end{table}

\subsection{Control Circuitry}

The control circuitry is fairly simple.  Three switches provide a
function to the circuit.  A pushbutton switch (GO) is synchronized so
that it is only asserted for one cycle and used to provide a signal
(GOSYNC) which is used by the control circuit to determine when to
execute the function at its input.  A logic diagram for GOSYNC is in
figure \ref{gosync:logic}.

\begin{figure}
\epsfbox{gosync_logic.ps}
\caption{GOSYNC Logic Diagram}
\label{gosync:logic}
\end{figure}

The four inputs described above are combined with the two outputs of
the SRAM Controller to control the FSM encoded in the two PALs.  When
GOSYNC is asserted, the function is executed.  The outputs of the PALs
drive the inputs of the SRAM Controller.

In addition to the the inputs described above, there is an
asynchronous RESET input, which clears the flag and puts the FSM in
the PAL into state zero (the ``Idle'' state).

\begin{figure}
\epsfbox{fsm_logic.ps}
\caption{FSM Logic Diagram}
\label{fsm:logic}
\end{figure}

\subsection{Finite State Machine}

State ``Idle'' is, obviously, the idle state.  When the circuit is not
doing anything, it's here.  Functions 0, 1, and 2 are simple enough
that they can be executed in one cycle, without leaving the ``Idle''
state.

Function 0 of the FSM is ``Load Address''.  It loads the MAR with the
value of the switches.  This is done by asserting /MARLOAD/.

Function 1 of the FSM is ``Read Memory''.  It displays in the LEDs the
value of the SRAM location indexed by the MAR.  This is done by
asserting /REGLOAD/.  (This is not really true.  See below.)

Function 2 of the FSM is ``Write Memory''.  It writes the value
specified by the switches into the memory location indexed by the MAR.
This is done by asserting /SWTTORAM/ and /WE/.

Function 3 of the FSM is ``FindMax''.  It reads all the memory
locations, and writes the largest value into memory location 0.  This
is a relatively complex operation.  First, in state ``ClearMar'', the
MAR is decremented until it is equal to zero (/MARCAR/ is asserted),
then an internal FLAG is cleared, and the FSM moves to state
``FindMax''.  Here, a loop is executed.  For each value in the SRAM,
it is compared to the stored value in REG1.  If the stored value is
smaller, then the value in the memory is written to REG1.  At the end
of the loop, an internal FLAG is set, REG2 is loaded from REG1, and
the FSM moves to ``Idle''.  In ``Idle'', the circuit notices that FLAG
is set and function 3 was just executed, so the contents of REG2 are
written into memory location 0.

Function 4 of the FSM is ``Bubble Sort''.  It uses a bubble sort
algorithm to sort the contents of the SRAM into ascending order.  It
begins by going to state ``ClearMar'' and clearing the MAR.  When this
is done, it begins the first iteration of the outer loop by going to
state ``DoSort''.

State ``DoSort'' executes one iteration of the bubble sort outer loop.
It initializes by clearing the FLAG and loading the value of memory
location 0 into REG1, and incrementing the MAR.  It then goes to the
test loop in state ``Test''.

At the beginning of iteration $n$ of state ``Test'', REG1 contains the
value of memory location $n$, and the SRAM is driving the contents of
memory location $n+1$.  If RAM[$n+1$] is less than RAM[$n$] (REG1),
then REG1 gets REM[$n+1$], REG2 gets RAM[$n$] (REG2), and the FSM
moves to state ``Swap1''.  Otherwise, if MARCAR is asserted (MAR =
15), then if the FLAG is set, the MAR is incremented to 0, REG1 is
loaded with memory location $n+1$, and the outer loop is executed
again.  If the FLAG is not set, then the sort is finished, and the
function returns to the ``Idle'' state.  If RAM[$n+1$] is greater than
or equal to RAM[$n$], then REG2 is loaded with RAM[$n$] (REG1), and
iteration $n+1$ begins.

In state ``Swap1'', the FLAG is set, RAM[$n+1$] gets RAM[$n$] (REG2),
REG2 gets RAM[$n+1$] (REG1), and the MAR is decremented to $n$.

In state ``Swap2'', RAM[$n$] gets RAM[$n+1$] (REG2), REG1 gets
REG[$n+1$], and the MAR is incremented to $n+1$.  At this point, REG1
contains REG[$n$], and the MAR contains $n+1$.  State ``Test'' is now
re-entered for the second half of the $n$th iteration.

\section{Implementation Details}

The FSM described above uses a FLAG register.  This register is
controlled by two inputs, SETFLAG and CLRFLAG.  These inputs are
not taken from outside the PAL, but instead are looped back inside the
PAL from combinational inputs.  The logic diagram for the FLAG
register is contained in figure \ref{flag:logic}.

\begin{figure}
\epsfbox{flag_logic.ps}
\caption{FLAG Register Logic Diagram}
\label{flag:logic}
\end{figure}

In the implementation of the five functions of the circuit, it turns
out that there are many places where /REGLOAD/ and /MARCNT/ are
asserted.  Because of limitations in the PAL (there can only be seven
terms in a combinational output), there are actually two combinational
outputs, /RL1/ and /RL2/, which are asserted in the {\tt .fsm} file.
These outputs are looped back and or'd together to generate the actual
/REGLOAD/ output.  Originally, /MARCNT/ also had too many terms, but
this turned out to be only a limitation in {\tt fsmc}'s optimizer.  By
unrolling the if statement, I was able to get /MARCNT/ down to seven
terms.

\section{Conclusions}

In this lab, I designed a fairly straightforward controller and an FSM
to drive it.  The only real conclusion I was able to make was that a
PAL is not infinite, and that it is not hard to write an FSM complex
enough to overflow some of its internal restrictions.

\end{document}
