Обучение › Тема 5
Метод Куайна — Мак-Класки шаг за шагом
7 мин чтения · Команда bitGateLab
Карта Карно удобна и быстра для четырёх переменных, но она полагается на ваш глаз и становится непрактичной при пяти и более. Метод Куайна — Мак-Класки делает ту же работу с помощью таблиц и механических правил: он не требует интуиции, всегда находит все простые импликанты и лежит в основе программ, упрощающих логические функции. Здесь вы разберётесь в двух его этапах, научитесь находить существенные простые импликанты и решите полный пример для четырёх переменных.
Словарь: импликанты и простые импликанты
- Термин импликанта функции F означает произведение, которое, будучи равным 1, гарантирует, что F равна 1. Каждый минтерм функции F — импликанта, как и любая допустимая группа на карте Карно.
- Далее, простая импликанта — это импликанта, которую уже нельзя укрупнить: если убрать из неё ещё одну переменную, она покроет какую-нибудь строку, где F равна 0. Ей соответствует максимальная группа на карте.
- Наконец, существенная простая импликанта — это простая импликанта, покрывающая хотя бы один минтерм, который не покрывает никакая другая простая импликанта. Она обязана входить в любое минимальное решение.
Метод состоит из двух этапов: сначала находят все простые импликанты, склеивая члены; затем выбирают наименьший набор простых импликант, покрывающий все минтермы.
Этап 1: склеивание членов
Каждый член записывается в двоичном виде, а позиция исключённой переменной отмечается прочерком. Например, при переменных A, B, C, D член 0-11 означает ACD (переменная B исключена).
- Сгруппируйте минтермы по количеству единиц в их двоичном коде.
- Сравните каждый член группы с каждым членом следующей группы. Если они различаются только одним битом, склейте их, поставив в этой позиции прочерк, и пометьте оба исходных члена как использованные.
- Повторите то же с новым списком. Склеивать можно только те члены, у которых прочерки стоят в одних и тех же позициях.
- Когда склеивать больше нечего, члены, которые так и остались непомеченными, — это простые импликанты.
Этап 2: таблица простых импликант
Составляется таблица, в которой каждой простой импликанте отведена строка, а каждому минтерму функции — столбец (для безразличных условий столбцы не заводятся). В ней отмечают, какие минтермы покрывает каждая простая импликанта. Затем:
- Найдите столбцы с единственной отметкой. Простая импликанта в этой строке — существенная: выберите её и вычеркните все столбцы, которые она покрывает.
- Для оставшихся столбцов выберите наименьшее число простых импликант, которое их покрывает. Если две импликанты покрывают одно и то же, подойдёт любая; предпочтите ту, в которой меньше литералов.
Полный пример. Упростите F(A, B, C, D) = Σm(0, 2, 3, 5, 7, 8, 10, 11, 13, 15).
Шаг 1. Группировка по количеству единиц.
| Единиц | Минтермы |
|---|---|
| 0 | 0 (0000) |
| 1 | 2 (0010), 8 (1000) |
| 2 | 3 (0011), 5 (0101), 10 (1010) |
| 3 | 7 (0111), 11 (1011), 13 (1101) |
| 4 | 15 (1111) |
Шаг 2. Первое склеивание (пары). Сравниваются соседние группы. Минтерм 8 не склеивается ни с 3, ни с 5, потому что они различаются более чем одним битом.
| Группы | Полученные пары |
|---|---|
| 0 и 1 | (0,2) 00-0; (0,8) -000 |
| 1 и 2 | (2,3) 001-; (2,10) -010; (8,10) 10-0 |
| 2 и 3 | (3,7) 0-11; (3,11) -011; (5,7) 01-1; (5,13) -101; (10,11) 101- |
| 3 и 4 | (7,15) -111; (11,15) 1-11; (13,15) 11-1 |
Все десять минтермов помечены как использованные; получилось 13 пар.
Шаг 3. Второе склеивание (четвёрки). Склеиваются пары с прочерком в одной и той же позиции, различающиеся одним битом:
- (0,2) с (8,10) или же (0,8) с (2,10): -0-0, покрывает 0, 2, 8, 10.
- (2,3) с (10,11) или (2,10) с (3,11): -01-, покрывает 2, 3, 10, 11.
- (3,7) с (11,15) или (3,11) с (7,15): --11, покрывает 3, 7, 11, 15.
- (5,7) с (13,15) или (5,13) с (7,15): -1-1, покрывает 5, 7, 13, 15.
Все 13 пар вошли в какую-нибудь четвёрку. Четыре четвёрки между собой уже не склеиваются (нет двух таких, у которых прочерки стояли бы в одних и тех же позициях и которые различались бы одним битом). Следовательно, простые импликанты таковы:
- P1 = -0-0 = BD
- P2 = -01- = BC
- P3 = --11 = CD
- P4 = -1-1 = BD
Шаг 4. Таблица покрытия.
| Импликанта | 0 | 2 | 3 | 5 | 7 | 8 | 10 | 11 | 13 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|
| P1 BD | ✔ | ✔ | ✔ | ✔ | ||||||
| P2 BC | ✔ | ✔ | ✔ | ✔ | ||||||
| P3 CD | ✔ | ✔ | ✔ | ✔ | ||||||
| P4 BD | ✔ | ✔ | ✔ | ✔ |
Шаг 5. Существенные импликанты. В столбцах 0 и 8 отметка есть только у P1, значит, P1 — существенная. В столбцах 5 и 13 отметка есть только у P4, значит, P4 тоже существенная. Вместе они покрывают 0, 2, 5, 7, 8, 10, 13 и 15.
Шаг 6. Покрытие остального. Остались минтермы 3 и 11. P2 покрывает оба, и P3 тоже. Любая из них завершает решение с одинаковым числом литералов.
Результат: F = BD + BD + BC или же F = BD + BD + CD. В обоих вариантах три члена и шесть литералов.
Если изобразить эту функцию на карте Карно, то P1 — это четыре угла, P4 — центральный блок, P2 — столбцы 11 и 10 в строках 00 и 10 (соединённые через край), а P3 — весь столбец 11. Табличный метод приходит к тому же результату, не глядя на карту.
Безразличные условия и циклические таблицы
Безразличные условия X включаются в этап 1 так, как если бы это были единицы, потому что они могут помочь получить более крупные импликанты. На этапе 2 они опускаются: столбцы для них не заводятся, ведь покрывать их не обязательно. Простая импликанта, составленная из одних только X, не нужна никогда.
Иногда после выбора существенных импликант или с самого начала в каждом столбце оказывается не меньше двух отметок, и очевидного способа сделать выбор нет. Такая ситуация называется циклической таблицей. Её решают перебором: выбирают одну простую импликанту, убирают всё, что она покрывает, и повторяют, сравнивая получающиеся решения. Для больших таблиц существует алгебраическая процедура (метод Петрика), которая перечисляет все возможные покрытия.
Типичные ошибки
- Склеивать члены с прочерками в разных позициях, например 0-01 и 00-1. Это недопустимо, даже если кажется, что они различаются одним битом.
- Забывать помечать как использованные оба члена каждого склеивания, а потом записывать в простые импликанты то, что ими не является.
- Заводить в таблице покрытия столбцы для безразличных условий X, что без нужды заставляет их покрывать.
- Выбирать несущественные простые импликанты раньше существенных. Сначала закрепите существенные, а потом решайте вопрос с остальными.
- Неправильно записывать член по его коду: в -0-1 переменная B идёт с отрицанием (она равна 0), D — без отрицания (она равна 1), а A и C исчезают.
Попробуйте в симуляторе
Симулятор упрощает функции с помощью процедуры такого же типа, поэтому им можно проверить каждый этап своей ручной работы.
- Создайте таблицу истинности для четырёх переменных и отметьте значением 1 минтермы из примера.
- Выполните этапы 1 и 2 на бумаге и запишите свой результат.
- Посмотрите на минимальное выражение, которое выдаёт инструмент, и на его карту Карно; определите, какая группа соответствует каждой простой импликанте.
- Преобразуйте оба возможных решения в схемы на одном холсте и переключайте входы, чтобы убедиться, что выход у них всегда одинаков.
Упражнения
- Найдите простые импликанты и минимальное выражение для F(A, B, C, D) = Σm(0, 1, 3, 7, 8, 9, 11, 15).
Ответ
Простые импликанты: -00- (BC), -0-1 (BD) и --11 (CD). Столбец 0 покрывает только BC, а столбец 7 — только CD: обе существенные и вместе покрывают всё. F = BC + CD. Импликанта BD лишняя.
- Решите F(A, B, C) = Σm(0, 1, 2, 5, 6, 7). Есть ли существенные простые импликанты?
Ответ
Пары: 00-, 0-0, -01, -10, 1-1 и 11-, и ни одна из них не склеивается в четвёрку: получается шесть простых импликант. Каждый минтерм покрывают ровно две из них, так что существенных нет (циклическая таблица). Два минимальных решения: AB + BC + AC или AC + BC + AB.
- Упростите F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15).
Ответ
Если включить X в этап 1, получаются четыре простые импликанты: -0-1 (BD), -01- (BC), --11 (CD) и 1--1 (AD). В таблице, без столбцов для 1, 10 и 15: минтерм 2 покрывает только BC, минтерм 7 — только CD, а 13 — только AD. Все три существенные и покрывают также 3, 9 и 11. F = BC + CD + AD.
- Почему на этапе 1 группу с одной единицей не сравнивают с группой с тремя единицами?
Ответ
Потому что два кода с одной и с тремя единицами различаются как минимум двумя битами, а для склеивания они должны различаться ровно одним.