Mealy state machine.

[omerysmi]

Hi,
I have an exercise which i need to detect a block of an odd number of '0's, and then the output will be 1.
for example if i get "10001" the output will be '1' after detecting "0001".

I need to implement it with mealy state machine (X is input, Y is output).
This is what i did, Does it right?

 

[andre_luis]

I didn't take a deep look at the diagram above, but in general the first step is to make a table containing the current and the next states and their corresponding outputs, and just after that, draw it in graphic mode.

 

[Mohammed Abrar]

Not really. Mealy state machine for detecting "10001" will have 5 different states. You only have two A and B.

 

[FvM]

The description isn't particularly clear, but I believe you need three states. The present state machine detects odd number of zeros.

 

[omerysmi]

The description isn't particularly clear, but I believe you need three states. The present state machine detects odd number of zeros.

I didn't explain myself very well but i can't edit the post now, so i will explain again:
if the machine detect a sequence of odd number of zeros the output will be '1'. for example:

X: 00010010110
Y: 10101001001

Maybe this is right?

 

[FvM]

O.K., different problem, different solution.

 

[omerysmi]

O.K., different problem, different solution.

I made a very big mistake, it should detect an odd number of zeros..the problem is that i cannot edit the post
I also don't know if a single '0' considered as a "block of zeros"..

 

[ads-ee]

The statement "block of zeros" would imply that 1 zero is not a block of zeros and that the block is atomic so only when the block is complete do you detect if it's odd or even. You should clarify this requirement.

At the moment the FSM you've proposed won't work (using my assumptions) as it flags all odd instances of 0 in a block of 0's.
e.g.
X=100000010001
Y=010101001010

You need four states where...

State1 (initial, or one): start with assuming input is 1 (initial state)
stay in this state until input is 0 and go to first zero state.
State2 (first zero): either go to state1, if a '1' shows up, or go to state 3 if a '0' shows up (even zeros)
State3 (even zero): either go to State1, if a '1' shows up (means the block of 0's is an even count), or if a '0' shows up then go to state4 (odd zero).
State4 (odd zero): either go to state1, if a '1' shows up and output a 1 on Y to indicate and odd number of zeros, or if a '0' shows up then go back to state3 (even zero)

If you are supposed to detect singleton '0's then get rid of state4 and adjust the Y output to go active when exiting state2 back to state1, and send state3 back to state2 instead of state4.

Of course this is probably a homework assignment so I probably should not have given such a detailed answer....

 

[omerysmi]

The statement "block of zeros" would imply that 1 zero is not a block of zeros and that the block is atomic so only when the block is complete do you detect if it's odd or even. You should clarify this requirement.

At the moment the FSM you've proposed won't work (using my assumptions) as it flags all odd instances of 0 in a block of 0's.
e.g.
X=100000010001
Y=010101001010

You need four states where...

State1 (initial, or one): start with assuming input is 1 (initial state)
stay in this state until input is 0 and go to first zero state.
State2 (first zero): either go to state1, if a '1' shows up, or go to state 3 if a '0' shows up (even zeros)
State3 (even zero): either go to State1, if a '1' shows up (means the block of 0's is an even count), or if a '0' shows up then go to state4 (odd zero).
State4 (odd zero): either go to state1, if a '1' shows up and output a 1 on Y to indicate and odd number of zeros, or if a '0' shows up then go back to state3 (even zero)

If you are supposed to detect singleton '0's then get rid of state4 and adjust the Y output to go active when exiting state2 back to state1, and send state3 back to state2 instead of state4.

Of course this is probably a homework assignment so I probably should not have given such a detailed answer....

But in your example a single zero considered as a block of zeros because after the first zero Y is '1'..

Anyway, why 4 states? I managed to do it with 3 states (here a single zero is not a block) A is the first state

 

[ads-ee]

Your FSM will produce the following output when you have the following input:
111000001000000111
AAABCBCBABCBCBCAAA
000001010001010000
You detect every time the number of 0's becomes odd (C->B transition) not that there are an odd number of 0's in an complete block of 0's.

I believe the design is supposed to detect odd blocks of 0's like this:
111000001000000111
000000010000000000
or more likely like this: note you detect that the end of the block of 0's occurs when the input goes back to 1.
111000001000000111
000000001000000000

The first block has five 0's the second block has six 0's, in this case only the first block should indicate an odd number of 0's.

 

[omerysmi]

1. to wait until '1' will appear and then to see if the block was even or odd (but there is a problem because '1' could also not appear in the end like "1101000"

If the block has no end then you can't say the block has an odd number of zeros as there is nothing to indicate the block has finished. Unless there is some other signal besides x that says the serial bit transmission is over. You could then use such a signal to end the block and determine there are an odd (or even) number of zeros.

My case for 4 states is that you need 2 states just to track the odd/even count of zeros. One state to idle in when there are only 1's. And one state if needed to deal with the singleton zero case (but this could be removed if it's a valid block).

 

[andre_luis]

You need four states

I agree; just 2 bits must be considered, One for the previous value and One for the current value, so there are 4 combinations, like that:

 

[ads-ee]

omerysmi,

Sorry but it somehow it ended up that I edited your post #11 instead of replying with quote. So take a look at my explanation there on what I think is required for sequences that end on 0.