Designing an Overlapping Mealy FSM to Detect the Pattern D–X–B–B

📌 Обнаружение шаблона D–X–B–B с помощью перекрывающегося автомата Мили

Цель — спроектировать перекрывающийся Mealy-автомат, который распознаёт шаблон D–X–B–B во входной последовательности.
Здесь:

• D, X, B — это символы входного алфавита.
• FSM должен быть перекрывающимся: если шаблон найден, последняя буква может быть началом следующего шаблона.

🧠 Как работает

Входной алфавит:

Σ = {D, X, B, ...}

Выход:

• Z = 1, если обнаружен конец шаблона D–X–B–B
• Z = 0 — в остальных случаях

Состояния:

• S0: начальное, ожидание D
• S1: принято D, ожидание X
• S2: принято D–X, ожидание B
• S3: принято D–X–B, ожидание ещё одного B

Таблица переходов:

Текущее состояние	Вход	Следующее состояние	Выход
S0	D	S1	0
S0	другое	S0	0
S1	X	S2	0
S1	D	S1	0
S1	другое	S0	0
S2	B	S3	0
S2	D	S1	0
S2	другое	S0	0
S3	B	S1	1
S3	D	S1	0
S3	другое	S0	0

Пример работы:

Вход: D X B B D X B B  
Выход: 0 0 0 1 0 0 0 1

FSM успешно распознаёт две перекрывающиеся последовательности.

✅ Преимущества

• Перекрывающийся — не теряет потенциальные шаблоны.
• Mealy-автомат требует меньше состояний по сравнению с Moore-автоматом.

❌ Недостатки

• Реализация может быть сложнее в синхронных цифровых схемах из-за вывода на переходах.

⚙️ Где применяется

• Синтез цифровых систем в Verilog / VHDL
• Контроллеры протоколов, где важен порядок команд (например, в SPI или UART)
• Распознавание последовательностей в системах управления

🔗 См. также

• Finite State Machine