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

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

х₁

х₃

x₄

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

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

y = f_min=x₁x₂Ú x₂x₃x₄Ú x₁x₃x₄Ú x₂_.

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

Рис. 5.21

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

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

, (5.28)

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

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

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

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

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

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

х₂

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

х₁

x₃

Рис. 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. Схемы в базисе «И-НЕ»

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

⇐ Назад

Далее ⇒