4
\$\begingroup\$

The accepted way for implementing a sequence detector is with a state machine. why implement a SM when (it seems) any sequence detector can be implemented with logic demonstrated below (ASIC and FPGA)

 module detect_1011;
       input bit in_bit;
       output bit detected
       bit [3:0] in_seq;
       always @(posedge clk);
          in_seq <= (in_seq<<1) | in_bit;
       assign detected  = in_seq == 4'b1011;
    endmodule
\$\endgroup\$
  • \$\begingroup\$ Sorry, we can't tell you with what's wrong with a random piece of code. From my perspective, I don't even see what would be wrong with this, especially since 4bit-LUTs do exist on some FPGAs. Does it work? Does it do the same as your FSM? Is the speed, resource consumption, power the same? \$\endgroup\$ – Marcus Müller Feb 12 at 12:14
  • \$\begingroup\$ edited the question to clarify. @MarcusMüller \$\endgroup\$ – Meir Feb 12 at 12:20
  • 1
    \$\begingroup\$ Even if you can contrive an analog approach to recognizing a sequence, the behavior will still be a state machine. \$\endgroup\$ – analogsystemsrf Feb 12 at 17:53
  • 2
    \$\begingroup\$ "why implement a SM when (it seems) any sequence detector can be implemented with logic demonstrated below" The logic presented is a state machine, though ... \$\endgroup\$ – DarthFennec Feb 12 at 21:44
  • \$\begingroup\$ Your approach only works for fixed-length sequences, while an FSM can detect any sequence expressed in a regular language, including sequences of unbound length. \$\endgroup\$ – Dmitry Grigoryev Feb 13 at 8:13
11
\$\begingroup\$

Just because you can find a different, and what seems to you easier, way to detect a toy sequence, doesn't mean that state machines are dead, or that you shouldn't do the exercise you've been set. Celebrate your creativity, it's good to think of alternatives, but work on the state machine solution as well.

It's frequently not clear to students that any given exercise is merely scratching the surface of a method. In order to be able to use it well, we often have to do exercises which seem trivial, or that they would be 'far simpler' if done in some other, usually later, way.

State machine can do much more than just detect sequences, and often faster and at lower power than FPGAs.

Due disclosure. As a physics undergrad, our year-long lab exercise was to build a quite comprehensive sine/square signal generator. It was suggested to us that the we use emitter coupled logic to implement the logic in the squarer. I went 'nah, ECL is old hat, I am sure that at 20MHz I can squeeze the speed out of simpler common emitter stages by reducing voltage swings and impedances. And I could.' Years later, I found myself learning ECL anyway to design a 3GHz ASIC, when it was the only viable route.

\$\endgroup\$
  • 1
    \$\begingroup\$ all the questions regarding sequence detection involve SM's... \$\endgroup\$ – Meir Feb 12 at 12:48
  • 8
    \$\begingroup\$ Schools love sequence detector state machines, because state machines are actually quite important to understand, not because a state machine is always the way to do sequence detection. The nice thing about a sequence detector from an academic perspective is that it lets you introduce a lot of state machine stuff without many dependencies on other complicated things. You don't want to be showing beginners how the state machines in say a DDR4 interface works because they are Complicated and have incestuous relationships will all sorts of really hairy bits of the FPGA. \$\endgroup\$ – Dan Mills Feb 12 at 13:21
8
\$\begingroup\$

You're right, you can implement any sequence detector that way.

But that means that if your sequence is \$N\$ bits long, you'll be doing

  • \$N\$ shifts
  • \$N\$ 1-bit comparisons
  • a logical AND of \$N\$ comparisons every time step

every time step. The first point means you need \$N\$ flipflops, the second and third means you need \$N\$ gates for the reference comparison and a \$N\$-input AND. That's a lot of resources, for sequences a bit longer than your cute little 4 bit. Worse even, assuming you only have dual input ANDs, a \$N\$-input AND takes roughly \$2N-1\$ 2-input AND gates in \$\log_2 N\$ combinatorial layers.

With the FSM, you'll need to two comparisons, and single combinatorical layer depth.

\$\endgroup\$
  • 3
    \$\begingroup\$ Except that this sort of question is usually a school problem in a HDL of one sort or another, and they are usually targeting an FPGA or such. In which case the mess of gates typically collapse to a couple of lookup tables. For trivial sequence detection in production code I would much rather see a short shift register and matching pattern then a classical state machine implementation because it is much easier to read and ease of reading is far more important in most code then saving a trivial number of logic cells. \$\endgroup\$ – Dan Mills Feb 12 at 13:17
  • \$\begingroup\$ @DanMills fully agree, that's what I commented on OP's question in the first place: Why would that even be wrong? Also, no guarantees that a synthesizer wouldn't look at that shift, first infer it's a shift register, use dedicated hardware for that, then infer that since the N-parallel comparisons need to be implemented cascadedly start cascading from the oldest bit – and hence end up in an equivalent FSM implementation, too, but based on the hardware that's actually available. \$\endgroup\$ – Marcus Müller Feb 12 at 13:21
5
\$\begingroup\$

The other answers are correct, but what they haven't mentioned is that your solution is a state machine. It has one state for every possible combination of the most recent \$N\$ bits, which means there are a total of \$2^N\$ states.

Explicitly constructing a state machine to match only the particular sequence of interest results in \$N\$ states, which can be encoded in \$\log_2 N\$ bits. For larger values of \$N\$ this is a pretty dramatic reduction.

\$\endgroup\$
3
\$\begingroup\$

Your approach can't always look back far enough

There are sequences a simple state machine can detect which your approach cannot. For example, a 1, followed by any even number of 0s, followed by a 1.

Your approach could detect 1001, 100001, 10000001, but it can't do the general case. This is because you can only examine a finite amount of history. While you can (at a cost) make that amount as large as you want, it's still finite.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.