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

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?

• Hint - There are only 5 states required - total of 0,1,2,3,4. You seem to think that it's necessary to have a state for each possible sequence, but that's not true. May 8, 2017 at 13:07
• The obvious solution is to simply store the last four input values in a four-bit shift register, and then a simple combinatorial circuit can count the ones. So there are at most 16 states, which really shouldn't be a problem in a homework assignment. May 8, 2017 at 13:09
• @DaveTweed, the obvious solution is not to use an FSM at all but that's not the homework OP's been given. May 8, 2017 at 13:41
• @TonyM: Can you explain how a shift register is NOT an FSM? May 8, 2017 at 13:55
• Your state machine is describing an up-/down counter, where a 1 counts up and 0 counts down. The counter has a range of 0..4, that means you have to implement a saturation counter (4 + 1 = 4). So in total you have 5 states for 0,1,2,3,4 and 10 transitions (1 input * 2 input states * 5 states). May 8, 2017 at 22:45

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

• Falstad simulation tinyurl.com/la8dwnk May 9, 2017 at 20:10
• Note that this solution is a Moore machine (output depends only on the current state), not a Mealy machine (output is a function of both state and inputs). I'm surprised you accepted it. May 11, 2017 at 15:26
• Sorry Dave but Shift Registers (4xD FF's) store 4 previous states ( the states of previous bits) which can be reduced to 3 plus current state. I am surprised at your response too. In fact any latch or register defines a primitive state machine. (memory). If you don't vote to agree, I would't be surprised or upset. May 11, 2017 at 15:47
• A Moore machine does not rely on memory , only combination logic. May 11, 2017 at 15:55
• That last comment makes no sense at all! ALL state machines have memory -- that's the very definition of a state machine. May 11, 2017 at 15:58

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.

• I think this will converge on the same solution that I came up with, but in a much more roundabout way. May 9, 2017 at 18:29
• @DaveTweed: Since this is a teaching exercise, I thought that learning to start with a full enumeration of states and identify those that can be merged would be useful. May 9, 2017 at 21:49

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.

• Note that the 16-state version that I mentioned previously is actually a Moore machine. May 8, 2017 at 14:20
• This design fails to work. U forgot if Input=1 with SR=000 then output is ALWAYS cleared. Your design is basically an Even Parity generator. May 9, 2017 at 18:21
• @TonyStewart.EEsince'75: Clearing the output in that case is correct. How could it be otherwise? May 9, 2017 at 18:23
• Then it will never count 2 one's 0000011 should become Out=1 on the last bit but your design always CLEARS output (all other cases) May 9, 2017 at 18:26
• @TonyStewart.EEsince'75: Look again. With that input sequence, the shift register will contain 001 when the current input is the second one -- this meets the second criterion, and the output will be set. May 9, 2017 at 18:32