5.2. Синтез конечных автоматов мура

5.2.1. Абстрактный синтез автомата Мура

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

Пример 5. . Получена следующая таблица соответствия: U₀U₁U₂U₀U₁U₂U₃U₀–V₀V₁V₂V₀V₂V₁V₁V₀. Аналогично, как и при синтезе автомата Мили, каждому переходу таблицы соответствия присваивается внутреннее состояние и получается таблица 5.21.

Таблица 5.21.

Таблица соответствия

U0	–	а0	–	V0
U1	–	а1	–	V1
U2	–	а2	–	V2
U0	–	а3	–	V0
U1	–	а4	–	V2
U2	–	а5	–	V1
U3	–	а6	–	V1
U0	–	а7	–	V0

Для синтеза схемы автомата Мура строится отмеченная таблица переходов. Отмеченная таблица переходов отличается от совмещенной таблицы переходов и выходов автомата Мили тем, что выходами автомата отмечаются все столбцы таблицы переходов. В клетках этой таблицы ставятся только внутренние состояния автомата, число строк и столбцов будет таким же, как и в совмещенной таблице переходов и выходов автомата Мили.

Таблица 5.22.

Отмеченная таблица переходов

	V0	V1	V2	V0	V2	V1	V1	V0
	а0	а1	а2	а3	а4	а5	а6	а7
U0	а0		а3	а3			а7	а7
U1	а1	а1		а4	а4
U2		а2	а2		а5	а5
U3						а6	а6

Для минимизации отмеченной таблицы переходов (для объединения столбцов) существуют два условия:

• необходимое условие заключается в том, что внутренние состояния, которыми обозначены столбцы, могут объединяться между собой, если они отмечены одинаковыми выходами;

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

При минимизации отмеченной таблицы переходов все символы внутренних состояний развиваются на R группы, количество которых равно числу попарно различимых выходных символов. В каждую группу вносятся только те символы внутренних состоянийа_i, которые отмечены одинаковыми выходными символамиV_j. В отмеченной таблице переходов 5.22. Переобозначив внутренние состояния символомпо необходимому условию получаем

х₀–а₀а₃а₇, отмеченные выходомV₀

х₁–а₁а₅а₆, отмеченные выходомV₁

х₂–а₂а₄ , отмеченные выходомV₂

После переобозначения внутренних состояний строится таблица 5.23 для проверки выполнения достаточного условия.

Таблица 5.23.

Отмеченная таблица переходов

	V0	V1	V2	V0	V2	V1	V1	V0
	а0	а1	а2	а3	а4	а5	а6	а7
	0	1	2	0	2	1	1	0
U0	0		0	0			0	0
U1	1	1		2	2
U2		2	2		1	1
U3						1	1

В полученной таблице 5.23 проверяется выполнение достаточного условия. В строке U₁ранее намеченные к объединению столбцыа₀иа₃по достаточному условию не объединяются в клетке столбцаа₀и строкиU₁стоит внутреннее состояниех₁, а клетке строкиU₁и столбцаа₃внутреннее состояниех₂.

По аналогичным причинам не объединяются столбцы а₁а₅иа₂а₄, поэтому необходимо произвести новое переобозначение внутренних состояний

₀–а₀а₇

₁–а₁

₂–а₅а₆

₃–а₂

₄–а₄

₅–а₃

Для проверки выполнения достаточного условия строится таблица 5.24. Из таблицы 5.24 следует, что достаточные условия выполняются. Минимальная таблица переходов автомата Мура представлена таблицей 5.25.

Таблица 5.24.

Отмеченная таблица переходов

	V0	V1	V2	V0	V2	V1	V1	V0
	а0	а1	а2	а3	а4	а5	а6	а7
	0	1	3	5	4	2	2	0
U0	0		5	5			0	0
U1	1	1		4	4
U2		3	3		2	2
U3						2	2

Таблица 5.25.

Минимальная таблица автомата Мура

	V0	V1	V2	V0	V2	V1
	0	1	3	5	4	2
U0	0		5	5		0
U1	1	1		4	4
U2		3	3		2	2
U3						2

5.2.2. Структурный синтез автоматов Мура

Кодирование входов, выходов и внутренних состояний осуществляется так же, как и для автоматов Мили

Для кодирования внутренних состояний необходимо построить граф автомата (рис. 5.9).

Рис. 5.9. Граф автомата Мура

После кодирования входов, выходов и внутренних состояний строится структурная таблица переходов автомата Мура.

Таблица 5.26.

Структурная таблица переходов

	у1у2
	00	01	10	00	10	01
Q1Q2Q3 х1х2	000	001	011	111	110	100
00	000		111	111		000
01	001	001		110	110
10		011	011		100	100
11						100

Из структурной таблицы 5.26 следует, что синтезируемый автомат Мура имеет два входа х₁х₂, два выходау₁у₂и три элемента памятиQ₁Q₂Q₃.

Уравнения выходов получаются непосредственно из структурной таблицы переходов следующим образом. Из столбцов где у₁равен единице в уравнениеу₁в качестве слагаемых берутся коды внутренних состояний, которыми обозначены столбцы таблицы переходов. Аналогично записывается уравнение дляу₂

.

Как видно из уравнений выходы у₁у₂автомата Мура формируются только элементами памяти, а выходы автомата Мили формируются как элементами памяти, так и входамих₁х…

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

Если в качестве элементов памяти будет использоваться реле, то таблица переходов автомата Мура 5.26 одновременно будет и таблицей возбуждения.

Для получения минимальных уравнений возбуждения элементов памяти необходимо таблицу 5.26 преобразовать к виду таблицы минимизации на пять переменных. Для этого надо последние две строки поменять местами и добавить два столбца с недостающими кодами 010 и 101.

Таблица 5.27.

Преобразовательная таблица переходов

q1q2q3 х1х2	000	001	011	010	110	111	101	100
00	000		111			111		000
01	001	001			110	110
11								100
10		011	011		100			100

Получение уравнения возбуждения элемента памяти Q₁

Таблица 5.28.

Таблица минимизации

	000	001	011	010	110	111	101	100
00	0		1			1		0
01	0	0			1	1
11								1
10		0	0		1			1

.

Аналогично получаются уравнения возбуждения элементов памяти Q₂иQ₃.

Таблица 5.29.

	000	001	011	010	110	111	101	100
00	0		1			1		0
01	0	0			1	1
11								0
10		1	1		0			0

.

Таблица 5.30.

	000	001	011	010	110	111	101	100
00	0		1			1		0
01	1	1			0	0
11								0
10		1	1		0			0

.

Схема электрическая функциональная автомата Мура на релейно-контактных элементах показана на рисунке 5.1.

Рис. 5.10. Схема электрическая функциональная автомата Мура