2.1. Отмеченная граф-схема алгоритма цифрового автомата.

Построим отмеченную граф-схему алгоритма (ГСА) управляющего автомата Мура (Мили):

Для автомата Мура: Для автомата Мили:

S₀

S₀

S₁

S₁

S₂

S₂

S₃

S₃

S₅

S₄

S₄

S₆

S₅

S_k=S₀

S_k=S₀

2.2. Построение графа переходов цифрового автомата.

Согласно отмеченной граф-схеме алгоритма управляющего автомата Мура (Мили) строим граф функционирования автомата.

Для автомата Мура:

Для автомата Мили:

2.3. Вычисление количества элементов памяти для цифрового автомата.

Число разрядов кода состояния соответствует числу элементов памяти и определяется по формуле: k =┐log2 S┌

Для автомата Мура S=7, k=3

Для автомата Мили S=6, k=3

2.4. Кодирование состояний цифрового автомата Мура (Мили).

Для того чтобы избежать гонок в автомате необходимо применить соседнее кодирование для состояний автомата. Однако, для возможности его применения, граф автомата должен обладать некоторыми свойствами:

1. В графе не должно быть циклов с нечетным числом вершин.

2. Два соседних состояния второго порядка не должны иметь более двух состояний, лежащих между ними. Под состоянием второго порядка понимаются такие два состояния, путь между которыми по графу автомата состоит из двух ребер.

В графе автомата Мура есть цикл с нечетным числом вершин S₃→S₄→S₆→S₃. Таким образом, применить соседнее кодирование для автомата Мура невозможно.

Соседнее кодирование для автомата Мили.

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

	00	01	11	10
0	S0	S1	S2	S5
1	S6	S7	S3	S4

Легко видеть, что при соседнем кодировании на каждом переходе переключается только один триггер, что принципиально устраняет гонки.

Таблица кодировки для состояний автоматов Мура и Мили:

Состояние	Код состояния для Мура	Код состояния для Мили
S0	000	000
S1	001	001
S2	010	011
S3	011	111
S4	100	110
S5	101	010
S6	110	100
S7	111	101

Для автомата Мили кодируем неиспользованные состояния S₆ и S₇, а для Мура S_7.

Таким образом, для автомата Мили появились 2 новых состояния, а для Мура 1 и надо скорректировать их графы функционирования, с учетом новых состояний.

Для Мура:

Для Мили: