1. Введение: зачем нужны методы минимизации
В цифровой схемотехнике любая логическая функция может быть реализована множеством способов. Однако неоптимальные решения приводят к:
- избыточному числу логических элементов;
- повышенным задержкам сигнала;
- увеличенному энергопотреблению;
- росту стоимости и площади кристалла.
Минимизация булевой функции — поиск её наиболее компактной формы, сохраняющей исходную логику работы. Карты Карно (или диаграммы Карно) — наглядный графический метод, особенно эффективный при числе переменных от 2 до 6.
2. Что такое карта Карно
2.1. Определение и принцип
Карта Карно — таблица, где:
- строки и столбцы соответствуют наборам значений входных переменных;
- каждая клетка — одна комбинация переменных (один ряд таблицы истинности);
- в клетках записаны значения функции (0 или 1).
Ключевая особенность: соседние клетки (по горизонтали и вертикали) отличаются только одной переменной. Это позволяет визуально находить группы единиц (или нулей), соответствующие простым конъюнкциям.
2.2. Правила разметки осей
- Переменные разбиваются на две группы: для строк и для столбцов.
- Значения переменных на осях идут в порядке кода Грея (соседние коды отличаются одним битом):
- 2 переменные: 00, 01, 11, 10;
- 3 переменные: 000, 001, 011, 010, 110, 111, 101, 100;
- и т. д.
- Это гарантирует «склеивание» соседних клеток по одной переменной.
3. Построение карты Карно
3.1. Шаг 1: подготовка данных
Исходные данные — таблица истинности или алгебраическое выражение. Для выражения сначала строят таблицу истинности.
Пример (функция трёх переменных):
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
3.2. Шаг 2: разметка карты
Для трёх переменных (A, B, C) обычно:
- строки — значения A (0 и 1);
- столбцы — комбинации B, C в порядке Грея: 00, 01, 11, 10.
Карта:
BC
00 01 11 10
+-----------+
A0| 0 1 1 0 |
A1| 1 1 0 0 |
+-----------+
3.3. Шаг 3: заполнение клеток
В каждую клетку вписывают значение F для соответствующей комбинации A, B, C.
4. Минимизация: правила «склеивания»
4.1. Основные принципы
- «Склеивать» можно только смежные клетки (включая «закрученные» края — карта тороидальна).
- В группе должны быть только единицы (для ДНФ) или только нули (для КНФ).
- Размер группы — 2k клеток (1, 2, 4, 8, …).
- Каждая единица должна войти хотя бы в одну группу (но может быть в нескольких).
- Цель — покрыть все единицы минимальным числом максимально больших групп.
4.2. Интерпретация групп
Каждая группа соответствует одному слагаемому (в ДНФ) или сомножителю (в КНФ):
- Переменные, не меняющиеся в пределах группы, входят в слагаемое;
- Переменные, меняющиеся, исключаются («склеиваются»).
Примеры для ДНФ:
- Группа из 2 клеток: исчезает одна переменная.
- Группа из 4 клеток: исчезают две переменные.
- Группа из 8 клеток: исчезают три переменные.
4.3. Алгоритм минимизации (для ДНФ)
- Отметить все единицы в карте.
- Выделить максимальные прямоугольные группы единиц (размер 2k).
- Для каждой группы:
- выписать переменные, остающиеся неизменными;
- взять их в прямой форме, если в группе =1, в инверсной — если =0;
- соединить конъюнкцией.
- Объединить все слагаемые дизъюнкцией.
5. Примеры минимизации
Пример 1: функция трёх переменных (из раздела 3.1)
Карта:
BC
00 01 11 10
+-----------+
A0| 0 1 1 0 |
A1| 1 1 0 0 |
+-----------+
Шаг 1: выделяем группы:
- Группа 1: клетки (A0,B0,C1) и (A0,B1,C1) → AC (переменная B меняется, исключается).
- Группа 2: клетки (A1,B0,C0) и (A1,B0,C1) → AB (C меняется, исключается).
Шаг 2: объединяем:
F=AC+AB.
Проверка: подставим A=0, B=1, C=1: F=1⋅1+0⋅0=1 (совпадает с таблицей).
Пример 2: функция четырёх переменных
Таблица истинности (частично):
| A | B | C | D | F |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 |
| … |
Карта (4×4):
CD
00 01 11 10
+-----------+
AB00| 1 1 0 0 |
AB01| 0 0 0 0 |
AB11| 0 0 0 0 |
AB10| 1 0 0 0 |
+-----------+
Группы:
- Верхняя левая 2×1: ABC (D меняется).
- Левая нижняя 1×1: ABCD.
ДНФ:
F=ABC+ABCD.
Можно ли объединить? Нет — они не смежны.
Пример 3: минимизация с «закруткой» (тороидальность)
Карта:
BC
00 01 11 10
+-----------+
A0| 1 0 0 1 |
A1| 1 0 0 1 |
+-----------+
Группа: угловые клетки (00–00, 00–10, 10–00, 10–10) → C (A и B меняются, C=0 везде).
Результат: F=C.
6. Минимизация для КНФ
Алгоритм аналогичен, но:
- «Склеиваем» нули вместо единиц.
- Для каждой группы выписываем дизъюнкцию (ИЛИ) неизменных переменных (с инверсией, если переменная =1).
- Объединяем конъюнкцией (И).
Пример: в карте выше (пример 1) нули:
- Группа: (A0,B0,C0), (A0,B1,C0), (A1,B1,C0), (A1,B1,C1) → (A+C).
- Другая группа: (A1,B1,C0
