Hello all,

I'm trying to draw a FSM (finite state machine) for this problem :
"design a divisible by 3 FSM considering the MSB is coming first"

I draw this FSM but I'm not sure its good.
Can someone please check and correct me if needed ?
The state describes the reminder from dividing the current number by 3.



thanks!

 

What strikes me immediately is that there is no way of getting to state 1.

 

Can you describe in words what your algorithm does? I'm dubious about the ability of your machine to do the job.

 

What strikes me immediately is that there is no way of getting to state 1.

You'r right. I didn't notice that :/
I have a mistake

Can you describe in words what your algorithm does? I'm dubious about the ability of your machine to do the job.

Yes,
suppose for example the input is (enters from right to left) : 1 0 0 1
the output will be :1 0 0 0

 

In a second thought, how can I generate a reminder of 2 ?
the initial state is from state 0 so either if you add 1 from the left side or 0 you won't get a reminder of two. Am I wrong ?
I'm starting to think that maybe the "2" state is wrong and we don't need it

 

If the states represent the remainder then you do need state 2, e.g. '101' remainder 2.
But I don't think that's a good way to solve this.

 

If the states represent the remainder then you do need state 2, e.g. '101' remainder 2.
But I don't think that's a good way to solve this.

you'r right.
so what the hell is wrong here ? What would you suggest of solving this problem ?

 

Rather than thinking of the remainder, think of whether the number so far is divisible by 3 or not.

 

Just thinking out loud, in decimal to decide if a number is divisible by 3, you sum the digits in loops until the result is less than 10, and if it is 3, 6 or 9 then the number is divisible by 3.
What method do you use in binary? You could keep subtracting 3 until you get to 10, 1 or 0 in binary, but you can´t describe that in a state machine unless you limit the size of the input number. You could use faster division with remainder, but the input number still cannot be arbitrarily long. Is there a limit, or should the FSM be working for any number?

Stack overflow suggest you add all the even digits and subtract all the odd digits and check the result for zero, but still you need to know how many digits there are in order to have enough states in your FSM..

(ref https://answers.yahoo.com/question/index?qid=1006030705672)

 

suppose for example the input is (enters from right to left) : 1 0 0 1
the output will be :1 0 0 0

That's not quite what I was looking for because you haven't explained the significance of the output stream.

 

Rather than thinking of the remainder, think of whether the number so far is divisible by 3 or not.

That's not enough because just knowing if the number so far is divisible by three does not give you enough information to determine whether the number, when appended by the next bit, is divisible by three.

For example,

Case 1: So far you have seen 100, which is not divisible by 3. Next you see a 1. The full number is 1001 which IS divisible by three.
Case 2: So far you have seen 101, which is not divisible by 3. Next you see a 1. The full number is 1011 which is NOT divisible by three.

 

Just thinking out loud, in decimal to decide if a number is divisible by 3, you sum the digits in loops until the result is less than 10, and if it is 3, 6 or 9 then the number is divisible by 3.
What method do you use in binary? You could keep subtracting 3 until you get to 10, 1 or 0 in binary, but you can´t describe that in a state machine unless you limit the size of the input number. You could use faster division with remainder, but the input number still cannot be arbitrarily long. Is there a limit, or should the FSM be working for any number?

Stack overflow suggest you add all the even digits and subtract all the odd digits and check the result for zero, but still you need to know how many digits there are in order to have enough states in your FSM..

(ref https://answers.yahoo.com/question/index?qid=1006030705672)

WAY too complicated.

Work in a mod-3 world. You have three possibilities: {0,1,2}. The results of ALL computations map to one of those three congruence classes (a.k.a., remainders).

Consider that

v = 1011001 = (101100 * 2) + 1

That 101100 is the string that has been read so far (just before reading the last bit). That number reduces to one of the three remainders in a mod-3 world.

So after reading the next bit you just need to compute

remainder_next = (remainder_prior * 2) + bit_next

That should be MORE than enough of a glaring hint to solve it.

 

Sounds like homework. Is it?

 

the stream of data starts with MSB making things easy...

1-bit value is not interesting since smallest number divisible by 3 is 3 (or 11 in binary which is 2-bits).

but if you have other value (00, 01 or 10) you need next bit.

any time both leading bits are set - reset them and wait for more data.
if they are not both set, wait till you receive three bits which will always be in 10x format (note MSB must be set).
that third bit will only have value 0 or 1, so group of three bits would be 100 and 101.
each will give you specific remainder... (are you following?)

so just keep crunching data stream till you get to the very last bit (LSB) and remainder will tell you everything.

 

the stream of data starts with MSB making things easy...

1-bit value is not interesting since smallest number divisible by 3 is 3 (or 11 in binary which is 2-bits).

but if you have other value (00, 01 or 10) you need next bit.

any time both leading bits are set - reset them and wait for more data.
if they are not both set, wait till you receive three bits which will always be in 10x format (note MSB must be set).
that third bit will only have value 0 or 1, so group of three bits would be 100 and 101.
each will give you specific remainder... (are you following?)

so just keep crunching data stream till you get to the very last bit (LSB) and remainder will tell you everything.

Boy, I'm sure not following.

It appears that you are designing a machine that has to not only be able to look at three bits of the input at the same time, but also to be able to change them.

It is SO much easier to just have three states and, after looking at just the next bit, you use only the state you are presently in and the value of the next bit to decide which of the three states to transition to. After reading the entire string, you can declare whether it is divisible by three based solely on the state you end up in.

 

Do you want the answer or do you want to work it out?
Is it homework?

 

suppose for example the input is (enters from right to left) : 1 0 0 1
the output will be :1 0 0 0

Does that make sense?

What order are your output bits in? Normal convention is for them to be ordered timewise with the earliest output being to the left.

Is there a reason that you are implementing this as a Mealy machine?

Why is the output 1 when you are in state 1 and are going to transition to State 0 but the output is a 0 when you are in State 2 and are going to transition to State 0?

If you are looking at the very first bit in the string and it is a 1, does this really represent a value that has a remainder of 2 when divided by 3?

What is the input value that the machine sees after reading the final bit in the sequence?

 

WBahn has already given the solution, but I will try to re-explain it.

Each state will represent the value N MOD 3 where N is the number input so far.
So, with each added bit, the new number will be (N * 2 + input), and it's new state will be that MOD 3.

State 0: (the number is 0 MOD 3)
input 0: keeps you in state 0
input 1: puts you in state 1.

State 1: (the number is 1 MOD 3)
input 0: go to state 2 since the number is now 2 + 0 = 2 which is 2 MOD 3
input 1: go to state 0 since the number is now 2 + 1 = 3 which is 0 MOD 3

State 2: (the number is 2 MOD 3)
input 0: go to state 1 since the result is 2 * 2 + 0 = 4 which is 1 MOD 3
input 1: stay in state 2 since the number is now 2 * 2 + 1 which is 5 which is 2 MOD 3

When the number is finished it is divisible by 3 if you are in state 0.

Bob

 

And drawn as a state machine here:
http://stackoverflow.com/questions/844867/check-if-a-number-is-divisible-by-3