Полная версия

Главная arrow Информатика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Сущность и критерии минимизации булевых функций

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

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

Таким образом, целью минимизации является получение наилучших технико-экономических показателей логических схем, отвечающих своему предназначению.

В качестве основных критериев минимизации БФ чаще всего используются:

- суммарное количество ЛЭ, требуемых для реализации логической схемы:

Для вышеприведенного словесного задания БФ

Если логическая схема реализована на комбинированных ЛЭ (И-НЕ,

ИЛИ-HE), то 1Млэ = Иклэ - суммарное количество диодов и транзисторов в логической схеме (цена реализации по Квайну).

Данный критерий используется реже. Оценка выполняется по структурной формуле в ДНФ (СДНФ).

При этом предполагается, что логические операции И, ИЛИ выполняются диодными ЛЭ, а операция НЕ - транзисторным ключом (инвертором). Тогда Нд можно подсчитать по количеству входов элементов И, ИЛИ, a NT - по числу инверторов. Так как каждый вход ЛЭ И, ИЛИ требует 1 диод, то общее количество диодов равно суммарному числу букв (переменных) всех слагаемых БФ, кроме слагаемых, представленных одной буквой (реализация логической операции И), плюс число слагаемых этой функции (реализация логической операции ИЛИ). Количество транзисторов равно суммарному числу операций НЕ над простыми переменными и промежуточными результатами преобразований.

Таким образом, для реализации рассматриваемой выше БФ потребуется:

  • - диодов - 3*4+4 = 16 (4 конъюнктора с 3 входами каждый + 1 дизъ- юнктор с 4 входами),
  • - транзисторов - 3 (3 инвертора).

Примечание: Подсчет диодов и транзисторов, необходимых для реализации более сложных БФ, выполняется с учетом приоритетности выполнения логических операций:

Задача минимизации может решаться различными способами. Результатом решения является минимальная по критериям БФ.

Форма БФ, эквивалентная заданной, для которой невозможны дальнейшие упрощения, называется тупиковой. Таких форм может быть множество, однако, среди них найдется только одна БФ, имеющая минимальную форму по выше приведенным критериям.

Тупиковая форма БФ, эквивалентная заданной, но требующая минимальных затрат, называется минимальной.

Для минимизации БФ используются:

  • - метод алгебраических преобразований;
  • - метод карт Карно.

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>