webdonsk.ruКак сделать карту карно для 4 переменных
Добавил пользователь Дмитрий К. Обновлено: 02.09.2024
Карты Карио представляют собой специально организованные таблицы соответствия, на которых удобно осуществляются операции склеивания при упрощении функции на пути к минимальным формам. Столбчы и строки таблицы соответствуют всевозможным наборам значений переменных, причем эти наборы расположены в таком порядке, что каждый последующий отличается от предыдущего только одной из переменных. Благодаря этому соседнне ячейки по горизонтали и вертикали отличаются значением только одной переменной. Ячейки, расположенные по краям таблицы, также считаются соседними и обладают этим свойством. На рис. 2.1 показаны карты Карно для двух, трех и четырех переменных.
Каждому набору значений переменных по строкам и столбцам соответствует своя ячейка, расположенная на их пересечении. Она заполняется единицей, если на соответствующем наборе функция принимает единичное значение, или нулем при нулевом значении функции (нули обычно не вписываются, а оставляются пустые клетки). Таким образом, отмеченные ячейки соответствуют ыицтермам, а неотмеченные — макстермам канонических форм. Например, на рис. 2.2,а показана карта Карно для функцин, заданной таблицей соответствия из рассмотренного в § 2.7 примере.
Операции склеивания двух минтермов ранга исходной формулы соответствует на карте Карно объединение двух соседних ячеек, отмеченных единицами, и эта объединенная пара ячеек представляет собой результирующий минтерм ранга. Аналогично склеивание двух минтермов ранга в минтерм ранга представляется объединением соответствующих пар ячеек в прямоугольную группу из четырех соседних ячеек и т. д. Полное число ичеек в любой группе всегда выражается целой степенью двойки , где а и b — соответственно целые числа пар ячеек по горизонтали и вертикали, причем каждая такая группа отображает минтерм ранга и покрывает минтермов ранга исходной канонической формы. Так, на рис. показано сокращенное покрытие, импликанты которого образованы в результате склеивания минтермов функции, изображенной на рис. 2.2,а. На рис. показаны тупиковые покрытия рассматриваемой функции, причем покрытие на рис. 2.2,в является минимальным.
Считывание минтермов с карты Карно осуществляется последовательным рассмотрением групп ячеек. В минтерм входят только те переменные, которые сохраняют свои значения в данной группе, причем значениям 1 соответствует сама переменная, а значению 0 — ее отрицание. Переменные, которые принимают в данной группе различные значения (0 и 1), являются свободными и в данном минтерме отсутствуют. Примеры считывания минтермов с карт Карно для различного числа переменных показаны на рис. 2.3.
Любая совокупность групп ячеек, покрывающая все отмеченные ячейки, соответствует некоторой сумме минтермов различных рангов, которая равнозначна данной функции. Стремление к простейшей форме интуитивно понимается как поиск такого минимального покрытия, число групп в котором было бы поменьше, а сами группы были покрупнее. Действительно, чем меньше групп в покрытии, тем меньше минтермов в формуле, а при увеличении размеров группы соответственно понижается ранг минтерма, а значит, уменьшается количество содержащихся в нем переменных.
Практически для отыскания минимальною покрытия на карте Карно прежде всего выбирается отмеченная ячейка, входящая в такую наибольшую группу, которая покрывает любые другие возможные группы с этой ячейкой. После формирования этой наибольшей группы по тому же признаку выбираетси другая не покрытая ячейка и формируется ее наибольшая группа. Эгот процесс продолжается до тех пор, пока все отмеченные ячейки окажутся в тех или иных группах либо останутся только такие непокрытые ячейки, которые можно сгруппировать различными способами. Из возможных вариантов выбираются те, которые приводят к минимальным покрытиям.
Наглядность карт Карно позволяет решать задачи минимизации, не прибегая к промежуточным покрытиям — сокращенным и тупиковым формам, существенно упрощает этот процесс. К сожалению, возможности этого метода ограничиваются по существу функциями четырех переменных. При большем числе переменных приходится прибегать к различным ухищрениям и основное преимущество — наглядность теряется. Тем не менее этот метод еще используется в инженерной практике для пяти, шести, а иногда и большего числа переменных, что требует увеличения количества карт Карно. Так, при пяти переменных используются две карты, одна которых соответствует инверсии пятой - переменной, а другая — этой же переменной без инверсии, причем они размечаются либо одинаково и сравниваются наложением (рис. 2.4,а), либо симметрично и сравниваются ошосительно оси симметрии (рис. ). Для упрощения разметки строки и столбцы, соответствующие значениям 1 для иекоюрой переменной, выделяются фигурной скобкой. Теперь смежными считаются и такие ячейки, которые занимают на картах одинаковые или симметричные области (в зависимости от способа разметки).
В качестве примера на рис. 2.4 показана функция, заданная таблицей соответствия:
Сначала строятся простейшие покрытия на каждой карте раздельно, с которых списываются две функции: для левой карты и для правой карты .
Затем ищутся такие импликанты в этих функциях, которые различаются только вхождением и их можно объгдннить. В данном случае это (соответствующие им группы ячеек, обведенные жирной линией на рис. 2.4, а, совпадают при наложении, а на рис. 2.4, б они расположены симметрично), в результате объединения которых получается иыпликанта . Наконец, можно также дополнять одну из карт несущественными нмпликантами, которые можно считать соседними имплшеантам другой карты и, объединяя их между собой, упрощать результирующее выражение. Так, в левую карту можно добавить импликанту (на рис. 2.4 она показана пунктиром), которая, объединяясь с имплнкантой правой карты , дает . Окончательное выражение получаем как сумму с учетом выполненных преобразований:
Для функций шести переменных потребовалось бы четыре карты Карно, а с каждой новой переменной количество требуемых карт увеличивается вдвое и, например, для восьми переменных уже равно 16. В практике используются и другие графические структуры, например, карты Вейча, которые отличаются только способом разметки переменных. Ясно, что графические методы пригодны для минимизации вручную сравнительно простых функций.
В то же время машинные методы анализа и проектирования логических схем основаны на формальном алгоритме Квайиа-Мак-Класки и его разновидностях.
Для получения минимальной формы инверсии функции необходимо найти на карте Карно минимальное покрытие совокупности нулевых ячеек и описать соответствующую формулу по указанному выше правилу. Так, для функции на рис. имеются два таких покрытия (рис. 2.5), отличающихся только одной импликантой. Если требуется найти минимальную форму как произведения макстермов, то в соответствии с изложенным в § 2.4 правилом достаточно в выражении для инверсной функции заменить все логические операции на дуальные, а вхождения переменных — на инверсные: . Эти же формы можно записать на основе принципа дуальности непосредственно по минимальным покрытиям нулевых ячеек карты Карно. Для этого достаточно каждую группу ячеек идентифицировать как сумму переменных при инверсной разметке карты Карно, т. е. считая отмеченные значения переменных нулевыми.
Метод карт Карно позволяет быстро получить минимальные ДНФ и КНФ.
Карта Карно – это таблица, каждая клетка в ней соответствует набору переменных булевой функции в её таблице истинности. Строки и столбцы карты обозначаются таким образом, чтобы любые соседние клетки по строкам или по столбцам отличались бы между собой значением только одной переменной. Это сделано для того, чтобы было бы возможно применить закон склеивания.
Виды карт Карно и метод их заполнение
Карта Карно для 2-х переменных – квадратная таблица размером (4 ячейки)
Ячейки заполняются 0 или 1, полученные в последнем столбце таблицы истинности, соответствующие наборам 00, 01, 10, 11.
Карта Карно для 3-х переменных – прямоугольная таблица размером (8ячеек). Каждая ячейка соответствует наборам 000, 001, 010, 011, 100, 101, 110, 111.
Любые две рядом расположенные клетки являются соседними. Клетки, находящиеся на границах одной строки или столбца, так же считаются соседними, то есть, клетки, которые будут соседними при скручивании карты в вертикальный и горизонтальный цилиндры.
Карта Карно для 4-х переменных – квадратная таблица размером (16 ячеек). Каждая ячейка соответствует наборам 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.
Карта Карно для 5-х переменных – прямоугольная таблица размером (32 ячейки).
Минимизация функций с помощью карт Карно или нахождение МДНФ (МКНФ) – это процесс склеивания одинаковых значений, стоящих в соседних ячейках.
Принципы склейки
Склейку клеток карты Карно можно осуществлять по единицам (если необходимо получить МДНФ) или по нулям (если требуется МКНФ).
Склеивать можно только прямоугольные области с числом единиц (нулей) 2 n , где n — целое число.
Область, которая подвергается склейке, должна содержать только единицы (нули).
Крайние клетки каждой горизонтали и каждой вертикали также граничат между собой и могут объединяться в прямоугольники. Следствием этого правила является смежность всех четырёх угловых ячеек карты Карно для N=4. Если во всех четырёх угловых ячейках стоят единицы (нули), они могут быть объединены в квадрат.
Все единицы (нули) должны попасть в какую-либо область.
С точки зрения МДНФ (МКНФ), число областей должно быть как можно меньше (каждая область представляет собой терм), а число клеток в области должно быть как можно больше (чем больше клеток в области, тем меньше переменных содержит терм).
Области могут пересекаться.
Область должна располагаться симметрично оси (оси располагаются через каждые четыре клетки) Несмежные области, расположенные симметрично оси, могут объединяться в одну.
Правило нахождения МДНФ (МКНФ).
Берём первую полученную область и смотрим, какие переменные не меняются в пределах этой области, выписываем конъюнкцию для МДНФ (дизъюнкцию для МКНФ) этих переменных; если неменяющаяся переменная нулевая, проставляем над ней инверсию для МДНФ (для МКНФ не ставим инверсию). Если переменная единичная, то не ставим инверсию для МДНФ (ставим инверсию для МКНФ). Берём следующую область, выполняем то же самое, что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией для МДНФ (дизъюнкции областей объединяем конъюнкцию для МКНФ).
Функции могут быть записаны не формулой, а аналитическим путем, то есть содержать номера наборов из таблицы истинности дизъюнктивно ( работает с 1) или конъюнктивно (& работает с 0). Например, Y= (1,4,8,10,12,14,15). Это означает, что карта Карно из 4-х переменных заполняется единицами в ячейках с номерами 1,4,8,10,12,14,15, а остальные ячейки заполняются нулями.
Пример.
B
Пример карты Карно. Это изображение фактически показывает две карты Карно: для функции ? , используя минтермов (цветные прямоугольники) и для его дополнения, используя maxterms (серые прямоугольники). На изображении E () обозначает сумму minterms, обозначенную в статье как . ? м я >
Карта Карно снижает потребность в обширных вычислениях за счет использования возможностей распознавания образов людьми. [1] Это также позволяет быстро идентифицировать и устранять потенциальные условия гонки .
Требуемые булевы результаты передаются из таблицы истинности на двумерной сетке , где в карты Карно, клетки упорядочены в коде Грея , [6] [4] , и каждая позиция ячейка представляет одну комбинацию входных условий. Ячейки также известны как minterms, в то время как каждое значение ячейки представляет соответствующее выходное значение логической функции. Идентифицируются оптимальные группы единиц или нулей, которые представляют термины канонической формы логики в исходной таблице истинности. [7] Эти термины можно использовать для написания минимального логического выражения, представляющего требуемую логику.
Карты Карно используются для упрощения требований реальной логики, чтобы их можно было реализовать с использованием минимального количества логических вентилей. Выражение сумм из побочных продуктов (СОП) всегда может быть реализован с использованием логических элементов И запитывания в ИЛИ ворота и экспрессии продукта из-сумм (POS) приводит к ИЛИ ворота , питающие И вентиль. Выражение POS дает дополнение к функции (если F - функция, то ее дополнением будет F '). [8] Карты Карно также могут использоваться для упрощения логических выражений при разработке программного обеспечения. Логические условия, используемые, например, в условных операторах, может быть очень сложным, что затрудняет чтение и сопровождение кода. После минимизации канонические выражения суммы произведений и произведений сумм могут быть реализованы напрямую с помощью логических операторов И и ИЛИ. [9]
Диаграммные и механические методы минимизации простых логических выражений существуют по крайней мере со средневековых времен. Более систематические методы минимизации сложных выражений начали разрабатываться в начале 1950-х, но до середины-конца 1980-х карта Карно была наиболее часто используемым подходом. [10]
СОДЕРЖАНИЕ
- 1.1 Карта Карно
- 1.2 Решение
- 1.3 Обратный
- 1.4 Не волнует
- 2.1 Устранение
- 2.2 Примеры карт с двумя переменными
- Заметим, что в картах Карно наборы аргументов в соседних строках и столбцах (включая первые и последние) отличаются значением одного аргумента.
- Для функций пяти и шести аргументов можно применять трёхмерную карту Карно.
Карты Карно используются для упрощения функций булевой алгебры . Например, рассмотрим логическую функцию, описанную следующей таблицей истинности .
| А | B | C | D | 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 и их обратных значений.
Карта Карно — это таблица истинности определённого вида для логической функции — была предложена в 1952 г. американским учёным Эдвардом В. Вейчем и усовершенствована в 1953 г. американским физиком Морисом Карно. Карты Карно используются для минимизации нормальной формы булевых функций, т.е. для построения МДНФ и МКНФ.
Содержание
Строим карту Карно для функции двух переменных
Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной 2 n .
Единицы карты Карно минимально покрываются двумя прямоугольниками вида 1х1, что соответствует двум элементарным конъюнкциям двух аргументов.
Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной 2 n .
Нули карты Карно минимально покрываются двумя прямоугольниками вида 1х1, что соответствует двум элементарным дизъюнкциям двух аргументов.
Строим карту Карно для функции трёх переменных
Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной 2 n .
Единицы карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным конъюнкциям двух аргументов. Заметим, что два неполных прямоугольника вида 2х1 соответствуют одному полному прямоугольнику покрытия.
Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной 2 n .
Нули карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным дизъюнкциям двух аргументов.
Строим карту Карно для функции четырёх переменных
Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной 2 n .
Единицы карты Карно минимально покрываются тремя квадратами вида 2х2, что соответствует трём элементарным конъюнкциям двух аргументов. Заметим, что четыре угловых неполных квадрата соответствуют одному полному квадрату покрытия.
Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной 2 n .
Нули карты Карно минимально покрываются одним квадратом вида 2х2, одним прямоугольником вида 1х4 и одним прямоугольником вида 2х1, что соответствует трём элементарным дизъюнкциям, в двух из которых два аргумента, а в одной три аргумента.
Читайте также: