Tags

, , , , , ,

This is the third post in the Full Adder series. The first post explored ways to code the abstract model of a full-adder. The second post explored one way to code a simulation of a physical system (where the models are of the components of the system).

This post explores another gate-based model, but one with only one type of gate. This simulation is close to being transistor-level.

But not quite.

In fact, the gate involved, the NOR gate, requires two (but only two) transistors. I’ll talk a little about a transistor-level simulation later.

§

Here is the full-adder logic circuit for the code simulate:

It consists entirely of NOR gates. (Which makes it a little more involved than the previous circuit that used an assortment of gates.)

The underlying logic is also more involved:

In the bottom two expressions, substitute progressively for z, y, and x, to realize the full complexity of the two expressions.[1]

Yet they are still just expressions. Conceptually, they have an instantaneous output value for any given input.

There are other pairs of logical expressions that return the same truth table just as there are other logic circuits that implement a full-adder. In fact, those are generally the same thing, the circuit reifies some logic diagram (alternately, any circuit has a logic diagram).

More about this later. Here is the code…

§

There are only two objects in the model, NOR gates and I/O points, so I just created two classes, Terminal and Nor, to represent those objects:

class Terminal (object):
    def __init__ (self, name):
        self.name = name
        self.state = False
        self.conns = []

    def input (self, state):
        self.state = state
        for conn in self.conns:
            conn(self.state)

class Nor (object):
    def __init__ (self, name):
        self.name = name
        self.a = False
        self.b = False
        self.state = True # default out is TRUE!
        self.conns = []

    def __call__ (self):
        self.state = False if self.a or self.b else True
        for conn in self.conns:
            conn(self.state)

    def in_a (self, state):
        self.a = state
        self()

    def in_b (self, state):
        self.b = state
        self()
#

The general architecture is similar to that used for the logic_gates hierarchy in the previous post, but with some simplifications.

¶ The Nor class is self-contained, with code to model a NOR gate.

One big difference from the last design is that the change() -> change(state) split-level processing is merged into a single method that implements the NOR logic and propagates changes. I used the built-in __call__ method for simplicity.

Another change is that signal changes are always propagated even when the state doesn’t change. (There’s no longer a check and early exit.)

¶ The Terminal class is simple; it just has state and possible connections to Nor gates.

As previously, output Terminals have no connections, but input Terminals do. Conversely, output Terminals receive input from the circuit, while input Terminals receive input (for the circuit) from the user (or controlling program).

§

Those are all the objects we need to create the full-adder model:

class full_adder_nor (object):
    def __init__ (self):
        # Inputs...
        self.i1 = Terminal('A')
        self.i2 = Terminal('B')
        self.i3 = Terminal('Ci')
        # Outputs...
        self.o1 = Terminal('S')
        self.o2 = Terminal('Co')
        # Gates...
        self.g1 = Nor('G1')
        self.g2 = Nor('G2')
        self.g3 = Nor('G3')
        self.g4 = Nor('G4')
        self.g5 = Nor('G5')
        self.g6 = Nor('G6')
        self.g7 = Nor('G7')
        self.g8 = Nor('G8')
        self.g9 = Nor('G9')
        # Connections...
        self.i1.conns = [self.g1.in_a, self.g2.in_a]
        self.i2.conns = [self.g1.in_b, self.g3.in_b]
        self.g1.conns = [self.g2.in_b, self.g3.in_a, self.g9.in_a]
        self.g2.conns = [self.g4.in_a]
        self.g3.conns = [self.g4.in_b]
        self.g4.conns = [self.g5.in_a, self.g6.in_a]
        self.i3.conns = [self.g5.in_b, self.g7.in_b]
        self.g5.conns = [self.g6.in_b, self.g7.in_a, self.g9.in_b]
        self.g6.conns = [self.g8.in_a]
        self.g7.conns = [self.g8.in_b]
        self.g8.conns = [self.o1.input]
        self.g9.conns = [self.o2.input]
        # Initialize...
        self(0,0,0)

    def __call__ (self, a, b, ci):
        self.i1.input(a)
        self.i2.input(b)
        self.i3.input(ci)
        return (self.o1.state, self.o2.state)

    def __str__ (self):
        return '%d, %d' % (self.o2.state, self.o1.state)
#

Which is, again, similar to the previous example but a little bigger in terms of number of gates used.

Usage is as simple as in, and basically identical to, the previous adder:

FA = full_adder_nor() 
def full_adder_7 (a, b, ci):
    return FA(a, b, ci)
#

And that’s the code.

§

NOR

Fig 1. ¬ a ∧ ¬ b

Given a requirement to build a logic circuit from only one type of gate, there are only two choices: NAND and NOR.

(The ordinary AND and OR won’t work because most logic expressions require at least one negation at some point. The NAND and NOR gates can be converted to NOT gates by wiring their inputs together.)

On the other hand, it is possible to construct any logic circuit (or expression) using only a NAND or a NOR, because:

NAND = NOT (a AND b) = (NOT a OR NOT b)
NOR = NOT (a OR b) = (NOT a AND NOT b)

So one can always be converted to the other. Figure 1 shows this implemented with gates. Two NOT gates for the inputs, plus an AND gate, create a NOR gate.

The situation is mirrored with NAND gates. They can be constructed similarly to a NOR with two NOT gates for the inputs, plus an OR gate.

Nor gate

Fig 2. 2×Q.

The focus here is on NOR gates because that’s what the logic diagram above uses, and that’s what I’m modeling.

(I don’t know of a NAND-based circuit.[2])

With regard to a transistor-level simulation, Fig 2 shows a possible implementation using two transistors.

It requires two, given our NPN-based design. There has to be at least one for the NOR (or NAND) to invert.

As it turns out, the NAND circuit only needs one; the inversion happens after the circuit’s logical reduction of two inputs to one. (See footnote [1] for the NAND transistor circuit.)

The NOR, as shown in Fig 1, inverts the inputs and then does the logical reduction (the AND). Therefore we need to transistors as those input-inverting NOT gates. The logical reduction stage uses a “wired AND.”

So there is a (meaningful) lower level simulation possible using transistors.

There are nine NOR gates in the above diagram, so a transistor-level simulation involves 18 transistors and nine wired-AND gates (27 objects total). Plus I/O terminals (5), which means 32 objects (of three different types).

As expected at lower levels, the simulation gets bigger. How complicated the objects are at any given level depends on… factors. The Nor gates are pretty simple.

§

In closing, a few words about how these simulations work.

An instance of the full-adder class has a data structure that emulates the logic circuit by connecting gates (or inputs) to downstream gates (or outputs).

The result is a unidirectional mesh structure that flows from input(s) to output(s). The nodes of the mesh are gates; the input(s) and output(s) are related objects with state but no logic.

A change to any input causes that input to call the input method of any gates it’s connected to. That starts a depth-first recursive flow of changes through the circuit.

The first gate called uses the passed state to perform logic and update its own state. It then calls any gates it’s connected to. The first gate it calls calls its own gates, which call their gates, and so on.

Only when the first gate called receives control back from all those sub-gates does it return control to the input (which calls the second gate, if any).

In the case of these full-adder simulations, the code calls all three inputs in sequence, which insures a valid output state, at least after the first call to the adder. It turned out the NOR simulation had an invalid start state due to the default TRUE condition of the NOR.[3]

§

Here’s an instrumented run of the first simulation:

INS: 0 0 0
OUT: 0 0
sum: False False   
car: False False False

 A.1:  (1)  [0 -> 1]
X1.1:  (1)  [0 -> 1]
X2.1:  (1)  [0 -> 1]
 S.1:  (1)  [0 -> 1]
A1.1:  (1)
A2.1:  (1)

 B.1:  (1)  [0 -> 1]
A2.2:  (1)  [0 -> 1]
R1.2:  (1)  [0 -> 1]
Co.1:  (1)  [0 -> 1]
X1.2:  (1)  [1 -> 0]
X2.1:  (0)  [1 -> 0]
 S.1:  (0)  [1 -> 0]
A1.1:  (0)

Ci.1:  (0)

INS: 0 1 1
OUT: 1 0
sum: False False   
car: False True True

The four-line blocks at the top and bottom are dumps of the full-adder’s internal state: Inputs; Outputs; the two XOR gates that sum; and the three gates that carry.

The lines in the middle show the intermediate states at the signal trickles through the adder. The left column names the node; the dotted number is which input, 1 or 2. The number in parentheses is the input state. The part in square brackets indicates a gate state change.

Note how output, S, changes to 1 and back to 0 as a second input trickles through.

The same inputs on the NOR adder are a lot more involved. Here is a partial listing:

INS: 0 0 0
OUT: 0 0
1-4: True False False True
4-9: False False True False False

 A.1: (1)
G1.1: (1)  [1 -> 0]
G2.2: (0)  [0 -> 1]
G4.1: (1)  [1 -> 0]
G5.1: (0)  [0 -> 1]
G6.2: (1)  [0 -> 0]
G8.1: (0)  [0 -> 0]
 S.1: (0)
G7.1: (1)  [1 -> 0]
G8.2: (0)  [0 -> 1]
 S.1: (1)
G9.2: (1)  [0 -> 0]
Co.1: (0)
G6.1: (0)  [0 -> 0]
G8.1: (0)  [1 -> 1]
 S.1: (1)
G3.1: (0)  [0 -> 1]
G4.2: (1)  [0 -> 0]
G5.1: (0)  [1 -> 1]
G6.2: (1)  [0 -> 0]
G8.1: (0)  [1 -> 1]
 S.1: (1)
G7.1: (1)  [0 -> 0]
G8.2: (0)  [1 -> 1]
 S.1: (1)
G9.2: (1)  [0 -> 0]
Co.1: (0)
G6.1: (0)  [0 -> 0]
G8.1: (0)  [1 -> 1]
 S.1: (1)
G9.1: (0)  [0 -> 0]
Co.1: (0)
G2.1: (1)  [1 -> 0]
G4.1: (0)  [0 -> 0]
G5.1: (0)  [1 -> 1]
G6.2: (1)  [0 -> 0]
G8.1: (0)  [1 -> 1]
 S.1: (1)
G7.1: (1)  [0 -> 0]
G8.2: (0)  [1 -> 1]
 S.1: (1)
G9.2: (1)  [0 -> 0]
Co.1: (0)
G6.1: (0)  [0 -> 0]
G8.1: (0)  [1 -> 1]
 S.1: (1)

 B.1: (1)
{{… 44 lines …}}
 S.1: (0)

Ci.1: (0)
{{… 11 lines …}}
 S.1: (0)

INS: 0 1 1
OUT: 1 0
1-4: False False False True
4-9: False False True False True

Notice how the output, S, receives multiple inputs as signals trickle through the network. Generally: the lower the simulation, the more involved it is.

§

So that’s full-adder modeling and simulating code for now.

But this all reminds me of a logical expression parser, compiler, execution engine I wrote a while back. I used it to validate some logic related to this, and it might be worth sharing some time.

Until then, comment as you go.

Ø


[1] And then compare with the expression for the previous adder:

The logical expression here is much more complex!

[2] That would make an interesting exercise. One has to exist.

If nothing else by just replacing all the NOR gates in the circuit above with a combinations of NAND gates. Like this:

Which also shows the (one!) transistor circuit for a NAND.

[3] Ideally, just after building the network, the inputs should push their default state through the circuit to insure all gates and outputs are in a valid default state.

That’s a detail I’m ignoring here for brevity, but note the “Initialize” line (#34) in the constructor for full_adder_nor.