Карта Карно

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

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

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

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

Принципы минимизации[править | править код]

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

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

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

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

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

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

Karnaugh map 01 fixed.gif

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

Karnaugh map 02.gif

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

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

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

Karnaugh map 03.gif

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

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

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

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

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

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

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

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

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

Карта Карно может быть построена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности представленная в виде матрицы в 2-мерном виде.

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

Существенно, что в карте Карно соседние клетки обязательно имеют соседние, в смысле расстояния Хэмминга коды, то есть расстояние Хэмминга между соседними клетками равно 1 и различаются только состоянием — с инверсией или без, одной и только одной из переменных. Соседними клетками считаются клетки, примыкающие друг к другу стороной, также соседними клетками считаются клетки крайнего левого и крайнего правого столбцов и клетки первой и последней строк. Таком образом, карта Карно на плоскости топологически эквивалентна поверхности тора в трёхмерном пространстве, или гипертору в пространстве с размерностью на 1 больше размерности соответствующей многомерной карты Карно.

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

При заполнении карты на пересечении строки и столбца проставляется соответствующее значение из таблицы истинности — 0 или 1. После того как карта заполнена, приступают к минимизации.

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

  1. Объединяем смежные клетки, содержащие единицы, в область так, чтобы одна область содержала ( целое число = 0…) клеток (помним про то, что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток, содержащих нули;
  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


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

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


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

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

Примеры[править | править код]

Пример 1[править | править код]

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

Nikolay true table.png



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

2d true table.png



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

Karnough map 4 empty.png



Заполним её значениями из таблицы истинности(первая строка не соответствует таблице истинности так как f=0 и разрешения на гулять нет):

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. В данном случае рациональный вариант только один.

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

Logic Nikolay.PNG

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


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

Nikolay map KNF.png



~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)