\documentstyle[epsf,12pt,listing]{article}
\oddsidemargin 0in
\evensidemargin 0in
\textwidth 6.5in
\topmargin -.5in
\textheight 9in
\parskip 8pt
\title{Design and Implementation of an SRAM Controller}
\author{Derek A. Atkins}
\date{\today}

\begin{document}
\maketitle

\begin{abstract}
A Static RAM needs to have a controller, a piece of hardware that
creates the correct timing signals to read and write from the RAM as
required.  This can be done by implementing a Finite State Machine
that will output the correct signals.  On top of this, a Bubble Sort
can be created that will take the values in the SRAM and sort them in
ascending order.  I designed and implemented the hardware systems to
control the SRAM and the software systems to perform the bubble sort
routine.  Unfortunately the design did not fully work at the end.
\end{abstract}
\thispagestyle{empty}
\newpage
\pagenumbering{roman}

\tableofcontents

\listoffigures
\newpage

\section{Overview}
\pagestyle{plain}
\pagenumbering{arabic}
A Static Random Access Memory (SRAM) is a device that can be used to
store information without the need for circuitry to periodically
refresh the element.  As such, this unit can be used to temporarily
store information while the system does other things, and then returns
to the data at a future time.  

This lab was to design and implement a controller for the SRAM and
then create a bubble sort routine on top of the hardware.  Using the
6.111 kit, the user would use the last four switches, S0-S3, as the
data bits, the next three higher switches, S4-S6, for the command, and
P1, a debounced switch, for the {\tt GO} signal to execute the
command.

A user would input a command in the three switches, and the data in
the four, and then hit the {\tt GO} button to execute the command, and
the results, if any, will be displayed in the eight LED's.  The lower
four LED's contain the current contents of the Memory Address Register
(MAR), which will usually be the address that will be used for the
{\it next} command executed.  The upper four LED's contain the data in
one of two registers.

The total system is controlled by a finite state machine (FSM) control
system, which is the backbone of the design (See figure
\ref{system-diagram}).  The FSM system keeps the current state of the
machine and, from a set of input signals, creates the necessary
outputs to control the other parts of the system, which include the
SRAM, two registers, two drivers for the tri-state bus, and a four-bit
comparator.  For a complete circuit diagram see Appendix
\ref{complete-circuit}.

This document contains details about the design and implementation of
the system, separated into each part of the design, a small section on
testing and debugging, and the circuitry and code used for the
machine.

\begin{figure}[tbp]
\epsfbox{block.ps}
\caption{Block Diagram of System}
\label{system-diagram}
\end{figure}

\section{Description}
The lab was divided into three sections, the design of the Finite
State Machine, a design of the hardware sections, and then the
software bubble sort.  I designed the original FSM system to test out
the hardware, then I created the actual hardware implementation, and
finally I re-wrote the FSM to implement the bubble sort routine.

\subsection{Finite State Machine Design}
The main part of the system is the FSM controller.  This was developed
in two steps.  The first step (see fig. \ref{fsm-diagram}) was to
design a finite state machine which would execute all commands needed
to test the hardware.  These commands include the following:

\begin{figure}[tbp]
\epsfbox{fsm-diagram.ps}
\caption{FSM State Diagram without Bubble Sort Routine}
\label{fsm-diagram}
\end{figure}

\begin{itemize}

\item{\bf Load Address} {\tt (0 0 0)}  
This command will load the data into the MAR.

\item{\bf Examine Memory} {\tt (0 0 1)}  
This command will take the current address of the MAR and put the
contents of that address into the display register, and then it will
increase the MAR.

\item{\bf Store} {\tt (0 1 0)}  
This will take the current data in the switches and write it into the
current location of the MAR, and then increase the MAR.

\item{\bf Findmax} {\tt (0 1 1)}  
This command will search the 16 possible SRAM locations used in this
lab and will find the address with the largest value, and it will then
place that value into location 0 of the SRAM.

\item{\bf NOP} {\tt (1 X X)}  
This command will do nothing.  Hence the name no operation.

\end{itemize}

At the time I designed this I didn't have the bubble sort in mind, so
I just used separate states for each function (which got changed for
the bubble sort, as I will explain in a later section.)  It was
designed in such a way that in each state the correct outputs would be
given, and these outputs would be state dependent, so they would
change only at the clock and not in the middle of a clock cycle.

\subsection{Hardware Design}

The hardware proved to be easier to design than the FSM module.  The
main data paths were given in the lab handout.  I just had to figure
out how to decipher the diagram and actually wire the chips.  The
design is in Appendix \ref{complete-circuit}.

The hardest part of the design of the hardware was trying to figure
out what the diagram in the initial lab handout actually meant.  I
just looked at the diagram from a different point of view.  Three
things could drive the bus: the SRAM, the switches, or the register.
There were also three things that were reading from the bus: the SRAM,
the register, and the comparator.  

Besides the bus control signals, the MAR needed both a load and a
count signal, and I needed a feedback signal from the comparator, to
know if the MAR was ready to turn over, and to process the user
command.  As mentioned earlier, most of these signals were explained
in the handout before the design was started.

To implement this design, I used a '169 for the MAR, which allowed a
four-bit count, upwards or downwards.  This gave 16 addresses for use.
All the other 6116 SRAM address pins were tied to ground, although it
wouldn't have mattered whether they were ground or VCC, just so that
they were tied to something to keep them stable.  

An LS'244 served as the driver for both the switches and the register
onto the tri-state bus.  The '244 is best used because it has two
separately controlled banks of 4 bits, which was perfect for the
four-bit bus used in this lab.  An LS'377 was used for the two
registers; one was loaded off the bus, and the other was loaded from
the output of the other, giving a one cycle delay between the time it
would be loaded from the bus and the time it could drive the bus.
This was implemented for my swap routine in the bubble sort, which I
will explain is section \ref{bubble-sort-section}.  An LS'85 four-bit
comparator is used between the bus and the first register, to find the
larger of the two.

I implemented a synchronous {\tt GO} signal using two D flip-flops in
an LS'74.  By connecting them through the correct gates, as shown in
Appendix \ref{complete-circuit}, I was able to get a pulse that is
asserted for only one clock cycle independent of the length of the
input assertion.  It resets itself one cycle after the input is
de-asserted.

\subsection{Bubble Sort FSM}
\label{bubble-sort-section}
Once the rest of the hardware was designed, the last section to
implement was the Bubble sort algorithm given in the lab handout.  The
bubble sort takes as input the values in the SRAM and rearranges them
in increasing order starting at location zero.

The first step was implementing a swap function.  This was done in
hardware, by having two registers read off each other, allowing a
cycle of storage time when the other address can be read.  Basically,
using the two registers, the first datum is loading from the bus, the
second datum is read into the first slot, and then the register writes
into the second slot.  This allowed a swap of data between two SRAM
locations.

The next step was to walk through all the locations in SRAM and swap
all those that needed to be swapped.  This was implemented as a
special state that would iteratively call itself with the next SRAM
location, check it against the starting point, and, if it was needed,
jump to the swap state.  The swap state would switch the two values and
set the flag signal, and then return to sort state.  When the sort got
to the beginning, it would check and clear the flag.  If the sort got
through all 16 locations and didn't set the flag, then the sort was
done and it would return to the idle state.  The state diagram is
pictured in fig. \ref{bubble-sort}.

\begin{figure}[tbp]
\epsfbox{bubble-sort.ps}
\caption{FSM State Diagram for the Bubble Sort Routine}
\label{bubble-sort}
\end{figure}

\section{Testing}
Testing was done in multiple stages.  The first section to be tested
and debugged was the Finite State Machine, since once that was working
it would be possible to test the other hardware by writing a machine
to implement the testing.

The FSM was debugged via hand-clocking and verifying that a given set
of inputs would produce the proper set of outputs.  The only bugs I
found were either typos or a missing or misplaced wire, both of which
were fixed relatively easily.

The next step was to try to get the hardware working.  I was able to
store values into any arbitrary location, and I was also able to read
them out, so the storage mechanisms worked.

However, I never got the full system to work properly.  The bubble
sort was flaky, working with some sets of initial values and not with
others.  I never got it totally working right in the end.

\section{Conclusion}
All in all, the SRAM was not hard to control.  Timing was controlled
through the Finite State Machine, and outputs from the FSM could be
made virtually glitchless by gating the output signals with the clock,
so that they could {\it only} be active during the second half of the
clock cycle.  Also, since the registers were all clocked on the rising
edge, I didn't have to worry about glitchy signals into the registers,
assuming that the clock was slow enough to allow the signals to settle
down.

Nothing in my design was out of the ordinary, in my opinion.  Had I
implemented the synchronous {\tt GO} signal in a PAL, instead of in
outside logic, I might have been able to save a few chips.  The same
goes for the {\tt FLAG} signal.

In my initial design I had mis-copied some pin numbers from the data
book onto my paper, so I had some bus-contention at the beginning.
Once I figured out that was my problem, and I fixed my wiring, I just
had to get my programming right.  Finding bugs in the programming was
a lot easier than finding bugs in the hardware, although in the end it
still didn't work completely.

One of the main lessons I learned is that I have to be patient while
trying to get systems to work.  If you try to rush things, you just
get real frustrated, and then angry, and you can't solve problems.
From there it's all downhill, because you become less objective about
your own design, and start looking elsewhere for your bugs.  Testing
should be done objectively, which means you have to be able to accept
flaws in your original thinking, which can be hard to do if you're
frustrated.

\newpage
\appendix
\section{Full Circuit Diagram}
\label{complete-circuit}

\begin{figure}[bh]
\epsfbox{circuit.ps}
\caption{Main Circuitry}
\end{figure}
\hbox{}
\clearpage

\begin{figure}[tbh]
\epsfbox{gosync.ps}
\caption{Syncronous Go Signal Circuitry}
\end{figure}

\hbox{}
\newpage
\section{FSMC Code to Implement the Full System}
\listing{lab3-2.fsm}
\newpage
\section{PALASM Files for Original Design (without Bubble Sort)}
\listing{lab3.pal}
\newpage
\listing{lab31.pal}
\newpage
\section{PALASM Files for Final Design Including Bubble Sort}
\listing{lab3-2.pal}
\newpage
\listing{lab3-21.pal}
\newpage

\end{document}