Методы упрощения логических выражений
Булевы функции упрощаются для уменьшения числа логических элементов в схеме. Меньше транзисторов = меньше площади чипа, ниже задержки, меньше потребление энергии.
- Алгебра Буля: применение законов (де Морган, дистрибутивность, поглощение). Подходит для простых выражений.
- Карты Карно: графический метод для 2-6 переменных. Самый популярный в учебной программе.
- Куайна-Маккласки: табличный, формализованный. Для большего числа переменных.
- Эспрессо: эвристика, используется в EDA-инструментах синтеза FPGA/ASIC.
Карты Карно
Изобретены Морисом Карно в 1953 г. Графический метод для 2-6 переменных. Таблица, где соседние клетки отличаются ровно одним битом (код Грея).
Алгоритм:
- Построить таблицу истинности.
- Перенести «1» в карту Карно.
- Объединить «1» в группы размером 2, 4, 8, 16 (степени 2). Группы могут «оборачиваться» по краям таблицы.
- Каждая группа даёт упрощённое слагаемое: переменные, которые меняют значение в группе, исчезают.
- Сумма слагаемых = упрощённая функция.
СДНФ vs СКНФ
- СДНФ (совершенная дизъюнктивная нормальная форма): F = ∨ (минтермы). Каждый минтерм — это «И» всех переменных (с инверсией или без), соответствует «1» в таблице. Пример: F = ABC ∨ ¬ABC ∨ AB¬C.
- СКНФ (совершенная конъюнктивная нормальная форма): F = ∧ (макстермы). Каждый макстерм — это «ИЛИ» всех переменных, соответствует «0» в таблице. Пример: F = (A∨B∨C) · (A∨B∨¬C) · (A∨¬B∨C).
Любая функция представима в обеих формах. Выбор между ними зависит от количества «0» и «1» в таблице — берут ту форму, которая даёт меньше слагаемых.
Применение упрощения
- FPGA / ASIC синтез: компилятор переводит описание на VHDL/Verilog в логические элементы. Минимизация уменьшает число LUT (Look-Up Tables) или транзисторов.
- Управляющие схемы: автоматизация, контроллеры стиральных машин, лифтов.
- Криптография: упрощение S-box в шифрах (DES, AES).
- Цифровая обработка сигналов: фильтры, алгоритмы кодирования.
- SAT-solvers: для решения проблемы выполнимости булевых формул (используются в верификации железа и ПО).
ИСТОЧНИКИ
- Karnaugh M. — The Map Method for Synthesis of Combinational Logic Circuits. Maurice Karnaugh. 1953.
- Hennessy J.L., Patterson D.A. — Computer Architecture: A Quantitative Approach. Hennessy & Patterson. 2017.
- Brayton R., Hachtel G. — Logic Minimization Algorithms (Espresso). Brayton, Hachtel et al.. 1984.
