Реализация булевой функции схемой из функциональных элементов — различия между версиями
Rybak (обсуждение | вклад) (→Логические элементы) |
м (rollbackEdits.php mass rollback) |
||
(не показана 41 промежуточная версия 11 участников) | |||
Строка 1: | Строка 1: | ||
== Логические элементы == | == Логические элементы == | ||
− | ''Функциональный элемент'' (англ. ''Combinational element'') — устройство, предназначенное для обработки информации в цифровой форме. Функциональный элемент имеет ''входы'' и ''выходы''. | + | {{Определение |
+ | |definition= | ||
+ | '''Функциональный элемент''' (англ. ''Combinational element'') — устройство, предназначенное для обработки информации в цифровой форме. Функциональный элемент имеет ''входы'' и ''выходы''. | ||
Сигналы на входах функционального элемента — аргументы функции, которую реализует функциональный элемент, сигналы на выходах — значение функции от аргументов. | Сигналы на входах функционального элемента — аргументы функции, которую реализует функциональный элемент, сигналы на выходах — значение функции от аргументов. | ||
+ | }} | ||
+ | {{Определение | ||
+ | |definition= | ||
+ | Если входные и выходные сигналы являются нулями и единицами, элемент называется '''логическим''' (англ. ''logic gate''). | ||
+ | При подаче на входы логического элемента любой комбинации двоичных сигналов, на выходах также возникает сигнал — значение [[Определение булевой функции|булевой функции]]. | ||
+ | }} | ||
− | + | Отождествление переменных осуществляется при помощи ветвления проводников.[[File:Отождествление.png|thumb|200px|Отождествление переменных]] | |
− | |||
− | Отождествление | ||
− | Чтобы осуществить подстановку одной функции в другую нужно выход | + | Чтобы осуществить подстановку одной функции в другую, нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию. |
[[File:Подстановка.png|thumb|200px|Подстановка]] | [[File:Подстановка.png|thumb|200px|Подстановка]] | ||
== Изображение логических элементов на схемах == | == Изображение логических элементов на схемах == | ||
− | {| class = " | + | {| class = "wikitable" border = "1" |
!Тип элемента | !Тип элемента | ||
− | |И | + | !-align="center" |И |
− | |ИЛИ | + | !-align="center" |ИЛИ |
− | |НЕ | + | !-align="center" |НЕ |
− | + | !Штрих Шеффера | |
− | + | !Стрелка Пирса | |
|- | |- | ||
!Традиционная форма | !Традиционная форма | ||
Строка 38: | Строка 44: | ||
[[Image:NAND_logic_relement2.png]] | [[Image:NAND_logic_relement2.png]] | ||
|[[Image:NOR_logic_relement.png]] | |[[Image:NOR_logic_relement.png]] | ||
− | |||
[[Image:NOR_logic_relement2.png]] | [[Image:NOR_logic_relement2.png]] | ||
|} | |} | ||
== Схемная сложность == | == Схемная сложность == | ||
− | ''Схемная сложность'' функции < | + | {{Определение |
− | это минимальное количество функциональных элементов из набора < | + | |
− | необходимое для реализации функции < | + | |definition= '''Схемная сложность''' (англ. ''Circuit complexity'') функции <tex>f</tex> относительно базиса <tex>B</tex> — это минимальное количество функциональных элементов из набора <tex>B</tex>, необходимое для реализации функции <tex>f</tex> в базисе <tex>B</tex>. |
− | Схемную сложность функции < | + | Схемную сложность функции <tex>f</tex> в базисе <tex>B</tex> обозначают так: <tex>size_B(f)</tex> |
+ | }} | ||
+ | |||
+ | {{Теорема | ||
+ | |statement = | ||
+ | Для любых базисов <tex>~B_1</tex>, <tex>~B_2</tex> и функции <tex>~f</tex> верно неравенство <tex>~size_{B_2}(f) \leqslant C_{(B_1,\;B_2)}size_{B_1}(f)</tex>, где константа <tex>~C</tex> зависит только от базисов <tex>~B_1</tex> и <tex>~B_2</tex>. | ||
+ | |proof = | ||
+ | Пусть базис <tex>~B_2</tex> состоит из функций <tex>~g_1, g_2, \ldots, g_n</tex>. Каждый функциональный элемент базиса <tex>~B_2</tex> можно собрать с помощью не более чем <tex>~size_{B_1}(g_i)</tex> элементов из базиса <tex>~B_1</tex>. Собрать <tex>f</tex> в базисе <tex>B_1</tex> можно следующим образом: заменить каждый элемент схемы <tex>f</tex> в базисе <tex>B_2</tex> на схему соответствующей функции в базисе <tex>B_1</tex>. Такая сборка использует не более чем в <tex>~C = \underset{i=1 \ldots n}{\max} \ size_{B_1}(g_i)</tex> раз больше функциональных элементов, чем соответствующая схема в <tex>B_2</tex>. Параметр <tex>~C</tex> зависит только от выбранных базисов. | ||
+ | }} | ||
+ | |||
+ | == Глубина схемы == | ||
+ | {{Определение | ||
+ | |||
+ | |definition= '''Глубина схемы''' для функции <tex>f</tex> относительно базиса <tex>B</tex> (англ. ''Circuit depth'') — это максимальная длина пути от входа до выхода по схеме соответствующей функции <tex>f</tex>, состоящей из элементов набора <tex>B</tex>, где за единицу длины принимается один элемент схемы. | ||
+ | Глубину схемы для функции <tex>f</tex> в базисе <tex>B</tex> обозначают <tex>depth_B(f)</tex> | ||
+ | }} | ||
+ | Примечание: понятие глубины имеет смысл только для схем с ограниченной степенью входа (''bounded fan-in''). | ||
+ | |||
+ | |||
+ | {{Теорема | ||
+ | |about=аналогична теореме про схемную сложность | ||
+ | |statement = | ||
+ | Для любых базисов <tex>~B_1</tex>, <tex>~B_2</tex> и функции <tex>~f</tex> верно неравенство <tex>~depth_{B_2}(f) \leqslant C_{(B_1,\;B_2)}depth_{B_1}(f)</tex>, где константа <tex>~C</tex> зависит только от базисов <tex>~B_1</tex> и <tex>~B_2</tex>. Доказательство аналогично доказательству предыдущей теоремы. | ||
+ | }} | ||
+ | |||
+ | == См. также == | ||
+ | * [[Простейшие методы синтеза схем из функциональных элементов]] | ||
+ | * [[Сумматор]] | ||
+ | * [[Каскадный сумматор]] | ||
+ | * [[Контактная схема]] | ||
+ | |||
+ | == Источники информации== | ||
+ | |||
+ | * Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ — 960 с. — ISBN 5-900916-37-5 | ||
+ | * [http://en.wikipedia.org/wiki/Logic_gate Wikipedia — Lodic gate] | ||
+ | * [http://www.intuit.ru/department/calculate/lancalc/2/ Лекция "Схемы из функциональных элементов" в НОУ "ИНТУИТ"] | ||
+ | |||
+ | [[Категория: Дискретная математика и алгоритмы]] | ||
− | + | [[Категория: Схемы из функциональных элементов ]] |
Текущая версия на 19:14, 4 сентября 2022
Содержание
Логические элементы
Определение: |
Функциональный элемент (англ. Combinational element) — устройство, предназначенное для обработки информации в цифровой форме. Функциональный элемент имеет входы и выходы. Сигналы на входах функционального элемента — аргументы функции, которую реализует функциональный элемент, сигналы на выходах — значение функции от аргументов. |
Определение: |
Если входные и выходные сигналы являются нулями и единицами, элемент называется логическим (англ. logic gate). При подаче на входы логического элемента любой комбинации двоичных сигналов, на выходах также возникает сигнал — значение булевой функции. |
Чтобы осуществить подстановку одной функции в другую, нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.
Изображение логических элементов на схемах
Тип элемента | И | ИЛИ | НЕ | Штрих Шеффера | Стрелка Пирса |
---|---|---|---|---|---|
Традиционная форма | ![]() |
![]() |
![]() |
![]() |
![]() |
Прямоугольная форма | ![]() |
![]() |
![]() |
![]() |
![]() |
Схемная сложность
Определение: |
Схемная сложность (англ. Circuit complexity) функции | относительно базиса — это минимальное количество функциональных элементов из набора , необходимое для реализации функции в базисе . Схемную сложность функции в базисе обозначают так:
Теорема: |
Для любых базисов , и функции верно неравенство , где константа зависит только от базисов и . |
Доказательство: |
Пусть базис | состоит из функций . Каждый функциональный элемент базиса можно собрать с помощью не более чем элементов из базиса . Собрать в базисе можно следующим образом: заменить каждый элемент схемы в базисе на схему соответствующей функции в базисе . Такая сборка использует не более чем в раз больше функциональных элементов, чем соответствующая схема в . Параметр зависит только от выбранных базисов.
Глубина схемы
Определение: |
Глубина схемы для функции | относительно базиса (англ. Circuit depth) — это максимальная длина пути от входа до выхода по схеме соответствующей функции , состоящей из элементов набора , где за единицу длины принимается один элемент схемы. Глубину схемы для функции в базисе обозначают
Примечание: понятие глубины имеет смысл только для схем с ограниченной степенью входа (bounded fan-in).
Теорема (аналогична теореме про схемную сложность): |
Для любых базисов , и функции верно неравенство , где константа зависит только от базисов и . Доказательство аналогично доказательству предыдущей теоремы. |
См. также
- Простейшие методы синтеза схем из функциональных элементов
- Сумматор
- Каскадный сумматор
- Контактная схема
Источники информации
- Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ — 960 с. — ISBN 5-900916-37-5
- Wikipedia — Lodic gate
- Лекция "Схемы из функциональных элементов" в НОУ "ИНТУИТ"