390
правок
Изменения
Нет описания правки
Построим логическую схему мультиплексора. Очевидно, что если входы $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$. Очевидно, что такая схема будет иметь размер, линейно зависящий от количества входов.
==Принцип работы демультиплексора==
==Логическая схема демультиплексора==
[[Файл:LogicSircuit1to4demux.png|thumb|180px|Логическая схема мультиплексора 1-to-4]]
Схема демультиплексора можно построить аналогично схеме мультиплексора за тем лишь исключением, что теперь на входе у нас, кроме входов $s_0$, $s_1$, $\ldots$, $s_n$, ещё один вход, а не $2^n$ входов, как это было в случае с мультиплексором, зато теперь у нас $2^n$ выходов вместо одного выхода. Мы также построим схему шифратора, у которой $n$ входов и $2^n$ выходов, также поставим $2^n$ гейтов $AND$, и с каждым гейтом $AND$ мы соединим вход $y$. Таким образом, мы построили схему демультиплексора.
==См. также==
