1. Введение: понятие базиса и задачи реализации
Базис в булевой алгебре — набор элементарных логических операций, достаточный для представления любой булевой функции.
Цель реализации — построить схему из элементов заданного базиса, которая:
- выполняет требуемую логическую функцию;
- отвечает критериям оптимальности (число элементов, задержка, потребление);
- учитывает ограничения технологии (число входов, нагрузочная способность).
Ключевые базисы:
- {И, ИЛИ, НЕ} — классический полный базис;
- {И‑НЕ} — универсальный базис (Шеффер);
- {ИЛИ‑НЕ} — универсальный базис (Вебб);
- {И, НЕ}, {ИЛИ, НЕ} — неполные, но практически важные.
2. Этапы реализации логической функции
2.1. Формализация задачи
- Задание функции:
- таблицей истинности;
- алгебраическим выражением (ДНФ, КНФ);
- словесным описанием («выход 1, если ровно два входа 1»).
- Определение переменных (входов) и выходного сигнала.
- Выбор базиса (зависит от технологии: ТТЛ, КМОП, FPGA).
2.2. Минимизация функции
Цель: сократить число операций и литералов для экономии элементов и повышения скорости.
Методы:
- алгебраические преобразования (законы булевой алгебры);
- карты Карно (для 2–6 переменных);
- метод Квайна‑МакКласки (для большого числа переменных);
- ПО для синтеза (Synopsys, Xilinx ISE).
Пример минимизации (ДНФ → минимальная ДНФ):
F=AB+AB=A(B+B)=A.
2.3. Приведение к заданному базису
Преобразование минимизированной функции к операциям выбранного базиса с использованием:
- законов Де Моргана;
- тождеств замены (например, A∨B=A⋅B);
- введения вспомогательных переменных.
2.4. Построение схемы
- Разбиение на каскады (уровни логики).
- Учёт нагрузочной способности (fan‑out).
- Оптимизация по задержке (балансировка путей).
- Добавление буферов при необходимости.
2.5. Верификация
- моделирование (SPICE, VHDL/Verilog);
- проверка на тестовых наборах;
- анализ временных характеристик.
3. Реализация в различных базисах
3.1. Базис {И, ИЛИ, НЕ}
Преимущества:
- естественность записи (ДНФ/КНФ напрямую);
- наглядность схемы.
Алгоритм:
- Получить ДНФ (для «1» в таблице истинности).
- Каждый конъюнкт → элемент И.
- Объединение конъюнктов → элемент ИЛИ.
- Инверсии переменных → элементы НЕ.
Пример: F=AB+AB
- 2 элемента И (входы: A,B и A,B);
- 1 элемент ИЛИ (входы от И);
- 2 инвертора (для A, B).
3.2. Базис {И‑НЕ} (универсальный)
Принцип: любая функция выражается через операции И‑НЕ.
Шаги:
- Получить ДНФ.
- Записать как двойное отрицание: F=F.
- Применить закон Де Моргана к F → получим выражение только через И‑НЕ.
Типовые преобразования:
- A=A↑A (инвертор на И‑НЕ);
- A⋅B=(A↑B) (И через два И‑НЕ);
- A+B=(A↑B) (ИЛИ через три И‑НЕ).
Пример (F=A+B):
- F=A+B=A⋅B.
- Схема:
- 2 И‑НЕ для A и B;
- 1 И‑НЕ для A⋅B=A+B.
3.3. Базис {ИЛИ‑НЕ} (универсальный)
Аналогично, но используем закон:
A⋅B=A+B.
Преобразования:
- A=A↓A;
- A+B=(A↓B);
- A⋅B=(A↓B).
Пример (F=A⋅B):
- F=A⋅B=A+B.
- Схема:
- 2 ИЛИ‑НЕ для A и B;
- 1 ИЛИ‑НЕ для A+B=A⋅B.
3.4. Базис {И, НЕ} или {ИЛИ, НЕ}
Ограничения: нельзя напрямую реализовать ИЛИ (в {И, НЕ}) или И (в {ИЛИ, НЕ}).
Решение: использовать законы Де Моргана для замены:
- В {И, НЕ}: A+B=A⋅B;
- В {ИЛИ, НЕ}: A⋅B=A+B.
Пример ({И, НЕ}, F=A+B):
- 2 инвертора (A, B);
- элемент И (A⋅B);
- инвертор на выходе (A⋅B=A+B).
4. Практические примеры реализации
4.1. Полусумматор (XOR + AND)
Функции:
- Сумма: S=A⊕B=AB+AB;
- Перенос: C=A⋅B.
Реализация в {И, ИЛИ, НЕ}:
- S: 2 И, 1 ИЛИ, 2 НЕ;
- C: 1 И.
В {И‑НЕ}:
- S=AB⋅AB (4 И‑НЕ);
- C=A⋅B (2 И‑НЕ).
4.2. Дешифратор 2→4
Функция: активирует один из четырёх выходов в зависимости от кода на входах A, B.
ДНФ выходов:
- Y0=AB;
- Y1=AB;
- Y2=AB;
- Y3=AB.
Схема:
- 2 инвертора (A, B);
- 4 элемента И (по два входа каждый).
4.3. Мультиплексор 2→1
Функция: Y=A⋅S+B⋅S, где S — селектор.
Реализация:
- 1 инвертор (S);
- 2 элемента И (A⋅S, B⋅S);
- 1 элемент ИЛИ (Y).
5. Оптимизация при реализации
5.1. Минимизация числа элементов
- Использование общих подвыражений (например, A для нескольких конъюнктов).
