Автомат. Синтез автомата. Таблица переходов. Таблица кодировки входных воздействий. Таблица кодировки внутренних состояний

  2. Автомат

2.1. Синтез автомата

Требуется синтезировать  синхронный  автомат  заданный  таб-лицей  переходов и таблицей выходов . В качестве элементов  па-    мяти   используется  D-триггер.

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

Запишем таблицу переходов и таблицу выходов.

Таблица 2.1.1

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

a   S	a1	a2
S0	S4	S0
S1	S0	S1
S2	S2	S3
S3	S3	S4
S4	S1	S2

Таблица 2.1.2

Таблица выходов

a S	a1	a2
S0	1	0
S1	1	0
S2	0	1
S3	1	0
S4	1	1

Произведем  кодировку входных и выходных сигналов , а также  составим таблицу кодировки  входных   и   выходных   воздействий.

Таблица 2.1.3

Таблица кодировки входных воздействий

Состояние	x
a1	0
a2	1

Таблица 2.1.4

Таблица кодировки выходных воздействий

Состояние	z
w1	0
w2	1

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

    На рис.2.1.1 представлен граф, вершины  которого соответству-

ют внутренним состояниям  нашего автомата. Переход  из  одного состояния в другое показаны стрелками ,  соответствующими  ветвям графа. На них проставляем буквы  входного  алфавита  ,  обус- лавливающие переходы.

Рис.2.1.1

Граф абстрактного автомата

Произведем переход от абстрактного к структурному автомату.

Каждое состояние абстрактного автомата кодируется в структур- ном автомате набором состояний элементов  памяти .  Обычно  элементы памяти бывают двоичными , и их число определяется как

R ³ ] log₂(M+1) [ , где М - число состояний абстрактного автомата ;

] log₂(M+1) [ - ближайшее целое число , большее или равное   log₂(M+1)=а , если а - целое .

В нашем случае получаем , что :

] log₂(M+1) [ £ 3 .

Далее составим таблицу кодировки внутренних  состояний  авто- мата  и запишем в таблицу . Кодировка выполняется произвольно .

    Таблица 2.1.5

Таблица кодировки внутренних состояний

Состояние	A	B	C
S0	0	0	0
S1	0	0	1
S2	0	1	0
S3	0	1	1
S4	1	0	0

Входные сигналы D-триггера при переходе его из одного состояния в другое представлены в таблице 2.1.6.

Таблица 2.1.6.

Таблица переходов D-триггера

Исходное состояние	Состояние перехода	Входной  сигнал D - триггера
1	1	1
0	0	0
0	1	1
1	0	0

        Исходя из таблиц кодировки  входных  и  выходных  воздейст -вий, таблицы кодировки внутренних состояний, таблицы переходов

D – триггера, а также графа абстрактного автомата строим граф структурного автомата.

Граф структурного автомата представлен на рис.2.1.2

    Рисунок 2.1.2

Граф структурного автомата

         По построенному графу структурного автомата построим фун-

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

D₁= ABCXÚABCX ;      

D₂= ABCXÚABCXÚABCXÚABCX ;

D₃= ABCXÚABCXÚABCXÚABCX ;

Z= ABCXÚABCXÚABCXÚABCXÚABCXÚABCX ;

Z= ABCXÚABCXÚABCXÚABCX ;

D₁= ABCXÚABCXÚABCXÚABCXÚABCXÚABCXÚABCXÚABCX ;

D₂= ABCXÚABCXÚABCXÚABCXÚABCXÚABCX ;

D₃= ABCXÚABCXÚABCXÚABCXÚABCXÚABCX ;

Далее минимизируем эти функции с помощью карт Карно.

Для D₁ имеем карту Карно, представленную на рис.2.1.3.

 

Рисунок 2.1.3

Карта Карно для D₁  

         Получаем, что D₁ = BCXÚABCX;

Для D₂ имеем карту Карно, представленную на рис.2.1.4.

									C

 

Рисунок 2.1.4

Карта Карно для D₂  

         Получаем, что D₂ = BXÚAXÚBCA;

Для D₃ имеем карту Карно, представленную на рис.2.1.5.

 

Рисунок 2.1.5

Карта Карно для D₃  

         Получаем, что D₃ = BCXÚBCXÚABXÚACX=CXÚABXÚACX;

Для Z имеем карту Карно, представленную на рис.2.1.6.

 

Рисунок 2.1.6

Карта Карно для Z  

         Получаем, что Z = AÚBXÚBCXÚBCX.

По полученным выражениям строим схему синхронного автомата.

Для схемы синхронного автомата применим базис реализации

И-НЕ. Для меньшего использования числа микросхем, а также из-за

большей распространненности этого базиса.

Для этого переведем полученные функции в базис И-НЕ и получим, что:

 

         D₁ = BCX×ABCX;

 

         D₂ = BX ×AX ×ABC;

 

         D₃ = CX ×ABX ×ACX;

 

Z = A ×BX ×BCX ×BCX.