Минимизация методом карт Карно

Цель работы

Изучение методов минимизации функций алгебры логики (ФАЛ).

Основные понятия

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

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

Исходными формами функции при решении канонической задачи минимизации являются ее ДСНФ и КСНФ. Если функция задана в другой форме, то ее преобразуют в ДСНФ или КСНФ. Рассмотрим минимизацию функций, заданных в дизъюнктивной нормальной форме.

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

где а - любая логическая функция.

Конъюнции, получаемые в результате склеивания соседних конституент, называют импликантами. Процесс многоступенчатого склеивания приводит к получению импликант, которые не склеиваются с другими и называются простыми.

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

Минимизируемая ФАЛ может содержать несколько тупиковых ДНФ.

Необходимо путем перебора выбрать тупиковую ДНФ с минимальным числом переменных, которая и будет искомой минимальной ДНФ минимизируемой ФАЛ.

Минимизация методом карт Карно

При минимизации ФАЛ небольшого числа переменных (три-пять) используются простые табличные методы, одним из которых является метод карт Карно.

Карты Карно позволяют минимизировать как полностью, так и не полностью определенные ФАЛ. Карта Карно (рис. 4.1) для ФАЛ четырех переменных, в которой проставленные единицы соответствуют единичным наборам ФАЛ, а нулевые не отмечены, соответствует аналитическому выражению минимизируемой ФАЛ

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

X 1 X 2 X 3 X 4

Рис. 4.1. Структура карты Карно

Рассмотренное свойство удобно использовать для группировки отдельных единичных наборов в так называемые "подкубы" (объединения из 2, 4, 8 и т.п. числа единичных наборов) с целью исключения одной, двух или нескольких переменных, входящих в единичные наборы. При склеивании единичных наборов, входящих в какой-либо подкуб, происходит исключение одной или нескольких переменных. Это является следствием того, что в подкубы входят пары наборов, отличающихся значением одной, двух или нескольких переменных.

Примеры образования двухклеточных, четырехклеточных и восьмиклеточных подкубов представлены в табл. 4.1-4.10.

Таблица 4.1

X 1 X 2 X 3 X 4				1 1 0 1 1 0 0 1   X1 X4 10

Таблица 4.2

X 1 X 2 X 3 X 4				0 0 0 1 0 0 1 1   X4 10

Таблица 4.3

X 1 X 2 X 3 X 4				0 1 0 0 0 1 1 0 10

Таблица 4.4

X 1 X 2 X 3 X 4				0 0 1 0 1 0 1 0 10

Таблица 4.5

X 1 X 2 X 3 X 4				0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 10

Таблица 4.6

X 1 X 2 X 3 X 4				0 0 1 1 0 1 1 0 0 1 1 1 0 1 1 0 10

Таблица 4.7

X 1 X 2 X 3 X 4				0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0   10

0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0

Таблица 4.8

X 1 X 2 X 3 X 4

0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0

Таблица 4.9

X 1 X 2 X 3 X 4

0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0

Таблица 4.10

X 1 X 2 X 3 X 4

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

Пример 1. Найти минимальную ДНФ для функции, заданной картой

Карно (табл.4.11).

В данном случае набор (1,1,0,0) можно объединить только с набором (1,1,1,0), набор (1,0,0,1) - с набором (1,0,1,1), набор (0,1,1,1) - с набором (1,1,1,1), а набор (0,0,1,0) - с набором (1,0,1,0).

Таблица 4.11

X 1 X 2 X 3 X 4

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

Окончательное выражение минимальной ДНФ имеет вид:

+ +