Обучение › Тема 4

Карты Карно для 2, 3 и 4 переменных с безразличными условиями X

7 мин чтения · Команда bitGateLab

Упрощение с помощью булевой алгебры работает, но всё зависит от того, «увидите» ли вы, какой закон применить. Карта Карно превращает этот поиск в наглядное упражнение: таблица истинности размещается на сетке, в которой соседние клетки различаются только одной переменной, и упрощение сводится к обведению групп единиц. Здесь вы научитесь строить карты для 2, 3 и 4 переменных, правильно объединять клетки (включая края, которые «замыкаются» друг на друга) и пользоваться безразличными условиями.

Идея: соседние клетки различаются одной переменной

Закон склеивания гласит, что AB + AB = A: два члена, различающиеся только одной переменной, сливаются, и эта переменная исчезает. Карта Карно располагает минтермы так, чтобы любые две клетки с общей стороной удовлетворяли этому условию. Для этого заголовки строк и столбцов идут не в двоичном порядке 00, 01, 10, 11, а в коде Грея: 00, 01, 11, 10. Между двумя соседними значениями меняется только один бит — в том числе между последним и первым (10 и 00). Поэтому карта ведёт себя так, будто её противоположные края склеены.

Карты для 2 и 3 переменных

В карте двух переменных 4 клетки: A — по строкам, B — по столбцам. В карте трёх переменных 8 клеток: A — по строкам, BC — по столбцам, в порядке кода Грея. Номер в каждой клетке показывает, какому минтерму она соответствует:

Обратите внимание, что m3 и m2 стоят именно в таком порядке: это следствие кода Грея и причина множества ошибок при заполнении карты вручную.

Правила объединения в группы

• В группы могут входить только единицы (или X, как вы увидите ниже), но ни в коем случае не нули.
• Размер каждой группы должен быть степенью числа 2: 1, 2, 4, 8 или 16 клеток.
• Группы — это прямоугольники из соседних клеток, включая соседство через края карты. Диагонали не считаются.
• Делайте каждую группу как можно больше: группа из 2^k клеток устраняет k переменных.
• Используйте наименьшее число групп, покрывающее все единицы. Группы могут перекрываться.

Чтобы прочитать группу, проверьте каждую переменную: если она сохраняет одно и то же значение во всех клетках группы, она входит в член (без черты, если равна 1, и с чертой, если равна 0); если меняется — исключается.

Карта для 4 переменных и соседство через края

При четырёх переменных в карте 16 клеток: AB — по строкам, CD — по столбцам, и то и другое в порядке кода Грея.

Левый столбец соседствует с правым, а верхняя строка — с нижней. Следовательно, четыре угла (m0, m2, m8, m10) образуют допустимую группу из 4 клеток: во всех них B = 0 и D = 0, поэтому группа читается как BD.

Безразличные условия (X)

Иногда некоторые комбинации входов никогда не возникают или значение выхода для них ни на что не влияет. Например, в двоично-десятичной цифре (BCD) кодов от 1010 до 1111 не существует. В таких строках пишут X (по-английски это называется don't care) и перечисляют их отдельно как d(...). При объединении каждую X можно принять за 1, если это помогает получить группу побольше, или не учитывать, если не помогает. Покрывать X никогда не обязательно.

Типичные ошибки

• Располагать заголовки в двоичном порядке (00, 01, 10, 11), а не в коде Грея. Соседние клетки перестают различаться одной переменной, и группы получаются неверными.
• Составлять группы из 3 или 6 клеток. Допустимы только степени числа 2.
• Забывать о соседстве через края и о четырёх углах, из-за чего группы выходят меньше, чем могли бы быть.
• Добавлять группу, все клетки которой уже покрыты другими. Она лишняя и только добавляет логические элементы.
• Заставлять себя покрывать X. Их используют только тогда, когда они увеличивают группу.

Попробуйте в симуляторе

Модуль карт Карно размещает функцию в порядке кода Грея, отмечает группы и записывает минимальное выражение, так что вы можете сравнить свои группы с теми, что предлагает инструмент.

1. Создайте функцию четырёх переменных и введите единицы из примера 2.
2. Сначала объедините клетки сами на бумаге и запишите свой результат.
3. Посмотрите, какие группы отмечает карта и какое выражение получается; если оно отличается от вашего, выясните, какая из групп не была максимальной.
4. Введите пример 3, отметив клетки 0, 2 и 5 как X, и посмотрите, как меняется упрощение, если эти X убрать.
5. Преобразуйте результат в схему и переключайте входы, чтобы убедиться, что он совпадает с таблицей.

Упражнения

1. Упростите F(A, B, C) = Σm(0, 2, 4, 6).
   Ответ

   Столбцы BC = 00 и BC = 10 соседствуют через край и заполнены целиком. Во всех четырёх клетках C = 0: F = C.

2. Упростите F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15).
   Ответ

   Углы: BD. Центральный блок m5, m7, m13, m15: BD. F = BD + BD, то есть XNOR от B и D.

3. Упростите F(A, B, C, D) = Σm(4, 5, 6, 7, 12, 13, 14, 15).
   Ответ

   Строки AB = 01 и AB = 11 образуют группу из 8 клеток; только B остаётся равной 1. F = B.

4. Двоично-десятичная цифра BCD (A — старший бит) должна включать выход, когда её значение равно 5 или больше. Упростите F = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15).
   Ответ

   С учётом X строки AB = 11 и AB = 10 образуют группу из 8 клеток: A. Блок m5, m7, m13, m15 даёт BD, а блок m6, m7, m14, m15 даёт BC. F = A + BD + BC = A + B(C + D).

Когда переменных больше четырёх-пяти, карту становится трудно читать; для таких случаев есть табличная процедура — метод Куайна — Мак-Класки.