Карта Карно

Рис. 1 Пример Карты Карно

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейч'ем и усовершенствованы в 1953 Морисом Карно, физиком из «Бэлл Лабс», и были призваны помочь упростить цифровые электронные схемы.

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

Описание

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

Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ):

1. объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала $2^{n}$ ($n$ целое число = 0...$\infty$) клеток(помним про то что крайние строки и столбцы являются соседними между собой), в области не должно находится клеток содержащих нули;
2. область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
3. не смежные области расположенные симметрично оси(ей) могут объединятся в одну;
4. область должна быть как можно больше, а кол-во областей как можно меньше;
5. области могут пересекаться;
6. возможно несколько вариантов накрытия.

Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем тоже самое что и для первой, и т.д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например(для Карт на 2-ве переменные):

${\overline {X1}}\ {\overline {X2}}$

${\overline {X1}}\ X2$

$X1\ X2\$

$X1\ {\overline {X2}}$

${\overline {X2}}$

${\overline {X1}}$

${X2}\$

${X1}\$

$S1\vee S2=$

$S1\vee S2=$

$S1\vee S2=$

$S1\vee S2=$

$S1\vee S2=$

$S1\vee S2=$

$=X1X2\vee$

$=X1{\overline {X2}}\vee$

$=X2\vee X1$

$=X1\vee {\overline {X2}}$

$={\overline {X1}}\vee {\overline {X2}}$

$=X2\vee {\overline {X1}}$

$\vee {\overline {X1}}\ {\overline {X2}}$

$\vee {\overline {X1}}X2$

Для КНФ всё то же самое, только рассматриваем клетки с нулями, не меняющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной. Так для Карты Карно на рис.1 вырожение в формате ДНФ будет иметь вид: $f(X1,X2,X3,X4)=S1\vee S2\vee S3={\overline {X1}}\ {\overline {X4}}\vee X1X2X4\vee {\overline {X2}}\ {\overline {X4}}$
В формате КНФ:
$f(X1,X2,X3,X4)=(S1)(S2)(S3)=(X1\vee {\overline {X4}})({\overline {X1}}\vee X2\vee {\overline {X4}})({\overline {X1}}\vee {\overline {X2}}\vee X4)$
Так же из ДНФ в КНФ и обратно можно перейти использовав Законы де Моргана.

Пример

У мальчика Коли есть мама, папа, дедушка и бабушка. Коля пойдёт гулять на улицу если ему разрешат хотя бы двое родителей.
Для краткости обозначим родителей Коли через буквы:
мама – х1
папа – х2
дедушка – х3
бабушка – х4
Условимся обозначать согласие родителей единицей, не согласие нулём. Возможность пойти погулять обозначим буквой f, Коля идёт гулять – f = 1, Коля гулять не идёт – f = 0.
Составим таблицу истинности:

Перерисуем таблицу истинности в 2-х мерный вид:

Переставим в ней строки и столбцы в соответствии с кодом Грея. Получили Карту Карно:

Заполним её значениями из таблицы истинности:

Минимизируем в соответствии с правилами:

1. 1. Все области содержат 2^n клеток;
2. 2. Т.к. Карта Карно на четыре переменные оси располагаются на границах Карты и их не видно (подробнее смотри пример Карты на 5 переменных);
3. 3. Т.к. Карта Карно на четыре переменные все области симметрично осей - смежные между собой (подробнее смотри пример Карты на 5 переменных);
4. 4. Области S3, S4, S5, S6 максимально большие;
5. 5. Все области пересекаются (не обязательное условие);
6. 6. В данном случае рациональный вариант только один.

$f(X1,X2,X3,X4)=S1\vee S2\vee S3\vee S4\vee S5\vee S6=$

$=X3X4\ \vee \ X1X2\ \vee \ X2X4\ \vee \ X1X4\ \vee \ X1X3\ \vee \ X2X3$

Теперь по полученной минимальной ДНФ можно построить логическую схему:

Из за отсутствия в наличии шести-входового элемента ИЛИ, реализующего функцию дизъюнкции, пришлось каскадировать пяти- и двух-входовые элементы(D7, D8).

Составим мин. КНФ:

$f(X1,X2,X3,X4)=(S1)\ (S2)\ (S3)\ (S4)=$

$=(X1\vee X2\vee X3)(X1\vee X3\vee X4)(X2\vee X3\vee X4)(X1\vee X2\vee X4)$

Пример Карты Карно на пять переменных

Имеем такую таблицу истинности:

Карта Карно будет выглядеть следующим образом (для лучшего визуального восприятия в Карту нули не записываем):


Неправильно (на примере ДНФ):

• - Область S1 – накрыта правильно;
• - Область S2 – нарушает п.1;
• - Область S3 – нарушает п.2;
• -Области S4 и S6 – не выполняют п.3, это не является ошибкой – выражение получится больше чем если бы S4 и S6 представляли собой одну область;
• - Область S5 - нарушает п.1 по кол-ву клеток и по недопустимости нахождения нулей в области.
  
  

Правильно:

Минимизировав эту Карту получаем минимальную ДНФ:
$f(X1,X2,X3,X4,X5)=S1\vee S2\vee S3\vee S4\vee S5\vee S6=$
$={\overline {X1}}\ {\overline {X2}}X3X5\ \vee \ X1{\overline {X2}}\ {\overline {X4}}\ {\overline {X5}}\ \vee \ {\overline {X1}}\ {\overline {X3}}X4{\overline {X5}}\ \vee \ {\overline {X1}}\ {\overline {X2}}X4{\overline {X5}}\ \vee \ {\overline {X1}}\ {\overline {X3}}\ {\overline {X4}}\ {\overline {X5}}\ \vee \ X1X4X5$

Составим минимальную КНФ:

$f(X1,X2,X3,X4,X5)=(S1)\ (S2)\ (S3)\ (S4)\ (S5)\ (S6)\ (S7)=$ $=({\overline {X1}}\vee {\overline {X4}}\vee X5)(X3\vee X4\vee {\overline {X5}})({\overline {X1}}\vee {\overline {X2}}\vee X4)$ $({\overline {X1}}\vee X4\vee {\overline {X5}})(X1\vee X3\vee {\overline {X4}}\vee {\overline {X5}})(X1\vee {\overline {X2}}\vee {\overline {X3}})(X1\vee {\overline {X3}}\vee X4\vee X5)$

Другой вариант той же самой Карты Карно:

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

Пример большой Карты Карно на восемь переменных

Предположим, по имеющейся таблицы истинности составлена такая Карта Карно:

Найдём минимальную ДНФ: $f(X1,X2,X3,X4,X5,X6,X7,X8)S1\vee S2\vee S3\vee S4=X1{\overline {X6}}\ {\overline {X7}}\vee X1{\overline {X6}}X7{\overline {X8}}\vee X1X6X7X8\vee {\overline {X1}}\ {\overline {X5}}X6{\overline {X7}}X8$

Минимальная КНФ: $f(X1,X2,X3,X4,X5,X6,X7,X8)=(S1)(S2)(S3)(S4)(S5)(S6)=\$ $=({\overline {X1}}\vee {\overline {X6}}\vee X7{\overline {X8}})(X6\vee {\overline {X7}}\vee {\overline {X8}})({\overline {X6}}\vee X8)(X1X6)(X1{\overline {X6}}\vee {\overline {X7}})(X1{\overline {X5}})$