Jump to content

Карта Карно

(Перенаправлено из диаграммы Маркванда )

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

Карта Карно ( 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 в таблице истинности).
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. Точно так

Решения каждой группы объединяются: нормальная форма схемы имеет вид .

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

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

Обратный

[ редактировать ]

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

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

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

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

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

Не волнует

[ редактировать ]
Значение для ABCD = 1111 заменяется на «все равно». Это полностью удаляет зеленый термин и позволяет красному члену стать больше. Это также позволяет синему обратному члену смещаться и становиться больше.

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

Пример справа аналогичен приведенному выше, но значение 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 переменных и более.

[ редактировать ]

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

  • Диаграмма Маркванда (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) Томаса Р. МакКаллы (трехмерное расширение карт Карно для большего количества входных данных)

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Это не следует путать с отрицанием результата ранее найденной функции.
  1. Перейти обратно: Перейти обратно: а б Карно, Морис (ноябрь 1953 г.) [23 апреля 1953 г., 17 марта 1953 г.]. «Метод карт для синтеза комбинационных логических схем» (PDF) . Труды Американского института инженеров-электриков, Часть I: Связь и электроника . 72 (5): 593–599. дои : 10.1109/TCE.1953.6371932 . Документ 53-217. Архивировано из оригинала (PDF) 16 апреля 2017 г. Проверено 16 апреля 2017 г. (Примечание. Также содержится краткий обзор Сэмюэля Х. Колдуэлла .)
  2. ^ Кертис, Герберт Аллен (1962). Новый подход к проектированию коммутационных схем . Серия Bell Laboratories (1-е изд.). Принстон, Нью-Джерси, США: компании Д. ван Ностранда, Inc. ISBN  0-44201794-4 . OCLC   1036797958 . S2CID   57068910 . ISBN   978-0-44201794-1 . ковчег:/13960/t56d6st0q. (viii+635 страниц) (Примечание. Эта книга была переиздана Чин Джи в 1969 году.)
  3. Перейти обратно: Перейти обратно: а б Вейч, Эдвард Уэстбрук (3 мая 1952 г.) [02 мая 1952 г.]. «Диаграммный метод для упрощения функций истинности». Протоколы ежегодного собрания ACM 1952 года . Ежегодная конференция/Ежегодное собрание ACM: материалы ежегодного собрания ACM 1952 года (Питтсбург, Пенсильвания, США). Нью-Йорк, США: Ассоциация вычислительной техники (ACM): 127–133. дои : 10.1145/609784.609801 .
  4. Перейти обратно: Перейти обратно: а б с д и ж г Браун, Фрэнк Маркхэм (2012) [2003, 1990]. Булево рассуждение - Логика булевых уравнений (переиздание 2-го изд.). Минеола, Нью-Йорк: Dover Publications, Inc. ISBN  978-0-486-42785-0 . [1]
  5. Перейти обратно: Перейти обратно: а б Маркванд, Аллан (1881). «XXXIII: О логических диаграммах для n термов» . Лондонский, Эдинбургский и Дублинский философский журнал и научный журнал . 5. 12 (75): 266–270. дои : 10.1080/14786448108627104 . Проверено 15 мая 2017 г. (Обратите внимание: довольно многие вторичные источники ошибочно цитируют эту работу как «Логическую диаграмму для n терминов» или «О логической диаграмме для n терминов».)
  6. Перейти обратно: Перейти обратно: а б Гарднер, Мартин (1958). «6. Машина Маркванда и другие». Логические машины и диаграммы (1-е изд.). Нью-Йорк, США: McGraw-Hill Book Company, Inc., стр. 104–116. ISBN  1-11784984-8 . LCCN   58-6683 . ковчег:/13960/t5cc1sj6b. (x+157 страниц)
  7. Перейти обратно: Перейти обратно: а б Клир, Георгий Иржи (май 1972 г.). «Справочные обозначения к главе 2». Введение в методологию коммутационных цепей (1-е изд.). Бингемтон, Нью-Йорк, США: Litton Educational Publishing, Inc. / Компания Д. ван Ностранд . п. 84. ИСБН  0-442-24463-0 . LCCN   72-181095 . C4463-000-3. (xvi+573+1 стр.)
  8. ^ Уэйкерли, Джон Ф. (1994). Цифровой дизайн: принципы и практика . Нью-Джерси, США: Прентис Холл . стр. 48–49, 222. ISBN.  0-13-211459-3 . (Примечание. В двух разделах страницы, взятых вместе, говорится, что K-карты помечены кодом Грея . В первом разделе говорится, что они помечены кодом, который меняет только один бит между записями, а во втором разделе говорится, что такой код называется Греем. код.)
  9. ^ Белтон, Дэвид (апрель 1998 г.). «Карты Карно – правила упрощения» . Архивировано из оригинала 18 апреля 2017 г. Проверено 30 мая 2009 г.
  10. ^ Додж, Натан Б. (сентябрь 2015 г.). «Упрощение логических схем с помощью карт Карно» (PDF) . Техасский университет в Далласе , Школа инженерии и информатики Эрика Джонссона . Архивировано (PDF) из оригинала 18 апреля 2017 г. Проверено 18 апреля 2017 г.
  11. ^ Кук, Аарон. «Использование карт Карно для упрощения кода» . Квантовая редкость. Архивировано из оригинала 18 апреля 2017 г. Проверено 7 октября 2012 г.

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

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: c7a19c9eb1922d796c2d547113aee252__1721775060
URL1:https://arc.ask3.ru/arc/aa/c7/52/c7a19c9eb1922d796c2d547113aee252.html
Заголовок, (Title) документа по адресу, URL1:
Karnaugh map - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)