Circuits from Truth Table
Suppose the last three digits of your
Banner ID are XXX. Use them to form a URL like this:
http://www.cs.utsa.edu/~dj/cs5513/hw1/problems/XXX-truth-table.txt.
There you will find your truth table.
Construct two circuits that compute the function in four variables given by
your truth table. One circuit may use only NAND gates. The other circuit
may use NAND, NOR, AND, OR, NOT, and XOR gates.
Circuit Syntax
The circuits should be specified with as many lines as there are gates.
Each line should contain the following elements:
- A gate number followed immediately by a colon. Gate numbers start
at 0 and proceed in ascending order.
- A two-character gate symbol, one of the following:
- && for AND
- || for OR
- !! for NOT
- ^^ for XOR (exclusive-OR)
- !& for NAND
- !| for NOR
- Two integers representing the input to this gate. Negative integers
represent variables (-1, -2, -3, or -4) while non-negative integers
represent the output of the gate with the corresponding number. For a
NOT gate, the output is the complement of the first input (although note
that NOT gates are not really needed; you can just use the NAND or NOR of
a variable with itself).
For instance, the following is a valid circuit description:
0: ^^ -1 -3
1: ^^ -3 -4
2: !| 0 -4
3: ^^ 1 -2
4: !& 1 0
5: || 3 2
6: !& 5 4
Gate #0 computes the XOR of variables -1 and -3. Gate #5 computes the OR
of the outputs of gates number 3 and 2. This circuit computes the following truth table:
-4 -3 -2 -1 | output
------------ |
0 0 0 0 | 0
0 0 0 1 | 1
0 0 1 0 | 0
0 0 1 1 | 0
0 1 0 0 | 1
0 1 0 1 | 0
0 1 1 0 | 1
0 1 1 1 | 0
1 0 0 0 | 0
1 0 0 1 | 1
1 0 1 0 | 1
1 0 1 1 | 1
1 1 0 0 | 1
1 1 0 1 | 1
1 1 1 0 | 0
1 1 1 1 | 0
Requirements
You are required to make two circuits: one using only NAND
gates, and one using any combintion of NAND, NOR, NOT, AND, OR, or XOR.
For every truth table distributed with the assignment, the corresponding
NAND circuit requires only 11 gates and the corresponding NAND, NOR, NOT,
AND, OR, and XOR circuit requires only seven gates. You should strive to
use only the minimum number of gates necessary; we will take points off
for excessive gates. No points will be rewarded for incorrect circuits.
Validation
We will use the validate.c program to validate
your solution. You should verify that your circuit actually computes the
truth table you were given using this program. If foo.txt contains
your truth table and bar.txt contains your solution as a list of
gates, then typing validate foo.txt bar.txt will evaluate your
circuit for each line of the truth table. If it prints success!
then your circuit is correct. Otherwise, use the output of the program as
debugging information and keep trying. Try out validate.c with
the truth table and circuit given above. Note that validate.c
is not very smart; any extraneous spaces or other information in the input
files can cause it to fail.
Machine Language Understanding
Send an email to your teaching assistant from your UTSA Computer Science
account. She will send you a file containing a sequence of hexadecimal
bytes representing a C function in either x86 (32-bit) or x86_64 (64-bit)
machine language. The file will also contain a type signature, i.e.,
a C declaration of the function giving its return type and the type(s)
of its parameter(s), as well as a line giving the instruction set used
for this function. Each student will receive a different file.
Requirements
- Provide a commented disassembly of the function. That is, for each
instruction in the function, give the equivalent line in x86 assembly
language and a comment on the same line giving the meaning of the
instruction.
- Write a function in C that carries out the same computation done by
the function.
- Your function is a well-known simple algorithm. Write a short sentence
describing the algorithm, giving the name of the algorithm if possible.
Note:
It is expected that most students are not familiar with x86 and x86_64
machine language. You are expected to be resourceful. Find information
and possibly tools on our systems or on the Internet to help you with
this problem. There is more than one right way to do this assignment.
For students with 64-bit instruction set files, you may use ssh
to log onto elk6401.cs.utsa.edu or elk6402.cs.utsa.edu
for a 64-bit version of Linux. Other students may log onto elk01,
elk02, etc. for the 32-bit version of Linux. Your teaching
assistant can provide you your login name for our systems if you are not
already aware of it. Your initial password is the last 8 digits of your
Banner ID.
You may not work together on this assignment with other classmates
or receive assistance from any person other than your professor. You may
consult literature or the Internet for assistance; if you do, indicate the
source in your writeup. Again, do not collaborate with others on
this assignment; this assignment is to be done individually.
Do the assignment you are assigned. Everyone has a different circuit and
a different sequence of bytes to disassemble.
Your assignment should be nicely typed or word-processed. Turn in this
assignment at the beginning of class on August 31, 2011. You must
turn in the assignment on paper at the beginning of class.
You must also send your two circuit files and your C function to
our teaching assistant as three attachments to one email message before
7:00pm August 31. Make sure to put your name on your paper assignment.
Make sure the circuits you turn in validate correctly. Make sure your C
function compiles correctly.
Note: This assignment is designed to be simple for students who are
well-prepared to take CS 5513 and difficult or impossible for students who
are not well-prepared. If you find that you don't know where to start or
how to do this assignment, you are strongly encouraged to switch to the
undergraduate version of this class, CS 3853, or perhaps the undergraduate
CS 3843, "Computer Organization."
Late assignments will not be accepted.