23.Задачи анализа и синтеза схем из функциональных элементов. Элементарные методы синтеза.
Элементарные методы синтеза
Рассмотрим несколько алгоритмов синтеза, использующих классический базис, состоящий из инвертора, дизъюнктора и конъюнктора.
1. Метод синтеза, основанный на совершенной ДНФ.
Рассмотрим разложение функции
const
в виде совершенной ДНФ:
.
Введем вспомогательный элемент (рис.
1), с помощью которого построим схему
(рис. 2)
,
реализующую конъюнкцию
.
…
при
,
=
при
.
Рис. 1
Рис. 2
Очевидно,
,
и
содержит подсхему
,
одинаковую для всех конъюнкций и имеющую
сложность
.
Если «склеить» схемы
,
начиная от входов
вплоть до вспомогательных элементов,
то получим схему
,
для которой
.
Подключая выходы схемы
к схеме из дизъюнкторов, мы осуществим
синтез схемы для
(рис. 3) по совершенной ДНФ (алгоритм
).
… Сложность этого алгоритма
.
Поскольку
,
то
и
.
Рис. 3
Пример. Построить
схему, реализующую функцию
.
Представим данную функцию формулой в
базисе
,
используя, например, совершенную ДНФ:
.
(1)
Для каждой логической операции в этой формуле возьмем соответствующие функциональные элементы и произведем их соединение так, как этого требует формула. В результате получим схему, показанную на рис. 4. Эта схема использует 10 элементов. Предварительное упрощение формулы (1)
позволяет для той же функции построить более простую схему (рис. 5).
Рис.
5
Рис. 4
2. Метод
синтеза, основанный на более компактной
реализации множества всех конъюнкций
.
На рис. 6 представлено индуктивное
построение многополюсника
(
),
реализующего множество всех конъюнкций
.
Имеем
,
,
.
…
…
…
Базис индукции Индуктивный переход
Рис. 6
Для построения схемы, реализующей
функцию
,
нужно в многополюснике
отобрать выходы, соответствующие членам
ее совершенной ДНФ
,
подключить их к схеме (см. рис. 3),
осуществляющей логическое сложение, и
удалить лишние элементы. Это потребует
не более
элементов .
Таким образом, этот метод (алгоритм
)
дает
.
3. Метод синтеза, основанный на разложении функции по переменной .
для краткости положим
,
.
На рис. 7 представлена индуктивная процедура построения схемы для .
0 1
Базис индукции
Индуктивный переход
Рис. 7
На основании этого метода имеем алгоритм
:
,
.
Окончательно имеем
.
Итак, мы видим, что построены алгоритмы
и
в некотором смысле дают возможность
получить все более компактные реализации
для функций и, в конечном счете, все
более хорошие оценки для функций Шеннона.
С другой стороны, получение более хороших
результатов синтеза достигается за
счет некоторого усложнения алгоритма.