fsm for detecting if a number is divisible by 5 when lsb comes first

If a stream of bits come in lsb first, how do we detect if a number is divisible by 5? I can figure out the fsm if msb comes in first by keep track of the remainder.

One such solution is attached for lsb first. Can someone explain how this fsm works?

hint: calculating the remainder is not the way to go. you have to think of a pattern. I have said too much already...

ThisIsNotSam said:

hint: calculating the remainder is not the way to go. you have to think of a pattern. I have said too much already...

Click to expand...

could you please be more specific and explain? I have already tried to figure out for some time now

The triangle on left is the input.
Follow the states as the bits come, lsb first.
so 101 (that is, 5), 1 (1's place) brings you to q1
0 (2's place) brings you to q4
1 (4's place) brings you to q0- no remainder

try a few other numbers and see how it works

wwfeldman said:

The triangle on left is the input.
Follow the states as the bits come, lsb first.
so 101 (that is, 5), 1 (1's place) brings you to q1
0 (2's place) brings you to q4
1 (4's place) brings you to q0- no remainder

try a few other numbers and see how it works

Click to expand...

I'm not asking if the fsm works...... I'm asking how one can come up with the fsm. If someone knows, please help me understand.

Looking at decimal numbers, only those ending in 5 or 10 are divisible by 5. So perhaps the aim is to look for binary patterns which tell us the number (when written in decimal) has 5 or 10 as the rightmost digits.

I'm asking how one can come up with the fsm. If someone knows, please help me understand.

Click to expand...

I think the OP is asking for a detailed explanation of the state transitions, in words (when in 0 in input in state1, goto state2, etc....)

Is this some homework exercise in a graduate school?

rtldesign said:

could you please be more specific and explain? I have already tried to figure out for some time now

Click to expand...

Nope. Google 'FSM verilog' and there will be your answer.

dpaul said:

I think the OP is asking for a detailed explanation of the state transitions, in words (when in 0 in input in state1, goto state2, etc....)

Click to expand...

No I'm asking how you can come up with the fsm. If you are asked to create an fsm, how would you do it?

for msb first, we use the states to remember what remainder we are at for each new bit we get.

for lsb first, what is the strategy?

rtldesign said:

No I'm asking how you can come up with the fsm.

Click to expand...

that's one question

If you are asked to create an fsm, how would you do it?

Click to expand...

second question

for msb first, we use the states to remember what remainder we are at for each new bit we get.

Click to expand...

statement

for lsb first, what is the strategy?

Click to expand...

Click to expand...

and last question

so you want to know how to go about the process of creating the state diagram you provided.

off hand, it takes a fair amount of thought, trial and error, and probably a lot of banging the head against the wall.

reference: see Franz Kafka's "Conversation with the Supplicant"

i.e. you have to put in the work.

wwfeldman said:

and last question

so you want to know how to go about the process of creating the state diagram you provided.

off hand, it takes a fair amount of thought, trial and error, and probably a lot of banging the head against the wall.

reference: see Franz Kafka's "Conversation with the Supplicant"

i.e. you have to put in the work.

Click to expand...

I guess no one knows how to arrive at the solution other than through trial and error?

rtldesign said:

I guess no one knows how to arrive at the solution other than through trial and error?

Click to expand...

No, not by trial and error.

Write down a bunch of binary values of values starting with 5,15,25,35, etc. All values that are even can be shifted till a 1 is in the LSB to check for divisible by 5. e.g. 1010 => 101 (5) 0 (dropped)

As you don't seem to be making that much of an effort to determine if there is a pattern to this I will stop at this point and let you make an effort to do what I've said and start looking for those unique divisible by 5 bit patterns.

ads-ee said:

No, not by trial and error.

Write down a bunch of binary values of values starting with 5,15,25,35, etc. All values that are even can be shifted till a 1 is in the LSB to check for divisible by 5. e.g. 1010 => 101 (5) 0 (dropped)

As you don't seem to be making that much of an effort to determine if there is a pattern to this I will stop at this point and let you make an effort to do what I've said and start looking for those unique divisible by 5 bit patterns.

Click to expand...

Thanks, but this doesn't work for 25 (11001), 35 (100011), 45 (101101), and so on... How can we come up with a solution that works for infinite stream of bits?

ads-ee said:

No, not by trial and error.

Write down a bunch of binary values of values starting with 5,15,25,35, etc. All values that are even can be shifted till a 1 is in the LSB to check for divisible by 5. e.g. 1010 => 101 (5) 0 (dropped)

As you don't seem to be making that much of an effort to determine if there is a pattern to this I will stop at this point and let you make an effort to do what I've said and start looking for those unique divisible by 5 bit patterns.

Click to expand...

It doesn't work for 30 (11110) which is a even number.

To build an algorithm I would start by looking for binary patterns that work... 101=5 is obviously the first.

The next is 1010=10. A 0 was the first incoming digit. Therefore all initial 0's can be ignored while we wait for a 1 to arrive. (The diagram has a small arrow above the first 0, jumping backwards. All initial 0's are the same as multiplying by powers of 2. )

As soon as a 1 arrives then we start looking for a pattern that works. Therefore 10100=20 works. And 101000=40 works. Etc.

Here is a different pattern: 1111=15. Therefore the list also includes 11110=30. 111100=60. Etc. (Because initial 0's are the same as multiplying by powers of 2.)

Here is a different pattern: 11001=25. Therefore include 110010=50. 1100100=100. Etc.

No doubt there are further new patterns divisible by 5. The diagram apparently contains an algorithm which recognizes these patterns. Someone certainly was clever enough to devise it.

You need to develop your analysis skills, they are currently far too weak.

I guess you don't even understand what the FSM does, it looks for bit sequences that comprise the sum total of fundamental sequences that are divisible by 5. I'm assuming, since I haven't worked it out myself that at some point there are repeating patterns of bit sequences that can be broken down into sub sequences. The FSM operates by finding a fundamental sequence where you end up back in the first state, which means you can start searching for the next fundamental sequence. When the FSM goes from q4 to q0 that signals a subsequence that is divisible by 5.

Now for a few of those "but this doesn't work" examples...geez

Your 30 that you claim doesn't work...
11110 drop the 0 that is what the first state in the FSM does.

1111 which is 15 and is divisible by 5 so any sequence that is from an LSB that has four 1's in sequence IS divisible by 5 and the FSM goes through states q0-q1-q3-q4-q0.

another example from your doesn't work list...
45
101101
101 is divisible by 5
101101
the second set of 101 is also divisible by 5

further more 101101101 is also divisible by 5

this is because the 101 sequence is divisible by 5 and the subsequent repeated sequences of 101 are divisible by 5.

35 is another fundamental sequence as it is not comprised of any other sequence that is divisible by 5

Other sequences of bits are divisible by 5 and shifting them up in bits doesn't change that fact like 1111 shifted up to 11110 is still divisible by 5 or 1111000000.

You need to improve your analysis skills, they are definitely a weakness in your skill set.

I guess no one knows how to arrive at the solution other than through trial and error?

Click to expand...

I must protest at this ignorant comment of yours.

From my personal view point, I cannot answer in details because I don't have so much time and motivation (apart from my 9 -6 job, I have a family and there are tons of other work). This is an open forum and each member has his/her choice to answer or not which will again depend on many factors. You cannot have the expectation here that your problem WILL BE SOLVED (again it depends on how well you have described the problem, what have you done so far and above all, your attitude towards the answers received and how much you want to work at your own problem).

Having said that, many members here have already tried to help you with the algorithm.

I had learnt how to draw FSM charts in my graduate school days. It was a homework on building a cola vending machine FSM. While designing FSMs at my work place now, I use the same logical analysis principles. So if someone says to me they don't know how to arrive at a FSM bubble chart (even if the algo is clear) I would be very suspicious!