In the last post, I explored different ways to model the logic of a full-adder. In this post I’ll explore a model of a physical instance of a full-adder — a model that simulates physical reality.

Because a full-adder is, at root, a mathematical expression, various software models can accomplish the same results. Models are abstractions, so the only thing a model can simulate perfectly is another model.

In the sense that a full-adder is a mathematical object — it can be fully expressed as a truth table or an FSM or a logical expression — algorithms can produce identical results. All the previous examples, and the ones in this post, could be substituted for real-world physical full-adders.

With two caveats:

1. An interface to the real world is required.
2. Software is usually slower than hardware.

The second one ultimately may, or may not, matter. The first is significant. There must be a translation between the software world of “variables” and the hardware world of voltages.

But these are topics I intend to address on my main blog. Here I want to talk about a software simulation of a physical full-adder.

§

Let’s start with the full-adder circuit. We’ll use a common one:

It has two XOR gates (dark green), two AND gates (red), and an OR gate (bright green). The circuit reifies two compound logical expressions:

Here is the truth table for the full-adder:

(The inputs and outputs were discussed in the previous post.)

§

The idea is to simulate the gates shown in the logic circuit above.

In particular, we want to simulate the asynchronous flow of current through the gates. If an input changes, the change potentially can trickle through the gates to an output as fast as current flows.

Which brings us to the first of many disconnects between the simulation and the physical reality. The simulation is limited in two ways with regard to current flow:

1. The timing is quite different, both in scale and nature.
2. We don’t have the parallelism the real thing does.

There is also that the whole mechanism, the means of operating, is significantly different from the real thing. When, and how much, this matters is a key point in debates about computationalism.

The possibly salient point (or not, depending on your axioms) is that there is no actual current is flowing! There’s no way to accidentally “short-circuit” these circuits. Or get a shock from them.^[1]

§

I’m a big fan of objected-oriented design, so naturally my first step was to create a set of logic gate classes.

I began with an abstract logic gate base class:

class logic_gate (object):
    def __init__ (self, name, kind):
        self.name = name
        self.kind = kind
        self.state = False
        self.gates = []

    def change (self, state):
        # If state matches, don't do anything...
        if self.state == state:
            return
        # Set the new state and signal connected inputs...
        self.state = state
        for gate in self.gates:
            gate(self.state)

    def __str__ (self):
        return '%3s[%s] %s' % (self.kind, self.name, self.state)
#

The change(state) method is the central workhorse of the simulation. It checks to see if the new state is the same as the current state and does nothing if no change is required. Otherwise it makes the change and then sends that change to any downstream gates this gate is connected to.^[2]

The constructor (the __init__ method) gives a logic-gate instance a name, a kind, a state, and a list of downstream gates.

The kind property is a gate type identifier — e.g. “XOR” — and the name property is user-provided. Both are for display and identification purposes. They’re used by the __str__ method.

This base class encapsulates the general idea of a logical circuit point. It has a state, and it links to points downstream.

§

The next two classes are also abstract classes:

class one_gate (logic_gate):
    def __init__ (self, name, kind):
        super().__init__(name, kind)
        self.a = False

    def input_a (self, state):
        self.a = state
        self.change()

class two_gate (one_gate):
    def __init__ (self, name, kind):
        super().__init__(name, kind)
        self.b = False

    def input_b (self, state):
        self.b = state
        self.change()
#

The intent here is to encapsulate the idea of a one- and two-input logic gates.

An input includes an input state and an input method. The two-input class inherits one input, a, from the one-input class and adds a second, b.

The input method (input_a or input_b) receives an update state from the caller and applies it to the input state.

Then it calls the change() method. Note this is not the same method shown in the logic_gate base class. The method actually invoked is in the derived sub-classes below. (They ultimately invoke the change(state) method of the top class.)

We’ll get to that now.

§

The first two concrete classes inherit one_gate and implement an I/O (input or output) point and a NOT gate:

class io_point (one_gate):
    def __init__ (self, name):
        super().__init__(name, 'I/O')

    def change (self):
        super().change(self.a)

class not_gate (one_gate):
    def __init__ (self, name):
        super().__init__(name, 'NOT')

    def change (self):
        state = False if self.a else True
        super().change(state)
#

These classes implement the change() method called by the input classes above. The method does the actual work of the gate.

¶ The io_point is for circuit inputs and outputs, it has no logic, it just applies any input state to its downstream gates. The change() method just invokes the base class logic_gate.change(state) method, passing it the current input state, a.

Output points have no downstream gates (so nothing happens), but they keep any state passed to them for readout. Input points have downstream gates they feed, but they only get new states from external user inputs.

¶ The not_gate isn’t necessary for the full-adder, but I included it for completeness. (It was the only gate not needed.) The change() method here inverts the current state and passes the new state to logic_gate, as just described.

We may not need it to implement a full-adder, but it completes a toolkit that allows us to model any basic logic circuit we want.

§

The final gate classes implement the three classic logic gates, AND, OR, & XOR:

class and_gate (two_gate):
    def __init__ (self, name):
        super().__init__(name, 'AND')

    def change (self):
        state = True if (self.a and self.b) else False
        super().change(state)

class or_gate (two_gate):
    def __init__ (self, name):
        super().__init__(name, 'OR')

    def change (self):
        state = True if (self.a or self.b) else False
        super().change(state)

class xor_gate (two_gate):
    def __init__ (self, name):
        super().__init__(name, 'XOR')

    def change (self):
        state = True if (self.a ^ self.b) else False
        super().change(state)
#

Note that, as with the io_point and not_gate classes, these concrete classes provide the kind label. The user-provided name value is just passed up the line.

In the change() method for each logic gate, the appropriate logic generates a new state from the two inputs, a and b, and passes that new state to the logic_gate.change(state) method where it gets passed to downstream gates.

§

The final class uses the gate classes to finally implement a full-adder:

class full_adder (object):
    def __init__ (self):
        # Inputs...
        self.i1 = io_point('a' )
        self.i2 = io_point('b' )
        self.i3 = io_point('Ci')
        # Outputs...
        self.o1 = io_point('S' )
        self.o2 = io_point('Co')
        # Gates...
        self.x1 = xor_gate('X1')
        self.x2 = xor_gate('X2')
        self.a1 = and_gate('A1')
        self.a2 = and_gate('A2')
        self.r1 =  or_gate('R1')
        # Connections...
        self.i1.gates = [self.x1.input_a, self.a2.input_a]
        self.i2.gates = [self.a2.input_b, self.x1.input_b]
        self.i3.gates = [self.x2.input_b, self.a1.input_b]
        self.x1.gates = [self.x2.input_a, self.a1.input_a]
        self.x2.gates = [self.o1.input_a]
        self.a1.gates = [self.r1.input_a]
        self.a2.gates = [self.r1.input_b]
        self.r1.gates = [self.o2.input_a]

    def __call__ (self, a, b, c):
        self.i1.input_a(a)
        self.i2.input_a(b)
        self.i3.input_a(c)
        return (self.o1.state, self.o2.state)
#

The constructor creates three io_point instances for the inputs (lines 4–6), two io_point instances for the outputs (lines 8,9), and various gate instances for the full-adder gates (lines 11–15).

The inputs and outputs are named appropriately. The gates are given simple obvious names to keep them straight. (The names follow the logic circuit shown above using a left-to-right and top-to-bottom protocol.)

In lines 17–24, the inputs and gates are linked to the appropriate inputs of their downstream gates. This builds the network of the full-adder circuit.

¶ The __call__ method allows us to use the full_adder class like this:

FA = full_adder() 
def full_adder_6 (a, b, ci):
    return FA(a, b, ci)
#

Which is pretty simple usage. (Just a rather involved implementation!)

Compare this with the five examples in the previous post. The usage code above makes it look like one of the simplest examples, but remember those other examples are fully self-contained. This one has all the above code behind it.

How the method works brings up a crucial point about the simulation…

§

Each of the inputs is applied separately and allowed to trickle downstream (potentially all the way to outputs) before the next input is applied.

In a physical adder, inputs are applied more-or-less in parallel, but at a nano-scale, they may not all arrive together. Therefore applying them one after the other in the function isn’t really an issue.

In real applications, outputs have time to settle, all changes having propagated through, before the system reads the output value. This synchronous behavior — standard in all computers — eliminates any race conditions due to trickle through delays.

In the function above, the outputs aren’t read until the end, which serves the same purpose. All input signals have trickled through.

§

An even finer-grained simulation might model the transistors. This potentially allows a simulation involving one basic type of functional object (the transistor).

It turns out that a full-adder simulation based on NOR gates comes very close to such a low-level representation.

That’ll be the topic of the next post.

∅

---

^[1] I find this a very strong argument against computationalism.

^[2] The nature of this design concealed why that design choice has problems. When gates have default True outputs, starting conditions need to propagate through the circuit to insure all gates have correct states.

But if an input sees its starting state as identical to its default state, it never propagates the starting state.

^[3] Which says a great deal about the complexity of modeling physical reality versus modeling an abstract object.

We’re modeling the physical thing that reifies the abstract thing. Our earlier models directly modeled the abstract thing.