Карта Карно

Карта Карно ( КМ или К-карта ) — это диаграмма, которая может быть использована для упрощения выражения булевой алгебры . Морис Карно представил ее в 1953 году ^[1]^[2] как усовершенствование диаграммы Вейча Эдварда У. Вейча 1952 года ^[3] [ ^4], которая сама по себе была переоткрытием логической диаграммы Аллана Маркванда 1881 года ^[5]^[6] (также известной как диаграмма Маркванда ^[4] ). Она также полезна для понимания логических схем. ^[4] Карты Карно также известны как диаграммы Маркванда–Вейча , ^[4]диаграммы Свободы ^[7] - (хотя и редко) - и карты Карно–Вейча ( карты KV ).

Определение

Карта Карно уменьшает необходимость в обширных вычислениях, используя способность человека распознавать образы. ^[1] Она также позволяет быстро идентифицировать и устранять потенциальные состояния гонки . ^{[ необходимо разъяснение ]}

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

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

Пример

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

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

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

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

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

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

Группировка

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

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

Сетка тороидально связана, что означает, что прямоугольные группы могут обертываться по краям (см. рисунок). Ячейки на самом правом краю фактически «смежные» с ячейками на самом левом краю, в том смысле, что соответствующие входные значения отличаются только на один бит; аналогично, те, что на самом верху, и те, что внизу. Поэтому $A D$ может быть допустимым термином — он включает ячейки 12 и 8 наверху и обертывается вниз, чтобы включить ячейки 10 и 14 — как и $B D$ , который включает четыре угла.

Решение

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

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

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

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

Для зеленой группы 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}}

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

Обратный

Обратная функция решается таким же образом, группируя нули. ^{[примечание 1]}

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

коричневый : $А$ $Б$
золото : $А$ $С$
синий : $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}}

Не волнует

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

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

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

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

Обратите внимание, что первый термин — это просто $A$ , а не $A C.$ В этом случае don't care удалил термин (зеленый прямоугольник), упростил другой (красный) и удалил опасность гонки (удалив желтый термин, как показано в следующем разделе об опасностях гонки).

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

{\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}}$

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

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

Примеры карт с 2 переменными

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

Блок может быть продолжен по нижней, верхней, левой или правой части диаграммы. Он может даже выходить за пределы края диаграммы для минимизации переменных. Это связано с тем, что каждая логическая переменная соответствует каждому вертикальному столбцу и горизонтальной строке. Визуализацию 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); К = А' + В ′
Σ m (1,2,4); К = А + В ′
Σ м (1,3,4); К = А ′ + В
Σ м (2,3,4); К = А + В
Σ м (1,2,3,4); К = 1

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

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

Диаграмма Маркванда (1881 г.) Аллана Маркванда (1853–1924) ^[5]^[6]^[4]
Диаграмма Вейча (1952) Эдварда В. Вейча (1924–2013) ^[3]^[4]
Карта свободы (1956) Антонина Свободы (1907–1980) ^[7]
Карта Махони ( M-карта , обозначения чисел , 1963) Мэтью В. Махони (зеркально-симметричное расширение карт Карно для большего числа входов)
Методы редуцированной карты Карно (RKM) (с 1969 года), такие как нечастые переменные , переменные, введенные на карту (MEV), переменная-введенная карта (VEM) или переменная-введенная карта Карно (VEKM) от GW Schultz, Thomas E. Osborne, Christopher R. Clare, J. Robert Burgoon, Larry L. Dornhoff, William I. Fletcher, Ali M. Rushdi и других (несколько последовательных расширений карты Карно, основанных на переменных входных данных для большего числа входных данных)
Карта Минтерм-кольца (MRM, 1990) Томаса Р. МакКаллы (трехмерное расширение карт Карно для большего числа входов)

Смотрите также

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

Примечания

^ Это не следует путать с отрицанием результата ранее найденной функции.

Ссылки

^ ab Karnaugh, Maurice (ноябрь 1953 г.) [1953-04-23, 1953-03-17]. "Метод карты для синтеза комбинационных логических схем" (PDF) . Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics . 72 (5): 593–599. doi :10.1109/TCE.1953.6371932. Paper 53-217. Архивировано из оригинала (PDF) 2017-04-16 . Получено 2017-04-16 .(Примечание. Также содержит краткий обзор Сэмюэля Х. Колдуэлла .)
^ Кертис, Герберт Аллен (1962). Новый подход к проектированию коммутационных схем . Серия Bell Laboratories (1-е изд.). Принстон, Нью-Джерси, США: D. van Nostrand Company, Inc. ISBN 0-44201794-4. OCLC 1036797958. S2CID 57068910. ISBN 978-0-44201794-1 . ark:/13960/t56d6st0q. (viii+635 страниц) (Примечание. Эта книга была переиздана Чин Джи в 1969 году.)
^ ab Veitch, Edward Westbrook (1952-05-03) [1952-05-02]. "Метод диаграмм для упрощения функций истинности". Труды национального собрания ACM 1952 года (Питтсбург) на - ACM '52 . Нью-Йорк, США: Ассоциация вычислительной техники . стр. 127–133. doi :10.1145/609784.609801. S2CID 17284651.
^ abcdefg Браун, Фрэнк Маркхэм (2012) [2003, 1990]. Булевое рассуждение - Логика булевых уравнений (переиздание 2-го изд.). Минеола, Нью-Йорк: Dover Publications, Inc. ISBN 978-0-486-42785-0.[1]
^ ab Marquand, Allan (1881). "XXXIII: On Logical Diagrams for n terms". The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science . 5. 12 (75): 266–270. doi :10.1080/14786448108627104 . Получено 15 мая 2017 г.(Примечание. Довольно много вторичных источников ошибочно цитируют эту работу как «Логическая схема для n терминов» или «О логической схеме для n терминов».)
^ ab Gardner, Martin (1958). "6. Marquand's Machine and Others". Логические машины и диаграммы (1-е изд.). Нью-Йорк, США: McGraw-Hill Book Company, Inc. стр. 104–116. ISBN 1-11784984-8. LCCN 58-6683. ковчег:/13960/t5cc1sj6b.(x+157 страниц)
^ ab Klir, George Jiří (май 1972). "Справочные обозначения к главе 2". Введение в методологию коммутационных схем (1-е изд.). Бингемтон, Нью-Йорк, США: Litton Educational Publishing, Inc. / D. van Nostrand Company . стр. 84. ISBN 0-442-24463-0. LCCN 72-181095. C4463-000-3.(xvi+573+1 страницы)
^ Уэйкерли, Джон Ф. (1994). Цифровой дизайн: принципы и практики . Нью-Джерси, США: Prentice Hall . стр. 48–49, 222. ISBN 0-13-211459-3.(Примечание. В двух разделах страницы, взятых вместе, говорится, что карты К помечены кодом Грея . В первом разделе говорится, что они помечены кодом, который изменяет только один бит между записями, а во втором разделе говорится, что такой код называется кодом Грея.)
^ Белтон, Дэвид (апрель 1998 г.). «Карты Карно – правила упрощения». Архивировано из оригинала 2017-04-18 . Получено 2009-05-30 .
^ Додж, Натан Б. (сентябрь 2015 г.). «Упрощение логических схем с помощью карт Карно» (PDF) . Техасский университет в Далласе , Школа инженерии и компьютерных наук Эрика Йонссона . Архивировано (PDF) из оригинала 2017-04-18 . Получено 2017-04-18 .
^ Кук, Аарон. «Использование карт Карно для упрощения кода». Квантовая редкость. Архивировано из оригинала 2017-04-18 . Получено 2012-10-07 .

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

Katz, Randy Howard (1998) [1994]. Contemporary Logic Design. Том 26. Издательская компания Benjamin/Cummings . С. 70–85. ISBN 0-8053-2703-7.
Vingron, Shimon Peter (2004) [2003-11-05]. "Карты Карно". Теория переключения: понимание через логику предикатов . Берлин, Гейдельберг, Нью-Йорк: Springer-Verlag . стр. 57–76. ISBN 3-540-40343-4.
Wickes, William E. (1968). "3.5. Диаграммы Вейча". Logic Design with Integrated Circuits . New York, USA: John Wiley & Sons . pp. 36–49. LCCN 68-21185. p. 36: […] уточнение диаграммы Венна , в котором круги заменены квадратами и организованы в виде матрицы. Диаграмма Вейча помечает квадраты минтермами . Карно присвоил квадратам и их меткам 1 и 0 и вывел общепринятую схему нумерации.
Максфилд, Клайв «Макс» (29.11.2006). «Логика Рида-Мюллера». Логика 101. EE Times . Часть 3. Архивировано из оригинала 19.04.2017 . Получено 19.04.2017 .
Линд, Ларри Фредерик; Нельсон, Джон Кристофер Канлифф (1977). "Раздел 2.3". Анализ и проектирование последовательных цифровых систем. Macmillan Press . ISBN 0-33319266-4.(146 страниц)
Холдер, Мишель Элизабет (март 2005 г.) [2005-02-14]. "Модифицированный метод карт Карно". IEEE Transactions on Education . 48 (1). IEEE : 206–207. Bibcode :2005ITEdu..48..206H. doi :10.1109/TE.2004.832879. eISSN 1557-9638. ISSN 0018-9359. S2CID 25576523.
Каванаг, Джозеф (2008). Компьютерная арифметика и основы Verilog HDL (1-е изд.). CRC Press .
Кохави, Цви; Джа, Нирадж К. (2009). Теория коммутации и конечных автоматов (3-е изд.). Издательство Кембриджского университета . ISBN 978-0-521-85748-2.
Грунд, Юрген (2011). KV-диаграмма в булевой алгебре - Verknüpfungen, Beweise, Normalformen, schaltalgebraische Umformungen, Anschauungsmodelle, Paradebeispiele [ KV-диаграммы в булевой алгебре - отношения, доказательства, нормальные формы, алгебраические преобразования, иллюстративные модели, типичные примеры ] (исполняемый файл для Windows/Mac или Adobe Flash) -работающий браузер включен CD-ROM) (электронная книга) (на немецком языке) (1-е изд.). Берлин, Германия: viademica Verlag. ISBN 978-3-939290-08-7. Архивировано (PDF) из оригинала 2022-11-12 . Получено 2022-11-26 .[2] (282 страницы с 14 анимациями)

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

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