Your browser (Internet Explorer 8 or lower) is out of date. It has known security flaws and may not display all features of this and other websites. Learn how to update your browser.



Finite State Machine

Mat385 Finite State Machine (Binary Adder)

Andrew E Long
The Binary Adder:

Andy LongSpring, 2020 - Year of Covid-19​
Having constructed a working example of a finite state machine (FSM), from Gersting's 7th edition (p. 730, Example 29), I decided to create a more useful one -- a binary adder (p. 732). It works!
Subject to these rules:
  1. Your two binary numbers should start off the same length -- pad with zeros if necessary. Call this length L.
  2. Now pad your two binary numbers with three extra 0s at the end; this lets the binary-to-decimal conversion execute.
  3. numbers are entered from ones place (left to right).
  4. In Settings, choose "simulation start" as 1, your "simulation length" as L+2 -- two more than the length of your initial input number vectors. (I wish that the Settings issues could be set without having to explicitly change it each time -- maybe it can, but I don't know how.)
Be attentive to order -- start with 1s place, 2s place, 4s, place, etc., and your output answer will be read in the same order.

To understand why we need three additional inputs of 0s:
  1. For the useless first piece of output -- so n -> n+1
  2. For the possibility of adding two binary numbers and ending up with an additional place we need to force out: 111 + 111 = 0 1 1 1
  3. For the delay in computing the decimal number: it reads the preceding output to compute the decimal value.

Computer Science Mathematics Binary Adder Finite State Machine FSM MAT385

  • 1 year 1 month ago

Mat385 Discrete Math FSM -- Recognition

Andrew E Long
One of my favorite topics in Discrete Math is Finite State Machines (FSM). We study deterministic machines without feedback, which can be used to
 * recognize certain types of strings * perform certain tasks (e.g. binary addition).

This particular example of an FSM recognizes input that include multiples of 3 0s (including none). If the nth input represents a complete multiple of 3 0s, then the output will be 1; otherwise 0.

Andy LongSpring, 2020
Year of Covid-19​

Computer Science Mathematics Finite State Machine FSM MAT385

  • 2 weeks 5 days ago