Минимизация булевых функций с помощью карт Карно

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

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

При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. Например, для функции двух переменных А и В (рис. 5) карта Карно имеет вид

Единицы, представленные в клетках, обозначают конституенты единицы рассматриваемой функции. Отыскание минимальной ее формы сводится к определению варианта, при котором все конституенты единицы накрываются (охватываются контурами покрытия) наименьшим числом наиболее коротких импликант. Объединение клеток на карте эквивалентно выполнению операции склеивания.

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

· площадь контура покрытия должна быть S_k = 2^m-i клеток, где  – целое число, m – число переменных. Если, например, m = 3, то S_k = 1, 2, 4, или 8 клеток;

· число сокращаемых переменных N_перем. = log₂ S_k , т.е. при S_k = 1 не сокращается ни одна переменная, при S_k = 2 сокращается одна переменная и т.д.

В примере на рис. 5 пара единиц верхней строки охватывается импликантой Ā (т.е. обе клетки ) имеют общий аргумент Ā). Пара единиц правого столбца накрывается импликантой B, как общей для обеих клеток. Следовательно, минимальная ДНФ функции F(A,B) = Ā Ú B.

Если имеется несколько вариантов объединения конституент контурами, то можно получить несколько различных эквивалентных минимальных ДНФ функции, одна из которых выбирается для реализации в цифровом устройстве.

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

.

Карта Карно, состоящая из 2³ = 8 клеток, может быть размечена, как показано на рис. 6.

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

.

Минимизация недоопределенных функций

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

Пусть необходимо минимизировать булеву функцию, заданную картой Карно (рис. 7).

Если группировать единицы в контурах только по исходному заданию (рис. 7, а), то минимальная форма функции будет иметь вид:

.

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

.

Функция j, значения которой совпадают со значениями заданной функции F на тех наборах, где F определена, называется эквивалентной.

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

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

Поэтому устранение опасных состязаний достигается возвращением импликант, которые оказались лишними при переходе от сокращенной к тупиковой ДНФ.