При использовании многовходовых логических элементов схема может быть получена на основе ДНФ или КНФ функции. В этом случае ( без учёта инверсий входных переменных) она получается двухуровневой. Например, функция реализуется схемой на рис. 2.3.

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

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

Дальнейшего упрощения схемы можно добиться путём получения скобочных форм. Для приведённого выше примера имеем следующую форму: которая реализуется схемой на рис. 2.4.

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

Таким образом, задача минимизации сводится к получению минимальных нормальных форм (МДНФ или МКНФ).

2.6. Минимизация нормальных форм булевых функций.

Существуют следующие методы минимизации:

1. Ручные методы минимизации.

2. Машинные методы минимизации.

Ручные методы минимизации используют, если число переменных не больше 7.

В основе машинных методов минимизации лежит алгоритм Квайна-Мак Класки, алгоритмы Роота, а также методы математического программирования. В дальнейшем будем рассматривать ручные методы минимизации.

Ручные методы минимизации делятся на:

1. Аналитические;

2. Топологические.

Аналитические методы минимизации основаны на законах булевской алгебры.

Особую роль играют законы склеивания, поглощения, введения и исключения лишних связок.

минимальная форма

С использованием правила введения и исключения лишних связок нет необходимости в переходе к совершенным формам:

.

2.7 Минимизация с помощью диаграмм Карно.

Диаграмма Карно эквивалентна таблице истинности. Это прямоугольная таблица, содержащая клеток, где n- число переменных функции. Каждому набору переменных функций соответствует своя клетка. Различают два вида таблиц:

- дизъюнктивную диаграмму Карно (ДДК). В ней записывают единичные значения функции;

- конъюнктивную диаграмму Карно (КДК), В ней записывают нулевые значения функции.

В
пределах одной и той же таблицы нельзя использовать 1 и 0 одновременно.

Код называется циклическим, если его соседние наборы отличаются только в одном разряде. Это касается первого и последнего набора. Из рисунка 2.8. видно, что кодировка переменных по каждой из сторон карт Карно удовлетворяет правилу образования циклического кода.

Это правило можно использовать для построения диаграмм Карно с любым числом переменных.

Н
а рисунке 2.9. приведена диаграмма Карно для n=5, при построении которой использовалось выше приведённое правило.

2.8 Топологическая интерпретация правил минимизации.

Единицы, симметричные относительно оси диаграммы, делящие её на две половинки, в одной из которых переменная равна единице, а в другой равна нулю, называются смежными или соседними. Изображённые на диаграмме единицы являются соседними относительно оси, делящей диаграмму Карно на две половинки , и склеивание осуществляется по переменной .

С межные или соседние единицы могут быть объединены в одну группу, причём число единиц в группе равно , например для рис. 2.11. эта группа состоит из четырёх единиц и её соответствует конъюнкция db.

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

Правила минимизации:

1. Объединяем единицы (нули) в группы, число которых в группе равно , причём k=0…n, где n – число переменных, каждой группе соответствует конъюнкция n-k переменных. Исключаются k переменных, относительно осей которых выполняется правило симметрии.

2. В объединение включается как можно большее число единиц и нулей.

3. Одни и те же единицы (нули) могут входить в разные объединения.

4. Минимизация начинается с тех единиц (нулей) которые образуют единственно возможные максимальные объединения.

5. Объединения должны покрывать все единицы (нули) функции.

Пример 2.9.

n=4

;

Минимизация не полностью определённых функций.

Поскольку значение переменных из запрещённого набора не могут появляться на входе схем, то доопределение функции на этих наборах осуществляется произвольно, так чтобы реализация была минимальна.

;

На одних и тех же запрещённых наборах при образовании различных форм функция может доопределяться по разному.

Минимизация систем логических функций.

С
хема, имеющая много выходов, описывается системой уравнений. Минимизация системы выполняется совместно с учётом общих частей функций системы.

2.9. Построение комбинационных схем на реальной элементной базе.

При проектировании комбинационных схем необходимо учитывать основные характеристики логических элементов:

1) Коэффициент объединения по выходу (коэффициент разветвления).

2) Коэффициент объединения по входу.

3) Быстродействие.

1) Коэффициент объединения по выходу.

К
оэффициент разветвления задает максимальное количество входов логических элементов, которые могут быть соединены с выходом данного элемента (см. рис. 2.16):

Коэффициент разветвления определяет нагрузочную способность элемента. На практике возникает ситуация, когда количество элементов, соединенных с выходом данного элемента, превышает его нагрузочную способность. Для предотвращения этого необходимо её увеличить. Это делается следующим образом:

1. Используются элементы с повышенным значением коэффициента разветвления.

2
. Используют метод дублирования и размножения (см. рис.2.17.):

3
. Используются буферные элементы с высокой нагрузочной способностью. Эти элементы являются усилителями мощности. В логических элементах с потенциальным выходом усиление мощности реализуется путём усиления тока. В вычислительной технике усилитель тока принято называть драйвером. На схемах элемент изображается в соответствие с рис. 2.18., где буферный элемент- драйвер.

Совместное использование метода размножения и буферных элементов приводит к схеме на рис. 2.19., которая позволяет обеспечить высокую нагрузочную способность.

2) Коэффициент объединения по входу.

К
оэффициентом объединения по входу называют количество выходов элементов, соединённых с входами данного элемента. Таким образом, он совпадает с числом входов данного элемента, как показано на рис. 2.20.

Число входов элементов ограничено. Например, для микросхем ТТЛ- серий число входов:

- на элементе «И» не больше четырех;

- на элементе «ИЛИ» не больше двух;

- на элементе «И-НЕ» от двух до восьми;

- на элементе «ИЛИ-НЕ» от двух до пяти.

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

_ _ _

a b c + d b + d c = a ( b c ) + d ( b + c );

_ _ _ _

a b c + d b + e c = a ( b c ) + ( d b + e c ).

3) Быстродействие.

Реальные элементы обладают конечным быстродействием, которое определяется распространением сигнала через этот элемент. Быстродействие схемы определяется временем распространения сигнала по самой длинной цепочке элементов схемы и равняется сумме задержек. Из-за задержек в элементах при одновременном изменении переменных на входе комбинационной схемы, изменение сигналов на выходах отдельных элементов происходит не одновременно. Это может привести к появлению кратковременных ложных значений выходных сигналов в комбинационной схеме.

Пример 2.10.

_

F(a,b,c) = a b + a c; Временные диаграммы: