Карта Карно

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Рис. 1 Пример Куба Карно

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

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

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

Принципы минимизации[править | править вики-текст]

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


\overline {X}_1X_2X_3X_4 
\vee
\overline{X}_1X_2\overline{X}_3X_4 =
\overline {X}_1X_2X_4 (X_3 \vee \overline{X}_3) =
\overline {X}_1X_2X_4 \cdot 1 =
\overline {X}_1X_2X_4.

Аналогично для КНФ:


(\overline {X}_1\vee X_2\vee X_3\vee X_4)
(\overline {X}_1\vee X_2\vee \overline{X}_3\vee X_4) =
\overline {X}_1\vee X_2\vee X_4\vee X_3\overline {X}_3 = 
\overline {X}_1\vee X_2\vee X_4\vee 0 = 
\overline {X}_1\vee X_2\vee X_4.

Возможность поглощения следует из очевидных равенств


A \vee \overline{A} = 1;
A\overline{A} = 0.

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

Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе 2N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.

На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:

Karnaugh map 01 fixed.gif

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

Karnaugh map 02.gif

Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:


\overline {X}_1\overline {X}_2\overline {X}_3
\vee
X_1\overline {X}_2\overline {X}_3
\vee
\overline {X}_1\overline {X}_2X_3
\vee
X_1\overline {X}_2X_3
=

 =
\overline {X}_2 (\overline {X}_1\overline{X}_3 \vee \overline {X}_1X_3 \vee X_1\overline {X}_3 \vee X_1X_3)
= \overline {X}_2 (\overline {X}_1 \vee X_1)(\overline {X}_3 \vee X_3) = \overline {X}_2

В общем случае можно сказать, что 2K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных.

Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.

Karnaugh map 03.gif

Аналогичным образом можно работать с функциями большего числа переменных.

Порядок работы с картой Карно[править | править вики-текст]

Исходной информацией для работы с картой Карно является таблица истинности минимизируемой функции. Таблица истинности содержит полную информацию о логической функции, задавая её значения на всех возможных 2N наборах входных переменных X1 ... XN. Карта Карно также содержит 2N клеток, каждая из которых ассоциируется с уникальным набором входных переменных X1 ... XN. Таким образом, между таблицей истинности и картой Карно имеется взаимно однозначное соответствие, и карту Карно можно считать соответствующим образом отформатированной таблицей истинности.

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

Рис. 2. Пример работы с картой Карно

Принципы склейки[править | править вики-текст]

  • Склейку клеток карты Карно можно осуществлять по единицам (если необходимо получить ДНФ) или по нулям (если требуется КНФ).
  • Склеивать можно только прямоугольные области с числом единиц (нулей) 2n, где n — целое число. Для карт Карно с числом переменных более четырёх могут получаться более сложные области, о чём будет сказано в следующих разделах.
  • Область, которая подвергается склейке должна содержать только единицы (нули).
  • Крайние клетки каждой горизонтали и каждой вертикали также граничат между собой (топологически карта Карно для четырёх переменных представляет собой тор) и могут объединяться в прямоугольники. Следствием этого правила является смежность всех четырёх угловых ячеек карты Карно для N=4. Если во всех четырёх угловых ячейках стоят единицы (нули) они могут быть объединены в квадрат, как показано на рис. 2в.
  • Все единицы (нули) должны попасть в какую-либо область.
  • С точки зрения минимальности ДНФ (КНФ) число областей должно быть как можно меньше (каждая область представляет собой терм), а число клеток в области должно быть как можно больше (чем больше клеток в области, тем меньше переменных содержит терм. Терм размером 2n ячеек содержит Nn переменных).
  • Одна ячейка карты Карно может входить сразу в несколько областей. Это следует из очевидного свойства булевых функций: повторение уже существующего слагаемого (сомножителя) не влияет на функцию:


A \vee A = A;
A \cdot A = A.

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

Описание[править | править вики-текст]

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

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

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

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

Karnough map 2 1 1.PNG Karnough map 2 1 2.PNG Karnough map 2 1 3.PNG Karnough map 2 1 4.PNG Karnough map 2 1 5.PNG Karnough map 2 1 6.PNG Karnough map 2 1 7.PNG Karnough map 2 1 8.PNG
\overline{X_1}\ \overline{X_2} \overline{X_1}\ X_2 X_1\ X_2\ X_1\ \overline{X_2} \overline{X_2} \overline{X_1} {X_2}\ {X_1}\


Karnough map 2 1 9.PNG Karnough map 2 1 10.PNG Karnough map 2 1 11.PNG Karnough map 2 1 12.PNG Karnough map 2 1 13.PNG Karnough map 2 1 14.PNG
S_1\vee S_2 = S_1\vee S_2 = S_1\vee S_2 = S_1\vee S_2 = S_1\vee S_2 = S_1\vee S_2 =
=X_1X_2\vee =X_1\overline{X_2}\vee =X_2\vee X_1 =X_1\vee\overline{X_2} =\overline{X_1}\vee\overline{X_2} =X_2\vee \overline{X_1}
\vee\overline{X_1}\ \overline{X_2} \vee\overline{X_1}X_2

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

f(X_1,X_2,X_3,X_4)=S_1\vee S_2\vee S_3=\overline{X_1}\ \overline{X_4}\vee X_1 \overline{X_2}\ X_4\vee \overline{X_4}

В формате КНФ:

f(X_1,X_2,X_3,X_4)=S_1 S_2 S_3=(X_1\vee \overline{X_4})(X_2\vee \overline{X_4})(\overline{X_1}\vee \overline{X_2} \vee X_4)

Так же из ДНФ в КНФ и обратно можно перейти использовав Законы де Моргана.

Примеры[править | править вики-текст]

Пример 1[править | править вики-текст]

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

Nikolay true table.png



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


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

Karnough map 4 empty.png



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


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

Nikolay map DNF.png



  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
Теперь по полученной минимальной ДНФ можно построить логическую схему:

Logic Nikolay.PNG

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

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

Nikolay map KNF.png


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)

~logic Nikolay.PNG

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]

Программное обеспечение

  • Karnaugh Minimizer, Коммерческое Windows приложение (часто работает некорректно, например для этого уравнения : 0,1,5,8,10,13).
  • Logic Minimizer, Коммерческое Windows приложение, но можно сделать чтобы запускалось на Unix.
  • Kmap minimizer Онлайн приложение (Flash).
  • GKMap, свободное ПО на SourceForge.net.
  • Karnaugh Map Minimizer, бесплатное (но часто некорректно работающее) ПО на SourceForge.net.
  • Gorgeous Karnaugh, коммерческое ПО Gorgeous Karnaugh для минимизации по картам Карно.

Литература[править | править вики-текст]

  • Р.Токхейм Основы цифровой электроники — М.: Мир, 1988. — 392 с. (Глава 4, страницы 88-95)