CSCE 312 Spring 2022
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. You know C, right? It's just like C++ only less. This assignment is due at 11:59pm on Thursday, February 10, 2022.

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. 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:
  1. Makefile - a little makefile to make the main program (if it downloads with a .txt extension just rename it to "Makefile").
  2. main.c - a simple program to call your code to build the circuit, then print and test the circuit.
  3. make_circuit.c - code to wire up an OR gate. Use this as a place to start.
  4. transistors.c - scary code that simulates networks of transistors. Feel free not to read this.
  5. 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:
  1. ZERO - zero or false.
  2. ONE - one or true.
  3. BAD_ZERO - a weak zero that was passed through a P-type transistor when it really shouldn't have been.
  4. BAD_ONE - a weak one that was passed through an N-type transistor when it really shouldn't have been.
  5. SWITCH_OFF - no value -- the switch is off and/or no value is being passed through.
  6. UNKNOWN - the value has not been computed yet.
  7. 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:

  1. VDD - This node produces a constant "one" or "true" on its OUTPUT terminal and ignores the other two terminals.
  2. VSS - This node produces a constant "zero" or "false" on its OUTPUT terminal and ignores the other two terminals.
  3. P - This node behaves as a P-type transistor. If the signal on the CONTROL terminal is false, 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 true, then there is no signal on the OUTPUT terminal, i.e., the value of the switch is SWITCH_OFF.
  4. 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.
  5. 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.
  6. 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 through Canvas. Your file should not do any extra input or output or any other sort of foolish thing. This assignment is due on Thursday, February 10, 2022.

Late assignments will not be accepted.