**Tags**

finite state machine, FSA, FSM, full adder, half adder, Python, state engine, state table, truth table

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) — tomato, tomahto. 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**and

_{o}**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}def full_adder_1 (a, b, ci): logic_table = [ [[[0,0],[1,0]], [[1,0],[0,1]]], # a=0 [[[1,0],[0,1]], [[0,1],[1,1]]], # a=1 ] # b=0 b=1 b=0 b=1 return logic_table[a][b][ci] #

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.)

def full_adder_2 (a, b, ci): s = (a ^ b) ^ ci co = ((a ^ b) and ci) or (a and b) return (s,co) #

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.

def full_adder_3 (a, b, ci): s = a + b + ci if s < 2: return (s, 0) return (s % 2, 1) #

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.)

def full_adder_4 (a, b, ci): s,co = (a+b, 0) if s == 2: s,co = (0, 1) s += ci if s == 2: s,co = (0, 1) return (s, co) #

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 #2) 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 #3 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 #4 adds the **C _{i}** bit to

**S**, and the following line (#5) 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}**.

def full_adder_5 (a, b, ci): state_table = { 'start':{0:'S#0', 1:'S#1'}, 'S#0':{0:'S#00', 1:'S#01'}, 'S#1':{0:'S#10', 1:'S#11'}, 'S#00':{0:'S#000', 1:'S#001'}, 'S#01':{0:'S#010', 1:'S#011'}, 'S#10':{0:'S#100', 1:'S#101'}, 'S#11':{0:'S#110', 1:'S#111'}, 'S#000':(0,0), 'S#001':(1,0), # final 'S#010':(1,0), 'S#011':(0,1), # states 'S#100':(1,0), 'S#101':(0,1), # " 'S#110':(0,1), 'S#111':(1,1), # " } state = state_table['start'][a] state = state_table[state][b] state = state_table[state][ci] return state_table[state] #

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 #15) 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 (#16) 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 #17 repeats the process with the **C _{i}** bit. The state from

**b**gets the dictionary, and

**C**indexes it to get the final state.

_{i}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 (#15 – #18) 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.

You must be logged in to post a comment.