### Tuesday, December 4, 2012

# Finite State Machine that adds two integers

**Q.**Construct a ﬁnite-state machine or finite state automaton that adds two integers (using binary representation of integers).

**Sol:**

Finite Automata (FA) or Finite State Machine to add two integers can be constructed using two states:

·

**q**: Start state to represent carry bit is 0_{0}
·

**q**: State to represent carry bit is 1_{1}
The inputs to FA will be pair of bits i.e. 00, 01, 10, and 11

The FA starts in state 1 (since carry is 0) and inputs a pair of bits. If the pair is 11, the FA outputs a 0 and switches to state 2 (since the carry is 1), where the next pair of bits is input and is added to a carry bit of 1.

Example: Consider the addition of 52 and 21

110100 - (binary representation of 52)

010101 - (binary representation of 21)

Since adding numbers is done from right to left, The first input symbol is 01, representing a 0 in the rightmost (binary) digit of 52 and a 1 in the rightmost digit of 21. The machine enters state

**q**(since there is no carry) and outputs a 1. The next input is 00 because both numbers have zero as the second rightmost digit. The machine enters state_{0 }**q**and outputs 0. The next input is 11. The machine enters state_{0}**q**(since the carry is 1) and outputs 0. Being in state_{1}**q**means that there is a carry from this position into the next. And the remaining bits can be worked out to get 1001001 (i.e. 73)._{1}
Subscribe to:
Post Comments (Atom)

AWESOME :)

ReplyDeleteplz explain or more i got confused

Deleteperfecto

ReplyDeleteThere is a typo in the first sentence directly below the diagram. It should read as follows: The FA starts in state 0 (since carry is 0) and inputs a pair of bits. The 1 should be changed to a 0.

ReplyDeletewell explained!

ReplyDeletegrt explanation

ReplyDeleteWhat is the equivalent Moore machine?

ReplyDeleteawesome and ty

ReplyDeleteWhat about the last carry bit

ReplyDeleteYou can write as many zeros to the left of integer as you want,because it doesn't change it's value.So we can consider that the last input is 00 and according to the graph,output for that will be 1.

Deletelast carry is write down i think

ReplyDelete