Designing a state machine to detect if input was high exactly 2 times in last 4 clocks

Question

Design a Mealy machine with a one bit input, and a one bit output. The output is 1 if in the last 4 clock s, exactly 2 of 4 values on input are 1. Use D flip-flops and discrete gates. Use binary state assignment

I have problem in drawing state diagram for this circuit. Isn't it too complicated? Because for each state, we can have too many different states based on previous one.

Can someone help me a little to simplify the problem?

Answer 1

CORRECTION

The Mealy machine stores each state with 3 sequentially stored bits plus INPUT.

Please revise my Moore Machine to a Mealy Machine by only using 3 bits stored and 1 present state input = D

(Just for Dave who was right but he is still trying to make his simple algorithm which has a more complex schematic)

Both types can produce output glitches if output is not re-sync'd with a register from transition delays of 0>1 and 1>0 on different gate inputs.

The Moore machine does not use present input as mine does below, which is easily corrected but requires an extra flip flop to convert random data into synchronized clocked data as the present state input, so result is the same!!

Note the FF at the output is necessary to prevent Race Conditions or Metastable glitches.

end edit

The function in a couple ways.

Dave's way with a 3 bit SIPO register, 3 bit adder and comparator for sum=010 for IN=0 and sum=001 for IN=1 and Out=0 for all else.

I prefer the SIPO to be the sequence memory

So the simple solution for me is to disable the output with 3 input NAND and 4 input OR for the count of all 1's and all 0's. (edit.. curses the iPad auto spell corrector)

Solution

• f(D,clk)= {XNOR & OR & NAND} AND all outputs {Qa,Qb,Qc,Qd}

  • (ignore numbered Q's for LSB 1st in simulator) The reason I like Falstad simulator is it only took 10 minutes to use the builtin white noise generator (ANT.enna) and -6dB/oct to convert to pink (-3dB/oct) then brown noise is clipped with the HPF self biased inverter then choose small Options Small grid and select the SIPO and Gates and edit to 4 input.

Note the scope traces with green arrows.

• The 1st shows the NAND output low with >=4 consecutive 1's.
• The 2nd arrow shows the OR output low with >=4 consecutive 0's.
• THese are the only times when the XOR output has to be disabled (AND) so that odd number of 1's = 1 or an even number of 1's =0 so an inverter is applied to make it XNOR.

In case you have a hard time seeing 1's and 0's I made a simple R ladder to count 1's so you see a (nonlinear) 5 level with two 1's being the 3rd level. ( I'm painting but this was too much fun to show a few tricks)

This gating causes glitches so the output must be resampled by same CLK and D FF.

Answer 2

Start by labeling 16 nodes with binary numbers "0000" through "1111". Then label each node with transitions to the state that would be achieved by shifting in a 0 from the right, and by shifting in a one from the right. Mark as "accepting" all states whose number includes exactly two "1"s, i.e. 0011, 0101, 1001, 0110, 1010, and 1100.

Next, observe that if two states are both "accepting" or "rejecting", the "0" transitions from each state go to the same place, and the "1" transitions go to the same place, the two states may be regarded equivalent. For example, "0111" and "1111" are both non-accepting states and both have transitions to "1110" and "1111". Thus, they may be replaced with a single state. Repeat this process until there no more states can be merged and you should have a minimal-state solution to your problem.

Answer 3

To refine my comment further, you need to keep track of whether the previous three inputs, plus the current input, contain exactly two ones, in order to set or clear the output on the next clock edge.

Since order matters, a 3-bit shift register (8 states) is the easiest way to remember the last three input values. Then the rest of the logic works like this:

• If the current input is zero, set the output if the shift register contains exactly two ones.

• If the current input is one, set the output if the shift register contains exactly one one.

• In all other cases, clear the output.

If that isn't the definition of a Mealy state machine, I don't know what is. It should be straightforward for you to fill in the details and complete your assignment.

---

For completeness (a different answer has been accepted), here's the full transition table:

Current          Next
 State   Input   State   Output
 -----   -----   -----   -----
 0 0 0     0     0 0 0     0
 0 0 0     1     0 0 1     0
 0 0 1     0     0 1 0     0
 0 0 1     1     0 1 1     1
 0 1 0     0     1 0 0     0
 0 1 0     1     1 0 1     1
 0 1 1     0     1 1 0     1
 0 1 1     1     1 1 1     0
 1 0 0     0     0 0 0     0
 1 0 0     1     0 0 1     1
 1 0 1     0     0 1 0     1
 1 0 1     1     0 1 1     0
 1 1 0     0     1 0 0     1
 1 1 0     1     1 0 1     0
 1 1 1     0     1 1 0     0
 1 1 1     1     1 1 1     0

It is straightforward to convert this into a logic implementation.