2.6. Табличные способы минимизации

Этот метод называют по разному: по картам Вейча (Вейтча), по картам Карно, используют также названия – диаграммы Карно – Вейча, но всё это графические методы, позволяющие быстро найти тупиковые и даже минимальные формы БФ. Карты Вейча и Карно отличаются только кодированием переменных. Мы будем далее называть их картами Вейча и излагать минимизацию применительно к этим картам.

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

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

Рис. 2.10. Карта Вейча для

Для элементарных БФ, при , карта будет содержать 1 клетку, для - 2 клетки, а для - карта будет иметь 4 клетки (рис. 2.10). Знаком (I или ) обозначено прямое значение переменной. В клетки таблицы записаны все 4 возможных комбинации аргументов.

Определение 2.11. Соседними клетками называются клетки карт Вейча, отличающиеся в записи только одним аргументом.

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

Рис. 2.11. Карта Вейча для	Рис. 2.12 Карта Вейча для

Отметим также, что можно склеивать число клеток (1, 2, 4, 8, …, 2^k), но, обязательно попарно соседних. Нельзя склеивать 3, 7, 11 и т.д. клеток. Рассмотрим карты Вейча для 3-х и 4-х переменных (рис. 2.11 и 2.12). Помимо задания областей знаками (I или ) можно задавать строки и столбцы двоичными кодами.

Между заданиями клеток карт в виде переменных и двоичными кодами должно быть однозначное соответствие. Найдем соседние клетки для (рис. 2.11) для клетки с координатами (или в кодах - 110). Видим, что две клетки соседние по карте являются и соседними по переменным (клетки и в кодах 010 и 111). Третья соседняя клетка для будет, если свернуть карту в цилиндр. Тогда клетка будет рядом с клеткой (100), т.е. окажется соседней.

Для карты на 4 переменных (рис. 2.12) для клетки найдем четыре соседних с ней клеток. Две первые клетки очевидны, это клетки и (0001 и 0100). Свернем, как в предыдущем случае, карту в цилиндр и убедимся в том, что клетка (0010) будет соседняя с заданной клеткой. Более того, сворачивая карту рис. 2.12 в тор (бублик), заметим, что клетка (1000) также будет соседней с , т.е. их можно склеивать. Для карт с , 6 и более нахождение соседних клеток становится несколько более сложным, но предсказуемым, если понять изложенную далее систему кодирования карт.

Рис. 2.13. Карта Карно

В картах Карно используется способ размещения переменных, при которых прямое значение аргументов в пределах полукарты, четверти карты и т.д. всегда располагается справа (или слева), как на рис. 2.13.

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

Кодирование столбов и строк в этом случае производится в коде Грея, который является однопеременным, т.е. любые две соседние кодовые комбинации отличаются в одном разряде, например, для 3-х разрядов:

Двоичные коды 000, 001, 010, 011, 100, 101, 110, 111.

Коды Грея 000, 001, 011, 010, 110, 111, 101, 100.

Последний и первый коды также отличаются в одном разряде. При построении 4-х разрядных двоичных кодов в коде Грея к первым 8-ми разрядам надо добавить 0 в старший разряд, а затем поставить 1 в старший разряд и снова повторить 8 младших разрядов. Для пятиразрядного кода Грея можно снова повторить эту же процедуру и т.д. Такое кодирование и будем называть картой Вейча.

На рис. 2.14 изображена карта на 5 переменных и приведено определение соседних клеток для клетки с координатами (оси симметрии оттенены более жирными линиями). Кроме явно соседних кодов , находим соседние коды по оси симметрии карты (01100) и половины карты (01010).

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

Рис. 2.14. Карта Вейча для	Рис. 2.15. Десятичные коды для

В этом случае может помочь знание координат клеток карты Вейча в двоичной системе счисления, если исходная минимизируемая функция задана номерами двоичных наборов, на которых функция равна 1 или 0 (таблица истинности). На рис. 2.15 приведено десятичное значение двоичных наборов функции от 5-ти переменных, по которым можно расставить 0 и 1 для заданной функции, если она задана таблицей истинности, или в цифровой записи в десятичном представлении двоичных наборов.

Рис. 2.16. Карта Вейча для

Представим карту на 6 переменных и покажем поиск 6-ти соседних клеток для одной из клеток (рис. 2.16). Коды по строкам и столбцам записаны в 8-ричной системе. Аналогично можно представить и более крупные карты, например, для карты на 7 переменных, содержащей 128 клеток. Необходимо по приведенному выше правилу найти число переменных в строках и столбцах для .

Число переменных в строках: . С учетом инверсных переменных это составит число строк, равных . Найдем число переменных в столбцах: . Значит, число столбцов карты будет , итого, число клеток будет . Чтобы изобразить такую карту и оцифровать ее запишем переменные и коды по строкам в 8- ричной системе, а коды по столбцам в 16-ричной системе (рис. 2.17). Получилась карта, в которой можно найти для каждой клетки семь соседних с ней, что показано на примере для клетки .

Рис. 2.17. Карта Вейча для

Запишем соседние коды для клетки (000 0000) используя для кодирования карты коды Грея. На рис. 2.17 показаны все соседние 7 клеток для исходной клетки :

- соседние с ней.