computer-science | Insight Maker

The Binary Adder:

Andy Long

Spring, 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:

Your two binary numbers should start off the same length -- pad with zeros if necessary. Call this length L.
Now pad your two binary numbers with three extra 0s at the end; this lets the binary-to-decimal conversion execute.
numbers are entered from ones place (left to right).
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:

For the useless first piece of output -- so n -> n+1
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
For the delay in computing the decimal number: it reads the preceding output to compute the decimal value.

Mat385 Finite State Machine (Binary Adder)

Andrew E Long

This is an example of a finite state machine (FSM), from Gersting's 7th edition (p. 730, Example 29).

It's the first time I've used vectors (for input); and there are a few interesting twists on models that are different for the Finite State Machine.

So it's been an interesting learning experience for me....

It works!

Andy Long

Spring, 2020

Year of Covid-19

Clone of Mat385 Discrete Math FSM -- First Example

ovil

The Binary Adder:

Andy Long

Spring, 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:

Your two binary numbers should start off the same length -- pad with zeros if necessary. Call this length L.
Now pad your two binary numbers with three extra 0s at the end; this lets the binary-to-decimal conversion execute.
numbers are entered from ones place (left to right).
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:

For the useless first piece of output -- so n -> n+1
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
For the delay in computing the decimal number: it reads the preceding output to compute the decimal value.

Clone of Mat385 Finite State Machine (Binary Adder)

Santiago Nicolás

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 Long

Spring, 2020

Year of Covid-19

Mat385 Discrete Math FSM -- Recognition

Andrew E Long