Другие предметы \ Теория дискретных устройств

Синтез абстрактного автомата. Абстрактный автомат, заданный таблицей переходов ТП. Графическое представление автомата

Страницы работы

Уважаемые коллеги! Предлагаем вам разработку программного обеспечения под ключ.

Опытные программисты сделают для вас мобильное приложение, нейронную сеть, систему искусственного интеллекта, SaaS-сервис, производственную систему, внедрят или разработают ERP/CRM, запустят стартап.

Сферы - промышленность, ритейл, производственные компании, стартапы, финансы и другие направления.

Языки программирования: Java, PHP, Ruby, C++, .NET, Python, Go, Kotlin, Swift, React Native, Flutter и многие другие.

Всегда на связи. Соблюдаем сроки. Предложим адекватную конкурентную цену.

Заходите к нам на сайт и пишите, с удовольствием вам во всем поможем.

Содержание работы

Синтез абстрактного автомата.

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

Синтезируем абстрактный автомат, заданный таблицей переходов ТП (табл. 1) и таблицей выходов ТВ (табл. 2) графическим методом.

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

S a	a₁	a₂
S₀	S₃	S₀
S₁	S₁	S₂
S₂	S₄	S₃
S₃	S₃	S₂
S₄	S₀	S₄

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

S а	a₁	a₂
S₀	0	0
S₁	1	1
S₂	1	0
S₃	0	0
S₄	1	1

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

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

Запишем таблицу, в которой будут закодированы заданные состояния схемы (таблица 3) и таблицу состояний D–триггера (таблица 4):

Таблица 3. Таблица 4.

ЭП Сост.	A	B	C	Переход	Входной сигнал
S₀	0	0	0	Переход	L	D
S₁	0	0	1	0→0	1	0
S₂	0	1	0	0→1	1	1
S₃	0	1	1	1→0	1	0
S₄	1	0	0	1→1	1	1

За входное воздействие а=0 примем а₁, а за а=1 — а₂; выходную функцию обозначим Y.

Таким образом получим следующие ТП и ТВ:

S a	a₁	a₂	S а	a₁	a₂
000	011	000	000	0	0
001	001	010	001	1	1
010	100	011	010	1	0
011	011	001	011	0	0
100	000	100	100	1	1

Составим кодируемый граф, на котором дополнительно проставим функции перехода триггеров:

Нарисуешь сам.

Запишем по графу формулы, позволяющие построить схему автомата:

Y= a ·A·B·C V a ·A·B·C V a ·A·B·C V a ·A·B·C V a ·A·B·C;

D_A= a ·A·B·C; D_B= a ·A·B·C V a ·A·B·C; D_C= a ·A·B·C;

L=1.

Для нахождения неопределенных состояний необходимо так же найти и инверсии этих функций:

D_A= a ·A·B·C; D_B= a ·A·B·C V a ·A·B·C; D_C= a·A·B·C V a ·A·B·C;

Y= a ·A·B·C V a·A·B·C V a·A·B·C V a ·A·B·C V a·A·B·C.

Упростим полученные формулы переходов состояний с помощью минимизации картами Карно, учитывая неопределенные состояния, появившиеся в результате неприменения при синтезе автомата трех состояний триггеров, а именно: S₅=101, S₆=110, S₇=111, и учитывая, что а₁= а₂ :

Таблички и полученные функции смотри на черновике.

Логическая схема автомата приведена на рисунке 2.2. Функции выходов и входных воздействий на триггеры реализованы в соответствии с вышеприведенными выражениями.

Схема электрическая принципиальная абстрактного автомата.

В схеме использованы микросхемы структуры ТТЛ — логические элементы и D-триггеры на микросхемах серии К555 [1]. Микросхемы данной серии являются маломощными (потребляемая микросхемой мощность не превышает 2 мВт) с диодами Шотки. Время задержки изменения логического уровня на выходе микросхемы при переходе 0®1 и 1®0 не превышает 10 нс, что позволяет автомату работать при больших частотах сигнала входного воздействия.

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