Минимизация булевых функций

Белорусский государственный университет информатики и радиоэлектроники

Кафедра РЭС

Реферат

На тему:

«Минимизация булевых функций»

Минск, 2009

Рассмотрим функцию, представленную в ДСНФ, вида:

Рис. 1. Пример реализации функции в базисе элементов И, ИЛИ, НЕ.

(1)

Для реализации этой функции потребуются три элемента И, один элемент ИЛИ и два элемента НЕ (рис. 1).

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

Попытаемся это сделать для функции (1). Приняв во внимание равенство , добавим к этому выражению еще один конъюнктивный член :

Теперь преобразуем полученное выражение, используя приведенные выше формулы:

(2)

Рис. 2. Примеры реализации минимизированных функций:

а) до преобразования

б) после преобразования

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

Как видно из рис. 1 и 3, одна и та же функция реализуется далеко неоднозначно по аппаратурным затратам. Это говорит о том, что существует такая форма представления функции, которая выполняется с наименьшими аппаратурными затратами. Применительно к рассматриваемой функции такой формой является представление ее в виде скобочной формулы:

.

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

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

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

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

(3)

то с помощью тождественных соотношений она должна быть развернута в виде ДСНФ. В частности, применив к выражению (3) правило де Моргана, получим:

(4)

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

то есть мы получили запись функции в виде ДСНФ, то есть суммы минтермов.

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

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

· выполним всевозможные склеивания 1-ого члена с остальными;

· выполним всевозможные склеивания 2-ого члена с остальными. кроме первого;

· выполним всевозможные склеивания третьего члена с остальными, кроме первого и второго.

Напомним, что операция склеивания осуществляется по формуле:

Результат склеивания запишем в виде:

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

После операции склеивания проводится операция поглощения, которая выполняется с помощью формулы:

.

Для проведения операции поглощения необходимо заданную функцию представить в виде:

где первые три члена получены от проведения операции склеивания. В этом выражении произведение поглощает члены и произведение поглощает члены и , и произведение поглощает члены и .

Таким образом, в результате операции поглощения все минтермы функции оказались поглощены импликантами, что позволяет записать исходную функцию в виде:

(5)

К полученной формуле повторно применяют операции склеивания и последующего поглощения, и эта процедура выполняется до получения простых импликант.

В рассматриваемом примере ни одно из произведений -- импликант не склеивается между собой. Такие импликанты называют простыми, а функцию (5), состоящую из дизъюнкции простых импликант, -- сокращенной ДНФ (СДНФ).

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

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

Таблица 1.

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

Для матрицы табл. 1 такими импликантами будут произведения и , причем первое из них поглощает минтермы и , а второе -- остальные два минтерма и . В результате тупиковая форма рассматриваемой функции запишется в виде:

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

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

Особенностью этого метода является также то, что в его основу положена табличная запись членов минимизируемого выражения, представляемого в виде ДНФ.

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

Покажем один из способов записи минтермов по методу Вейча-Карно (рис. 2).

Рис. 2. Карта Карно для функций от четырех аргументов

В качестве примера здесь показана карта Карно для функций от четырех аргументов: X₁, X₂, X₃, X₄. Нетрудно увидеть, что любой из 16 минтермов находятся как бы в окружении со всех четырех сторон смежными минтермами, расположенными в соседних (смежных) ячейках.

Например, смежными ячейками (клетками) для минтерма m₈ будут клетки m₁₂, m₉, m₀ и m₁₀, так как каждый из минтермов, записанных в этих клетках, отличается от минтерма m₈ формой вхождения только одного аргумента (под формой вхождения понимают запись аргумента в прямом или инверсном виде).

Необходимо иметь в виду, что на рис. 2 скобками обозначены ячейки таблицы, в которые аргументы обязательно должны входить с прямой формой вхождения. Аргументы с инверсной формой вхождения при такой маркировке расположения аргументов, как правило, скобками не обозначаются.

Процесс минимизации по картам Вейча-Карно фактически состоит из двух этапов: нанесения функции на карту Карно и считывания упрощенных форм. Рассмотрим этап нанесения на карту Вейча-Карно функции:

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

Таким образом, для нанесения его на карту достаточно записать 1 в клетку, в которую входят все символы минтерма (рис. 3).

Чтобы нанести на карту выражение , обозначенное цифрой 2, которое не является минтермом, следует вписать единицы в клетки карты, относящиеся к символам . Как видно из рис. 3, таких единиц, удовлетворяющих выражению, можно поставить две. На рис. 3 эти единицы отмечены цифрой 2 в кружке.

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

Рис. 1.9 Карта Карно с минимизацией минтермов

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

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

Порядок нанесения функции на карты Карно практически не отличается от ранее рассмотренного. В качестве примера на рис. 4 показана запись на карту функции:

,

а на рис. 5 функции:

После нанесения выражения на карту начинается этап считывания упрощенных форм.

Рис. 4. Карта Карно для Рис. 5. Карта Карно для

функции четырех переменных функции пяти переменных

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

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

Рис. 6. Упрощенные формы карты Карно

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

Этап считывания упрощенных форм с карт Карно рассмотрим на рис. 6, где представлена функция от трех переменных со скобочной формой маркирования минтермов.

На рисунках иллюстрируется неоднозначность считываемых упрощенных форм. Считывание с рис. 6, а-в приводит к тупиковым формам, содержащим по четыре импликанты:

При считывании, как показано на рис. 6, г, д, поглощения минтермов осуществляются наиболее удачно, поскольку они приводят к минимальным формам, содержащим по три импликанты:

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

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

Литература

1. Новиков Ю.В. Основы цифровой схемотехники. Базовые элементы и схемы. Методы проектирования. М.: Мир, 2001. - 379 с.

2. Новиков Ю.В., Скоробогатов П.К. Основы микропроцессорной техники. Курс лекций. М.: ИНТУИТ.РУ, 2003. - 440 с.

3. Пухальский Г.И., Новосельцева Т.Я. Цифровые устройства: Учеб. пособие для ВТУЗов. СПб.: Политехника, 2006. - 885 с.

4. Преснухин Л.Н., Воробьев Н.В., Шишкевич А.А. Расчет элементов цифровых устройств. М.: Высш. шк., 2001. - 526 с.

5. Букреев И.Н., Горячев В.И., Мансуров Б.М. Микроэлектронные схемы цифровых устройств. М.: Радио и связь, 2000. - 416 с.

6. Соломатин Н.М. Логические элементы ЭВМ. М.: Высш. шк., 2000. - 160 с.