How to Implement Mealy Finite State Machine for Sequence Detection?

Fig. Mealy FSM

A Mealy FSM is a type of finite state machine where the output depends on both the current state and the current input. This makes it well-suited for tasks like sequence detection, where the output (detection signal) depends on both the current state in the sequence recognition process and the incoming bit.

Sequence Detector FSM Example: Detecting "1001" Sequence

Fig. Sequence Detector for 1001 sequence

Here's how we can design a Mealy FSM to detect the sequence "1001":

1.) States:

• S0: Initial state (waiting for the sequence to begin)

• S1: Detected "1" (first bit)

• S2: Detected "10" (first two bits)

• S3: Detected "100" (first three bits)

• S4: Sequence Detected ("1001" complete)

2.) Inputs:

• 0: Input bit is 0.

• 1: Input bit is 1.

3.) Outputs:

• Z = 0: Sequence not detected yet.

• Z = 1: Sequence "1001" detected.

4.) State Transition Table:

Current State	Input (Bit)	Next State	Output (Z)
S0	0	S0	0
S0	1	S1	0
S1	0	S0	0
S1	1	S2	0
S2	0	S0	0
S2	1	S3	0
S3	0	S0	0
S3	1	S4	1

5.) Explanation:

The FSM starts in state S0. Upon receiving a "1" input, it transitions to S1, indicating the possibility of the sequence starting. It then checks for subsequent bits. If the sequence doesn't match ("0" received instead of "100"), it resets to S0. Only when the complete sequence "1001" is received, does the FSM transition to S4 and set the output Z to 1, indicating successful detection.

Moore FSM for "1001" Sequence Detection (Possible, but Less Efficient)

While possible, a Moore FSM for this sequence detection might be less efficient. In a Moore FSM, the output depends only on the current state. This would require additional states:

·One state for each valid prefix of the sequence ("1," "10," "100")

· A separate state to represent successful sequence detection ("1001")

This approach increases the number of states for the same functionality. The Mealy FSM directly relates the output to both the current state and the input bit, making it more efficient for this specific sequence detection task.

Check out our Latest Training & Internship, Courses, and NI Jobs Alert.

Live Training & Internship

NI Jobs

Courses

Check out our DIY Kits & Sensors, Electronics Projects & Assistance Plan.

Order DIY Kits & Sensors

Assistance Plans

Projects