3.1.2.1. Задача анализа

Задача анализа формулируется следующим образом: по заданной комбинационной схеме (комбинационной логической сети) построить систему булевых функций. Проиллюстрируем ее решение на примере. Пусть комбинационная сеть представлена на рис. 3.3.

Рис. 3.3

Ее элементы сопоставлены элементарным булевым функциям. Двигаясь от входов к выходам, получим булеву функцию f =   (  ) .

Задачи анализа комбинационной логической сети разнообразны и связаны, например, с построением тестовых наборов, обнаруживающих искажения (неисправности) сети, с многозначным моделированием сети и др. Однако в рамках данного курса мы их не рассматриваем.

3.1.2.2. Синтез в базисе днф

Задача синтеза комбинационной схемы (комбинационной логической сети) заключается в ее построении из логических элементов по системе булевых функций. Обычно предоставляется подмножество логических элементов, называемое элементным базисом. Функции, сопоставляемые элементам базиса, образуют функционально полную систему.

Система M функционально полна, если ее замыкание совпадает с множеством всех булевых функций, [M] = .

Остановимся на простейших методах решения задачи синтеза, применяя известные в рамках данного курса результаты минимизации ДНФ.

Дизъюнктивной нормальной формой называется дизъюнкция D = = … элементарных конъюнкций , в которой все различны, j = =1,…, n. Число l называется длиной ДНФ. Для l = 0 ДНФ называется пустой и полагается равной 0.

Пусть задана система ДНФ, представляющая m функций от n переменных. Предположим также, что в нашем распоряжении имеются элементы И, ИЛИ с любым числом входов. Наряду со значением входного сигнала доступно его инверсное значение. Если первое предположение никогда не реализуется на практике, то второе предположение выполняется, если входные сигналы на схему поступают с выходов регистра.

Предположим, система состоит из единственной функции. Тогда синтез комбинационной схемы может быть выполнен непосредственно по ДНФ следующим образом.

Каждая конъюнкция ДНФ реализуется отдельным элементом И, выходы элементов И являются входами единственного элемента ИЛИ. Пусть система ДНФ имеет вид:

тогда ей сопоставляется схема рис. 3.4.

Рис. 3.4

Кратчайшей ДНФ соответствует схема с минимальным числом элементов И, минимальной ДНФ – схема с минимальным числом линий связей между элементами.

Кратчайшей ДНФ функции f( ,…, ) называется ДНФ, реализующая f и содержащая наименьшее число элементарных конъюнкций по сравнению со всеми другими ДНФ, реализующими эту функцию.

Минимальной ДНФ функции f( ,…, ) называется ДНФ, реализующая f и содержащая наименьшее число символов переменных по сравнению со всеми другими ДНФ, реализующими эту функцию.

Предположение о доступности инверсных сигналов можно снять, добавив в схему элементы НЕ. Схема рис. 3.4 преобразуется к виду

Рис. 3.5

Можно также снять предположение о наличии элементов И, ИЛИ с произвольным числом входов.

Поясним сказанное примером. Пусть требуется реализовать логическое произведение , а в нашем распоряжении имеются только двухвходовые элементы И. Расставим скобки так, чтобы в каждой из них число операндов равнялось двум: . Реализуем это выражение древовидной подсхемой, представленной на рис. 3.6.

Рис. 3.6

Аналогичным образом можно реализовать древовидной подсхемой элемент ИЛИ с произвольным числом входов.

Заметим, что использование кратчайших и минимальных ДНФ из простых импликант приводит к упрощению древовидных подсхем и сокращению их числа.

В случае задания на синтез системы из m функций, m > 1, можно синтезировать по отдельности каждую ДНФ, приведя ее предварительно к минимальной или кратчайшей ДНФ. Этот подход не всегда эффективен. Часто бывает выгодно прибегать к совместной минимизации системы, а затем по ней строить комбинационную схему. Однако методы совместной минимизации выходят за рамки нашего рассмотрения.

КАДР