Конечные автоматы Мура и Мили: полное проектирование

7 мин чтения · Команда bitGateLab

Конечный автомат (FSM) — это последовательностная схема, которая «помнит», на каком шаге процесса она находится. Светофоры, кодовые замки, контроллеры лифтов и приёмники последовательной связи — всё это конечные автоматы. Здесь вы познакомитесь с двумя классическими моделями, Мура и Мили, и пройдёте всё проектирование целиком, от словесного описания до уравнений триггеров, на примере детектора последовательности 101.

Из чего состоит конечный автомат

В любом синхронном автомате есть три блока:

Регистр состояния: n триггеров (почти всегда D-типа), которые хранят текущее состояние; их хватает максимум на 2ⁿ состояний.
Логика следующего состояния: комбинационная; вычисляет следующее состояние по текущему состоянию и входам.
Логика выходов: комбинационная; вычисляет выходы.

Разница между двумя моделями — в последнем блоке:

Автомат Мура: выходы зависят только от текущего состояния. Их записывают внутри кружка каждого состояния (например, S3/1).
Автомат Мили: выходы зависят и от состояния, и от входов. Их записывают над стрелками (вход/выход, например 1/1).

Автомату Мили обычно требуется меньше состояний, и он реагирует в том же такте, в котором приходит входной сигнал, но его выход может измениться в любой момент, если изменится вход. Автомат Мура реагирует на такт позже, а его выход меняется только сразу после фронта тактового сигнала, поэтому он «чище».

Задача: детектор последовательности 101

Последовательный вход X поступает синхронно с тактовым сигналом, по одному биту за такт. Выход Z должен быть равен 1 каждый раз, когда три последних принятых бита — это 1, 0, 1. Допускается перекрытие: в цепочке 10101 два обнаружения, потому что последняя 1 первой последовательности служит первой для следующей.

Первый шаг — решить, что должен помнить автомат. Каждое состояние означает «какая часть последовательности уже набрана»:

S0: ничего полезного не набрано.
S1: последний бит был 1.
S2: последние биты были 1, 0.
S3: только что приняты 1, 0, 1 (Z = 1).

Диаграмма и таблица состояний (автомат Мура)

Для каждого состояния и каждого значения X спросите себя: какой самый длинный суффикс с учётом нового бита совпадает с началом 101? Этот суффикс и определяет следующее состояние.

Детектор 101 с перекрытием на автомате Мура. Числа над стрелками — значение X; выход записан внутри каждого состояния.

Текущее состояние	X = 0	X = 1	Z
S0	S0	S1	0
S1	S2	S1	0
S2	S0	S3	0
S3	S2	S1	1

Обратите внимание на два перехода, в которых часто ошибаются. В S1 приходит ещё одна 1: цепочка оканчивается на 11, и последняя 1 по-прежнему годится как начало, поэтому автомат остаётся в S1. В S3 приходит 0: цепочка оканчивается на 1010, её суффикс 10 совпадает с началом 101, поэтому автомат переходит в S2, а не в S0. Именно это и обеспечивает перекрытие.

Кодирование состояний и уравнения

Для 4 состояний достаточно 2 D-триггеров (Q1 Q0). Самое прямолинейное кодирование — двоичное: S0 = 00, S1 = 01, S2 = 10, S3 = 11. Для D-триггеров таблица возбуждения тривиальна, потому что D = Q⁺.

Q1	Q0	X	Q1⁺ = D1	Q0⁺ = D0
0	0	0	0	0
0	0	1	0	1
0	1	0	1	0
0	1	1	0	1
1	0	0	0	0
1	0	1	1	1
1	1	0	1	0
1	1	1	0	1

Упрощение:

D0 равно 1 в точности в строках с X = 1, поэтому D0 = X. Это логично: при таком кодировании Q0 = 1 означает «последний бит был 1».
D1 = Σm(2, 5, 6) при порядке переменных Q1 Q0 X. Минтермы 2 (010) и 6 (110) соседние и образуют Q0·X. У минтерма 5 (101) нет соседей со значением 1, и он остаётся один: Q1·Q0·X. D1 = Q0·X + Q1·Q0·X.
Выход автомата Мура зависит только от состояния: Z = Q1·Q0.

В схеме получается 2 D-триггера, элемент AND с 2 входами для Z, а для D1 — AND с 2 входами, AND с 3 входами и OR с 2 входами (плюс инверторы для Q0 и X).

Проверка на тестовой последовательности

Вход X = 1 0 1 0 1 1 0 1, начинаем с S0. Состояние после каждого фронта:

Фронт	1	2	3	4	5	6	7	8
X	1	0	1	0	1	1	0	1
Состояние	S1	S2	S3	S2	S3	S1	S2	S3
Z	0	0	1	0	1	0	0	1

Обнаружений три: в битах с 1 по 3, с 3 по 5 (перекрытие) и с 6 по 8. Проверьте фронт 4 по уравнениям: состояние S3 = 11 и X = 0, D1 = 1·1 + 1·0·0 = 1 и D0 = 0, следующее состояние 10 = S2. Совпадает.

Вариант на автомате Мили

В автомате Мили выход относится к переходу, поэтому состояние S3 становится лишним: обнаружение происходит «по приходе 1 в состоянии S2». С тремя состояниями A (ничего), B (последний бит 1) и C (последние биты 1, 0):

Состояние	X = 0	X = 1
A	A / 0	B / 0
B	C / 0	B / 0
C	A / 0	B / 1

По-прежнему нужны 2 триггера, но выход Z = 1 появляется в том же такте, в котором приходит последняя 1, — на такт раньше, чем в варианте Мура.

Типичные ошибки

Направлять в S0 все «неудачные» переходы, не проверяя, какая часть последовательности ещё пригодится; так теряются обнаружения с перекрытием.
Писать выходы над стрелками в автомате Мура или внутри состояний в автомате Мили.
Забывать о неиспользуемых комбинациях триггеров (например, о коде 11 в варианте Мили): нужно решить, куда они ведут, или пометить их как X и убедиться, что автомат возвращается в последовательность.
Считывать выход автомата Мили в произвольный момент: его нужно брать непосредственно перед фронтом, когда вход уже установился.
Менять вход X точно в момент фронта тактового сигнала при проверке автомата.

Попробуйте в симуляторе

Когда уравнения готовы, сборка детектора занимает несколько минут, а временная диаграмма позволяет проверить каждый переход.

Поместите два D-триггера с общим тактовым сигналом; назовите их выходы Q1 и Q0.
Подключите вход X напрямую к D0.
Соберите D1 = Q0·X + Q1·Q0·X из двух инверторов, двух AND и одного OR и подключите к D1.
Подключите AND от Q1 и Q0 к светодиоду для Z.
Меняйте X перед каждым фронтом по последовательности 1 0 1 0 1 1 0 1 и убедитесь по временной диаграмме, что Z загорается после фронтов 3, 5 и 8.

Упражнения

Сколько раз автомат с перекрытием обнаружит 101 в цепочке 1010101?
Ответ
Три раза: в битах с 1 по 3, с 3 по 5 и с 5 по 7.
Переделайте таблицу автомата Мура для детектора 101 без перекрытия (после обнаружения всё начинается с нуля).
Ответ
Меняется только строка S3: при X = 0 переход в S0, а при X = 1 — в S1. Остальные строки остаются прежними.
При кодировании варианта Мили A = 00, B = 01, C = 10 найдите Z.
Ответ
Z = 1 только в состоянии C при X = 1: Z = Q1·Q0·X. Если код 11 никогда не появляется, его можно пометить как X, и получится Z = Q1·X.
Сколько триггеров, как минимум, нужно автомату с 9 состояниями?
Ответ
4, потому что 2³ = 8 не хватает, а 2⁴ = 16 достаточно.

Чтобы повторить триггеры, из которых состоит регистр состояния, обратитесь к теме «защёлки и триггеры».