Карты карно. Правила минимизации с использованием карт карно

Лекция №11

Упрощение логических выражений методом карт Карно

1. Куб Карно.

2. Принцип минимизации.

3. Порядок работы с картой Карно.

Куб Карно

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

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

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

Принцип минимизации

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

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

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

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

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

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

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

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

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

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

Аналогичным образом можно работать с функциями пяти, семи (обязательно простое число) и т.д., используя не визуализируемые многомерные булевы кубы.

Порядок работы с картой Карно

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

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

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

Принципы склейки

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

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

· Область, которая подвергается склейке должна содержать только единицы (нули).

· Крайние клетки каждой горизонтали и каждой вертикали также граничат между собой (топологически карта Карно для четырёх переменных представляет собой тор) и могут объединяться в прямоугольники. Следствием этого правила является смежность всех четырёх угловых ячеек карты Карно для N =4. Если во всех четырёх угловых ячейках стоят единицы (нули) они могут быть объединены в квадрат, как показано на рис. 2в.

· Все единицы (нули) должны попасть в какую-либо область.

· С точки зрения минимальности ДНФ (КНФ) число областей должно быть как можно меньше (каждая область представляет собой терм), а число клеток в области должно быть как можно больше (чем больше клеток в области, тем меньше переменных содержит терм. Терм размером 2 n ячеек содержит N n переменных).

· Одна ячейка карты Карно может входить сразу в несколько областей. Это следует из очевидного свойства булевых функций: повторение уже существующего слагаемого (сомножителя) не влияет на функцию:

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

Описание

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

Рис. 4.1. Метод скручивания карты Карно

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

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

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

2. Область должна располагаться симметрично оси (ей) (оси располагаются через каждые четыре клетки);

3. Несмежные области, расположенные симметрично оси(ей), могут объединяться в одну;

4. Область должна быть как можно больше, а количество областей как можно меньше;

5. Области могут пересекаться;

6. Возможно несколько вариантов покрытия.

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

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

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

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

Примеры:

Пример 1.

Упростить полученную СДНФ, используя склеивание, а так же применить карту Карно для получения ДНФ.

Применено свойство и склеивание по «z» и по «y».

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

Для нашей функции имеем

yz x

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

1) Каждый руг может содержать только 2 K (к = 0, 1, 2,…) единиц, например16, 8, 4, 2, 1.

2) Круги должны быть наибольшего размера.

3) Число кругов наименьшее, покрывающее все единицы.

4) Так как наборы (0,0) и (1,0) соседние. То края карты соединяются друг с другом.

5) По каждому из кругов составляется простая конъюнкция, входящая в ДНФ. При этом оставляются только те переменные, которые сохраняют свое значение во всем круге и как обычно, если х i = 1, то пишем х i , если х i = 0, то .

Построим круги для нашего примера.

yz x
1 1 1 2

Имеем две конъюнкции. Для первого круга и сохраняют свое значение, получаем . Во втором круге не меняется и , получаем . Окончательно .

Пример 2

У мальчика Коли есть мама, папа, дедушка и бабушка. Коля пойдёт гулять на улицу, если ему разрешат хотя бы двое родственников.
Для краткости обозначим родственников Коли через буквы:
мама - х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. В данном случае рациональный вариант только один.

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

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

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

Заключение .

Для минимизации логических функций возможно использовать разные методы:

  • карта Карно (Вейча)
  • Квайна
  • Квайна- Мак-Класки
  • Петрика

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

Метод минимизационных карт Карно (или карт Вейча) хорошо работает при числе аргументов 3,4 и даже 5 и обеспечивает простоту получения результата. Этот метод основан на зрительном анализе таблиц (карт) и не может быть применен для обработки вычислительной техникой.

Домашнее задание:

1. Минимизировать нижеприведённые функции, представленные картами Карно.

Не заполненные клетки соответствуют нулю. Переменные, обозначенные буквами, соответствуют прямому значению, а не обозначенные - инверсному.

Контрольные вопросы:

1. Определение куба Карно.

2. Кем и в каком году были изобретены карты Карно?

3. Основной метод минимизации логических функций?

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

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

Для примера, представленного на рис. 1.6 , каноническая сумма минтермов будет выглядеть так:

(2.1)

Из сравнения (1.1) и (2.1) видно, что одной и той же таблице истинности (рис. 1.6 ,б) соответствуют два разных логических выражения, причем (1.1) записывается более компактно, но возможности минимизации для него еще есть. Следовательно, есть возможность минимизировать и логическую схему, представленную на рис. 1.6, a .

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

Минимизация с помощью карт Карно

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

Назначение карты Карно - найти логические суммы прямого и инверсного значения переменных. Для любой переменной, например, , такая сумма равна при любом значении : при это будет , при это . Поэтому при вынесении за скобки в выражении:

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

  1. Вертикальная ось размечается независимо от горизонтальной.
  2. Начинать разметку можно с любого сочетания переменных.
  3. Все сочетания переменных должны быть перечислены.
  4. Для соседних клеток карты сочетание переменных должно отличаться не более чем одним знаком, причем соседними являются крайние клетки строки (столбца).

Для функции двух переменных карта Карно - это квадрат 2x2 клетки. В этих клетках размещаются 4 значения функции из последнего столбца таблицы истинности (рис. 2.2).


Рис. 2.2.

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

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

Для функции пяти переменных карта Карно представляет собой уже объемную фигуру - куб 4x4x4 клетки, поэтому для минимизации логических выражений она не применяется.

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

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

Пример 1 рис. 2.5 ,а и нарисовать по нему логическую схему.

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

Первый контур охватывает четыре единицы, ему соответствует сумма минтермов : , в которой не изменяется только переменная . Второй контур охватывает две единицы. Ему соответствует сумма минтермов , в которой переменная принимает оба возможных значения, а произведение остается неизменным. Таким образом, получаем минимальное выражение:

(2.2)

Ему соответствует логическая схема на рис. 2.5 ,г.



Рис. 2.5.

Для сравнения запишем максимальное выражение:

(2.3)

Разница между (2.2) и (2.3) очевидна и в комментариях не нуждается, за исключением того, что схема, реализованная по (2.3), будет на порядок сложнее и, соответственно, менее надежна, чем схема, показанная на рис. 2.5 ,г.

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

Логика работы цифрового устройства описывается таблицей истинности, в которой показывается, какие логические уровни будут присутствовать на выходе цифровой схемы при заданных логических уровнях на входе этой схемы. Для того чтобы синтезировать схему с заданной логикой работы необходимо составить булево уравнение (в случаи если у схемы предполагается один выход) или систему уравнений (в случаи если выходов у схемы больше одного). Рассмотрим два способа составления уравнений из таблицы истинности: прямым и методом карт Карно.

Способ первый: составление уравнений из таблицы истинности прямым способом.

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

Выделим алгоритм составления уравнения по таблице истинности:

  • 1. Выделим те строки, в которых функция принимает истинное значение;
  • 2. Составим для этих строк минтермы операндов;
  • 3. Соединим минтермы при помощи операции дизъюнкции.

Рассмотрим пример.

Составим уравнение для устройства, имеющего один выход y, три входа x 0 , x 1 , x 2 . Логика работы устройства описана в таблицы 8.

Таблица 8 - Описание работы устройства

Составим функцию для строки три. В этой строке x 0 и x 2 принимают ложные значения, x 1 принимает истинное значение. Соединим эти операнды при помощи конъюнкции (элемент И):

Такая функции (принимающая истинное значения), в которую входит конъюнкция переменных или их отрицания называется минтермом.

Составим минтерм для строки пять:

Так как имеется два минтерма, соединим их при помощи дизъюнкции (элемент ИЛИ):

Что и будет уравнением устройства описанной таблицей истинности 8.

Выделим алгоритм составления системы уравнений по таблице истинности:

  • 1. Определим количество выходов, следовательно, и количество уравнений в системе;
  • 2. Для каждого из выходов составим уравнение:
  • 2.1 Выделяем те строки, в которых функция принимает истинное значение;
  • 2.2 Составлим для этих строк минтермы операндов;
  • 2.3 Если минтермов больше одного, то соединим минтермы при помощи операции дизъюнкции.
  • 3. Объединим полученные уравнения в систему.

Рассмотрим пример.

Пусть заданно устройство, логика работы которого описана в таблице 10. У устройства имеется два входа x 0 и x 1 , и два выхода y 1 , y 0 . Так как задано два выхода уравнения для каждого из выходов будут составляться отдельно. Составим систему уравнений, состоящую из двух уравнений.

Таблица 10 - Описание работы устройства

Выделим строки, в которых y 0 принимает истинные значения. y 0 принимает истинное значение только в одной строке, а именно в четвертой строке. Составим уравнение для y 0:

Выделим строки, в которых y 1 принимает истинные значения. Здесь имеется две строки: вторая и пятая. Для второй строки минтерм будет иметь вид. Для пятой. Объединим их с помощью операции ИЛИ, тем самым составив уравнение для y 1:

Остается составить систему уравнений, описывающую заданное устройство:

Способ второй: составление уравнений из таблицы истинности методом карт Карно.

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

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

Перед тем как привести примеры, отметим основные положения, которыми будем руководствоваться при объединении областей (групп):

  • 1. Область, которая подвергается объединению, должна состоять из логических единиц, при этом объединению подлежат только прямоугольные области, содержащие число логических единиц 2 n (т.е. 2 клетки, 4 клетки и т.д.).
  • 2. Клетки, находящиеся на границе карты, граничат между собой, и могут быть объединены.
  • 3. Все единицы должны быть объединены в какую-либо область, причем количество областей должно быть минимальным.
  • 4. Одна ячейка может быть включена в разные области.

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

Уравнение составляется следующим образом: в конъюнкцию области входит только те операнды, которые не меняют свои состояния на противоположные в пределах области. В случае если областей больше одного, между конъюнкциями областей ставятся дизъюнкции.

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

Пример 1. Составим уравнение содержащих два операнда (или их инверсию) по таблице истинности 11 посредствам карт Карно.

Таблица 11 - Карта Карно для двух операндов

Составим карту Карно, для этого преобразуем таблицу истинности к виду, показанному на рисунке 18.

Рис. 18.

Здесь, горизонтальная часть отводится операнду x 1 , которое принимает значение 0 и 1 (). Вертикальной части таблицы аналогично соответствует x 0 .

Выделим те строки таблицы истинности 11, где y принимает значение логической единицы: строки два и три. Заметим, что во второй строке x 0 и x 1 принимает значение 00 (), в третьей строке x 0 и x 1 принимает значение 10 ().

Проставим в карте Карно 18 на пересечениях x 0 x 1 единицы в тех местах, где и (рис. 19).

Рис. 19.

Выделим область согласно положениям объединения областей (Рис. 20).

Рис. 20.

Получена одна область, составим уравнение. Операнд меняет в области свое значение на инверсию. Неинвертированный операнд x 1 не входит в область. Единственный операнд, который не меняет своего значения в полученной области - . Тогда уравнение примет вид:

Заметим, что если составлять уравнение из таблицы 10 прямым способом, то получилось бы не минимизированное уравнение:

которое можно преобразовать к минимально возможной форме путем применения аксиом и свойств алгебры логики.

Пример 2. Составим уравнение содержащих три операнда (или их инверсию) по таблице истинности 12 посредствам карт Карно.

Таблица 12 - Карта Карно для трёх операндов

Составим карту Карно дл трех операндов (рис. 21).

Рис. 21.

Для трех операндов горизонтальная часть соответствует операндам x 1 x 2 , которые принимают значение 00, 01, 11, 10. Важно отметить, что порядок 00, 01, 11, 10 должен соблюдаться в точности, изменения его на другой порядок не допускается. Вертикальной части таблицы соответствует операнд x 0 , принимающей значение 1 и 0).

Заполним карту Карно. Аналогично предыдущему примеру: выделим строки в таблице истинности 12, где y принимает истинное значение (вторая, третья, четвертая, седьмая строки). Проставим единицы в те ячейки карты Карно, которые соответствуют значениям операндов в этих строках (рис. 22).

Рис. 22.

Выделим области согласно положениям объединения областей (Рис. 23).

Рис. 23.

Выделено две области. В первой области полностью находится операнды и, объединим их конъюнкцией. Во второй области не меняют своего значения операнды, объединим их в конъюнкцию. Так как есть две области, объединим конъюнкции областей операцией дизъюнкции, тем самым составив конечное уравнение:

Пример 4. Составим уравнение содержащих четыре операнда (или их инверсию) по таблице истинности 13 посредствам карт Карно.

Таблица 13 - Карта Карно для четырех операндов

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

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

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

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

Алгоритм минимизации по методу карт Карно:

1.Метод Карно основан на представлении исходной функции, заданной в форме СДНФ, в виде карты следующего вида:

2. Объединяем смежные клетки, содержащие единицы, в область так, чтобы одна область содержала 2 n (т.е. 2, 4, 8, и т.д.) клеток (помним про то, что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток, содержащих нули, области могут пересекаться, возможно несколько вариантов покрытия.

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

4. Конъюнкции областей объединяем дизъюнкцией.

Пример. Методом Карно минимизировать функцию:

$$y=f\left (A,B,C \right)=\bar{A}\bar{B}\bar{C}\vee \bar{A}B\bar{C}\vee A\bar{B}\bar{C}\vee A\bar{B}C$$

1.Заданную функцию представим с помощью карты Карно:

2. Затем производится объединение 2-х, 4-х или 8-ми единиц. В данном случае объединение двух единиц по горизонтали соответствует операции склеивания над конституентами $\bar{A}\bar{B}\bar{C}$ и $\bar{A} B \bar{C}$ , в результате которой исключается переменная B и получена импликанта $\bar{A} \bar{C}$ . Объединение двух единиц по вертикали соответствует операции склеивания над конституентами $A\bar{B}\bar{C}$ и $A\bar{B}C$ , в результате которой исключена переменная $С$ и будет получена импликанта $A\bar{B} $ .

Поскольку логическую функцию, даже такую простую, как Исключающее ИЛИ, можно реализовать различными способами, часто бывает нужно найти для нее самое простое решение, или, возможно, наиболее удобное схемное решение. Над этой проблемой бились многие светлые умы и в настоящее время существует несколько способов ее разрешения, включая алгебраические методы, реализуемые с помощью ЭВМ. При числе входов, не превышающем четырех, наилучшим методом является составление карты Карно. Этот метод позволяет также найти логическое выражение (если оно заранее неизвестно) по таблице истинности. Проиллюстрируем этот метод с помощью примера. Предположим, что требуется построить схему для мажоритарного подсчета голосов при баллотировке. Будем считать, что имеются три входа, работающие в положительной логике (на любом из них может быть 1 или 0) и выход (0 или 1). Выход равен 1, если 1 присутствует не менее чем на двух входах.

Шаг 1. Составим таблицу истинности

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

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

Шаг 2. Составим карту Карно. Она представляет собой нечто очень близкое к таблице истинности, но содержит переменные, которые расположены по двум осям. Переменные должны быть расположены таким образом, чтобы при переходе от каждого квадрата к соседнему менялось бы состояние только одного входа (рис. 8.27).

Шаг 3. Отметим на карте группы, содержащие 1 (можно также использовать и группы, содержащие 0). Три овала на рис. 8.27 определяют логические выражения АВ, АС и ВС.

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

Это выражение может оказаться полезным для случая, когда в каких-либо точках схемы имеются дополнения А, В и С.

Некоторые комментарии к картам Карно.

1. Ищите группы, содержащие 2, 4, 8 и т.д. квадратов. Они имеют простые логические выражения.

2. Логика будет тем проще, чем крупнее блок вы опишете.

3. Состыкуйте края карты Карно. Например, карта на рис. 8.29 описывается выражением С.

4. Блок «единиц», содержащий один или два «нуля», лучше всего описывается с помощью группировки, показанной на рис. 8.30. Этому блоку соответствует логическое выражение .

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