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

  2. Автомат

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

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

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

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

Таблица 2.1.1

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

Таблица 2.1.2

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

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

Таблица 2.1.3

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

Таблица 2.1.4

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

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

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

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

Рис.2.1.1

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

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

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

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

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

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

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

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

    Таблица 2.1.5

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

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

Таблица 2.1.6.

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

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

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.