# Sequence Detector forced to wait a specific number of bits

So I have this little problem, where I am supposed to build a sequence detector which is forced to wait a specific number of bits before going into the reset state. It's kind of like pin codes work. You put the whole 4-digit sequence number and in the end it says if the output is true (1) or not (0). An example our professor gave is: A sequence detector waits for 4 bits and outputs 1 if the 4-bit sequence has at least two 1s. If anyone does not mind explaining how to build a system like this or find me a lecture/notes/site/tutorial where I can understand this concept. I can only use Mealy machines state diagrams.

• Can't your professor help? – HandyHowie Feb 12 at 13:21
• @HandyHowie To be honest, I don't really understand nor like his way of explaining concepts. – c0mp13x Feb 12 at 13:25
• What is the protocol or condition where a 4-bit sequence is interpreted to contain two 2s? Is it two 2-bit integers? – Cristobol Polychronopolis Feb 12 at 13:25
• @CristobolPolychronopolis My mistake, I'm sorry. I meant to write two 1s. The sequence inputs are binary, 1s or 0s. So for every 4bits it has two check if there are two 1s. – c0mp13x Feb 12 at 13:27
• At least two 1s (bits set, right?) or exactly two 1s? – Cristobol Polychronopolis Feb 12 at 13:39

You have two possible inputs -- a "0" or a "1". What happens when one of those is entered?

It seems like you need to maintain TWO counters, one with how many digits have been entered, and one with how many of them are "1".

There are shortcuts you can take to minimize the number of states. For example, if you've already got two "1"s or three "0"s, there's no longer a need to maintain the counter with the number of "1"s. Also, history of the sequence doesn't count in your example case; e.g., if you have reached one "1" after two inputs, you don't care if the history that got you there was "01" or "10", so you don't need to maintain a state for each.

Generalizing these things involves truth tables, Karnaugh maps, and tedium. I don't think you really need to do that. In your sequence, you have 2^4 possible combinations of inputs. Brute force will thus bring you to 16 states you can end up in, plus a starting state, plus 2+4+8 intermediate states. Truth tables will show you some duplicate states, so you can reduce.

I've drawn up something real quick. The left to right columns are the number of inputs entered, and the down to up rows basically correspond to how many ones have been entered. I've labeled the states with how many "1" have been entered so far, and you can see where I've reduced duplicate states, as those states are labeled with $$\<\$$ or $$\\geq\$$ signs, or have more than one input path to them. You can also see that the arrows with two numbers show that success or failure (given you reach four inputs) has already been determined. Note that I did not include the final step of returning to the starting state.

• Ohh, that is absolutely brilliant, thanks a lot, Scott. I finally seem to understand how it works. – c0mp13x Feb 12 at 15:39

I always find it mind bogging why anybody would write a huge many-states FSM for this sort of code.
In practice I would use two counters:

• First counter counts the number of keys pressed.
• Second counter counts the number of ones pressed.

Both reset if the first counter gets to four. At that same time you output a one if the second counter is above a certain threshold .e.g 2.

Yes, you might use a register or two more then needed, but you save hours in development time and the code will be a lot easier to read and thus to maintain. My guesstimate is that the Verilog FSM code is about ten times bigger than the two counters code.

• Writing Scott's state machine in HDL takes about as long as it took him to draw the diagram. The core logic is about a dozen lines of Verilog or VHDL. After that, the synthesis tools do all the heavy lifting. – Dave Tweed Feb 12 at 18:12