CS 3843 Spring 2011
Computer Organization
Homework 2
CMOS Full Adder
Read these instructions carefully. For this assignment, you will design a
full-adder circuit using CMOS technology. You will write a C file called
make_circuit.c that links with files provided by the instructor
to simulate and test the circuit. This assignment is due at 11:59pm on
Friday, January 28, 2011.
The operation of a full adder is described in our Lecture 2. Scroll down toward the end where
it gives the truth table. The full adder takes three bits of input and
produces two bits of output: the parity and majority of
the three inputs. The parity is just the three-input exclusive OR of the
three inputs. The majority of bits a, b, and c
can be described as ab+bc+ac where juxtaposition
(i.e. putting two things next to each other) means AND and addition means OR.
Build a Full Adder
For this assignment, you should build a full adder circuit using CMOS P and
N transistors in a little C program I came up with just now. Currently the
C program implements an OR gate with two inputs and one output. You should
modify or replace the code to implement a full adder with three inputs and
two outputs. The program will call your code to build the circuit, then
print the circuit in a somewhat human-readable format, then exhaustively test
the circuit with all possible combinations of three inputs. You're done
when the output of the program shows the correct truth table for a full
adder, i.e. something like this:
...
found 3 input nodes, 2 output nodes
2 1 0 | 4 3
----------------
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
Your full adder should consume no more than 200 nodes and 200 wires (the
most egregiously foul full adder should not take that many resources).
You get full credit for making a working full adder. You get extra credit
for making it small, i.e. fewer nodes than a naive implementation, as long
as it still works. The smallest working full adder in the class gets a
lot of extra credit; in the event of a tie, the points are divided equally
among the winners. The only metric for the size of the full adder circuit
is the number of nodes printed printed out when the program runs.
The Code
You will be interested in the following files:
- Makefile - a little makefile to make the main program.
- main.c - a simple program to call your code to build the circuit, then print and test the circuit.
- make_circuit.c - code to wire up an OR gate. Use this as a place to start.
- transistors.c - scary code that simulates networks of transistors. Feel free not to read this.
- transistors.h - a header file needed by the C files with macro definitions and function declarations.
For the purpose of this program, a circuit is a network of nodes
connected by wires. A network is not exactly a graph in the
data structures sense. It is really a hypergraph where edges (wires)
can be incident on more than two vertices (nodes), but it's probably best
not to think too hard about that. Nodes and wires are both represented by
integers. You can allocate a new node with the new_node() function that
returns a distinct integer representing a new node, and you can allocate a new wire
with the new_wire() function that returns a distinct integer representing a new wire.
There are other functions for hooking up nodes and wires and doing other things.
Circuit
A new circuit is allocated with the new_circuit() function, e.g. from main.c:
#include "transistors.h"
...
circuit c;
initialize_circuit (&c);
Every circuit operation is done using a pointer to the circuit structure.
Values
Nodes and wires can have one of seven values:
- ZERO - zero or false.
- ONE - one or true.
- BAD_ZERO - a weak zero that was passed through a P-type transistor when it really shouldn't have been.
- BAD_ONE - a weak one that was passed through an N-type transistor when it really shouldn't have been.
- SWITCH_OFF - no value -- the switch is off and/or no value is being passed through.
- UNKNOWN - the value has not been computed yet.
- INVALID - more than one value somehow got to this node or wire.
We only want to see ZERO or ONE (represented by 0
and 1, respectively) as output values. However, as you debug your
circuit, you are likely to see one of these other values (see transistor.h for the list of values).
Nodes
The type signature of new_node is int new_node (circuit *,
int);.
The circuit pointer gives the circuit struct for which the node
is intended and the int gives the type of the node as defined
in transistors.h.
Each node has three "ports" or "terminals" that can be attached to
wires. The terminals are defined as INPUT, OUTPUT,
or CONTROL.
There are six kinds of nodes:
- VDD - This node produces a constant "one" or "true" on its OUTPUT terminal and ignores the other two terminals.
- VSS - This node produces a constant "zero" or "false" on its OUTPUT terminal and ignores the other two terminals.
- P - This node behaves as a P-type transistor. If the signal on
the CONTROL terminal is true, then the signal on the INPUT
terminal is sent to the OUTPUT terminal. If the input signal is
ONE then the output signal is also ONE. If the input
signal is ZERO then the output signal is BAD_ZERO.
If the signal on the CONTROL terminal is not true, then there is
no signal on the OUTPUT terminal, i.e., the value of the switch
is SWITCH_OFF.
- N - This node behaves as an N-type transistor. If the
signal on the CONTROL terminal is true, then the signal on the
INPUT terminal is sent to the OUTPUT terminal. If the
input signal is ONE then the output signal is BAD_ONE.
If the input signal is ZERO then the output signal is ZERO.
If the signal on the CONTROL terminal is not true, then there is
no signal on the OUTPUT terminal.
- INPUT - This node is an input to the circuit from the
outside world. The INPUT and CONTROL terminals
are ignored. The value of the OUTPUT terminal is set by the
print_truth_table() function that finds all the input nodes and
then tries all possible combinations of inputs. So, only make three inputs;
your logic gates don't each need inputs, they just need wires carry signals.
For our purposes, the order in which you make the inputs doesn't matter
since full adder is a symmetric function.
- OUTPUT - This node is an output from the circuit to the outside
world. The INPUT and CONTROL terminals are ignored.
The value of the OUTPUT terminal is computed by propagating the
inputs through the network. The print_truth_table() function
prints the values of all the OUTPUT nodes, so only make two for
a full adder.
Wires
There is only one kind of wire. Allocate a wire by calling new_wire(), a function
that takes no arguments and returns an integer.
Making Connections
Connect nodes and wires using the attach_node_to_wire function:
int attach_node_to_wire (circuit *c, int n, int w, int port);
This function connects the wire with number w to the node with
number n by the terminal number port. port
is one of INPUT, OUTPUT, or CONTROL; remember
that INPUT and CONTROL only make sense for P
and N nodes.
Putting It All Together
See make_circuit.c for a make_circuit
function that allocates two input nodes and one output node, then wires
up other nodes and wires to make an OR gate.
Resources
You may use resources you find on the Internet or in books to help design
your logic gates. If you use resources, cite them in the comments of
your code. That is, provide a URL, or a book's name and authors, or some
way of identifying where you found the resource.
Working Together
For this assignment, you may work together with classmates or you may
work individally. If you work together, each student is still responsible
for turning in his or her code, but the code may be identical to that of
the other group members. If you turn in code that is the result of group
collaboration, you must identify each group member by name in the
comments of the code.
How can you work together? Well, one idea would be for one person to come up
with the majority circuit and the other to come up with the parity circuit,
and then at the end you figure out how to put them together as a full adder.
Another idea would be to have one person work on getting the full adder
working in any way at all, and the other person working on optimizing,
say, a CMOS XOR circuit that can be plugged in instead of the gross XOR
the first person used. One idea, which I do not recommend, is to have
one person do all the work while the rest of the group does nothing.
The extra credit points for the winning circuit will be divided evenly
among the tied winners, so the person doing all the work might just decide
to quit the group, work alone, and watch the slackers fail.
Think carefully before joining a group. The assignment is somewhat
challenging to do alone, but the communication and planning involved in
a group effort can also be challenging.
What To Turn In
Turn in your well-commented make_circuit.c that implements a full
adder. We will test it with our versions of the other files; make sure
your make_circuit.c works with these files and doesn't depend on
modifications to the other files that you have made. Turn in only
your make_circuit.c file by emailing it to our teaching assistant.
Your file should not do any extra input or output or any other sort of
foolish thing. This assignment is due on Friday, January 28, 2011.
Late assignments will not be accepted.