3.5 Карты Карно.

Карта Карно является таблицей для графического способа представления ФАЛ. Карта Карно функции n переменных представляет собой матрицу из клеток и обычно имеет квадратную или прямоугольную форму, близкую к квадратной. Переменные ФАЛ разбиваются на две равные или отличающиеся на единицу группы (в зависимости от четного или нечетного их числа). Одна группа переменных служит для нумерации столбцов, другая – для нумерации строк карты Карно. Столбцы и строки таблицы отмечаются номерами наборов переменных, порядок следования номеров наборов соответствует двоичному коду Грея.

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

Характерные особенности кода Грея:

1. Каждая комбинация отличается от соседних только в одной позиции (в одном разряде).

2. Смена значений элементов в каждом разряде при переходах от комбинации к комбинации происходит в два раза реже, чем в простом двоичном коде.

3. В коде Грея можно выделить оси симметрии (оси отражения). Относительно осей симметрии имеет место ʺзеркальноеʺ расположение (отражение) символов в некоторых разрядах. Так, в двухразрядном коде (см. первые два столбца справа и первые четыре строки табл.4) имеет место ʺзеркальноеʺ расположение символов в первом разряде относительно оси, проведенной между строками 1 – 2; в трехразрядном коде (см. первые три столбца справа и восемь строк табл.4) имеет место ʺзеркальноеʺ расположение символов в двух младших разрядах относительно оси, проведенной между строками 3 – 4, а также в младшем разряде относительно осей 1 – 2 и 5 – 6; в четырехразрядном коде имеет место ʺзеркальноеʺ расположение символов в трех младших разрядах относительно оси, проведенной между строками 7 – 8, в двух младших разрядах относительно осей 3 – 4 и 11 – 12, а также в младшем разряде относительно осей 1 – 2, 5 – 6, 9 – 10, 11 – 12. Ось симметрии, которая проходит в n-разрядном коде Грея между комбинациями, соответствующими числам называется главной осью симметрии. Относительно нее симметрично (т.е.ʺзеркальноʺ) расположены символы в (n – 1) разрядах кода Грея. Для четырехразрядного кода Грея главная ось проходит между стоками 7 – 8, относительно которой ʺзеркальноʺ расположены символы в трех младших разрядах.

Правило перевода простого двоичного кода в код Грея:

1) под двоичным числом записывают такое же число со сдвигом вправо на один разряд, при этом младший разряд сдвигаемого числа отбрасывается;

2) поразрядно (т.е. без учета переносов) суммируют несдвинутое и сдвинутое двоичные числа по модулю два.

Результат суммирования дает изображение исходного двоичного числа в коде Грея.

В табл.4 приведены десятичные числа от 0 до 15, выраженные комбинациями простого двоичного кода и кода Грея.

Таблица 4

Десятичное число	Простой двоичный код	Код Грея
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101
10	1010	1111
11	1011	1110
12	1100	1010
13	1101	1011
14	1110	1001
15	1111	1000

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

Рис. 1. Карты Карно двух, трех, четырех и пяти переменных

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

На рис. 1 в качестве некоторых примеров короткими отрезками линий (оси симметрии, или оси «отражения») отмечены границы карт меньшего числа переменных, из которых строятся карты Карно большего числа переменных. Например, карта Карно для трех переменных (рис. 1,б) состоит из двух карт для двух переменных х₂ и х₁, столбцы которых соединены по границе, отмеченной вертикальным отрезком линии. Нумерация столбцов левой карты для двух переменных х₂,х₁ следует в порядке 0, 1, а для правой – 1, 0, т.е. идет отражение («зеркальное») порядка нумерации столбцов по переменной х₂. Левая карта для двух переменных х₂, х₁ соответствует переменной , правая – х₃, а поэтому нумерация столбцов по переменным х₃, х₂ имеет порядок 00, 01, 11, 10. Аналогично можно представить, что карта Карно для пяти переменных составлена из двух карт для четырех переменных. Левая карта для четырех переменных имеет порядок нумерации столбцов по переменным х₄, х₃ 00, 01, 11, 10, правая –10, 11, 01, 00, т.е. отраженный («зеркальный»). Левая карта Карно четырех переменных х₄, х₃, х₂ х₁ соответствует переменной , правая – переменной х₅. Поэтому нумерация столбцов по переменным х₅, х₄, х₃ карты Карно для пяти переменных имеет порядок 000, 001, 011, 010, 110, 111, 101, 100. Далее на картах Карно разделение на карты меньшего числа переменных отрезками линий не отмечается, но подразумевается.

Каждой клетке на карте Карно соответствует определенный набор переменных. Например, на карте Карно для пяти переменных клетке, расположенной на пересечении столбца 010 и строки 11, соответствует набор 0, 1, 0, 1, 1 переменных х₅, х₄, х₃, х₂, х₁.

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

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

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

Две конституенты единицы (нуля) склеиваются, если:

-они расположены в соседних клетках одной строки или одного столбца;

-они расположены в противоположных клетках одной строки или одного столбца;

-они находятся в клетках, симметрично расположенных относительно осей симметрии карт для двух, трех, четырех и большего числа переменных, а сами карты расположены по соседству друг с другом или в противоположных концах столбцов или строк карт (не клеток).

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

На рис. 2 приведена карта Карно для шести переменных x₆, x₅,…, x₁, составленная из восьми карт для трех переменных или из четырех карт для четырех переменных.

Рис. 2. Примеры склеивающихся конституент единицы

Поясним правила нахождения склеивающихся конституент единицы. Конституента единицы, обозначенная на карте Карно (рис. 2) буквой a ( склеивается с соседними конституентами единицы b (по переменной х₁), с (по переменной х₄), d (по переменной х₃), расположенных в соседних клетках карты трех переменных, а также с конституентами единицы i (по переменной х₅), h (по переменной х₆), расположенных в соседних картах, а каждая из клеток i и h расположена симметрично с клеткой a относительно границ раздела карт для трех переменных. Kонституенты единицы a и e не склеиваются, так как расположены несимметрично относительно границы соседних карт Карно для трех переменных. Конституента единицы а не склеивается с конституентами единицы j и f, так как карты Карно трех переменных, в которых они расположены, не являются соседними с картой Карно трех переменных, в которой расположена конституента единицы а.

По принципу соседства расположения клеток и карт можно определить группы клеток, содержащих единицы и образующих квадрат или прямоугольник. Эти группы клеток с единицами склеиваются сразу по k переменным.

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

Рис. 3. Примеры групп склеивающихся конституент единицы

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

1. Выбирается клетка, содержащая «единицу», и определяются все возможные группы этой клетки с другими клетками, содержащими«единицы». Группам клеток, соответствуют конъюнкции, ранг которых меньше ранга конституент единицы. Определяют эти конъюнкции, соответствующие группам клеток, содержащих «единицы».

2. Анализируются эти группы. Если все «единицы» одной группы содержатся в другой группе, то первую вычеркивают. Невычеркнутые группы являются простыми импликантами.

Если для рассматриваемой клетки с «единицей» невычеркнутой осталась одна группа, то соответствующая ей конъюнкция является также и существенной импликантой. Если клетка с «единицей» ни с какой другой не склеивается, то соответствующая этой клетке конституента единицы является и простой, и существенной импликантой.

3. Повторяются пункты 1 и 2 для каждой клетки карты, содержащей «единицу», т.е. для каждой конституенты единицы. При достаточном опыте запись всех промежуточных групп становится ненужной, поэтому сразу записываются простыеимпликанты.