Задача 4. Элементы математической логики и теории автоматов ⇐ ПредыдущаяСтр 3 из 3
Конечный автомат задан графом, определенным в задаче 1 контрольной работы № 1. Вершины графа отождествляются с состояниями автомата таким образом, что множество состояний Q = {q1, q2 ,…, qn}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X={x1, x2, x3, x4}. Переходы определяются законом отображения Г вершин графа, причем каждому переходу соответствует только одна из букв множества X. При задании графа эти буквы расставить произвольно.
Автомат позволяет вырабатывать выходные сигналы Y={y1, y2, y3}: y1 – переход из состояния qi в состояние qi (петля); y2 – переход из состояния qi в qj при i<j; y3 – переход из состояния qi в qj при i>j.
Осуществить структурный синтез конечного автомата. Реализацию осуществить на элементах, указанных в табл. 1, в соответствии с номером варианта. Обязательной является минимизация реализуемых функций. Таблица 1
Решение: Множество вершин X = {x1, x2, x3, x4, x5}. Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний Q = {q1, q2, q3, q4, q5}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X={x1, x2, x3, x4}. Автомат позволяет вырабатывать выходные сигналы Y={y1, y2, y3}. Так как в графе нет петель, выходной сигнал y1 будет отсутствовать. На основании аналитического описания ориентированного графа из задания № 1 запишем закон отображения состояний автомата:
Гq1 = { q2(x1/y2), q4(x2/y2)}, Гq2 = {q1(x3/y3), q3(x4/y2)}, Гq3 = {q2(x1/y3), q4(x2/y2)}, Гq4 = {q1(x3/y3), q5(x4/y2), q3(x1/y3)}, Гq5 = {q4(x2/y3)}.
Обобщенная таблица переходов и выходов соответствующего конечного автомата представлена в табл. 2. Таблица 2
Осуществим структурный синтез автомата, заданного табл. 1. В качестве элементов памяти используем JK-триггеры, в качестве элементной базы используем логические элементы И-НЕ.
n = 4 p ≥ log2 n = log2 4 = 2; m = 2 e ≥ log2 m = log2 2 = 1; r = 5 z ≥ log2 r = log2 5 = 3.
Приступаем к кодированию:
На основании результатов кодирования строим обобщенную таблицу переходов и выходов структурного автомата (табл.3), заменяя состояния, входные и выходные переменные их кодами. Таблица 3
Используя таблицу переходов JK-триггера и данные предыдущей таблицы, составим обобщенную таблицу функционирования структурного автомата (табл.4). Функции возбуждения трех триггеров обозначены через J1K1, J2K2, J3K3, соответственно.
Таблица 4
По этой таблице запишем СДНФ выходных функций V и функций возбуждения триггеров J1K1, J2K2, J3K3, зависящих от набора переменных u1, u2, w1(t), w2(t), w3(t). В результате получим систему логических функций для построения комбинационной части автомата:
.
. .
. .
. .
Минимизируем функции согласно картам Карно:
Представим логические функции в базисе И-НЕ:
; . ; .
; . Функциональная схема структурного автомата: ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|