кратчайших претендентов.

При использовании метода булева функция представляется матрицей наборов аргументов, на которых функция равна единице (матрица единиц) и матрицей наборов, на которых функция равна нулю (матрица нулей). Под претендентом будем понимать в зависимости от требуемой формы представления функции произведение, сумму, функцию Шеффера, либо функцию Пирса над аргументами, взятые с отрицанием, либо без него. При получении МДНФ претендент – произведение аргументов. При получении МКНФ претендент – сумма аргументов, при минимизации в базисах Шеффера и Пирса – претендент операция И-НЕ и ИЛИ-НЕ над аргументами.

Число аргументов претендента будем называть длиной претендента.

Рассмотрим метод получения МДНФ методом подбора кратчайших произведений.

Пример. Задана не полностью определенная булева функция

,

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

- не подходит, поскольку оно равно 1 не только на 0100 матрицы единиц, но и на наборах 0101, 0110, 0111 матрицы нулей;

- не подходит, поскольку равно 1 на всех наборах матрицы нулей;

-не подходит, т.к. равно 1 на наборах 0101, 1101 матрицы нулей;

- не подходит, т.к. равно 1 на наборе 0110;

-не подходит, т.к. равно 1 на наборе 0101, 0110, 0111;

- не подходит, т.к. равно 1 на наборе 0101;

- не подходит, т.к. равно 1 на наборе 0110;

- не подходит, т.к. равно 1 на наборах 0101 и 1101;

- не подходит, т.к. равно 1 на наборе 0110;

-подходит, поскольку не равно 1 ни на одном наборе матрицы нулей и покрывает наборы 0100, 0000 матрицы единиц.

Вписываем в МДНФ и удаляем наборы 0100 и 0000 из матрицы единиц:

,

Выписываем набор 0001 матрицы единиц и аналогично ищем кратчайшее произведение равное единице на этом наборе:

- не подходит, поскольку дает значение 1 наборам 0101, 0110, 0111 матрицы нулей;

-подходит, поскольку не равно 1 ни на одном наборе матрицы нулей и покрывает наборы 0001, 1001 матрицы единиц. Вписываем в МДНФ и удаляем наборы 0001 и 1001 в матрице единиц: ,

, .

Выписываем набор 1110 и, поочередно рассматривая претенденты , находим кратчайшее произведение равное 1 на наборах 1110 и 1100 и равное нулю на всех наборах матрицы нулей. Вычеркиваем наборы 1110 и 1100 из матрицы единиц. Поскольку матрица единиц пуста – минимизация закончена. МДНФ имеет вид: .

Замечание: если искать покрытие матрицы единиц функцией Шеффера с минимальным числом аргументов, то получим минимальную форму в базисе Шеффера. Естественно, что следует учитывать особенности этой функции:

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

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

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

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

Алгоритм получения МДНФ:

1) Задать длину претендента ;

2) Рассматривая матрицу нулей сформировать очередь всех допустимых претендентов длины ;

3) Если очередь пуста, принять и перейти к пункту 2, иначе – к пункту 4;

4) Взять первого допустимого претендента из очереди и проверить покрывает ли он хотя бы один набор в матрице единиц. Если – нет, то допустимый претендент удалить из очереди и перейти к пункту 3, если – да, то перейти к пункту 5.

5) Включить допустимый претендент в формулу, представляющую собой сумму претендентов;

6) Исключить наборы, покрываемые претендентом из матрицы единиц;

7) Исключить претендент из очереди;

8) Если матрица единиц не пуста, то перейти к пункту 3, иначе – конец.

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

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

наборы 0000, 0001,1001 матрицы единиц, поэтому он входит в формулу

. Матрица единиц после удаления этих наборов примет вид:

, .

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

Допустимые претенденты не покрывают ни одного набора матрицы единиц и удаляются. Допустимый претендент покрывает наборы 1110 и 1100 матрицы единиц, поэтому он вписывается в формулу, а наборы 1110 и 1100 исключаются из матрицы единиц: ,

, .

Допустимые претенденты не покрывают набора 0101 и исключаются. Допустимый претендент покрывает набор 0101, следовательно, он входит в формулу: . Поскольку матрица единиц после удаления набора 0100 пуста – минимизация закончена.

Получение МКНФ и минимальных форм в базисе Пирса.

В этих базисах допустимые претенденты ищут, рассматривая матрицу единиц. Рассмотрим алгоритм получения МКНФ. Претендентом служит сумма аргументов взятых с отрицанием или без него.

1) Задать длину претендента ;

2) Рассматривая матрицу единиц сформировать очередь всех допустимых претендентов длины ;

3) Если очередь пуста, принять и перейти к пункту 2, иначе – к пункту 4;

4) Взять первого допустимого претендента из очереди и проверить обнуляет ли он хотя бы один набор в матрице нулей. Если – нет, то допустимый претендент удалить из очереди и перейти к пункту 3, если – да, то перейти к пункту 5.

5) Включить допустимый претендент в формулу, представляющую собой произведение претендентов;

6) Исключить наборы матрицы нулей, на которых допустимый претендент равен нулю;

7) Исключить претендент из очереди;

8) Если матрица нулей не пуста, то перейти к пункту 3, иначе – конец.

Рассмотрим получение МДНФ той же функции:

,

Претенденты недопустимы, потому что обращают в нуль хотя бы один набор матрицы единиц.

Из претендентов длины 2 в очередь допустимых претендентов входят . Допустимый претендент равен нулю на наборах 0101 и 0110 матрицы нулей, поэтому он входит в МКНФ: . После исключения наборов 0101, 0110, 0111 получим:

, . Следующий допустимый претендент из очереди равен нулю на наборах 1111 и 1101 матрицы нулей, т.е. входит в МКНФ: . Т.к. после удаления наборов матрица нулей пуста – минимизация закончена.

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

- если претендент, равный нулю на наборе матрицы нулей и равный единице на всех наборах матрицы единиц состоит из одного аргумента, он должен записываться в минимальную форму с дополнительным отрицанием;

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

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

где - число разрядов в машинном слове;

- выделенное число слов.

Число слов матрицы при минимизации функции аргументов определяется по формуле: , где -символ округления результата к большему целому. Номер набора в матрице определяется его положением:

, где - номер разряда в слове.

Пример: в гипотетической четырехразрядной машине задана матрица

Разряд 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. Такой объем оперативной памяти доступен для современных ЭВМ. Главными ограничениями метода являются приемлемое время ввода значений функции и время собственно минимизации функции. Однако не следует смотреть на проблему минимизации слишком пессимистично, т.к. известно, что реальные булевы функции большого числа аргументов в подавляющем большинстве случаев не определены, причем число неопределенных наборов возрастает с ростом числа аргументов булевой функции.

Синтез комбинационных схем.

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

Такие схемы называют комбинационными. Они описываются системой булевых функций.

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

Если синтезируется комбинационная схема, то последующие этапы это

- упрощение математической модели (минимизация системы булевых функций в заданном базисе);

- построение функциональной схемы устройства;

- преобразование функциональной схемы в принципиальную схему. (Это преобразование Вы сможете проводить после изучения курса «Схемотехника»).

Задача. Разработать схему одноразрядного двоичного сумматора. При реализации схемы использовать элементы И-НЕ.

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

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

Минимизируем эти функции в базисе Шеффера (И-НЕ):

;

.

Достаточно часто при изображении схем используют так называемый жгут. Жгут – это изображение множества проводников одной жирной линией. Естественно, что провода входящие в жгут и выходящие из него должны маркироваться.

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

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