= Solution
\b[Use five cascaded banks of 32 two-input <multiplexers>, for optional shifts of $1,2,4,8,16$ <bits>.] The original circuit schematic below shows one bank per shift-amount <bit>; this is a <left bit shift> with zero fill, not a <bit rotation>.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/digital-systems-linear-algebra-introduction-to-formal-proof-barrel-shifter.png]
{title=Five optional power-of-two shifts implement every 32-bit logical left-shift distance}
If $s=\sum_{j=0}^4s_j2^j$, stage $j$ selects either its unchanged input or that input shifted left by $2^j$. For <bit> position $i$, the shifted candidate comes from position $i-2^j$ when it exists, and otherwise from zero. Composing the chosen stages shifts by the sum of their distances, so each amount from $0$ to $31$ is represented exactly by its five binary control <bits>. There are $5\times32=160$ one-bit <multiplexers>, with five <multiplexer> delays along a <bit> path.
A one-bit <multiplexer> with selector $s$, unselected input $u$ and selected input $v$ has output \b[$(\neg s\land u)\lor(s\land v)$]. It can be made from one <NOT gate>, two <AND gates> and an <OR gate>; a bank can share the selector inversion. The two possible selector values directly verify its behaviour.
Back to article page
