Изменения

Построим Для того, чтобы построить логическую схему мультиплексора. Очевиднонеобходимо воспользоваться вспомогательной схемой [[дешифратор|дешифратора]], что если входы а именно мы подключаем дешифратор к входам $s_0$, $s_1$, $\ldots$, $s_{n-1}$ задают вход . Обозначим провода как $x_iy_0$, причем значение на входе $x_iy_1$ равно , $0\ldots$, то на выходе $zy_{2^n-1}$ будет , где провод $0y_i$означает, если же что на нём будет значение на входе $x_i$ равно $1y_i$, то и на выходе где $zi$ значение тоже будет $1$. Также давайте построим логическую схему- число, которая перебирает всевозможные варианты значений на входах которое кодируется входами $s_0$, $s_1$, $\ldots$, $s_{n-1}$, т.е. имеет $n$ входов и Потом выходы дешифратора соединим соответственно со входами $2^nx_0$ выходов, причём на всех выходах будет $0$ кроме $ix_1$-ого выхода, на котором будет $1\ldots$, где $i$ - число, которое кодируется входами. Такая схема называется шифратором, и подробное её устройство можно почитаться в соответствующей статье, размер такой схемы будет $O(x_{2^n)-1}$. Теперь давайте соединим гейтами с помощью гейтов $AND$ , причем мы соединяем вход $x_i$ и выход провод $iy_i$ шифратора, а получившиеся провода от потом соединим все выходы с гейтов $AND$ мы все сведём к выходу в выход $Zz$. Очевидно, что такая Полученная схема будет иметь имеет размер, линейно зависящий от количества количество входови выходов.