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

 

Анализируя временные диаграммы (рис.2), следует пронумеровать состояние схемы, используя два правила:

1) вводится начальное устойчивое состояние, соответствующее интервалу времени t₁, когда: x₁x₂=00, z₁z₂=00 (в таблице 1 это состояние (а₁, 1));

2) для каждого последующего такта вводится новое устойчивое состояние (рис.3).

 

Рассмотрим первый цикл работы: из состояния (а₁, 1) со значением входов x₁x₂=00 и выходов z₁z₂=00 схема под воздействием входного сигнала 01 переходит в состояние (а₂, 2) со значением выходов z₁z₂=11. Затем под воздействием входного сигнала 00 схема переходит в состояние (а₃, 3) со значением выходов z₁z₂=01. В состояние 4 (а₁, 4) схема переходит под воздействием входного сигнала 01, под воздействием сигнала 11 схема переходит в состояние 5 (а₂, 5) со значением выходов z₁z₂=10. Завершается циклическая вход-выходная последовательность подачей входного сигнала 00 и переходом схемы в начальное состояние (а₁, 1).

Затем таблица переходов расширяется с учетом второй и третьей вход-выходных последовательностей. При этом их начальное состояния совпадают с начальным состоянием первой последовательности.

Построим граф переходов (рис. 4).

 

Рис.2. Временные диаграммы вход-выходных последовательностей.

Рис. 3. Нумерация состояний.

 

Таблица переходов

таблица 1

а	а1	а2	а3	а4
S	x1x2
	(1), 00	2, 11	6, 01	11, 00
	3, 01	(2), 11
	(3), 01	4, 01
		(4), 01		5, 10
	1, 00			(5), 10
			(6), 01	7, 11
		8, 00		(7), 11
	9, 11	(8), 00
	(9), 11			10, 11
	1, 00			(10), 11
			12, 10	(11), 00
			(12), 10	13, 11
		14, 10		(13), 11
	1, 00	(14), 10

 

Рис. 4. Граф переходов.

 

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

3. Минимизация числа строк таблица переходов.

Нахождение максимальных подмножеств совместимых строк (МПСС ТП).

Находятся множества - множества строк в которых в столбце j проставлено состояние i или знак безразличного состояния (~).

Для составления таблица покрытий (табл. 2) имеем:

Находятся множества для всех четверок

 

 

Из полученных множеств исключаются те, которые полностью входят в другое множество. Оставшиеся множества являются максимальными подмножествами совместимых строк, они обозначаются латинскими буквами:

 

 

Составление таблицы покрытий

Столбцы таблицы соответствуют множествам А, В, С, …., а строки- строкам первичной таблицы переходов. На пересечении строки и столбца ставиться знак «+», если данная строка таблицы входит в данное подмножество совместимых строк.

Таблица покрытий

таблица 2

S

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

Решение задачи покрытия.

Находятся минимальное множество столбцов W такое, что каждая строка (состояние) входит хотя бы в одно из них. Для этого составляется алгебраическое выражение Q типа конъюнкция дизъюнкций. Каждая дизъюнкция образуется как дизъюнкция тех столбцов, в которых стоит метка «+» в данной строке (табл. 2).

Нахождение минимального множества таблицы покрытий.

 

С использованием правил повторения и поглощения выражение Q приводится к виду дизъюнкция конъюнкций. Выбирается любая из минимальных конъюнкций W.

W=AEQRBDHL

Объединение строк первичной таблицы переходов:

Далее исключается повторение цифр:

 

 

Построение минимизированной таблицы переходов

 

Строится таблица с учетом объединения строк(табл. 3)

Минимизированная таблица переходов Таблица3

а	а1	а2	а3	а4
S	x1x2
{1}	(1), 00	2, 11	6, 01	11, 00
{2}	3, 01	(2), 11
{3, 11}	(3), 01	4, 01	12, 10	(11), 00
{4, 5}	1, 00	(4), 01		(5), 10
{6, 7, 8}	9, 11	(8), 00	(6), 01	(7), 11
{9}	(9), 11			10, 11
{10}	1, 00			(10), 11
{12, 13, 14}	1, 00	(14), 10	(12), 10	(13), 11

Перенумерация строк минимизированной ТП

Производится перенумерация строк. Она заключается в присвоении каждой строке таблицы порядкового номера. Затем цифры состояний внутри клеток таблицы заменяются цифрами присвоенными тем подмножествам, в которые эти состояния входят.Получаем минимизированную таблицу переходов (ТП) (табл.4)

 

Таблица переходов после перенумерации

таблица 4

а	а1	а2	а3	а4
S	x1x2
	(1), 00	2, 11	5, 01	3, 00
	3, 01	(2), 11
	(3), 01	4, 01	8, 10	(3), 00
	1, 00	(4), 01		(4), 10
	6, 11	(5), 00	(5), 01	(5), 11
	(6), 11			7, 11
	1, 00			(7), 11
	1, 00	(8), 10	(8), 10	(8), 11

Блок-схема синхронного автомата

 

Рис. 5. Блок-схема синхронного автомата

 

1) СС – схема синхронизации, обеспечивает синхронизацию поступления входных сигналов;

2) ЛП- логический преобразователь, реализует функции включения внутренних элементов памяти;

3) БП- блок памяти, производит задержку сигналов Y на время t;

4) ВП – выходной преобразователь, реализует выходные функции Z.

 

⇐ Предыдущая123Следующая ⇒

Поделиться: