Routine automates pattern/sequence detection

Sequence detection is a common operation in many communication and security systems. Some good examples are HDLC-flag identification and signature analysis. As the complexity of the system increases, designing circuitry for sequence detection becomes tedious and laborious. Using the software tool in this Design Idea, you can generate HDL code in VHDL or Verilog formats for both Mealy and Moore machines for any sequence of arbitrary length. The tool additionally presents options for inferring the sequence-detector state machine in one of the popular encoding styles, such as one-hot, binary, and Gray. Let S0 to Sn–1 be the states of a Mealy machine for n-bit sequence detection. The key to any state-machine design is to find the next state transition, which is a function of the input and the current state. Any state Sm (0≤m≤n–1) indicates that the m bit of the n-bit sequence has been detected so far.

The state machine switches from Sm to Sm+1 on detecting an input that matches the next bit of the sequence. Otherwise, the state machine stays in the same state or switches one of the previous states. The state machine's status depends on the currently received bit and the previously received bits. If this pattern of bits matches the pattern of bits successfully detected in any of the previous states, then the state machine switches to that state. Listing 1 is the pseudocode of the algorithm for determining the next state transition from any state Sm (where m can assume values of 0 to n–1). Let the n-bit sequence be represented as an array of bits called SEQ. The index of the array ranges from 0 to n–1. In the pseudocode, the state machine generally switches from Sm to Sm+1 on detecting an input that matches the next bit in the sequence. But this is not the case for the last state. For nonoverlapping sequence detection, the state machine switches from the last state to the initial state (S0) upon detecting the last bit of the sequence. On the other hand, for an overlapping sequence detection, the state machine either stays in the last state or switches to one of the previous states upon detecting the last bit of the sequence. The routine determines the state-machine behavior in the same way as it determines the next state transition for an input that doesn't match the next bit of the sequence. Refer to the "while" loop of the "if" and "else" blocks of the pseudocode.

For both overlapping and nonoverlapping sequence detection, the output switches high from the last state when the method detects the last bit of the sequence. You could generate a Moore machine by following the same concepts. The only difference would be that the number of states is one more than that of a Mealy machine. Moreover, the output depends only on the states and not on the input, and it goes high only in the last state where the sequence has been successfully detected. This tool can no doubt help a designer to focus on high-level designs, rather than intricate design details. You can extend the idea to detecting double sequences, such as start-of-frame and end-of-frame sequences, and sequences having more than one bit as inputs. Click here to download a zip file containing  Listing 1 and an executable file that creates a GUI (Figure 1) for the sequence detection.

Is this the best Design Idea in this issue? Select at www.ednmag.com.