# How should I proceed with implementing a multiple sequence detector FSM?

I was given the following question:

Design a finite state machine (FSM), with not more than 4 states, that will detect more than one number of 1’s in the previous 3 samples. For example -

Input Sequence: 0101011001
Output Sequence: 0001011100


So this means, I have to build a sequence detector which would detect -

011
101
110


Now the problem I am facing is -

1. How should I define the states and decide the number of states? Is there any standard procedure for multiple sequence detectors?
2. On what basis should I decide the type of machine - mealy or moore?

One way to solve the problem is making 3 different sequence detectors and then OR the outputs, but that would definitely be treated as a wrong and inefficient answer besides the fact that I can't use more than 4 states.

• you don't need to detect 111 Jul 17, 2023 at 6:20
• @jsotola Ah, yes. My bad Jul 17, 2023 at 6:29
• I would shift the data bit for bit into an input register of known width (e.g. 4bits) and compare this to an array of patterns possible. The result of the comparison i would "OR" together. Not what you asked, but how i would solve this problem. Jul 17, 2023 at 6:41
• @Killjoy It's a Mealy. And the 4-state limitation is why. Consider this. You've been asking about HDL and I'm surprised you aren't well past this. But then I don't know the modern curriculum, either. The states shown just tell you which bits have been seen previously, prior to the current incoming bit. That incoming bit tells you what new state to move towards. I've added a notation of NC (no change), SET and CLR for the output FF for each state transition. Not the only way. See if it makes sense. See if you can come up with a new approach. Jul 17, 2023 at 10:44

One approach would be to use the state to encode the history of the previous two inputs:

• 0: b'00
• 1: b'01
• 2: b'10
• 3: b'11

You can use the state bits and the current input to determine the output:

• when two or all three bits are '1', then the output is '1'
• otherwise the output is '0'

You can easily determine the next state by updating the history:

• shift out the oldest value
• shift in the current input

Hint: Your FSM could just track how long it's been since the last 1. Draw three states as circles, name the states with that duration. Then add arrows that represent state change given an input. There's one special case you need to track, so that's what you can use the fourth state for.