Реализация булевой функции схемой из функциональных элементов
Содержание
Логические элементы
Функциональный элемент (англ. Combinational element) — устройство, предназначенное для обработки информации в цифровой форме. Функциональный элемент имеет входы и выходы. Сигналы на входах функционального элемента — аргументы функции, которую реализует функциональный элемент, сигналы на выходах — значение функции от аргументов.
Если входные и выходные сигналы — являются нулями и единицами, элемент называется логическим (англ. logic gate). При подаче на входы логического элемента любой комбинации двоичных сигналов, на выходах также возникает сигнал — значение булевой функции.
Отождествление переменных
Отождествление переменных осуществляется при помощи ветвления проводников.Подстановка
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.
Изображение логических элементов на схемах
Тип элемента | И | ИЛИ | НЕ | Штрих Шеффера | Стрелка Пирса |
---|---|---|---|---|---|
Традиционная форма | |||||
Прямоугольная форма |
Схемная сложность
Определение: |
Схемная сложность функции | относительно базиса — это минимальное количество функциональных элементов из набора , необходимое для реализации функции в базисе . Схемную сложность функции в базисе обозначают так:
Теорема: |
Для любых базисов , и функции верно неравенство , где константа зависит только от базисов и . |
Доказательство: |
Пусть базис | состоит из функций . Каждый функциональный элемент базиса можно собрать с помощью элементов не более чем элементов из базиса . Собрать в базисе можно следующим образом: заменить каждый элемент схемы в базисе на схему соответствующей функции в базисе . Такая сборка использует не более чем в раз больше функциональных элементов, чем соответствующая схема в . Параметр зависит только от выбранных базисов.
Глубина схемы
Определение: |
Глубина схемы для функции | относительно базиса — это максимальная длина пути от входа до выхода по схеме соответствующей функции , состоящей из элементов набора , где за единицу длины принимается один элемент схемы. Глубину схемы для функции в базисе обозначают
Примечание: понятие глубины имеет смысл только для схем с ограниченной степенью входа (bounded fan-in).
Теорема (аналогична теореме про схемную сложность): |
Для любых базисов , и функции верно неравенство , где константа зависит только от базисов и . |
Доказательство аналогично доказательству предыдущей теоремы.
Источники
- Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2000. — 960 с. — ISBN 5-900916-37-5
- Статья Logic Gate на английской википедии
- Лекция "Схемы из функциональных элементов" в Интернет Университете Информационных Технологий