Пример минимизации числа состояний автомата Мура

Шаг 2 – Выполняется разбиение на 0-эквивалентные множества по значению выходов автомата

	0	1	y П0 = {A0 , A1} A0 = { a0 , a1, a2 , a3, a4 , a6} A1 = { a5} * т.к. в множестве А1 есть только одно состояние, то состояние a5 отмечается звездочкой в таблице и не участвует в дальнейшей минимизации, как состояние не имеющее эквивалентных
a0	a2	a1	0
a1	a3	a4	0 А0
a2	a4	a3	0
a3	a5	a6	0
a4	a6	a5	0 А1
a * 5	a2	a1	1 А0
a6	a2	a1	0

Шаг 3 – Таблица переходов автомата записывается без выделенных «звездочкой» состояний. В ячейках таблицы вместо названий состояний записываются названия классов эквивалентности, к которым они относятся.

	0	1 П1 = {B0 , B1, B2} B0 = { a0 , a1, a2, a6} B1 = { a3} * B2 = { a4} * т.к. в множестве B1 и В2 есть только одно состояние, то состояние a3 и a4 отмечаются звездочкой в таблице и не участвуют в дальнейшей минимизации, как состояния не имеющие эквивалентных
a0	A0	A B0 0
a1	A0	A0
a * 2	A0	A B1 0
a3	A1	A B2 0
a * 4	A0	A1
a * 5	a2	a B0 1
a6	A0	A0

Шаг 4 – Таблица переходов автомата записывается без выделенных «звездочкой» состояний. В ячейках таблицы вместо названий состояний записываются названия классов эквивалентности, к которым они относятся.

	0	1 П2 = {C0 , C1, C2} C0 = { a0, a6} C1 = { a1} * C2 = { a2} * т.к. в множестве C1 и C2 есть только одно состояние, то состояние a1 и a2 отмечаются звездочкой в таблице и не участвуют в дальнейшей минимизации, как состояния не имеющие эквивалентных C0
a0	B0	B C1 0
a1	B1	B C2 2
a * * * 2	B2	B1
a3	A1	A B1 0
a * 4	A0	A B2 A0 1
a * 5	a2	a C0 1
a6	B0	B0

Шаг 5 – Таблица переходов автомата записывается без выделенных «звездочкой» состояний. В ячейках таблицы вместо названий состояний записываются названия классов эквивалентности, к которым они относятся.

	0	1 П3 = {D0 } D0 = { a0, a6} т.к. в множестве D0 и C0 одинаковые состояния, а сами множества получены на двух последовательных шагах разбиения, то состояния a0 и a6, которые составляют данное множество являются полностью эквивалентными D0
a * 0	C1	C C1 2
a * 1	B1	B C2 2
a * 2	B2	B1
a3	A1	A B1 0
a * 4	A0	A B2 A0 1
a * 5	a2	a D0 1
a6	C1	C2

На данном шаге минимизация окончена, т.к. выделено множество полностью эквивалентных состояний, а все остальные состояния не имеют эквивалентных т.к. они попали в множества из одного элемента.

В исходной таблице переходов/выходов цифрового автомата вычеркивается строка, которая соответствует состоянию a₆, а в остальных строках a₆ заменяется на a₀

	0	1	y
a0	a2	a1	0
a1	a3	a4	0
a2	a4	a3	0
a3	a5	a6	0
a4	a6	a5	0
a5	a2	a1	1
a6	a2	a1	0

Таблица переходов/выходов автомата после минимизации будет иметь следующий вид:

Структурный синтез ЦА выполняется с привязкой к запоминающим элементам и внутренней структуре. Структурный синтез включает:

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

В простейшем случае под кодированием понимают назначение всем символам алфавитов двоичных кодов. Как правило, длину кода выбирают исходя из количества букв в алфавите. Например, если у автомата три возможных входных значения, то каждое значение кодируется двумя битами, если 5, то уже тремя.

1-2 буквы – 1 бит

2-4 буквы – 2 бита

3-8 букв – 3 бита

и т.д.

Введем некоторые определения.

Пусть Г(S) – неориентированный граф переходов автомата S. Вершины графа отождествляются с состояниями автомата. Вершины i и j соединены ребром, если есть переход из а_i и а_j или наоборот.

Обозначим q(i, j) число всевозможных переходов автомата из а_i в а_j. Каждому ребру (i, j) графа Г(S) поставим в соответствие вес ребра р(i, j) = q(i, j) + q(j, i).

Введем функцию w(i, j) = р(i, j) d(i, j), где d(i, j) – число компонентов, которыми коды состояний а_i в а_j отличаются друг от друга (т.е. кодовое расстояние между кодами а_i в а_j).

Функция w(i ,j) имеет простой физический смысл. Перход автомата из а_i в а_j (или наоборот) сопровождается переключением стольких триггеров, сколькими компонентами отличаются коды этих состояний, т.е. их число равно w(i ,j). Следовательно, при переходе автомата по всем ребрам, соединяющим состояниям а_i и а_j (их число p(i, j)!) всего переключится количество триггеров, равное p(i, j)d(i ,j) =w(i ,j).

Но тогда функция показывает, сколько всего переключается триггеров при прохождении автомата по всем возможным переходам. Функция w показывает, сколько всего единиц в функции возбуждения, т.е. позволяет оценивать сложность комбинационной схемы автомата. W можно рассматривать как некую целевую функцию, минимум которой определит такое кодирование, при котором комбинационная схема наиболее простая. Кстати, миинмальное кодовое расстояние между различными состояниями равно 1 и если удается закодировать все состояния соседним кодированием, то очевидно, что w будет минимально возможным и равным , т.е. суммарному числу переходов для автомата.

Из выражения для w следует, что переход из а_i в а_i, для которого d(i,i)=0, не влияет на w (что вполне очевидно, если учесть, что на этом переходе ни один триггер не переключается).

		i	j	p(i,j)
		1	2	2
		1	3	1
T	=	1	5	1
		2	3	3
		2	4	1
		2	5	1
		3	4	2
		3	5	2

Для определения того, какая пара займет второе место в матрице находим веса компонентов пар:

В данном случае для всех пар совпадают и их веса и веса их компонентов. Поэтому на второе место матрицы может быть поставлена любая из пар (1,2), (3,4), (3,5). Но тогда на 3-м и 4-м будут остальные две. Выполнив упорядочивание всех пар, получим матрицу в виде:

		i	j	p(i,j)
		2	3	3
		1	2	2
M	=	3	4	2
		3	5	2
		1	3	1
		1	5	1
		2	4	1
		2	5	1