CS 5513 Fall 2011, Homework 1

Due at the beginning of class, August 31, 2011.
  1. 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:
    1. A gate number followed immediately by a colon. Gate numbers start at 0 and proceed in ascending order.
    2. A two-character gate symbol, one of the following:
      • && for AND
      • || for OR
      • !! for NOT
      • ^^ for XOR (exclusive-OR)
      • !& for NAND
      • !| for NOR
    3. 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.
  2. 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

    1. 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.
    2. Write a function in C that carries out the same computation done by the function.
    3. 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.