Continue to Site

# state machine question

Status
Not open for further replies.

#### maie

##### Newbie level 5
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

##### Full Member level 3
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

### maie

Points: 2

#### maie

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

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

##### Newbie level 5
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.

maie and mrinalmani

Points: 2

### maie

Points: 2

#### 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

### maie

Points: 2

#### maie

##### Newbie level 5
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?

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

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

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

#### Attachments

• Capture27.PNG
86.3 KB · Views: 56
• Consider an arbitrary number N.pdf
286.7 KB · Views: 40
• Capture27.PNG
86.6 KB · Views: 66
Last edited:

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

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

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*

I have just expanded my post in #4.

mrinalmani

### mrinalmani

Points: 2

#### Tunelabguy

##### Full Member level 5

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.

Status
Not open for further replies.