20-CS-122-001 Computer Science II Spring 2012
Homework Assignment 7

Virtual functions, classes, inheritance, lists, queues, stacks, applications

Logic Analyzer in Software

Due: June 1, 2012 (submit instructions: here)

 

Rationale:

This is a simple application of a Queue class to a common computer engineering problem: namely, design a circuit and test to see whether it meets specifications. In this case, you will develop software that allows users to construct a logic circuit from primitive logic components and then set input truth values and monitor output values as desired. Many queues will be needed, in general, to support the fan-out of signals to many logic devices.

Background:

A Boolean value is one of the set {0,1}. A Boolean variable is a variable which takes a Boolean value. A Boolean function is a mapping from one or more Boolean variables to the set {0,1}. That is, a Boolean function takes one or more Boolean variables as input and returns a value that is determined uniquely by the values of the input variables.

All primitive Boolean functions are so common they have been given names. For example, the Nand function maps all input value combinations except all 0 to 0 and maps an input of all 1 values to 1.

A primitive Boolean function is implemented in hardware as a Gate. The value of such a function implemented as a gate is delivered to the output of the gate. A gate's output may be connected to inputs of gates, including, possibly, those of the gate itself. However, no two gate outputs may be connected. A Logic circuit is a collection of gates, with connections between inputs and outputs of gates, a collection of observable points representing the input of the circuit, with connections to inputs of gates, and a collection of observable points representing the output of the circuit, with connections from gate outputs. A logic circuit implements a complex Boolean function. The following picture illustrates a logic circuit which is used to add two bits, designated A and B, and a carry bit, designated C. The output bits are X, representing the sum, and Y, representing the carry.

The circuit uses three types of gates called And (depicted by ∧), Or (depicted by ∨), and Exclusive-or (depicted by ⇔). Mappings from input values to output value for each of these types is given by the following tables.

Once values are assigned to inputs of a gate, some time passes before the effect is observed at the output of the gate. In this assignment we will assume that the delay through all gates is the same and we will call this time the delay interval. Suppose value 1 is applied simultaneously to inputs A, B, and C in the adder circuit above. The input signals arrive at inputs to gate 1, gate 2, and gate 3 simultaneously. This causes internal points u and w to take value 1 one delay interval later. Before the end of the first delay interval the value of internal point v is not yet stabilized because it depends on the value of internal point u. Having received all its input values by the start of the second delay interval, gate 2 is able to stabilize its output (point v) at value 1 by the end of the second delay interval. Also, by the end of the second delay interval gate 4 produces the value of X which is 1 because u has value 0 and C has value 1. Finally, by the end of the third delay interval, the value of Y is established as 1.

When simulating the propagation of logic values through a circuit, it is very important to account for delays through gates since some circuits can perform differently depending on how much delay a gate causes. Such differences are observed in circuits having circular logic paths (a signal may be propagated forward a few gates then back to the starting gate).

Homework Problem:

Write a program which facilitates the (simulated) construction and monitoring of elementary logic circuits. The program should provide the following:

Gate class: Holds all the information about a gate including: an individual name (type char*), an array (type bool[]) of input values, a list (type Queue - use our Queue class or one from STL) of connections (type Connect - see below) from the gate's output to inputs of various gates, the current output value (type bool), the current number of inputs (type int), and possibly some maximum number of inputs (type int). The first principal method of this class is called propagate of return value void and input arguments specifying a value (type bool) and an input number (type int) which is to be set to that value. The purpose of the propagate method is to set the output value of the gate and the input values of any connected gates, given the new input information. Because the functionality of the gate is described within propagate, it should be declared virtual and overridden by other classes which are derived from the Gate class such as the Nand class (see below). The second principal method of this class is connectGate with return type void and input type Gate *. This method adds a new Gate object to this gate's queue and updates other information such as increasing the number of inputs the gate has. This class serves as the base class for all classes representing primitive gates.
 
Nand class:
Nor class:
Not class:
Interconnect class:    
These classes are derived from the Gate class. Most important for each is to implement the propagate method which is specialized for each gate type. The Not gate, identified using the symbol ¬, takes one input and has output value opposite to that input value: thus, the output is 1 if the input is 0 and is 0 if the input is 1. The Nand and Nor classes implement the complement of the And and Or functions shown in the logic mapping diagram above. That is, the Nand of inputs a and b is ¬(a ∧ b); and the Nor of inputs a and b is ¬(a ∨ b). It is not necessary to code Exclusive-or (see below). Observe it is convenient to implement Not gates as one-input Nand gates. The Interconnect class implements an observable input connection point.
 
Connect class: Objects of this class contain connection information for use by the propagate method of a gate to distribute the gate's output value. These objects are enqueued in a gate's output queue (see above). They contain a pointer to a destination gate, the destination gate's input number whose value is to change, and the value it will change to.
 
connect function: This function is defined outside of any class and is used by the operator of the software to make a connection between two gates. It takes two pointers to Gate objects as input. The left pointer in the argument list is assumed to be the output gate and the right one the input gate. The code should automatically assign input numbers during invocation of this function as the burden of such bookkeeping should be taken off the operator.
 
setValue function: This function is defined outside of any class and is used by the operator of the software to set a value of true or false to an Interconnect object. It takes a pointer to an Interconnect object, called wire, and a bool, called value, as input and assigns wire the value value. Assigning a value entails propagating that value through the circuit. Therefore, this function enqueues a Connect object in an event Queue and then propagates from the event Queue until no events remain.

The specifications for the above classes and functions are contained in the following include files:

circuit.h     gengates.h     prototypes.h

Programming Notes:

Here are some examples of the use of the classes and functions above.

  1. Exclusive-or: This may be built as a separate class in terms of existing primitive classes. You can check that ab is the same function as ¬(¬(a ∧ ¬ b) ∧ ¬(¬ a ∧ b)). We can now define a class XOR as follows:
       // xor.h
       #include 
       #include 
       #ifndef _GENGATES
       #include "gengates.h"
       #endif
       #define _XOR
       using namespace std;
    
       class XOR : public Gate {
        friend ostream & operator << (ostream &, XOR &);
          Nand *g1, *g2, *g3;
          Not *n1, *n2;
          Interconnect *A, *B, *O;
       public:
          XOR (char *s);
          Interconnect *getA ();
          Interconnect *getB ();
          Interconnect *getO ();
       };
       ostream & operator << (ostream &, XOR &);
    
    and
       // xor.cc
       #include "gengates.h"
       #include "xor.h"
    
       XOR::XOR (char *s) : Gate(s) {
          g1 = new Nand("G1");
          g2 = new Nand("G2");
          g3 = new Nand("G3");
          n1 = new Not("N1");
          n2 = new Not("N2");
          A = new Interconnect("A");
          B = new Interconnect("B");
          O = new Interconnect("O");
    
          connect(A,g1);
          connect(A,n1);
          connect(B,g2);
          connect(B,n2);
          connect(n2,g1);
          connect(n1,g2);
          connect(g1,g3);
          connect(g2,g3);
          connect(g3,O);
       }
    
       Interconnect *XOR::getA () { return A; }
       Interconnect *XOR::getB () { return B; }
       Interconnect *XOR::getO () { return O; }
    
       ostream & operator << (ostream & out, XOR & xorg) {
          out << *xorg.A  << " " << *xorg.B  << " "    << *xorg.O;
          return out;
       }
    

  2. Full Adder: This is the circuit pictured above. It can be defined using two XOR gates, two Nand gates, one Nor gate, and three Not gates (less complex solutions are possible - we use this for illustration only). Since XOR gates are not primitive, one must use their Interconnect objects in the connect function (obtained with ...->getA(), ...->getB(), or ...->getO()).

       #include 
       #include 
       #ifndef _GENGATES
       #include "gengates.h"
       #include "xor.h"
       #endif
       #define _ADDER
       using namespace std;
    
       class ADDER : public Gate {
        friend ostream & operator << (ostream &, ADDER &);
          Nand *gate2, *gate3;
          Nor *gate5;
          Not *n2, *n3, *n5;
          XOR *gate1, *gate4;
          Interconnect *A, *B, *C, *X, *Y;
       public:
          ADDER (char *s);
          Interconnect *getA ();
          Interconnect *getB ();
          Interconnect *getC (); 
          Interconnect *getX ();
          Interconnect *getY ();
       };
       ostream & operator << (ostream &, ADDER &);
    

    and

       #include "gengates.h"
       #include "xor.h"
       #include "adder.h"
    
       ADDER::ADDER (char *s) : Gate(s) {
          gate2 = new Nand("Gate2");
          gate3 = new Nand("Gate3");
          gate5 = new Nor("Gate5");
          gate1 = new XOR("Gate1");
          gate4 = new XOR("Gate4");
          n2 = new Not("Not2");
          n3 = new Not("Not3");
          n5 = new Not("Not5");
          A = new Interconnect("A");
          B = new Interconnect("B");
          C = new Interconnect("C");
          X = new Interconnect("X");
          Y = new Interconnect("Y");
    
          connect(A,gate1->getA());
          connect(A,gate3);
          connect(B,gate1->getB());
          connect(B,gate3);
          connect(C,gate2);
          connect(C,gate4->getA());
          connect(gate1->getO(),gate2);
          connect(gate1->getO(),gate4->getB());
          connect(gate3,n3);
          connect(n3,gate5);
          connect(gate4->getO(),X);
          connect(gate2,n2);
          connect(n2,gate5);
          connect(gate5,n5);
          connect(n5,Y); 
       }
    
       Interconnect *ADDER::getA () { return A; }
       Interconnect *ADDER::getB () { return B; }
       Interconnect *ADDER::getC () { return C; }
       Interconnect *ADDER::getX () { return X; }
       Interconnect *ADDER::getY () { return Y; }
    
       ostream & operator << (ostream & out, ADDER & adder) {
          out << *adder.A  << " " << *adder.B  << " "    << *adder.C
              << " : " << *adder.X << " " << *adder.Y;
          return out;
       }
    

  3. Here is a simple test of the above adder which tests all possible input values.

       #include <fstream>
       #include <iostream>
       #include "circuit.h"
       #include "gengates.h"
       #include "xor.h"
       #include "adder.h"
       using namespace std;
    
       int main () {
    
          cout << "----1 Bit Adder ------------------\n";
    
          ADDER *adder = new ADDER("ADDER");
          Interconnect *A = adder->getA();
          Interconnect *B = adder->getB();
          Interconnect *C = adder->getC();
    
          setValue(A, false); setValue(B, false); setValue(C, false);
          cout << *adder << "\n";
          setValue(A, false); setValue(B, false); setValue(C, true);
          cout << *adder << "\n";
          setValue(A, false); setValue(B, true); setValue(C, false);
          cout << *adder << "\n";
          setValue(A, false); setValue(B, true); setValue(C, true);
          cout << *adder << "\n";
          setValue(A, true); setValue(B, false); setValue(C, false);
          cout << *adder << "\n";
          setValue(A, true); setValue(B, false); setValue(C, true);
          cout << *adder << "\n";
          setValue(A, true); setValue(B, true); setValue(C, false);
          cout << *adder << "\n";
          setValue(A, true); setValue(B, true); setValue(C, true);
          cout << *adder << "\n";
       }