State diagram for 2-bit parity generator

So the question I need help with is: Design a minimal moore state machine for a 2-bit parity generator that outputs ‘1’ if the number of 1s in a 2-bit sequence is odd, and outputs ‘0’ otherwise. Overlap is allowed. (Hint: this can be done with 4 states.)

Sample input: 0 1 0 0 1 1 0
output: 0 0 1 1 0 1 0 1

a) Describe the states.
b) Draw a state diagram.

I've covered three pages trying to figure out how to draw the state diagram and I can't seem to get it to work. A 1-bit parity generator seems easy, but for some reason I can't figure it out for 2 bits. Any help is greatly appreciated.

As given in the question, first we will try to describe the states and then will try to draw the state diagram.

The output of this machine depends on the present and previous input. So there can be four combinations:

-----------------------------------------
Previous_input   Present_input   Output
-----------------------------------------
0               0           0       S0
0               1           1       S1
1               0           1       S2
1               1           0       s3
-----------------------------------------

Since you need Moore implementation you have to consider 4 states corresponding to the four combinations given above. I have labelled the states using symbols S0-S3. From your sample input-output combination, it is clear that the initial state should be S0.

Part-a of your question can be answered from the above table.

Since we have got the states and corresponding output, the next step is to make the transition state table. The next state depends on the input and previous state.

------------------------------------
Present-state   Input   Next-state
------------------------------------
S0          0         S0
S0          1         S1
S1          0         S2
S1          1         S3
S2          0         ??
S2          1         ??
S3          0         ??
S3          1         ??
------------------------------------

I think you can replace the ??s in the table by your own. Drawing state diagram is simple once the this table is completed. Because, state diagram is the schematic representation of this table.

• Ahh I get it now, thanks! I didn't realize that with just one input of 1 it should output a 1, but I guess that is odd afterall. – Austin Apr 8 '15 at 15:05