390
правок
Изменения
Нет описания правки
[[Файл:LogicSircuit2to1mux.png|thumb|180px|Логическая схема мультиплексора 4-to-1]]
Построим логическую схему мультиплексора. Очевидно, что если входы $s_0$, $s_1$, $\ldots$, $s_{n-1}$ задают вход $x_i$, причем значение на входе $x_i$ равно $0$, то на выходе $z$ будет $0$, если же значение на входе $x_i$ равно $1$, то и на выходе $z$ значение тоже будет $1$. Также давайте построим логическую схему, которая перебирает всевозможные варианты значений на входах $s_0$, $s_1$, $\ldots$, $s_{n-1}$, т.е. имеет $n$ входов и $2^n$ выходов, причём на всех выходах будет $0$ кроме $i$-ого выхода, на котором будет $1$, где $i$ - число, которое кодируется входами. Такая схема называется шифратором, и подробное её устройство можно почитаться в соответствующей статье, размер такой схемы будет $O(2^n)$. Теперь давайте соединим гейтами $AND$ вход $x_i$ и выход $i$ шифратора, а получившиеся провода от гейтов $AND$ мы все сведём к выходу $Z$. Очевидно, что такая схема будет иметь размер, линейно зависящий от количества входов.
==Логическая схема демультиплексора==
