Синтез комбинацонных схем и конечных автоматов, сети Петри
01 1 1 1
x1x2
11 1
10 1 1 1
Рисунок 1.2.1 – карта Карно
На основании выбранной комбинации покрытий выписываем минимизированное выражение для функции F1:
.
(1.3.3)
Для второй функции применяем метод Квайна-МакКласки.
На первом шаге алгоритма выписываем комплекс K0-кубов заданной функции, упорядоченных по возрастанию количества единиц:
![]()
![]()
![]()
![]()
![]()
![]()
0 0 0 0 0 1 1 1 1
0 0 1 1 1 0 0 1 1
K0 = 0 1 0 0 1 0 1 0 1 (1.3.4)
0 0 0 1 0 1 0 0 0 .
Второй этап основан на операции склеивания. Каждый из кубов проверяется на “склеиваемость” со всеми остальными. Склеивающиеся кубы должны различаться не более чем в одном разряде. Склеенный разряд в дальнейшем обозначается как x. Куб, участвовавший в операции склеивания, соответствующим образом помечается. Поскольку таких кубов мало, будем отмечать не участвовавшие в операции склеивания кубы. В результате получаем комплекс K1-кубов, также упорядоченный по возрастанию количества единиц в разрядах:
![]()
![]()
![]()
![]()
0
0 0 x 0 0 x
x 1 1
0 x x 0 1 1 1 1 x 1
K1 = x 0 1 1 0 x 0 1 1 x (1.3.5)
0 0 0 0 x 0 0 0 0 0 .
Повторяем вышеописанную операцию для комплекса K1-кубов, после чего удаляем из полученного комплекса K2-кубов повторяющиеся:
![]()
![]()
![]()
![]()
![]()
0 0 x x x x
0 x x
x x x x 1 1 x x 1
K2 = x x 1 1 x x = x 1 x (1.3.6)
0 0 0 0 0 0 0 0 0
Те кубы, которые не участвовали в операциях склеивания, называются импликантами – это кандидаты на то, чтобы попасть в итоговую ДНФ. Для них составляем таблицу покрытий K0-кубов. Импликанта считается покрывающей K0-куб, если они совпадают при x, принимающем произвольное значение.
|
K0 z |
0 0 0 0 |
0 0 1 0 |
0 1 0 0 |
0 1 0 1 |
0 1 1 0 |
1 0 0 1 |
1 0 1 0 |
1 1 0 0 |
1 1 1 0 |
Импликанты |
|
1001 |
+ |
|
||||||||
|
010x |
+ | + |
|
|||||||
|
0xx0 |
+ | + | + | + |
|
|||||
|
xx10 |
+ | + | + | + |
|
|||||
|
x1x0 |
+ | + | + | + |
|
Таблица 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 ,
.
Требуется:
а) построить таблицы переходов, выходов и общую таблицу переходов автомата;
б) минимизировать автомат по числу состояний с использованием таблиц, полученных ранее;
в) построить граф минимизированного автомата и выписать для него матрицу переходов;
г) переходя ко двоичному представлению входа X, выхода Y и состояния S, составить таблицу входов и выходов комбинационной схемы автомата и выполнить минимизацию булевых функций, соответствующих выходам и состояниям автомата;
д) разработать логическую схему автомата в базисе И – НЕ, реализуя элементы памяти на триггерах и задержках.
2.2 Теоретические сведения
Конечным автоматом называется такое дискретное устройство, выходные сигналы которого в определённые моменты времени зависят не только от последнего пришедшего входного сигнала, но и от некоторого количества предыдущих его значений.
Различают синхронные и асинхронные автоматы. У асинхронных смена выходных сигналов y(tj) может происходить только в моменты изменения входных x(tj) , у синхронных – в моменты времени, определяемые дополнительным синхронизирующим сигналом c(t) .
Определим множества, которым могут принадлежать входные и выходные сигналы (условимся обозначать tj как j):
– множетва
входных и выходных
сигналов.
Тогда выражения
(2.2.1)
определяют входной и выходной алфавиты автомата.
Пусть
.
Тогда если
y(j) = λ(x(j)), то
этот автомат
является, очевидно,
комбинационной
схемой.
Введём дополнительную переменную для того, чтобы охарактеризовать состояние автомата в каждый момент времени j:
(2.2.2)
В том случае, если X, Y и S – конечные множества, то и сам автомат называют конечным.
В виде уравнений любой конечный автомат можно записать разными способами. Одна из





