Введение

Задача о покрытии в булевой алгебре

Данный метод предназначен для решения важнейшей практической задачи в булевой алгебре – а именно задачи о покрытии. Неформальная формулировка может звучать так: имеется булева функция от нескольких входных переменных (возможно, не полностью определенная). Требуется найти минимальное покрытие этой функции в заданном базисе. (Причем, в качестве базиса может применяться номенклатура элементов какой-либо логической серии микросхем либо просто библиотека элементов для ПЛИС либо ASIC)

Данная задача имеет прикладное практическое значение в области цифровой электроники и логического синтеза. Иногда эту задачу сводят к нахождению минимальной ДНФ или КНФ, но в практическом плане наше определение более полезно. Причем, как правило, решается она в два этапа – сначала находится минимальная ДНФ либо КНФ, а затем ищется ее оптимальное покрытие в заданном базисе. Сейчас такие задачи решаются программами компьютерного логического синтеза. Наилучшее решение, в общем случае, находится методом полного перебора, который в случае достаточно большого числа переменных требует нереальных затрат ресурсов и времени. (Известно, что количество всех возможных булевых функций зависит от числа входных переменных n как . Таким образом, от одной переменной мы имеем всего 4 различных функции, от двух – 16, от трех – уже 256 и так далее.)

Простой практический пример

Зададим простую булеву функцию от 2хвходных переменных и напишем для нее ДНФ и КНФ. Функцию зададим следующей таблицей:

Чтобы написать для нее ДНФ, надо написать формулы для всех строчек, где Y равна единице и соединить их через функцию “или”:

Y = !X1&X0 | X1&!X0

Чтобы получить КНФ, надо закодировать все нули через операции “или” и соединить их через операцию “и”:

Y=X1|X0 & !X1|!X0

Легко понять, что формулы эти эквивалентны:

(!X1&X0) | (X1&!X0) ó (!X1&X0)|X1 & (!X1&X0)|!X0 ó(!X1|X1) & (X0|X1) & (!X1|!X0) & (X0|!X0) ó(X0|X1) & (!X1|!X0)

Чтобы реализовать эту логическую функцию в виде электронной схемы, надо закодировать (покрыть) одну из этих формул доступными нам логическими элементами. Это могут быть либо микросхемы, реализующие функции программируемой логики, либо библиотечные функции из какой-либо библиотеки элементов. Например, использовав микросхемы К1533ЛА3, содержащие элементы 2И-НЕ, можно покрыть эту функцию так:

Рис. 1. Реализация функции “исключающее или” на элементах 2И-НЕ

Здесь мы использовали тождество Y = !X1&X0 | X1&!X0 ó! [!(!X1&X0) & !(X1&!X0)]

При этом мы израсходовали 5 логических вентилей и 2 корпуса, т.к. в каждом корпусе содержатся 4 лог. вентиля. Можно убедиться (самостоятельно), что использование функции 2ИЛИ-НЕ приводит к аналогичному результату.

Если нам доступен более широкий набор логических элементов, как это бывает в библиотеках функций для ПЛИС или ASIC, то можно покрыть эту логическую функцию иначе, например так:

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

Если же, например, у нас имеется мультиплексор, то мы можем реализовать эту функцию непосредственно на нем:

Рис. 3. Вариант реализации на мультиплексоре

Конечно, ввиду того, что сам мультиплексор реализуется с посредством нетривиальных логических функций, такой прием неэффективен при проектировании для ASIC и ПЛИС, но он широко применялся при проектировании на схемах малой степени интеграции.

Даже на таком простом примере видно, что задача покрытия – весьма нетривиальна. Добавим, что с повышением числа входных переменных, сложность ее решения растет экспоненциально и уже для нескольких сотен переменных решение “в лоб”, т.е. полным перебором становится нереализуемым на любом современном компьютере.

И, в заключение, для тех, кто еще не догадался – мы рассматривали реализацию функции “исключающее или”.

Задача поиска минимальной ДНФ (КНФ)

ДНФ и КНФ

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

В частности, имеется математическая теорема, что любую логическую функцию от n переменных можно покрыть функциями вида . Здесь знаком “|” обозначена операция “логическое или”, а индекс i пробегает по всем выходным единицам. Выражение вида называется “логический терм”, а домик означает переменную либо ее инверсию. Такое представление называется “дизъюнктивная форма”, сокращенно ДНФ. ДНФ может быть “совершенной”, когда присутствуют все n входных переменных, либо сокращенной, когда количество переменных в терме меньше n.

Соответственно, выражение вида называется “конъюктивная форма”, сокращенно КНФ. Все вышесказанное сказанное про ДНФ относится и к КНФ, за исключением того, что операции “и” и “или” меняются местами, а термы выписываются для выходных значений, равных 0.

 

Постановка задачи

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

Учебная задача

Задача: Разработать схему преобразования цифр от 0 до 9, заданных в двоичном коде в сигналы управления семисегментного индикатора. Выход – 1 – сегмент включен, 0 – сегмент выключен. Так же условимся, что код больше, чем 9 в двоичном представлении появиться не может.

Рис. 4. Модуль управления семисегментным индикатором

Как решаются задачи такого типа?

Для начала выпишем таблицу функций для всех входных и выходных переменных:

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

 

Общий принцип минимизации

Общий принцип – исключение из терма незначащих переменных. Так, для кодирования одной точки нам требуются все n входных переменных. Для кодирования отрезка – n-1. Квадрат кодируется n-2 переменными, а куб – n-2. И так далее. Таким образом, мы должны находить элементы с общими переменными и исключать эти переменные из термов. Для этого нам нужно находить в многомерном пространстве входных переменных геометрические элементы – точки отрезки, плоскости, кубы и гиперкубы.

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

Карты Карно

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

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

Минимизация на многомерных булевых кубиках

Что такое булевый кубик

Рассмотрим ось, соответствующую какой-либо булевой переменной, на которой имеются два входных значения – 0 и 1. Нарисуем на ней два кружочка. Значение входных переменных будем писать под кружочками, а выходной – внутри. Получаем булевый отрезок.

Рис. 5. Булевый отрезок

В этом случае возможны всего 4 булевы функции – константы 0 и 1, повторитель и логический инвертор. Они запишутся так:

Рис. 6. Все функции от двух булевых переменных

Для двух входных переменных у нас получится булевый квадрат и количество реализуемых функций составит 16 (перечислять их не будем):

Рис. 7. Булевый квадрат

Абсолютно аналогично, получим булевый кубик:

Рис. 8. Булевый куб

Здесь мы подписали под кружочками входные переменные в формате {X2,X1,X0}

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

Рис.9 . Четырехмерный булевый гиперкуб

Вот он какой, наш четырехмерный кубик! Кружочки подписаны значением входных переменных, что можно и не делать. Штрих-пунктирной линией обозначена переменная X3, а пунктиром – трехмерный подкубик X2=1. (Вообще, легко показать, что один 4х-мерный гиперкуб содержит в себе 8 трехмерных разрезов).

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

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

Булевы гиперкубы размерностью выше четвертой

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

Рис. 10. Семимерный булевый гиперкуб (развертка на плоскости)

Возможно, впрочем, правило 7 измерений относится только к развертке на плоскости, изображенной на предыдущем рисунке. На рисунке ниже изображен гиперкубик размерности 9, состоящий из 64х обычных трехмерных кубиков. Честно признаемся, мы с таким кубиком не работали, но выглядит он так, что похоже, его можно использовать на практике.

Рис. 11. Девятимерный булевый гиперкуб

Учебная задача (продолжение)

Сегмент a