Реферат: Синтез комбинацонных схем и конечных автоматов, сети Петри
0
Импликанты
Таблица 1.3.1 – Покрытия K0-кубов
Существенной импликантой, или экстремалью, называется такая импликанта, которая в единственном числе покрывает хотя бы один из K0-кубов.
Из таблицы следует, что все импликанты являются экстремалями. Следовательно, они все войдут в запись функции в виде сокращённой ДНФ:
. (1.3.7)
Комбинационная схема – это дискретное устройство, каждый из выходных сигналов которого в момент времени tm определяется так:
yj(tm) = ƒ ( x1(tm), x2(tm),…,xn(tm)) , (1.3.8)
где 
. Видно, что выходной сигнал в m-й момент времени определяется только комбинацией входных сигналов в данный момент и не зависит от их предыдущих значений. Поэтому комбинационную схему можно реализовать на логических элементах, выполняющих операции из определённого базиса булевых функций.
Приведём F1 к базису И – НЕ, а F2 – к базису ИЛИ – НЕ:
(1.3.9)
. (1.3.10)
Получив выражения для функций, приведённых к соответствующим базисам, можно нарисовать комбинационные схемы, реализующие эти функции, на элементах одного вида: для первой функции это будут И – НЕ-элементы, для второй – ИЛИ – НЕ :
Рисунок 1.3.1 – Схема на И – НЕ-элементах
Рисунок 1.3.2 – Схема на ИЛИ – НЕ-элементах
1.4 Выводы по разделу
В первой части были рассмотрены примеры минимизации (упрощения) булевых функций двумя разными способами. Была практически показана возможность приведения функций двух аргументов к базису, состоящему всего из одной функции. Были построены комбинационные схемы, иллюстрирующие полученные результаты. Выгода рассмотренных преобразований функций становится очевидной при их практической реализации на стандартизованных электронных микросхемах.
2 Синтез конечных автоматов
2.1 Постановка задачи
Конечный автомат задан своими уравнениями переходов и выходов:
s(j+1) = [2∙s(j) + x(j) + B] mod 8 ,
y(j) = [ s(j) + x(j) + A] mod 2 ,
.
Требуется:
а) построить таблицы переходов, выходов и общую таблицу переходов автомата;
б) минимизировать автомат по числу состояний с использованием таблиц, полученных ранее;
в) построить граф минимизированного автомата и выписать для него матрицу переходов;