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

digital-logicflipflopstate-machines

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?

Best Answer

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.

enter image description here

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)

enter image description here

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