I was involved in a debate recently about whether a full adder logic circuit is a computer. The computer science answer is: “No, not as we define a computer.”

I plan to address that answer in detail on my main blog. Here I wanted to show some of the different ways a full adder can be modeled and implemented.

A full adder logic circuit takes two inputs (two binary bits, a and b) plus a third input, C_i, a carry bit from an adjacent adder (or zero if no adjacent adder). It has two outputs, the sum bit, S, and a carry bit, C_o.

The truth table looks like this:

It can be expressed as two logical expressions:

(The ? symbol means XOR; the ? symbol means AND, and the ? symbol means OR.)

It is commonly implemented logically like this:

Although there are other logic circuits that are functionally identical. (It can be constructed entirely from NOR gates, for example — an exercise for the reader.)

The logical expressions, and the equivalent logic gate circuits, show that the underlying circuit of a full-adder is not, in itself, computational (as computation is usually defined).

The truth table shows the logic has distinct states — eight, in this case. Given the mechanism does have these distinct states, there is a map of those states to an abstract machine that simulates the same states. Thus, the operation can be simulated (or modeled) with a computation.

The map of states for a full adder can be to a truth table (as above), to a Turing Machine, a Lambda calculus, or a Finite State machine (aka automaton).

Above is a diagram of an FSM. I learned it as “machine” — some say “automaton” (so, FSA) — to-may-toe, to-mah-toe. The important part is the Finite State.

Incidentally, the simplicity and regularity of the state diagram is another indicator of the physicality of a full-adder. A given set of inputs immediately trickles down to the output state.

The FSM branches on each of the three input bits, a, b, and C_i. The final state features a payload that is the output bits, C_o and S, respectively. The states are labeled by the bit-pattern established at that point (bits build from right to left).

§

With that in mind, let’s consider how to implement the logic with code. We can model many of the above expressions of the full-adder logic.

Note that all these examples take the input bits, a, b, and C_i, and return a tuple containing the output bits, S and C_o.

The example above implements a logic table version that only requires a single lookup step. This trades code and time for (potentially) large data, since all the logic is contained in the table.

(A real-world implementation might take many steps to accomplish the lookup. The single step is conceptual, as if looking at the truth table to get an output for a given input.)

The second example implements the actual logical expression shown above. The tophat (^) is Python’s xor operator. The and and or are built-in Python operators.

The code here directly corresponds to the logical expressions shown above.

Note that the intermediate steps of assigning the respective expression values to S and C_o aren’t necessary. Those result values could be directly returned in a single step.

Example three models the adder as an actual base two addition (of all three input bits), which requires detecting whether that operation carried.

The logic may not be obvious:

If s is less than two, there was no carry, so just return the sum (which will be 0 or 1), and return C_o=0.

Otherwise, there was a carry, so take the mod 2 of the sum (which removes the carry), and return C_o=1. (The sum will be two or three, and the mod 2 of those is zero and one, respectively.)

The fourth example also uses a mathematical model but acts as if the sum is a single bit with an overflow. (That is, the only allowed values are 0, 1, and overflow.)

The code may not be obvious if you’re not familiar with Python, which very nicely allows setting multiple variables with a list of values. That’s what might seem weird in the assignment statements; they’re setting the value of both S and C_o.

The first step (line #5) sets S to the value of a+b (so it will be 0, 1, or 2). It also sets C_o=0, assuming no carry.

Line #6 checks for a carry. If it occurred, reset S=0 and C_o=1. The output at this point is a correct half-add.

For the full-add, line #7 adds the C_i bit to S, and the following line (#8) checks for the carry (S was either 0 or 1, so it could be 2 now). If there was a carry, the output is reset, as above.

The last step just returns S and C_o.

The fifth example models the FSM version of the adder. Each input, a, b, and C_i, serially drives the FSA from starting state (@) to final state.

All states (in state_table), except the final states, contain a dictionary of possible next states. Here, any given state can only have two possible next states — one for each bit value (0 or 1) that causes a move to that next state.

The final (leaf) states are special in containing the output payload rather than a dictionary. The function returns that payload (the bits S and C_o).

The first step (line #20) gets the ‘start’ state from state_table. As an intermediate (branch) state, the state is a dictionary to possible next states. The a input indexes the dictionary (with a 0 or a 1), so the whole expression returns the next state, depending on a.

The next line (#21) uses that next state to get that state’s dictionary from state_table. In this case the input b indexes the dictionary for the state that depends on b.

Line #22 repeats the process with the C_i bit. The state from b gets the dictionary, and C_i indexes it to get the final state.

Lastly (line #18), the final state gets the payload from state_table and returns it.

As you can see, modeling the FSM results in a large data segment. The code lines (#20 – #22) are unrolled for clarity, but more generally a design would use a loop.

[See the State Engines series (part 1, part 2, part 3), for more.]

§

These examples show some of the different ways we can implement the logic of a full adder. There can certainly be others.

One implementation I didn’t explore is modeling the physical circuit, the logic gates.

I do have such an implementation to show you, but it’s so big it needs its own post. Modeling physical reality is much more complicated! (A separate post will give me elbow room to talk a little about modeling the circuit below the gates at the transistor level.)

But fundamentally, the adder is the logical expression:

Nothing more.

Calling it a computation is equivalent to calling the creeks, streams, and rivers of a watershed a computation — the processes involved are more similar than with the computations shown above.

But that’s an argument for my other blog. This is about the code itself.

Ø