БУЛЕВЫ ФУНКЦИИ (2). Булевы функции
![]()
|
Получение МКНФ и минимальных форм в базисе Пирса. В этих базисах допустимые претенденты ищут, рассматривая матрицу единиц. Рассмотрим алгоритм получения МКНФ. Претендентом служит сумма аргументов взятых с отрицанием или без него. 1) Задать длину претендента ![]() 2) Рассматривая матрицу единиц сформировать очередь всех допустимых претендентов длины ![]() 3) Если очередь пуста, принять ![]() 4) Взять первого допустимого претендента из очереди и проверить обнуляет ли он хотя бы один набор в матрице нулей. Если – нет, то допустимый претендент удалить из очереди и перейти к пункту 3, если – да, то перейти к пункту 5. 5) Включить допустимый претендент в формулу, представляющую собой произведение претендентов; 6) Исключить наборы матрицы нулей, на которых допустимый претендент равен нулю; 7) Исключить претендент из очереди; 8) Если матрица нулей не пуста, то перейти к пункту 3, иначе – конец. Рассмотрим получение МДНФ той же функции: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Претенденты ![]() Из претендентов длины 2 в очередь допустимых претендентов входят ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Замечание: если искать допустимые претенденты в виде функции Пирса с минимальным числом аргументов, которые равны нулю хотя бы на одном наборе матрицы нулей и равны единице на всех наборах матрицы единиц, то получим минимальную форму в базисе Пирса. Естественно, что следует учитывать особенности этой функции: - если претендент, равный нулю на наборе матрицы нулей и равный единице на всех наборах матрицы единиц состоит из одного аргумента, он должен записываться в минимальную форму с дополнительным отрицанием; - если претендент равен нулю на всех наборах матрицы нулей и равен единице на всех наборах матрицы единиц, то он записывается с общим отрицанием. Для рассмотренного примера допустимые претенденты, которые входят в минимальную форму: ![]() ![]() ![]() Замечание. При минимизации функций большого числа аргументов, матрицы единиц и нулей занимают значительный объем памяти ЭВМ. При большом числе аргументов его можно уменьшить более чем на порядок, если применить следующий прием: для минимизируемой функции выделяются две матрицы размером ![]() где ![]() ![]() Число слов матрицы при минимизации функции ![]() ![]() ![]() ![]() ![]() Пример: в гипотетической четырехразрядной машине задана матрица Разряд 3 2 1 0 Слово 0 0 0 0 1 Слово 1 0 1 1 0 Слово 2 1 0 0 0 Слово 3 1 0 0 1 Единицы этой матрицы соответствуют наборам 0,5,6,10,11,12,15. Минимизируемую функцию задают двумя подобными матрицами. Исходно эти матрицы заполняются нулями. Затем в матрицу единиц вписывают единицы в позиции, которые соответствуют наборам на которых функция равна единице, а в матрицу нулей вписывают единицы в позиции, которые соответствуют наборам на которых функция равна нулю. Пример: ![]() ![]() Эти матрицы задают не полностью определенную функцию равную единице на наборах 0,5,6,11,12,15 и нулю на наборах 4,13,14. Нетрудно подсчитать, что число слов в каждой из матриц при минимизации функций 32 аргументов на 32-разрядных машинах составит 134217728. Такой объем оперативной памяти доступен для современных ЭВМ. Главными ограничениями метода являются приемлемое время ввода значений функции и время собственно минимизации функции. Однако не следует смотреть на проблему минимизации слишком пессимистично, т.к. известно, что реальные булевы функции большого числа аргументов в подавляющем большинстве случаев не определены, причем число неопределенных наборов возрастает с ростом числа аргументов булевой функции. Синтез комбинационных схем. Существует класс логических устройств, у которых выходные сигналы схемы в данный момент времени зависят только от комбинации входных сигналов поступивших на схему в данный момент времени: ![]() Такие схемы называют комбинационными. Они описываются системой булевых функций. Задача синтеза обратна задаче анализа. Для решения задачи синтеза схема должна быть представлена так называемым техническим заданием. В этом задании, каким – либо способом формулируют основные технические требования, предъявляемые к устройству. Обычно это текстовое описание, при необходимости сдобренное таблицами, графиками, формулами и.т.п. В нем иногда отражают типы логических элементов, на которых реализуется устройство. Как правило, это задание неоднозначно описывает это устройство и поэтому первым шагом синтеза является построение математической модели устройства, в которой эти неоднозначности исключены. Это трудно формализуемый этап, поэтому эту задачу обычно решают самые квалифицированные сотрудники коллектива разработчиков. Если синтезируется комбинационная схема, то последующие этапы это - упрощение математической модели (минимизация системы булевых функций в заданном базисе); - построение функциональной схемы устройства; - преобразование функциональной схемы в принципиальную схему. (Это преобразование Вы сможете проводить после изучения курса «Схемотехника»). Задача. Разработать схему одноразрядного двоичного сумматора. При реализации схемы использовать элементы И-НЕ. ![]() Зачем нужен одноразрядный сумматор? Очевидно для изготовления многоразрядного сумматора. Но при суммировании многоразрядных слов необходимо учитывать перенос из предыдущего младшего разряда, поэтому входов должно быть три: на два входа ![]() ![]() ![]() ![]() ![]()
Минимизируем эти функции в базисе Шеффера (И-НЕ): ![]() ![]() ![]() Достаточно часто при изображении схем используют так называемый жгут. Жгут – это изображение множества проводников одной жирной линией. Естественно, что провода входящие в жгут и выходящие из него должны маркироваться. Изобразим функциональную схему одноразрядного сумматора: ![]() Самостоятельно получите минимальные выражения для этих функций в булевом базисе в дизъюнктивной форме, в булевом базисе в конъюнктивной форме, в базисе Пирса (ИЛИ-НЕ) и начертите схему сумматора в каждом из этих базисов. |