state machine question

[maie]

so today my professor gave us a challenge, and whoever gets it right will recive 15 points in the finals.
the challenge is to build a state machine, which recives an endless 0 and 1, in random order, for example-
01011
and everytime the number can be divided by 5, the output (z) will be 1.
for example, for the input (x) above-
0 - can be divided, z=1.
01 - cant, z=0.
010... and so on.
any ideas?

 

[chipseller]

check that the modulus 5 of the input is zero. If so the number is divisible by 5.

VHDL = if (input mod 5) = 0 then output <= 1 else 0;

verilog: always @(input)
if (input % 5 == 0)
output <= 1;
else
output <= 0;
end

or something like that. My VHDL is a bit rusty, so you will have to sort out the syntax yourself

 

[maie]

thanks.
yeah its not a problem with vhdl, but the challenge is hand-writing.

 

[Venkadesh_M]

I assume its a endless stream so it cant be completely stored in any reg,

https://mathforum.org/library/drmath/view/55908.html

You want to sum up the odd and and even bits thats all. for the first bit that was a odd bit but when receiving the second bit new bit set is odd and the old odd set is even.

 

[maie]

intersting..
in that case, whats the state diagram will look like?

 

[D.A.(Tony)Stewart]

Revised 2nd Try

1st you need a word size. Pick an 8, 16, or 32 bit word.
2nd you must define the order of bits by significance, lsb first or last
3rd if you to divide by 5 to get an integer Z=1 else, Z=0

e.g. 0,5,10,15,20,....250,255...
0000 0000 0
0000 0101 5
0000 1010 10
0000 1111 15
0001 0100 20
0001 1001 25
0001 1110 30
0010 0011 35

...separate even & odd bits the complement the polarity of every second odd and even bit start from the LSB then add up as follows;

If Σ even' + 2 * Σ odd' = 0 , Z=1

e.g.
00011110 30
0+0+1+1 odd
-0+0-1+1 odd' with alt. -ve from lsb
2*Σ odd=0

+0+1+1+0 even
-0+1-1+0 even' with alt.-ve from lsb
Σ even' =0

thus 00011110 is an even /5


Now I see the state reduction must use a different method of division by using counters and adders.

 

[mrinalmani]

Are you looking for an algorithm to divide an arbitrary binary number by 5 and determine whether the remainder is zero? (without performing actual division?)

- - - Updated - - -

Well Mr. Skyguy has got it!
Mine was based more on number system, but somewhere in the middle it did involve an arithmetic progression with common difference = 4 (a hint that the pattern maybe a recursive one with four states)

 

[maie]

wow SunnySkyguy, thanks man.
mrinalmani also thanks, helped me understand it more deeply.
is there any way it can be done with mealy or moore?

 

[Venkadesh_M]

1st you need a word size. Pick an 8, 16, or 32 bit word.
2nd you must define the order of bits by significance, lsb first or last
3rd if you to divide by 5 to get integer solution in binary matching the patterns.

e.g. 0,5,10,15,20,....250,255...
0000 0000
0000 0101
0000 1010
0000 1111 ...
1111 1010
1111 1111

Now you can see the simple state reduction to only 4 patterns on 4 least bits and the rest are (x)

Solution is now trivial pattern match.

Then where is 20, 25, 30 and all ? The whole byte will change and whole value will change.

I first got the same thought, this method is only applicable for 2, 4, 8 , 16 divisors..

 

[mrinalmani]

Yes, Venkadesh is correct!
Now let me discuss my algorithm, maybe that'll work. I'll attach a PDF, since its difficult to write equations in this editor.

 

[Venkadesh_M]

Hi SunnySkyguy,

Why don you just post it as a new post ? Or just marked as edited ? It is un-noticeable, or confusing the thread flow.

 

[mrinalmani]

See the attachments

- - - Updated - - -

See the first image, there's a typo in the second image

 

[Venkadesh_M]

Hi mrinalmani,

For this logic also you will need all the data available on a reg is which is not possible for a endless stream.

Try this logic,

I'll work with the number 617283950 = 100100110010110000000101101110.

First split the number into odd and even bits (I'm calling "even" the 
bits corresponding to even powers of 2):

   100100110010110000000101101110
    0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 even
   1 0 0 1 0 1 1 0 0 0 0 0 1 1 1  odd

Now in each of these, add and subtract the digits alternately, as in 
the standard test for divisibility by 11 in decimal (starting with 
addition at the right):

   100100110010110000000101101110
   +0-1+0-1+0-0+1-0+0-0+1-1+0-1+0 = -2
  +1-0+0-1+0-1+1-0+0-0+0-0+1-1+1  =  1

Now double the sum of the odd digits and add it to the sum of the even 
digits:

   2*1 + -2 = 0

If the result is divisible by 5, as in this case, the number itself is 
divisible by 5.

 

[mrinalmani]

@Venkadesh
Your algorithm #13 indefinitely is simpler but it seems to belong to Greece! Would you please explain the basic logic behind it.

And also, as far as the algorithm in post #12....
Storing of number is not required. Only the first level of remainder needs to be stored and updated as new bits arrive. The remainder for bit n is dependent only on the nth bit and not on the entire number.

 

[D.A.(Tony)Stewart]

Mine is same as #13. state machine can stream in both. A word length MUST be defined and needs to be buffered.

The last bit leaving the buffer must be removed from the counters if it is a "1" as the new bit is entering. The parallel operation is easier than the sequential to figure out as each "1" bit changes from even to odd to even affects the product sum if (alternate polarity {2*odd+even} =0, Z=1

Parallel adders must be used with a odd bits shifted left for *2 function. Ie. LSB of odd bit added input is not used.

- the odd "1" bits are counted twice and even "1" bits counted once with another T filpflip to alternate polarity of even& odd bits.

This alternate bit strategy comes from the value of the divisor, 5 which in binary is 101

Repeated my earlier revised post for convenience.

................

...separate even & odd bits the complement the polarity of every second odd and even bit start from the LSB then add up as follows;

If Σ even' *+ 2 * Σ odd' = 0 , Z=1*

* *e.g.
* 00011110 30 * * * * * * * *
* 0+0+1+1 *odd
* -0+0-1+1 *odd' with alt. -ve from lsb
2*Σ odd=0

* *+0+1+1+0 even
* -0+1-1+0 even' with alt.-ve from lsb
Σ even' =0

thus 00011110 is an even /5*

 

[Venkadesh_M]

I have just expanded my post in #4.

 

[Tunelabguy]

The answer:

Initial state = S0, output=1

S0 (output=1). if 0 goto S0. if 1 goto S1
S1 (output=0). if 0 goto S2. if 1 goto S3
S2 (output=0). if 0 goto S4. if 1 goto S0
S3 (output=0). if 0 goto S1. if 1 goto S2
S4 (output=0). if 0 goto S3. if 1 goto S4

This defines 5 states, with no other memory needed. State S0 outputs the 1, saying that the number so far is divisible by 5. All the other states say no. For each state, the table describes where to go if the next bit in the stream is a 0 or a 1.