UW CSE
Autumn 1999
CSE467 Advanced Digital Systems Design
Instructor: C. Diorio

Homework / Lab 5
DUE: Nov 15,1999, 5:00 pm

Collaboration Policy:
This is a group assignment: Your lab group must turn in a written solution, and demonstrate a working state machine to the lab TA. Your group may collaborate with other CSE467 groups on this assignment. Collaboration means that you may discuss the problem and make notes during the discussion, but you may not copy another group’s design; you may not copy experimental results from another group; and you may not copy any part of another group’s solution. In addition, every individual in a group must understand the design, must participate in the writeup, and should understand the results. Collaboration does not mean that one person may design the state machine and another do the lab—all lab partners must share equally in all parts of the assignment.

Late Policy:
This assignment is due at 5 pm on 11/15/99. Assignments handed in late will incur a 10% penalty; the penalty will increase by 10% for each additional day late. Your completed assignment must have a TA signature, certifying a working state machine for problem 1.

Overview:
The purpose of this assignment is to:

(1) Design a memory controller for the XESS board
(2) Design and implement a state machine that uses the memory controller The assignment:
Answer all questions in your writeup. Show all of your work. Your solutions must be legible. This assignment is worth a total of 80 points.
 

1. (70 pts) Design and implement an Ant-in-a-Maze FSM. A detailed problem description (and some ideas on solutions) is here. You must document your completed design for us, including handwritten state and dataflow diagrams, your state assignments, your Xilinx schematics, your Verilog code, explanations of what you did, and anything else that will help us to understand your design.

Part A) Design and implement a memory controller. You can find a datasheet for the W24257A 32k ´ 8 SRAM that is on the XESS board here. Your memory controller should accept as inputs the 8-bit data, clock, a 15-bit memory address, and a write request. If you are not actively writing the memory, then by default your controller is in the read state. Your memory controller should output all the signals you need to read or write data to/from the SRAM. You should be able to read or write in a single clock cycle (you may need to use both the rising and falling edges of the clock to accomplish a write in one cycle). Design the memory controller using either Verilog blocks or a few Xilinx logic gates. Turn in your schematic, as well as some annotated timing diagrams (hand drawn) that show how your memory controller works. Save your memory controller—you will use it again in your final project. You can use the logic analyzer to examine the signals you are writing to/from the memory. All the SRAM pin assignments are in the UCF from Lab3 (here).

Part B) Design and implement an Ant-in-a-Maze FSM. Code that generates a  maze file for you to download to the on-board SRAM (using XSRAM) is here. The maze is a 128´ 128 grid. You specify the current position of your ant in [x, y] coordinates, where x and y are 7-bit binary values (0 <x< 127 and 0 < y< 127). Your start your ant at [1, 1], and it wanders through the maze. At each new grid location (i.e. at each new [x, y] coordinate), you read the value stored in the SRAM to find the wall situation. Your ant’s grid position [x, y] is the index into the SRAM. The memory address as a 15-bit word, that you specify for read operations as [0xy]. At each memory location you will read one of the following values (or an OR of two values, if your ant is in a corner), and your ant should move appropriately:

00000001 º No wall
00000010 º North wall
00000100 º West wall
00001000 º South wall
00010000 º East wall
00100000 º Maze exit
01000000 º Inside a wall

The memory byte may indicate two walls—for example, 00000110 indicates that the current grid has walls on the North and West sides. Your ant has 3 possible moves: (1) move forward one grid, (2) turn right, and (3) turn left. Your ant should never see the 01000000 code (unless it manages to penetrate a wall).

At every grid location (x, y pair), there are crumbs in the maze that your ant must eat. You indicate that your ant has eaten the crumbs by writing 00000000 into the SRAM, at coordinates [1xy], every time the ant enters a grid box. When your ant finds the exit, your state machine should halt. You then read the crumb file back to the PC using XSRAM, save it to a flat file called mazefile, and display your ant’s crumb file using the C code here. The code runs on both Linux and NT. The code produces an RGB file called mazefile.rgb. You can view the RGB file using ImageMagick with the window size set to 512´256. You will see the original grid and the crumb grid displyed side by side. On a Linux platform, you can display the file using display -size 512´256 <filename .rgb>. ImageMagick is  available for NT/95 here. The default flatfile name is mazefile, but you can specify an alternative name as a command line parameter when you run the C code (convert <filename> will produce <filename.rgb>). The 128´128 grid is zoomed out to twice its original size.

Your design will comprise 4 parts: (1) A memory controller, (2) two 7-bit counters (for x and y), (2) a 4-bit counter to indicate your ant’s current heading (N, S, E, W), and (4) a FSM to determine your ant’s next move. Note that you must keep track of your ant’s heading as well as position.

We recommend that you use one-hot encodings for your state machines and counters. In addition, where possible your one-hot encoding should also be an output encoding.

Use Verilog code and Xilinx schematics to build your design. Modularize your code. Turn in a completed design, including handwritten state and dataflow diagrams, your state assignments, your Xilinx schematics, your Verilog code, explanations of what you did, and anything else that will help us to understand your design.
 
 
 

 2. (10 pts) Draw a dataflow diagram for your DES implementation. Explain the conceptual operation in one or two paragraphs.