Карта Карно

Пример карты Карно. На этом изображении фактически показаны две карты Карно: для функции ƒ с использованием minterms (цветные прямоугольники) и для ее дополнения с использованием maxterms (серые прямоугольники). На изображении E () обозначает сумму минтермов, обозначенную в статье как $\sum m_{i}$.

Карта Карно ( KM или K-map ) — это метод упрощения выражений булевой алгебры . Морис Карно представил его в 1953 году. как уточнение Эдварда В. Вейча 1952 года диаграммы Вейча , который сам по себе был повторным открытием Аллана Маркванда 1881 года. логической диаграммы она же диаграмма Маркванда но теперь основное внимание уделяется его полезности для переключения цепей. Диаграммы Вейча также известны как диаграммы Маркванда-Вейча . Svoboda charts -(хотя и редко)- и даже карты Карно как карты Карно – Вейча ( карты КВ ).

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

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

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

Пример

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

Таблица истинности функции

	А	Б	С	Д	⁠ $f(A,B,C,D)$⁠
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

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

• $f(A,B,C,D)=\sum _{}m_{i},i\in \{6,8,9,10,11,12,13,14\}$ где $m_{i}$ — это минтермы для сопоставления (т. е. строки, имеющие выход 1 в таблице истинности).
• $f(A,B,C,D)=\prod _{}M_{i},i\in \{0,1,2,3,4,5,7,15\}$ где $M_{i}$ являются максимальными терминами для сопоставления (т. е. строками, имеющими выходной сигнал 0 в таблице истинности).

K-отображение, нарисованное на торе и плоскости. Ячейки, отмеченные точками, являются соседними.

Построение К-карты. Вместо выходных значений (крайние правые значения в таблице истинности) на этой диаграмме показано десятичное представление входных значений ABCD (крайние левые значения в таблице истинности), поэтому это не карта Карно.

В трёх измерениях прямоугольник можно согнуть в тор.

Строительство

В приведенном выше примере четыре входные переменные можно комбинировать 16 различными способами, поэтому таблица истинности имеет 16 строк, а карта Карно — 16 позиций. Таким образом, карта Карно имеет сетку 4 × 4.

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

Группировка

После построения карты Карно она используется для поиска одной из простейших возможных форм — канонической формы — для информации в таблице истинности. Соседние единицы на карте Карно представляют собой возможности упростить выражение. Минтермы («минимальные термины») для окончательного выражения находятся путем обведения групп единиц на карте. Группы минтермов должны быть прямоугольными и иметь площадь, равную степени двойки (т. е. 1, 2, 4, 8...). Прямоугольники Minterm должны быть как можно большего размера и не содержать нулей. Группы могут перекрываться, чтобы каждая из них была больше. Оптимальные группировки в примере ниже отмечены зеленой, красной и синей линиями, а красная и зеленая группы перекрываются. Красная группа представляет собой квадрат 2×2, зеленая группа — прямоугольник 4×1, а область перекрытия обозначена коричневым цветом.

Ячейки часто обозначаются сокращением, которое описывает логическое значение входных данных, которые охватывает ячейка. Например, AD будет означать ячейку, которая покрывает область 2x2, где A и D верны, то есть ячейки с номерами 13, 9, 15, 11 на диаграмме выше. С другой стороны, AD будет означать ячейки, в которых A истинно, а D ложно (т. е. D истинно).

Сетка имеет тороидальное соединение, что означает, что прямоугольные группы могут перетекать по краям (см. рисунок). Крайние правые ячейки на самом деле «смежны» с крайними левыми в том смысле, что соответствующие входные значения отличаются только на один бит; точно так же обстоят дела и с теми, кто находится на самом верху, и с теми, кто внизу. Следовательно, AD , может быть допустимым термином — он включает ячейки 12 и 8 вверху и переносится вниз, включая ячейки 10 и 14, — как и который BD включает четыре угла.

Решение

Диаграмма, показывающая две K-карты. K-карта для функции f(A, B, C, D) показана в виде цветных прямоугольников, соответствующих минтермам. Коричневая область представляет собой перекрытие красного квадрата 2×2 и зеленого прямоугольника 4×1. K-карта для обратной функции f показана серыми прямоугольниками, которые соответствуют maxterms.

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

Для красной группы:

• А одинаков и равен 1 во всей коробке, поэтому его следует включить в алгебраическое представление красного минтерма.
• B не поддерживает то же состояние (он меняется с 1 на 0), поэтому его следует исключить.
• С не меняется. Он всегда равен 0, поэтому необходимо включить его дополнение NOT-C. Таким образом, C должен быть включен.
• D меняется, поэтому исключается.

первый минтерм в булевом выражении суммы произведений — это AC Таким образом , .

Для зеленой группы A и B сохраняют одно и то же состояние, а C и D изменяются. B равен 0 и должен быть инвертирован, прежде чем его можно будет включить. Таким образом, второй член равен A B . Обратите внимание, что допустимо перекрытие зеленой группы красной.

же синяя группировка дает термин BC D. Точно так

Решения каждой группы объединяются: нормальная форма схемы имеет вид $A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}$.

Таким образом, карта Карно привела к упрощению

${\begin{aligned}f(A,B,C,D)={}&{\overline {A}}BC{\overline {D}}+A{\overline {B}}\,{\overline {C}}\,{\overline {D}}+A{\overline {B}}\,{\overline {C}}D+A{\overline {B}}C{\overline {D}}+{}\\&A{\overline {B}}CD+AB{\overline {C}}\,{\overline {D}}+AB{\overline {C}}D+ABC{\overline {D}}\\={}&A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}\end{aligned}}$

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

Обратный

Обратная функция решается таким же образом, вместо этого группируются 0.

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

• коричневый : А Б
• золото : А С
• синий : BCD

Это дает обратное:

${\overline {f(A,B,C,D)}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD$

Используя законы Де Моргана , произведение сумм можно определить :

${\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}}\right)\left({\overline {{\overline {A}}\,{\overline {C}}}}\right)\left({\overline {BCD}}\right)\\&=\left(A+B\right)\left(A+C\right)\left({\overline {B}}+{\overline {C}}+{\overline {D}}\right)\end{aligned}}$

Не волнует

Значение ⁠ $f(A,B,C,D)$⁠ для ABCD = 1111 заменяется на «все равно». Это полностью удаляет зеленый термин и позволяет красному члену стать больше. Это также позволяет синему обратному члену смещаться и становиться больше.

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

Пример справа аналогичен приведенному выше, но значение f (1,1,1,1) заменено на «все равно». Это позволяет красному члену полностью расшириться вниз и, таким образом, полностью удалить зеленый термин.

Это дает новое уравнение минимума:

$f(A,B,C,D)=A+BC{\overline {D}}$

Обратите внимание, что первый член — это просто A , а AC не . В данном случае слово «безразлично» отбросило термин (зеленый прямоугольник); упрощенный другой (красный); и устранили опасность гонки (удалив желтый термин, как показано в следующем разделе об опасностях гонки).

Обратный случай упрощается следующим образом:

${\overline {f(A,B,C,D)}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+{\overline {A}}D$

Используя законы Де Моргана , произведение сумм можно определить :

${\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+{\overline {A}}\,D}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}}\right)\left({\overline {{\overline {A}}\,{\overline {C}}}}\right)\left({\overline {{\overline {A}}\,D}}\right)\\&=\left(A+B\right)\left(A+C\right)\left(A+{\overline {D}}\right)\end{aligned}}$

Опасности гонки

Устранение

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

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

На этой диаграмме присутствуют расовые опасности.

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

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

В нашем случае дополнительный срок $A{\overline {D}}$ устранит потенциальную опасность гонки, создавая мост между зеленым и синим выходными состояниями или синим и красным выходными состояниями: это показано как желтая область (которая охватывает снизу вверх правую половину) на соседней диаграмме.

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

Аналогично, дополнительный срок ${\overline {A}}D$ необходимо добавить к обратному, чтобы исключить еще одну потенциальную опасность гонки. Применение законов Де Моргана создает другое произведение выражения сумм для f , но с новым коэффициентом $\left(A+{\overline {D}}\right)$.

Примеры карт с двумя переменными

Ниже приведены все возможные карты Карно размера 2 × 2 с двумя переменными. Рядом с каждым из них перечислены минтермы в зависимости от ${\textstyle \sum m()}$ и уравнение минимума без гонок ( см. предыдущий раздел ). Минтерм определяется как выражение, которое дает наиболее минимальную форму выражения отображаемых переменных. Могут быть сформированы все возможные горизонтальные и вертикальные взаимосвязанные блоки. Эти блоки должны иметь размер степени двойки (1, 2, 4, 8, 16, 32,...). Эти выражения создают минимальное логическое отображение выражений минимальных логических переменных для отображаемых двоичных выражений. Вот все блоки с одним полем.

Блок можно продолжить в нижней, верхней, левой или правой части диаграммы. Это может даже выходить за край диаграммы для минимизации переменных. Это связано с тем, что каждая логическая переменная соответствует каждому вертикальному столбцу и горизонтальной строке. Визуализацию k-карты можно считать цилиндрической. Поля по краям слева и справа смежны, а сверху и снизу смежны. K-карты для четырех переменных должны быть изображены в форме пончика или тора. Четыре угла квадрата, нарисованного k-картой, являются смежными. Еще более сложные карты необходимы для 5 переменных и более.

• 
  Σ м (0); К = 0
• 
  Σ м (1); К знак равно А ′ Б ′
• 
  Σ м (2); К = АВ ′
• 
  Σ м (3); К = А ′ Б
• 
  Σ м (4); К = АБ
• 
  Σ м (1,2); К = Б ′
• 
  Σ м (1,3); К = А ′
• 
  Σ м (1,4); К = А ′ В ′ + АВ
• 
  Σ м (2,3); К = АВ ′ + А ′ В
• 
  Σ м (2,4); К = А
• 
  Σ м (3,4); К = Б
• 
  Σ м (1,2,3); К = А' + В '
• 
  Σ м (1,2,4); К = А + В ′
• 
  Σ м (1,3,4); К = А ′ + В
• 
  Σ м (2,3,4); К = А + Б
• 
  Σ м (1,2,3,4); К = 1

Связанные графические методы

Дополнительная информация: Логическая оптимизация § Графические методы.

Связанные методы графической минимизации включают:

• Диаграмма Маркванда (1881 г.), автор Аллан Маркванд (1853–1924 гг.)
• Диаграмма Вейча (1952) Эдварда В. Вейча (1924–2013)
• Хартия свободы (1956 г.) Антонина Свободы (1907–1980)
• Карта Махони ( M-map , номера обозначений , 1963) Мэтью В. Махони (отражательно-симметричное расширение карт Карно для большего количества входных данных)
• Методы сокращенной карты Карно (RKM) (с 1969 г.), такие как нечастые переменные , переменные, вводимые с помощью карты (MEV), карта с вводом переменных (VEM) или карта Карно с вводом переменных (VEKM), авторы Г. В. Шульц, Томас Э. Осборн , Кристофер Р. Клэр, Дж. Роберт Бургун, Ларри Л. Дорнхофф, Уильям И. Флетчер, Али М. Рушди и другие (несколько последовательных расширений карты Карно, основанных на переменных входных данных для большего количества входных данных).
• Карта кольца Минтерма (MRM, 1990) Томаса Р. МакКаллы (трехмерное расширение карт Карно для большего количества входных данных)

См. также

• Алгебраическая нормальная форма (АНФ)
• Диаграмма двоичных решений (BDD), структура данных, которая представляет собой сжатое представление логической функции.
• Минимизатор эвристической логики эспрессо
• Список тем по булевой алгебре
• Оптимизация логики
• Квадрат Пеннета (1905 г.), аналогичная диаграмма в биологии.
• Алгоритм Куайна – Маккласки
• Расширение Рида – Мюллера
• Диаграмма Венна (1880 г.)
• Полином Жегалкина

Дальнейшее чтение

• Кац, Рэнди Ховард (1998) [1994]. Современный логический дизайн . Издательская компания Бенджамина/Каммингса . стр. 70–85 . дои : 10.1016/0026-2692(95)90052-7 . ISBN  0-8053-2703-7 .
• Вингрон, Шимон Питер (2004) [2003-11-05]. «Карты Карно». Теория переключения: понимание через логику предикатов . Берлин, Гейдельберг, Нью-Йорк: Springer-Verlag . стр. 57–76. ISBN  3-540-40343-4 .
• Уикс, Уильям Э. (1968). «3.5. Диаграммы Вейча». Логическое проектирование с помощью интегральных схем . Нью-Йорк, США: John Wiley & Sons . стр. 36–49 . LCCN   68-21185 . п. 36: […] уточнение диаграммы Венна , заключающееся в том, что круги заменены квадратами и расположены в виде матрицы. На диаграмме Вейча квадраты помечены минтермами . Карно присвоил квадратам и их меткам 1 и 0 и вывел общепринятую схему нумерации.
• Максфилд, Клайв «Макс» (29 ноября 2006 г.). «Логика Рида-Мюллера» . Логика 101 . ЭЭ Таймс . Часть 3. Архивировано из оригинала 19 апреля 2017 г. Проверено 19 апреля 2017 г.
• Линд, Ларри Фредерик; Нельсон, Джон Кристофер Канлифф (1977). «Раздел 2.3». Анализ и проектирование последовательных цифровых систем . Макмиллан Пресс . ISBN  0-33319266-4 . (146 страниц)
• Холдер, Мишель Элизабет (март 2005 г.) [14 февраля 2005 г.]. «Модифицированная техника карты Карно» . Транзакции IEEE по образованию . 48 (1). IEEE : 206–207. дои : 10.1109/TE.2004.832879 . eISSN   1557-9638 . ISSN   0018-9359 . S2CID   25576523 . [2]
• Кавана, Джозеф (2008). Основы компьютерной арифметики и Verilog HDL (1-е изд.). ЦРК Пресс .
• Кохави, Цви; Джа, Нирадж К. (2009). Теория коммутации и конечных автоматов (3-е изд.). Издательство Кембриджского университета . ISBN  978-0-521-85748-2 .
• Грунд, Юрген (2011). алгебраические преобразования, иллюстративные модели, типичные примеры ] KV-диаграммы в булевой алгебре - отношения, доказательства, нормальные формы, браузер с поддержкой Adobe (исполняемый файл для Windows/Mac или Flash на компакт-диске) (электронная книга) (на немецком языке) (1-е изд.) .). Берлин, Германия: viademica Verlag. ISBN  978-3-939290-08-7 . Архивировано (PDF) из оригинала 12 ноября 2022 г. Проверено 26 ноября 2022 г. [3] (282 страницы с 14 анимациями)

Внешние ссылки

• Обнаружение перекрывающихся прямоугольников , Герберт Гларнер.
• Использование карт Карно в практическом применении . Проект схемы управления светофором.
• Учебное пособие по K-Map для 2,3,4 и 5 переменных
• УПРОЩЕНИЕ БУЛЕВЫХ ФУНКЦИЙ POCKET–PC, Ледион Битинка — Джордж Э. Антониу
• Устранение неполадок с K-картой
• «Путеводитель по K-карте (Карта Карно» (PDF) . Калифорнийский государственный университет в Сан-Маркосе . Проверено 18 декабря 2023 г. .