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

8.2.4.1. Диаграммы Вейча

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

1. Коды единичной длины (n=1) являются зеркальными.

2. Если построен код длины (n-1), то нужно построить новую ось симметрии и отобразить зеркально коды длины (n-1) относительно этой оси, а затем приписать слева всем кодам, расположенным выше оси, цифру 0, а кодам, расположенным ниже оси, цифру 1. В результате получаем зеркальные коды длины n.

Процесс построения зеркальных кодов для n=1,2,3 показан на рис. 8.18, а диаграммы, построенные с использованием этих кодов, приведены на рис. 8.19. Диаграмма для пяти переменных показана на рис. 8.20.

n = 1

n = 2

n = 3

Ось симметрии

00 01 11 10

Ось симметрии

000 001 011 010 110 111 101 100

Ось симметрии

Рис.8.18

Рис.8.19

Для удобства построения и использования диаграмм коды строк и столбцов опущены. Вместо них на диаграммах строки и столбцы, соответствующие единичным значениям переменных x_i, i=1,..,n отмечены чертой с обозначением переменной x_i. Таким образом, клетки, расположенные в строке или столбце, отмеченными чертой с переменной x_i, соответствуют наборам, в которых x_i=1. На диаграмме, приведенной на рис. 8.20, показаны также оси симметрии, которые соответствуют границам изменения значений переменных. Нетрудно проверить, что коды клеток, расположенных симметрично относительно оси с номером k, отличаются только значением одной переменной x_k. Свойство симметрии диаграмм является основой визуальных методов минимизации переключательных функций, которые будут рассмотрены в одном из последующих разделов.

Рис.8.20

Дата добавления: 2015-07-07