Синтез КС в классическом базисе

Пример 5. 28. ПФ, заданная СДНФ, представлена на карте Карно (рис. 5.20). Требуется реализовать КС в классическом базисе.

 

х1 1	1
1			х3
1

x4

 

 

Рис. 5.20. Минимизация функции четырех переменных

 

По карте Карно (рис. 5.20) найдем минимальную форму

y = f_min=x₁x₂Ú x₂x₃x₄Ú x₁x₃x₄Ú x_{2 .}

 

По структуре формулы строим схему, при этом инверсии значений аргументов получаем с помощью элементов «НЕ», конъюнкции в термах посредством элементов «И» и, наконец, объединяем термы с помощью четырех- входового элемента «ИЛИ» (рис. 5.21).

 

Рис. 5.21

 

Данная схема имеет 3 уровня, каждый из которых вносит свой вклад в задержку: 1-й уровень – инверторы, 2-й – элементы «И», 3-й – элемент «ИЛИ».

Для оценки сложности схем часто используется критерий Квайна

, (5.28)

где l_i – число элементов i -го типа,

m_i – числ о входов элемента i -го типа,

k – число типов логических элементов.

Таким образом, данный критерий определяется как суммарное число входов логических элементов.

Для схемы из последнего примера С = 17.

 

В рассмотренном примере использовалась только минимизация ПФ и производилось собственно построение схемы. Часто бывает полезно выполнить дополнительные преобразования, позволяющие снизить сложность схем. Рассмотрим следующий пример.

х2

Пример 5.29. Построить КС для функции, заданной на карте Карно рис. 5.22.

х1 1			1
1

x3

 

Рис. 5.22. Пример функции трех переменных

 

По карте Карно (рис. 5.22) определяем:

y = f_min = x₁x₂ Ú ,

в соответствии с данным выражением строим схему (рис. 5.23а). Сложность схемы по критерию Квайна соответствует С = 10.

а) б)

Рис. 5.23. Пример дополнительного преобразования

 

Полученное выражение можно преобразовать, выполнив вынесения за скобки, например:

.

Для данного выражения КС приводится на рис. 5.23б.

Сложность данной схемы по критерию Квайна соответствует С = 9, т.е. меньше.

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

 

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

Пример 5.30. .

Непосредственная реализация исходного выражения требует трех логических элементов (два элемента «И» и один элемент «ИЛИ»). Преобразованное выражение может быть реализовано одним элементом «ИЛИ-НЕ».

Замечание. В некоторых случаях более эффективной (в смысле критерия Квайна) оказывается минимизация по нулям, рассмотренная в п. 5.2.6 (см. пример 5.24).

 

5.3.4. Синтез КС в базисах «И-НЕ», «ИЛИ-НЕ»

 

Реализация КС в базисе И-НЕ без ограничения на число входов ЛЭ достаточно проста. Пусть булева функция задана в ДНФ.

 

,

где означает либо либо . Выполним преобразование:

.

Применяя правила Де Моргана, получим

.

Таким образом, булева функция, заданная в ДНФ может быть реализована в базисе «И-НЕ» трехранговой КС. Первый ранг – двухвходовые элементы, играющие роль инверторов; второй ранг – элементы, реализующие элементарные дизъюнкты; третий ранг – объединительный элемент.

Для выражения из примера 5.28 имеем

,

 

.

Комбинационная схема в базисе «И-НЕ» приведена на рис. 5.24.

Рис. 5.24. Схема в базисе «И-НЕ» без ограничений на количество входов

 

Для синтеза КС в базисе «ИЛИ-НЕ» удобно использовать выражение для , полученное при минимизации по нулям.

Пример 5.31. Для задания из примера 5.24 имеем

,

,

.

Схема приводится на рис. 5.25.

Рис. 5.25. Схема в базисе «ИЛИ-НЕ»

 

Если наложено требование, ограничивающее число входов ЛЭ до двух, для реализации сложных термов можно использовать преобразования:

 

,

.

При реализации сложных термов одинаковые пары переменных реализуются на одном элементе, например

.

В данном примере части выражения в скобках будут реализованы один раз (на трех элементах «И-НЕ», два из них в роли инвертора), соответствие между выражением и КС обеспечивается посредством связей (с выхода последнего элемента, реализующего выражения в скобках (точка V схемы рис. 5.26б), будут исходить две связи в соответствии со структурой выражения). Схема данных фрагментов КС приводится на рис. 5.26, схема без ограничения на число входов приводится на рис. 5.26а (С=10), схема на двухвходовых элементах «И-НЕ» приводится на рис. 5.26б (С=12).

 

а) б)

Рис. 5.26. Схемы в базисе «И-НЕ»

 

Примеры, применяемые при реализации КС на базе двухвходовых элементов «ИЛИ-НЕ», аналогичны описанным.