Карта Карно ( KM или K-карта ) - это метод упрощения выражений булевой алгебры . Морис Карно представил ее в 1953 году [1] [2] как уточнение диаграммы Эдварда В. Вейча 1952 года [3] [4], которая была повторным открытием логической диаграммы Аллана Маркванда 1881 года [5], также известной как диаграмма Маркванда. [4], но теперь основное внимание уделяется его полезности для коммутации схем. [4] Поэтому диаграммы Вейча также известны как диаграммы Маркуанда – Вейча ,[4] и отображения Карно как отображения Карно – Вейча ( карты KV ).
Карта Карно снижает потребность в обширных вычислениях за счет использования возможностей распознавания образов людьми. [1] Это также позволяет быстро идентифицировать и устранять потенциальные условия гонки .
Требуемые булевы результаты передаются из таблицы истинности на двумерной сетке , где в карты Карно, клетки упорядочены в коде Грея , [6] [4] , и каждая позиция ячейка представляет одну комбинацию входных условий. Ячейки также известны как minterms, в то время как каждое значение ячейки представляет соответствующее выходное значение логической функции. Идентифицируются оптимальные группы единиц или нулей, которые представляют термины канонической формы логики в исходной таблице истинности. [7] Эти термины можно использовать для написания минимального логического выражения, представляющего требуемую логику.
Карты Карно используются для упрощения требований реальной логики, чтобы их можно было реализовать с использованием минимального количества логических вентилей. Выражение сумм из побочных продуктов (СОП) всегда может быть реализован с использованием логических элементов И запитывания в ИЛИ ворота и экспрессии продукта из-сумм (POS) приводит к ИЛИ ворота , питающие И вентиль. Выражение POS дает дополнение к функции (если F - функция, то ее дополнением будет F '). [8] Карты Карно также могут использоваться для упрощения логических выражений при разработке программного обеспечения. Логические условия, используемые, например, в условных операторах , могут быть очень сложными, что затрудняет чтение и сопровождение кода. После минимизации канонические выражения суммы произведений и произведений сумм могут быть реализованы напрямую с помощью логических операторов И и ИЛИ. [9]
Пример
Карты Карно используются для упрощения функций булевой алгебры . Например, рассмотрим логическую функцию, описанную следующей таблицей истинности .
А | 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 и их обратных значений.
- где - это минтермы для сопоставления (т. е. строки, которые имеют выход 1 в таблице истинности).
- где - это maxterms для сопоставления (т. е. строки, которые имеют вывод 0 в таблице истинности).
Карта Карно
В приведенном выше примере четыре входные переменные могут быть объединены 16 различными способами, поэтому таблица истинности имеет 16 строк, а карта Карно - 16 позиций. Таким образом, карта Карно организована в виде сетки 4 × 4.
Индексы строк и столбцов (показанные сверху и снизу слева на карте Карно) упорядочены в коде Грея, а не в двоичном числовом порядке. Код Грея гарантирует, что между каждой парой соседних ячеек изменяется только одна переменная. Каждая ячейка завершенной карты Карно содержит двоичную цифру, представляющую выход функции для этой комбинации входов.
После того, как карта Карно построена, она используется для поиска одной из простейших возможных форм - канонической формы - для информации в таблице истинности. Смежные единицы на карте Карно представляют возможности для упрощения выражения. Минтермы («минимальные термины») для окончательного выражения находятся обведением групп единиц на карте. Группы Minterm должны быть прямоугольными и иметь площадь, равную степени двойки (т. Е. 1, 2, 4, 8 ...). Прямоугольники Minterm должны быть как можно больше и не содержать нулей. Группы могут перекрываться, чтобы увеличивать каждую. Оптимальные группы в приведенном ниже примере отмечены зеленой, красной и синей линиями, а красная и зеленая группы перекрываются. Красная группа представляет собой квадрат 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 меняется, поэтому он исключен.
Таким образом, первый minterm в логическом выражении сумм из-продуктов С .
Для зеленой группы A и B сохраняют то же состояние, в то время как C и D изменяются. B равен 0 и должен быть инвертирован, прежде чем его можно будет включить. Второе слагаемое поэтому Б . Обратите внимание, что допустимо, чтобы зеленая группа перекрывалась с красной.
Таким же образом, синяя группировка дает термин BC D .
Решения каждой группы объединены: нормальная форма схемы .
Таким образом, карта Карно позволила упростить
Можно было бы также получить это упрощение, тщательно применяя аксиомы булевой алгебры , но время, необходимое для этого, растет экспоненциально с увеличением числа членов.
Обратный
Обратное значение функции решается таким же образом путем группировки нулей.
Все три термина, описывающие обратное, показаны серыми прямоугольниками с разноцветными границами:
- коричневый : A B
- золото : A C
- синий : BCD
Это дает обратное:
Используя законы Де Моргана , можно определить произведение сумм :
Не волнует
Карты Карно также позволяют упростить минимизацию функций, таблицы истинности которых включают условия " безразличия ". Условие «безразлично» - это комбинация входных данных, для которых разработчику безразлично, каков будет результат. Следовательно, условия «безразлично» могут быть включены в любую прямоугольную группу или исключены из нее, в зависимости от того, что делает ее больше. Обычно они обозначаются на карте знаком тире или X.
Пример справа такой же, как и в примере выше, но с заменой значения f (1,1,1,1) на «безразлично». Это позволяет красному члену полностью расширяться вниз и, таким образом, полностью удаляет зеленый член.
Это дает новое уравнение минимума:
Обратите внимание , что первый член только , не C . В этом случае, команда безразлично потеряла термин (зеленый прямоугольник); упрощенный другой (красный); и удалил гоночную опасность (убрав желтый термин, как показано в следующем разделе, посвященном гоночным опасностям).
Обратный случай упрощается следующим образом:
Используя законы Де Моргана , можно определить произведение сумм :
Опасности гонки
Устранение
Карты Карно полезны для обнаружения и устранения условий гонки . Опасности расы очень легко обнаружить с помощью карты Карно, потому что состояние гонки может существовать при перемещении между любой парой соседних, но не пересекающихся регионов, обозначенных на карте. Однако, из-за природы кодирования Грея, у соседнего есть специальное определение, объясненное выше - мы фактически движемся по тору, а не по прямоугольнику, охватывая верх, низ и стороны.
- В приведенном выше примере потенциальное состояние гонки существует, когда C равно 1, а D равно 0, A равно 1, а B изменяется с 1 на 0 (переход из синего состояния в зеленое состояние). Для этого случая определено, что выходной сигнал остается неизменным на уровне 1, но поскольку этот переход не покрывается определенным членом в уравнении, существует вероятность сбоя (мгновенный переход выходного сигнала в 0).
- В том же примере есть второй потенциальный сбой, который труднее обнаружить: когда D равно 0, а A и B оба равны 1, при этом C изменяется с 1 на 0 (переход из синего состояния в красное состояние). В этом случае сбой происходит от верхнего края карты к низу.
Возникнут ли сбои на самом деле, зависит от физической природы реализации, а нужно ли нам об этом беспокоиться, зависит от приложения. В синхронизированной логике достаточно, чтобы логика установила желаемое значение вовремя, чтобы уложиться в крайний срок. В нашем примере мы не рассматриваем синхронизированную логику.
В нашем случае дополнительный срок устранит потенциальную опасность гонки, установив мост между зеленым и синим выходными состояниями или синим и красным выходными состояниями: это показано как желтая область (которая обтекает правую половину снизу вверх) на соседней диаграмме.
Этот термин является избыточным с точки зрения статической логики системы, но такие избыточные или согласованные термины часто необходимы для обеспечения динамических характеристик без гонок.
Точно так же дополнительный срок должен быть добавлен к обратному, чтобы исключить еще одну потенциальную гоночную опасность. Применение законов Де Моргана создает другой продукт выражения сумм для f , но с новым коэффициентом.
Примеры карт с двумя переменными
Ниже приведены все возможные карты Карно с 2-мя переменными и 2 × 2. Рядом с каждым из них перечислены минтермы в зависимости оти минимальное уравнение гонки без опасностей ( см. предыдущий раздел ). Минтерм определяется как выражение, которое дает наиболее минимальную форму выражения отображаемых переменных. Могут быть сформированы все возможные горизонтальные и вертикальные взаимосвязанные блоки. Эти блоки должны иметь размер степени 2 (1, 2, 4, 8, 16, 32, ...). Эти выражения создают минимальное логическое отображение выражений минимальных логических переменных для отображаемых двоичных выражений. Вот все блоки с одним полем.
Блок может быть продолжен в нижней, верхней, левой или правой частях диаграммы. Это может даже выйти за край диаграммы для минимизации переменных. Это потому, что каждая логическая переменная соответствует каждому вертикальному столбцу и горизонтальной строке. Визуализацию k-карты можно считать цилиндрической. Поля по краям слева и справа смежны, а сверху и снизу - рядом. K-карты для четырех переменных должны быть изображены в виде бублика или тора. Четыре угла квадрата, нарисованного k-картой, смежны. Еще более сложные карты необходимы для 5 и более переменных.
Σ m (0); К = 0
Σ м (1); К = А ' В '
Σ м (2); K = AB ′
Σ м (3); К = А ' В
Σ м (4); K = AB
Σ м (1,2); К = B ′
Σ м (1,3); К = А ′
Σ м (1,4); К = А ' В ' + АВ
Σ м (2,3); К = AB ′ + A ′ B
Σ м (2,4); К = А
Σ м (3,4); К = В
Σ м (1,2,3); К = А ' + В '
Σ м (1,2,4); К = А + В '
Σ м (1,3,4); К = А '+ В
Σ м (2,3,4); К = А + В
Σ м (1,2,3,4); К = 1
Связанные графические методы
К связанным графическим методам минимизации относятся:
- Диаграмма Маркуанда (1881) Аллана Маркуанда (1853–1924) [5] [4]
- График Вейча (1952 г.) Эдварда В. Вейча (1924–2013 гг.) [3] [4]
- Карта Махони ( M-карта , номера обозначений , 1963) Мэтью В. Махони (отражательно-симметричное расширение карт Карно для большего количества входных данных)
- Уменьшенная карта Карно (РАЯ) методы (с 1969 года)как нечастые переменные , карта введенной переменные (мы), переменная вводятся карта (ВАЯ) или переменная вводятся карта Карно (VEKM)помощью GW Schultz, Thomas E. Осборн , Christopher R . Клэр, Дж. Роберт Бургун, Ларри Л. Дорнхофф, Уильям И. Флетчер, Али М. Рушди и другие (несколько последовательных расширений карты Карно, основанных на переменных входных данных для большего количества входных данных)
- Карта Minterm-ring (MRM, 1990) Томаса Р. МакКаллы (трехмерное расширение карт Карно для большего количества входных данных)
Смотрите также
- Алгебраическая нормальная форма (АНФ)
- Диаграмма двоичных решений (BDD), структура данных, которая представляет собой сжатое представление логической функции
- Минимизатор эвристической логики эспрессо
- Список тем по булевой алгебре
- Оптимизация логики
- Квадрат Пеннета (1905), аналогичная диаграмма в биологии
- Алгоритм Куайна – Маккласки
- Разложение Рида – Мюллера
- Диаграмма Венна (1880 г.)
- Полином Жегалкина
Рекомендации
- ^ a b Карно, Морис (ноябрь 1953) [1953-04-23, 1953-03-17]. "Метод отображения для синтеза комбинационных логических схем" (PDF) . Труды Американского института инженеров-электриков, Часть I: Связь и электроника . 72 (5): 593–599. DOI : 10.1109 / TCE.1953.6371932 . Документ 53-217. Архивировано из оригинального (PDF) 16 апреля 2017 года . Проверено 16 апреля 2017 .(NB. Также содержит краткий обзор Сэмюэля Х. Колдуэлла .)
- ^ Кертис, Герберт Аллен (1962). Новый подход к проектированию коммутационных схем . Серия Bell Laboratories (1 - е изд.). Принстон, Нью-Джерси, США: D. van Nostrand Company, Inc. ISBN 0-44201794-4. OCLC 1036797958 . S2CID 57068910 . ISBN 978-0-44201794-1 . ковчег: / 13960 / t56d6st0q. (viii + 635 страниц) (NB. Эта книга была перепечатана Чин Джи в 1969 году.)
- ^ а б Вейтч, Эдвард Уэстбрук (1952-05-03) [1952-05-02]. «Диаграмма метода для упрощения функций истины». Труды Ежегодного собрания ACM 1952 года . Ежегодная конференция / ежегодное собрание ACM: Материалы ежегодного собрания ACM 1952 г. (Питтсбург, Пенсильвания, США). Нью-Йорк, США: Ассоциация вычислительной техники (ACM): 127–133. DOI : 10.1145 / 609784.609801 .
- ^ Б с д е е г Браун, Фрэнк Маркхэм (2012) [2003, 1990]. Boolean Reasoning - The Logic of Boolean Equations (переиздание 2-го изд.). Минеола, Нью-Йорк: ISBN Dover Publications, Inc. 978-0-486-42785-0. [1]
- ^ а б Маркуанд, Аллан (1881). «XXXIII: О логических диаграммах для n терминов» . Лондонский, Эдинбургский и Дублинский философский журнал и научный журнал . 5. 12 (75): 266–270. DOI : 10.1080 / 14786448108627104 . Проверено 15 мая 2017 .(NB. Довольно много вторичных источников ошибочно цитируют эту работу как «Логическая диаграмма для n терминов» или «На логической диаграмме для n терминов».)
- ^ Вакерли, Джон Ф. (1994). Цифровой дизайн: принципы и практика . Нью-Джерси, США: Прентис Холл . С. 48–49, 222. ISBN 0-13-211459-3.(NB. Два раздела страницы, взятые вместе, говорят, что K-карты помечены кодом Грея . В первом разделе говорится, что они помечены кодом, который изменяет только один бит между записями, а второй раздел говорит, что такой код называется Gray. код.)
- ^ Белтон, Дэвид (апрель 1998 г.). «Карты Карно - Правила упрощения» . Архивировано 18 апреля 2017 года . Проверено 30 мая 2009 .
- ^ Додж, Натан Б. (сентябрь 2015 г.). «Упрощение логических схем с помощью карт Карно» (PDF) . Техасский университет в Далласе , Школа инженерии и информатики Эрика Джонссона . Архивировано (PDF) из оригинала 18 апреля 2017 года . Проверено 18 апреля 2017 .
- ^ Повар, Аарон. «Использование карт Карно для упрощения кода» . Квантовая редкость. Архивировано 18 апреля 2017 года . Проверено 7 октября 2012 .
дальнейшее чтение
- Кац, Рэнди Ховард (1998) [1994]. Современный логический дизайн . Издательство Бенджамин / Каммингс . С. 70–85 . DOI : 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:
[…] уточнение диаграммы Венна, в котором круги заменены квадратами и расположены в форме матрицы. Диаграмма Вейча помечает квадраты с минтермами . Карно присвоил квадратам и их меткам единицы и нули и вывел широко используемую схему нумерации.
- Максфилд, Клайв «Макс» (29 ноября 2006 г.). «Логика Рида-Мюллера» . Логика 101 . EE Times . Часть 3. Архивировано 19.04.2017 . Проверено 19 апреля 2017 .
- Линд, Ларри Фредерик; Нельсон, Джон Кристофер Канлифф (1977). «Раздел 2.3». Анализ и проектирование последовательных цифровых систем . Macmillan Press . ISBN 0-33319266-4. (146 стр.)
- Держатель, Мишель Элизабет (март 2005 г.) [2005-02-14]. «Модифицированная техника карты Карно» . IEEE Transactions по образованию . IEEE . 48 (1): 206–207. DOI : 10.1109 / TE.2004.832879 . eISSN 1557-9638 . ISSN 0018-9359 . S2CID 25576523 . [2]
- Кавана, Джозеф (2008). Основы компьютерной арифметики и Verilog HDL (1-е изд.). CRC Press .
- Кохави, Цви; Джа, Нирадж К. (2009). Теория переключений и конечных автоматов (3-е изд.). Издательство Кембриджского университета . ISBN 978-0-521-85748-2.
Внешние ссылки
- Обнаружение перекрывающихся прямоугольников , Герберт Гларнер.
- Использование карт Карно в практических приложениях , проект схемотехники для управления светофорами.
- K-Map Tutorial для 2, 3, 4 и 5 переменных
- Пример карты Карно
- УПРОЩЕНИЕ БУЛЕВЫХ ФУНКЦИЙ POCKET – PC, Ledion Bitincka - George E. Antoniou
- Устранение неполадок K-Map