Карта Карно
Вы можете помочь дополнить эту статью текстом, переведенным из соответствующей статьи на немецком языке . (Февраль 2018 г.) Нажмите [показать], чтобы просмотреть важные инструкции по переводу. |
Карта Карно ( KM или K-map ) — это метод упрощения выражений булевой алгебры . Морис Карно представил его в 1953 году. [1] [2] как уточнение Эдварда В. Вейча 1952 года диаграммы Вейча , [3] [4] который сам по себе был повторным открытием Аллана Маркванда 1881 года. логической диаграммы [5] [6] она же диаграмма Маркванда [4] но теперь основное внимание уделяется его полезности для переключения цепей. [4] Диаграммы Вейча также известны как диаграммы Маркванда-Вейча . [4] Svoboda charts [7] -(хотя и редко)- и даже карты Карно как карты Карно – Вейча ( карты КВ ).
Карта Карно уменьшает потребность в обширных вычислениях, используя возможности человека по распознаванию образов. [1] Это также позволяет быстро выявлять и устранять потенциальные состояния гонки . [ нужны разъяснения ]
Требуемые логические результаты переносятся из таблицы истинности в двумерную сетку, где в картах Карно ячейки упорядочены по коду Грея , [8] [4] и каждая позиция ячейки представляет одну комбинацию входных условий. Ячейки также называются минтермами, при этом каждое значение ячейки представляет соответствующее выходное значение логической функции. Идентифицируются оптимальные группы единиц или нулей, которые представляют собой члены канонической формы логики в исходной таблице истинности. [9] Эти термины можно использовать для написания минимального логического выражения, представляющего требуемую логику.
Карты Карно используются для упрощения реальных логических требований, чтобы их можно было реализовать с использованием минимального количества логических элементов . Выражение суммы произведений (SOP) всегда может быть реализовано с использованием вентилей И, подающих в вентиль ИЛИ , а выражение произведения сумм (POS) приводит к тому, что вентили ИЛИ подают вентиль И. Выражение POS дает дополнение функции (если F является функцией, то ее дополнением будет F'). [10] Карты Карно также можно использовать для упрощения логических выражений при разработке программного обеспечения. Логические условия, используемые, например, в условных операторах , могут быть очень сложными, что затрудняет чтение и поддержку кода. После минимизации канонические выражения суммы произведений и произведения сумм могут быть реализованы непосредственно с использованием логических операторов И и ИЛИ. [11]
Пример
[ редактировать ]Карты Карно используются для упрощения функций булевой алгебры . Например, рассмотрим логическую функцию, описываемую следующей таблицей истинности .
А | Б | С | Д | | |
---|---|---|---|---|---|
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 в таблице истинности).
- где являются максимальными терминами для сопоставления (т. е. строками, имеющими выходной сигнал 0 в таблице истинности).
Строительство
[ редактировать ]В приведенном выше примере четыре входные переменные можно комбинировать 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 включает четыре угла.
Решение
[ редактировать ]После того как карта Карно построена и соседние единицы связаны прямоугольными и квадратными прямоугольниками, можно найти алгебраические минтермы, проверив, какие переменные остаются неизменными в каждом блоке.
Для красной группы:
- А одинаков и равен 1 во всей коробке, поэтому его следует включить в алгебраическое представление красного минтерма.
- B не поддерживает то же состояние (он меняется с 1 на 0), поэтому его следует исключить.
- С не меняется. Он всегда равен 0, поэтому необходимо включить его дополнение NOT-C. Таким образом, C должен быть включен.
- D меняется, поэтому исключается.
первый минтерм в булевом выражении суммы произведений — это AC Таким образом , .
Для зеленой группы A и B сохраняют одно и то же состояние, а C и D изменяются. B равен 0 и должен быть инвертирован, прежде чем его можно будет включить. Таким образом, второй член равен A B . Обратите внимание, что допустимо перекрытие зеленой группы красной.
же синяя группировка дает термин BC D. Точно так
Решения каждой группы объединяются: нормальная форма схемы имеет вид .
Таким образом, карта Карно привела к упрощению
Это упрощение также можно было бы получить, тщательно применив аксиомы булевой алгебры , но время, необходимое для этого, растет экспоненциально с увеличением количества членов.
Обратный
[ редактировать ]Обратная функция решается таким же образом, вместо этого группируются 0. [номер 1]
Все три члена, покрывающие обратное, показаны серыми прямоугольниками с разноцветными рамками:
- коричневый : А Б
- золото : А С
- синий : BCD
Это дает обратное:
Используя законы Де Моргана , произведение сумм можно определить :
Не волнует
[ редактировать ]Карты Карно также позволяют упростить минимизацию функций, таблицы истинности которых включают условия « безразличия ». Условие «безразлично» — это комбинация входных данных, для которой разработчика не волнует, каков будет результат. Таким образом, условия «неважно» можно либо включить в любую прямоугольную группу, либо исключить из нее, в зависимости от того, что делает ее больше. На карте они обычно обозначаются тире или Х.
Пример справа аналогичен приведенному выше, но значение f (1,1,1,1) заменено на «все равно». Это позволяет красному члену полностью расшириться вниз и, таким образом, полностью удалить зеленый термин.
Это дает новое уравнение минимума:
Обратите внимание, что первый член — это просто A , а AC не . В данном случае слово «безразлично» отбросило термин (зеленый прямоугольник); упрощенный другой (красный); и устранили опасность гонки (удалив желтый термин, как показано в следующем разделе об опасностях гонки).
Обратный случай упрощается следующим образом:
Используя законы Де Моргана , произведение сумм можно определить :
Опасности гонки
[ редактировать ]Устранение
[ редактировать ]Карты Карно полезны для обнаружения и устранения состояний гонки . Опасности расы очень легко обнаружить с помощью карты Карно, поскольку состояние гонки может существовать при движении между любой парой соседних, но непересекающихся регионов, описанных на карте. Однако из-за природы кодирования Грея смежность имеет специальное определение, объясненное выше — на самом деле мы движемся по тору, а не по прямоугольнику, охватывая верх, низ и стороны.
- примере В приведенном выше потенциальное состояние гонки существует, когда C равен 1, D равен 0, A равен 1, а B изменяется с 1 на 0 (переход из синего состояния в зеленое). В этом случае выходной сигнал определяется как остающийся неизменным и равным 1, но поскольку этот переход не описывается конкретным термином в уравнении, существует вероятность сбоя ( мгновенного перехода выходного сигнала в 0).
- В том же примере есть второй потенциальный сбой, который труднее обнаружить: когда D равен 0, а A и B оба равны 1, при этом C меняется с 1 на 0 (переходя из синего состояния в красное). В этом случае глюк охватывает верхнюю часть карты вниз.
Возникнут ли на самом деле сбои, зависит от физической природы реализации, а нужно ли нам об этом беспокоиться, зависит от приложения. В тактовой логике достаточно, чтобы логика вовремя установила желаемое значение, чтобы уложиться в срок. В нашем примере мы не рассматриваем тактовую логику.
В нашем случае дополнительный срок устранит потенциальную опасность гонки, создавая мост между зеленым и синим выходными состояниями или синим и красным выходными состояниями: это показано как желтая область (которая охватывает снизу вверх правую половину) на соседней диаграмме.
Этот термин является избыточным с точки зрения статической логики системы, но такие избыточные или согласованные термины часто необходимы для обеспечения динамической производительности без гонок.
Аналогично, дополнительный срок необходимо добавить к обратному, чтобы исключить еще одну потенциальную опасность гонки. Применение законов Де Моргана создает другое произведение выражения сумм для f , но с новым коэффициентом .
Примеры карт с двумя переменными
[ редактировать ]Ниже приведены все возможные карты Карно размера 2 × 2 с двумя переменными. Рядом с каждым из них перечислены минтермы в зависимости от и уравнение минимума без гонок ( см. предыдущий раздел ). Минтерм определяется как выражение, которое дает наиболее минимальную форму выражения отображаемых переменных. Могут быть сформированы все возможные горизонтальные и вертикальные взаимосвязанные блоки. Эти блоки должны иметь размер степени двойки (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 гг.) [5] [6] [4]
- Диаграмма Вейча (1952) Эдварда В. Вейча (1924–2013) [3] [4]
- Хартия свободы (1956 г.) Антонина Свободы (1907–1980) [7]
- Карта Махони ( M-map , номера обозначений , 1963) Мэтью В. Махони (отражательно-симметричное расширение карт Карно для большего количества входных данных)
- Методы сокращенной карты Карно (RKM) (с 1969 г.), такие как нечастые переменные , переменные, вводимые с помощью карты (MEV), карта с вводом переменных (VEM) или карта Карно с вводом переменных (VEKM), авторы Г. В. Шульц, Томас Э. Осборн , Кристофер Р. Клэр, Дж. Роберт Бургун, Ларри Л. Дорнхофф, Уильям И. Флетчер, Али М. Рушди и другие (несколько последовательных расширений карты Карно, основанных на переменных входных данных для большего количества входных данных).
- Карта кольца Минтерма (MRM, 1990) Томаса Р. МакКаллы (трехмерное расширение карт Карно для большего количества входных данных)
См. также
[ редактировать ]- Алгебраическая нормальная форма (АНФ)
- Диаграмма двоичных решений (BDD), структура данных, которая представляет собой сжатое представление логической функции.
- Минимизатор эвристической логики эспрессо
- Список тем по булевой алгебре
- Оптимизация логики
- Квадрат Пеннета (1905 г.), аналогичная диаграмма в биологии.
- Алгоритм Куайна – Маккласки
- Расширение Рида – Мюллера
- Диаграмма Венна (1880 г.)
- Полином Жегалкина
Примечания
[ редактировать ]- ^ Это не следует путать с отрицанием результата ранее найденной функции.
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б Карно, Морис (ноябрь 1953 г.) [23 апреля 1953 г., 17 марта 1953 г.]. «Метод карт для синтеза комбинационных логических схем» (PDF) . Труды Американского института инженеров-электриков, Часть I: Связь и электроника . 72 (5): 593–599. дои : 10.1109/TCE.1953.6371932 . Документ 53-217. Архивировано из оригинала (PDF) 16 апреля 2017 г. Проверено 16 апреля 2017 г. (Примечание. Также содержится краткий обзор Сэмюэля Х. Колдуэлла .)
- ^ Кертис, Герберт Аллен (1962). Новый подход к проектированию коммутационных схем . Серия Bell Laboratories (1-е изд.). Принстон, Нью-Джерси, США: компании Д. ван Ностранда, Inc. ISBN 0-44201794-4 . OCLC 1036797958 . S2CID 57068910 . ISBN 978-0-44201794-1 . ковчег:/13960/t56d6st0q. (viii+635 страниц) (Примечание. Эта книга была переиздана Чин Джи в 1969 году.)
- ↑ Перейти обратно: Перейти обратно: а б Вейч, Эдвард Уэстбрук (3 мая 1952 г.) [02 мая 1952 г.]. «Диаграммный метод для упрощения функций истинности». Протоколы ежегодного собрания ACM 1952 года . Ежегодная конференция/Ежегодное собрание ACM: материалы ежегодного собрания ACM 1952 года (Питтсбург, Пенсильвания, США). Нью-Йорк, США: Ассоциация вычислительной техники (ACM): 127–133. дои : 10.1145/609784.609801 .
- ↑ Перейти обратно: Перейти обратно: а б с д и ж г Браун, Фрэнк Маркхэм (2012) [2003, 1990]. Булево рассуждение - Логика булевых уравнений (переиздание 2-го изд.). Минеола, Нью-Йорк: Dover Publications, Inc. ISBN 978-0-486-42785-0 . [1]
- ↑ Перейти обратно: Перейти обратно: а б Маркванд, Аллан (1881). «XXXIII: О логических диаграммах для n термов» . Лондонский, Эдинбургский и Дублинский философский журнал и научный журнал . 5. 12 (75): 266–270. дои : 10.1080/14786448108627104 . Проверено 15 мая 2017 г. (Обратите внимание: довольно многие вторичные источники ошибочно цитируют эту работу как «Логическую диаграмму для n терминов» или «О логической диаграмме для n терминов».)
- ↑ Перейти обратно: Перейти обратно: а б Гарднер, Мартин (1958). «6. Машина Маркванда и другие». Логические машины и диаграммы (1-е изд.). Нью-Йорк, США: McGraw-Hill Book Company, Inc., стр. 104–116. ISBN 1-11784984-8 . LCCN 58-6683 . ковчег:/13960/t5cc1sj6b. (x+157 страниц)
- ↑ Перейти обратно: Перейти обратно: а б Клир, Георгий Иржи (май 1972 г.). «Справочные обозначения к главе 2». Введение в методологию коммутационных цепей (1-е изд.). Бингемтон, Нью-Йорк, США: Litton Educational Publishing, Inc. / Компания Д. ван Ностранд . п. 84. ИСБН 0-442-24463-0 . LCCN 72-181095 . C4463-000-3. (xvi+573+1 стр.)
- ^ Уэйкерли, Джон Ф. (1994). Цифровой дизайн: принципы и практика . Нью-Джерси, США: Прентис Холл . стр. 48–49, 222. ISBN. 0-13-211459-3 . (Примечание. В двух разделах страницы, взятых вместе, говорится, что K-карты помечены кодом Грея . В первом разделе говорится, что они помечены кодом, который меняет только один бит между записями, а во втором разделе говорится, что такой код называется Греем. код.)
- ^ Белтон, Дэвид (апрель 1998 г.). «Карты Карно – правила упрощения» . Архивировано из оригинала 18 апреля 2017 г. Проверено 30 мая 2009 г.
- ^ Додж, Натан Б. (сентябрь 2015 г.). «Упрощение логических схем с помощью карт Карно» (PDF) . Техасский университет в Далласе , Школа инженерии и информатики Эрика Джонссона . Архивировано (PDF) из оригинала 18 апреля 2017 г. Проверено 18 апреля 2017 г.
- ^ Кук, Аарон. «Использование карт Карно для упрощения кода» . Квантовая редкость. Архивировано из оригинала 18 апреля 2017 г. Проверено 7 октября 2012 г.
Дальнейшее чтение
[ редактировать ]- Кац, Рэнди Ховард (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 г. .