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

Позиционные карты (карты Карно, диаграммы Вейча) представ­ляет собой специально организованные таблицы соответствия, на которых удобно осуществляются операции склеивания при упрощении логических функции на пути к минимальным формам. Столбцы и стро­ки таблицы соответствуют всевозможным наборам значений перемен­ных, причем эти наборы расположены в таком порядке, что каждый последующий отличается от предыдущего только одной из переменных. Благодаря этому соседние ячейки по горизонтали и вертикали от­личаются только одной переменной. Ячейки, расположенные по краям таблицы, также считаются соседними и обладают этим свойством. Каждому набору значений переменных по строкам и столбцам соответ­ствует своя ячейка, расположенная на их пересечении. Она запол­няется единицей, если на соответствующем наборе функция принимает единичное значение, или нулем при нулевом значении функции (нули иногда не вписываются, а оставляются пустые клетки). Таким образом, отмеченные ячейки соответствуют минтермам, а неотмеченные - макс­термам канонических форм.

На рис. 2.1 приведены примера позиционных карт для трех переменных (а), для четырех переменных (б) и для пяти переменных (в).

Рис.2.1.

Операции склеивания двух минтермов n-го ранга исходной формулы соответствует на карте Карно объединение двух соседних ячеек, отмеченных единицами, и эта объединенная пара ячеек представляет собой результат (n-1)-го ранга. Аналогич­но склеивание двух минтермов (n-1)-го ранга в минтерм (n-2)-го ранга представляется объединением соответствующих пар ячеек и т.д.

Считывание минтермов с карты Карно осуществляется последовательным рассмотрением групп ячеек. В минтерм входят только те переменные, которые сохраняют свои значения в данной группе, при­чем значениям единицы соответствует сама переменная, а значению 0 - ее отрицание. Переменные, которые принимают в данной группе различные значения (0 и 1), являются свободными и в данном мин­терме отсутствуют. Любая совокупность групп ячеек, покрывающая все отмеченные ячейки, соответствует некоторой сумме минтермов различных рангов, которая равнозначна данной функции.

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

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

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

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

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

Модифицированные позиционные карты представляют собой правильный прямоугольник (с соотношением сторон 1: 1 при четном количестве переменных или 1: 2 - при нечетном). Главным отличием рассматривае­мых карт является обозначение переменных в виде разрывных линий.

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

Рис. 2.2

Каждой конъюнкции переменных на карте соответствует определенная правильная конфигурация, площадь которой S равна

S = 2^{(n - r)},

где n - количество переменных,

r - ранг конъюнкции, т.е. количество переменных, входящих в конъюнкции.

На рис.2.3 приведены примеры правильных конфигураций.

Рис.2.3

Алгоритм минимизации логических функций состоит из следующих этапов.

1. Рассматриваются правильные конфигурации r=1.

2. Если в конфигурации есть хотя бы одно значение «0» или все ячейки уже отмечены (т.е. склеены ранее), то склеивание невозможно, иначе записывают конъюнкцию, а все, входящие в нее ячейки отмечают (в данном примере ставят «2»).

3. Проверяют все ли ячейки склеены, если да, то процесс минимизации окончен.

4. Повторяют п.п. 1, 2, 3 для r=2, …, n.