Binary addition FSM
Contents
Binary addition FSM¶
Binary Addition can be solved with an FSM (Finite State Machine). The addition itself is similar than a normal decimal addition except that there are only 4 possible outcomes.
Fig. 9 Binary Addition¶
In digital electronic it is solved as follows:
Fig. 10 Binary Adder Schematic¶
There are more efficient resp. quicker implementation for but the sake of simplicity the above implementaion is best.
The eight outcome state of the binary addition blocs are:
\(c_i\) |
\(b_i\) |
\(a_i\) |
\(q_i\) |
\(c_{i+1}\) |
|---|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
Solution¶
Outcome has 4 states depending on \(q_i = 0,1\) \(c_{i+1} = 0,1\)
Fig. 11 Binary Adder FSM¶
Imports¶
import itertools
print(itertools.zip_longest("010", "111", fillvalue=0))
<itertools.zip_longest object at 0x102851770>
Algorithm¶
def binary_addition(a: str, b: str):
"""Addition of two binary number represented as strings
Args:
a (str): first binary number
b (str): second binary number
Returns:
str: binary addition of a+b
"""
# states (output, {list of transitions})
_q0c0 = 0, {}
_q0c1 = 0, {}
_q1c0 = 1, {}
_q1c1 = 1, {}
# state transitions
_q0c0[1].update({(0, 0): _q0c0, (1, 0): _q1c0, (0, 1): _q1c0, (1, 1): _q0c1})
_q0c1[1].update({(0, 0): _q1c0, (1, 0): _q0c1, (0, 1): _q0c1, (1, 1): _q1c1})
_q1c0[1].update({(0, 0): _q0c0, (1, 0): _q1c0, (0, 1): _q1c0, (1, 1): _q0c1})
_q1c1[1].update({(0, 0): _q1c0, (1, 0): _q0c1, (0, 1): _q0c1, (1, 1): _q1c1})
# reverse to start at the lowest bit
a = map(int, reversed(a))
b = map(int, reversed(b))
_q = []
# simulate state machine
value, transition = _q0c0
# pick element after element for a and b and fill 0 if one number is sharter
for a_i, b_i in itertools.zip_longest(a, b, fillvalue=0):
value, transition = transition[a_i, b_i]
_q.append(value)
# handle carry
_q.append(transition[0, 0][0])
return ''.join(map(str, reversed(_q)))
Test¶
a = "01101100"
b = "01011010"
result = binary_addition(a, b)
print("{}".format(a))
print("{}".format(b))
print("{}".format(len(result)*"-"))
print(result)
01101100
01011010
---------
011000110