1.4.3 Минимизация функций алгебры логики

по методу Квайна - Мак-Класки

Недостаток метода Квайна - необходимость исчерпывающего попарного срав-

нения или сопоставления всех минтермов на этапе нахождения первичных импликант. С ростом числа минтермов увеличивается количество попарных сравнений.

Числовое представление ФАЛ позволяет упростить самый трудоёмкий этап 1. Все минтермы СДНФ ФАЛ записываются в виде их двоичных кодов, а все коды разбиваются по числу единиц на непересекающиеся группы.

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

F= (2)345711131415(17) (20)(21)(30)=

=(00010)0001100100001010011101001010110110001101(01111) 

(10000)(10001)(11000); (28)

Группа 0: пустая

Группа 1: (00010) 00100 (10000)

Группа 2: 00011 00101 01100 01001 (10001) (11000)

Группа 3: 00111 01011 01101

Группа 4: (01111)

Э т а п 1. Нахождение первичных импликант.

Сравнение минтермов соседних групп проведём с использованием таблиц.

Двоичный код переменной, по которой склеиваются импликанты, после склеивания заменяется в ячейках таблиц нечисловым символом .

В заголовочных строках таблиц 8, 9 и 10 нет двоичных кодов минтермов, которые не подверглись склеиванию. Значит первичных импликант среди минтермов минимизируемой ФАЛ нет. Минтермы с кодами (20), (21) и (30), на которых ФАЛ не определена, склеились только между собой. ФАЛ на этих наборах переменных должна быть доопределена как имеющая нулевые значения и, следовательно, из дальнейшего рассмотрения должны быть исключены и эти минтермы и импликанты, полученные в результате их склеивания в таблицах 8, 9 и 10.

В ячейках таблицы 8 находятся импликанты группы 1, в ячейках таблицы 2 находятся импликанты группы 2, в ячейках таблицы 3 находятся импликанты группы 3.

В таблицах 11 и 12 произведено сопоставление импликант соседних групп.

Первичные импликанты: 0001 010 011 011 011

Э т а п 2. Расстановка меток.

Э т а п 3. Нахождение существенных импликант.

Существенные импликанты в таблице 13 отмечены знаком ^c синего цвета. Первая существенная импликанта 0001 представляет набор (00010), на котором СДНФ ФАЛ не определена. Очевидно, что следует доопределить ФАЛ как имеющую нулевое значение на этом наборе переменных. Тогда первая существенная первичная импликанта 0001 исключается из дальнейшего рассмотрения, а первичная импликанта 011 помеченная знаком ^з зелёного цвета, становится существенной для набора 00011.

Э т а п ы 4 и 5. Для исходной СДНФ ФАЛ, минимизируемой по методу Квайна - Мак-Класки, эти этапы выполняются точно так же, как и при минимизации СДНФ ФАЛ по методу Квайна и, поскольку получена всего одна несущественная импликанта 011, в описание минимизированной ФАЛ эта первичная импликанта не включается.

Э т а п 6. Выбирается минимальное покрытие минтермов СДНФ ФАЛ существенными первичными импликантами и записывается единственно возможный вариант минимальной ФАЛ:

F = 010  011  011 = ; (29)

Возможна дальнейшая минимизация этой функции с использованием скобочной формы записи. Общая переменная всех первичных импликант выносится за скобки, в которые заключается дизъюнкция оставшихся двухместных наборов переменных. Такая форма записи минимальной ФАЛ нецелесообразна при технической реализации этой функции. Скобочная форма записи ФАЛ при технической реализации на логических элементах требует многокаскадного последовательного включения логических элементов, что понижает быстродействие всей схемы. Кроме этого, постоянное значение во всех первичных импликантах для минимальной ФАЛ при технической реализации означает подключение одного из входов всех конъюнкторов к источнику «логической 1». Такие входы конъюнкторов можно из схемы исключить, то есть использовать логические схемы с количеством входов меньшим на число переменных, имеющих постоянное значение, чем количество переменных. Из аналитической записи МДНФ ФАЛ общие переменные для всех первичных импликант, имеющие постоянное значение, нужно исключить в соответствии с правилом 1&F(X) = F(X), где X - множество булевых переменных . Минимальная дизъюнктивная нормальная форма для рассмотренного примера ФАЛ запишется как:

F = (30)