Конечные автоматы (FSM): состояния и переходы

Знакомимся с конечным автоматом — универсальной моделью управляющей логики в железе.

Конечный автомат (FSM, Finite State Machine) — схема, которая в каждый момент находится в одном из конечного набора состояний и по тактам переходит между ними в зависимости от входов.

Счётчики и регистры хранят данные, но настоящая «логика поведения» схемы — это конечный автомат. FSM — главный паттерн цифрового дизайна: на нём строят контроллеры протоколов, светофоры, управление памятью, декодеры команд процессора. Если вам нужно описать схему, которая «делает шаги» и реагирует на события по-разному в зависимости от ситуации, — почти всегда это FSM.

Идея автомата

Автомат описывается тремя вещами: набором состояний, правилами переходов (из какого состояния в какое и при каком условии) и выходами (что схема выдаёт в каждом состоянии). Текущее состояние хранится в регистре, а переходы происходят по фронту такта. Рассмотрим автомат-турникет: состояния «закрыт» (LOCKED) и «открыт» (UNLOCKED), вход — «бросили монету» (coin) или «прошли» (push):

            coin                 push
   +-------------------+   +-------------------+
   |                   v   |                   v
[LOCKED] ----coin----> [UNLOCKED] ----push----> [LOCKED]
   ^  |                       ^  |
   |  +------push (нет монеты)-+  +--coin (уже открыт)--+
   |     остаёмся в LOCKED         остаёмся в UNLOCKED
   +-------------------------------------------------+

Читаем диаграмму: в LOCKED монета переводит в UNLOCKED, толчок — ничего не меняет. В UNLOCKED толчок возвращает в LOCKED, монета — ничего. Это классический пример: поведение зависит не только от входа, но и от текущего состояния.

Мили против Мура

Автоматы делят на два типа по тому, от чего зависит выход:

• Автомат Мура: выход зависит только от текущего состояния. Проще и стабильнее (выход не дёргается между тактами), но иногда требует больше состояний.
• Автомат Мили: выход зависит от состояния и текущего входа. Компактнее, реагирует на такт раньше, но выход может «глитчить» вслед за входом.

На практике в FPGA чаще предпочитают Мура — его синхронные выходы дружелюбнее к таймингу.

Как работает под капотом

Промоделируем автомат-турникет на Python, прогнав последовательность событий. Это показывает, как одно и то же событие даёт разный результат в зависимости от состояния:

LOCKED, UNLOCKED = "LOCKED", "UNLOCKED"

def step(state, event):
    if state == LOCKED:
        return UNLOCKED if event == "coin" else LOCKED
    else:  # UNLOCKED
        return LOCKED if event == "push" else UNLOCKED

state = LOCKED
events = ["push", "coin", "coin", "push", "push"]
print("состояние -> событие -> новое состояние")
for e in events:
    new = step(state, e)
    print(f"{state:9} -> {e:5} -> {new}")
    state = new

Вывод:

состояние -> событие -> новое состояние
LOCKED    -> push  -> LOCKED
LOCKED    -> coin  -> UNLOCKED
UNLOCKED  -> coin  -> UNLOCKED
UNLOCKED  -> push  -> LOCKED
LOCKED    -> push  -> LOCKED

Обратите внимание на строки с push: первый раз (в LOCKED) он ничего не меняет, а четвёртый (в UNLOCKED) — закрывает турникет. Один и тот же вход, разный результат — в этом суть автомата: память о состоянии определяет реакцию.

Частые ошибки

• Путать FSM с простым счётчиком. Автомат отличается тем, что переходы зависят от входов и могут быть нелинейными, а не просто +1.
• Забывать состояние по умолчанию. Если не описать все переходы, автомат может «зависнуть» или попасть в неопределённое состояние.
• Смешивать выход и переход в одну кашу. Чёткое разделение «логика переходов» и «логика выходов» делает автомат читаемым и правильным (об этом — следующий урок).

Итог

• FSM — главный паттерн управляющей логики: конечный набор состояний и переходы по входам.
• Текущее состояние хранится в регистре, переходы — по фронту такта.
• Мур: выход от состояния; Мили: выход от состояния и входа.
• Реакция на вход зависит от состояния — в этом сила автомата.