Минимизация логики и карты Карно

Одна и та же логическая функция может быть реализована разным количеством вентилей. Минимизация уменьшает число термов и литералов, что может снизить аппаратные ресурсы, задержку и энергопотребление. Карта Карно — визуальный способ объединять соседние наборы входов и получать упрощённое выражение.

Ячейки карты расположены в коде Грея: соседние клетки отличаются только одной переменной. Это позволяет объединять группы единиц (для суммы произведений) или нулей (для произведения сумм) размером 1, 2, 4, 8…

• Размер группы должен быть степенью двойки.
• Группы стараются делать максимально большими и могут перекрываться.
• Края карты считаются соседними, потому что порядок циклический по коду Грея.
• Переменная, меняющаяся внутри группы, исчезает из соответствующего терма.
• Don’t care X можно включать в группу, если это упрощает функцию, но использовать необязательно.

Карта Карно не меняет таблицу истинности — она лишь показывает, какие комбинации можно объединить по правилам булевой алгебры. Для четырёх переменных карта содержит 16 клеток.

Минимальное по числу вентилей выражение не всегда является лучшим физическим решением: временные hazards, доступные элементы FPGA и требования тестируемости могут изменить реализацию. Но для обучения K-map показывает структуру функции.

Начинайте с 2–3 переменных и сверяйте полученное выражение новой таблицей истинности.

1. Постройте карту для функции из заданного списка minterm.
2. Разместите единицы в порядке Gray code.
3. Найдите максимально крупные группы, включая края карты.
4. Запишите терм для каждой группы и итоговое выражение.
5. Проверьте упрощённую функцию по исходной таблице для всех комбинаций.

• Заполнять оси карты обычным двоичным порядком 00,01,10,11 вместо Gray 00,01,11,10.
• Забывать соседство противоположных краёв.
• Создавать группы размера 3 или 6.
• Считать don’t care обязательной единицей.

Если минимизированная схема даёт неверную комбинацию, сравните карту с исходными minterm/maxterm и проверьте, не включена ли в группу клетка с обязательным противоположным значением.

Карта Карно делает правила булевой минимизации видимыми. Она особенно удобна до 4–6 переменных и помогает понимать, какие переменные действительно влияют на функцию.