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.

![Binary Addition]/resources/005-binary-addition.svg)

In digital electronic it is solved as follows:

Figure 1: 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$

Figure 2: Binary Adder FSM

Imports¶

In [6]:

import itertools
print(itertools.zip_longest("010", "111", fillvalue=0))

import itertools print(itertools.zip_longest("010", "111", fillvalue=0))

<itertools.zip_longest object at 0x102851770>

Algorithm¶

In [15]:

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

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¶

In [16]:

a = "01101100"
b = "01011010"
result = binary_addition(a, b)

print("{}".format(a))
print("{}".format(b))
print("{}".format(len(result)*"-"))
print(result)

a = "01101100" b = "01011010" result = binary_addition(a, b) print("{}".format(a)) print("{}".format(b)) print("{}".format(len(result)*"-")) print(result)

01101100
01011010
---------
011000110