Минимизация логики: карты Карно
Схема из СДНФ заводится с первого раза, но вентилей в ней больше, чем нужно. Голосование трёх судей из предыдущей статьи собрано из 8: три NOT, четыре AND с тремя входами, один OR с четырьмя. Тот же сигнал описывают 4 вентиля: три AND с двумя входами и один OR с тремя. Метод карт опубликовал Морис Карно в 1953 году, работая инженером в Bell Labs, и с тех пор это первый инструмент ручной минимизации, которому учат инженеров.
Склеивание соседних строк
Основа метода — одно тождество: если два минтерма отличаются только одной переменной, эта переменная исчезает. Возьмём последние две строки таблицы голосования, A = 1, B = 1:
(A И B И C) ИЛИ (A И B И НЕ C) = A И B И (C ИЛИ НЕ C) = A И BСкобка «C ИЛИ НЕ C» всегда равна 1, поэтому вместо двух AND с тремя входами остаётся один AND с двумя. Такие пары строк называются соседними: они отличаются ровно одним битом.
Карта: те же строки, но по коду Грея
Чтобы соседей было видно глазами, Карно предложил переставить строки таблицы. Карта для трёх переменных выглядит так: строки соответствуют A, столбцы — набору BC в порядке 00, 01, 11, 10 (код Грея, где соседние наборы отличаются одним битом):
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
Порядок 00, 01, 11, 10 выбран не случайно: в обычном двоичном порядке от 01 к 10 меняются сразу два бита, и соседство теряется. В коде Грея любые соседние клетки, включая переход через край карты, отличаются ровно одним битом.
Петли
Единицы на карте обводят петлями. Три правила: размер петли равен степени двойки (1, 2, 4, 8 клеток); края карты замкнуты, поэтому левый столбец соседствует с правым, а верхняя строка с нижней; петли могут пересекаться, но каждая единица должна попасть хотя бы в одну. Переменная, которая внутри петли успевает побывать и 0, и 1, выбрасывается из результата.
Голосование накрывается тремя петлями по две клетки: столбец BC = 11 целиком (меняется только A, остаётся B И C), нижняя пара во втором и третьем столбце (A = 1 при BC = 01 или 11, меняется только B, остаётся A И C), нижняя пара в третьем и четвёртом столбце (A = 1 при BC = 11 или 10, меняется только C, остаётся A И B):
F = (B И C) ИЛИ (A И C) ИЛИ (A И B)assign f = (b & c) | (a & c) | (a & b);Итог: 8 вентилей сокращаются до 4. Глубина тоже падает: в СДНФ-схеме сигнал проходит NOT, затем AND, затем OR — три вентиля подряд; в минимизированной только AND и OR, то есть два. Чем короче цепь, тем раньше схема устоялась после переключения входа; как задержки складываются по цепочке, разобрано в статье о задержке распространения.
Don't care: безразличные наборы
Иногда часть наборов входов заведомо не приходит. Классический пример — двоично-десятичный код: четыре бита дают 16 значений, а цифры только 10, поэтому наборы от 1010 до 1111 никогда не появляются. На карте такие клетки помечают X. С каждой клеткой X можно поступить как удобно: включили в петлю, считаем единицей; оставили снаружи, считаем нулём. Подбор X часто сокращает петли и итоговую схему.
Пределы метода
До пяти переменных карта остаётся удобной. При шести она превращается в таблицу 8×8, где соседство между четвертями уже не увидишь глазами, и ручной метод проигрывает автоматике: алгоритм Куайна — Мак-Класки формализует склеивание, а синтезаторы применяют его эвристики к тысячам переменных. Когда вы пишете assign f = (a & b) | (a & c) | (b & c); в Verilog, минимизацию под конкретный кристалл выполняет синтезатор; карты нужны, чтобы понимать, откуда берётся его результат.
Зачем это в игре
Перенос полного сумматора (уровень 1.7) — это в точности голосование трёх судей: перенос появляется, когда хотя бы два из A, B и входного переноса равны 1. В форме СДНФ перенос занимает восемь вентилей, после минимизации четыре: (A И B) ИЛИ (A И P) ИЛИ (B И P), где P — входной перенос.
Экономия накапливается: 8-битный сумматор уровня 1.8 собирается из восьми полных сумматоров, и путь переноса через все разряды определяет, успеет ли схема устояться за такт. Каждый сэкономленный вентиль в этом пути сокращает задержку.
Проверь себя
Почему столбцы карты идут в порядке 00, 01, 11, 10, а не 00, 01, 10, 11?
Код Грея: соседние столбцы отличаются одним битом, поэтому любые две соседние клетки склеиваются в петлю. В двоичном порядке переход 01 → 10 меняет сразу два бита.
Каких размеров бывают петли?
1, 2, 4, 8, 16 клеток — всегда степень двойки. Петля из трёх клеток минтерму не соответствует.
Запишите минимальную форму переноса полного сумматора.
(A И B) ИЛИ (A И P) ИЛИ (B И P), где P — входной перенос. Это та же функция голосования, что и в предыдущей статье.
Резюме
1. Соседние минтермы, отличающиеся одной переменной, склеиваются, и переменная исчезает из формулы.
2. Карта Карно расставляет наборы по коду Грея, чтобы соседство клеток показывало склейку; края карты замкнуты.
3. Петли берут размером в степень двойки; переменные, меняющиеся внутри петли, выбрасываются.
4. Безразличные наборы X разрешено включать в петли ради экономии.
5. Ручная карта работает до 5–6 переменных, дальше минимизацию выполняет автоматика.
На уровнях 1.6–1.8 соберите полный сумматор и сравните оба варианта переноса: СДНФ и минимизированный. Оба проходят тесты, но второй содержит вдвое меньше вентилей. Дальше вас ждёт полином Жегалкина, а применение минимальным формам найдётся в мультиплексоре и дешифраторе инструкций.