Изменения

Давайте построим логическую схему дешифратора рекурсивным способом: допустим, что мы построили схему для $n-1$ элемента, теперь попробуем слить $n$-ый выход с предыдущими $n-1$ выходами. Для $n=1$ схема выглядит тривиальным образом: от входа $s_0$ отходят два провода, один напрямую соединён с выходом $z_0$, другой соединён с гейтом $NOT$, а гейт $NOT$ соединён с выходом $z_1$. Очевидно, что при $n=1$ у нас схема линейно зависит от количество входов и выходов. Теперь допустим, что мы можем построить схему для $n-1$ входов. Тогда $n$-ый вход соединим с дешифратором $1-to-2$, и потом соединим каждый выход дешифратора ${n-1}-to-{2^{n-1}}$ с каждым выходом дешифратора $1-to-2$ с помощью гейтов $AND$, потом соединим соответствующие гейты с выходами $z_i$. Очевидно, что мы увеличил размер схемы по сравнению со схемой дешифратора для $n-1$ входа на $2^n$ гейтов и бесконечно малое, по сравнению с размером схемы для $n$ элементов, элементов дешифратора $1-to-2$.