Question 5 of 5: Barrel Shifter — Concept and a 4:1-MUX Realization

Question 5: Barrel Shifter — Concept and a 4:1-MUX Realization (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

(a) A barrel shifter is a combinational circuit that shifts or rotates an $n$-bit word by any amount from 0 to $n-1$ positions in a single clock cycle (one gate-delay pass through a MUX network), instead of one bit-position per cycle the way a shift-register built from cascaded flip-flops would. Three advantages/applications: (1) Single-cycle ALU shift/rotate instructions — every general-purpose CPU's ALU uses a barrel shifter so a "shift left by 5" instruction costs one cycle, not five; (2) Floating-point normalization — aligning a mantissa after addition/subtraction requires shifting by an arbitrary, data-dependent amount, which a barrel shifter does in one step; (3) Cryptographic and CRC/hashing datapaths — algorithms such as AES and many hash functions require fixed, arbitrary bit-rotations of a word on every round, and a barrel shifter performs that rotation with fixed, predictable (data-independent) latency, which is also important for avoiding timing side-channels.

Given. $D_3D_2D_1D_0$ (data), $S_1S_0$ (rotate-left amount $k=0,1,2,3$), $Q_3Q_2Q_1Q_0$ (rotated output); worked examples for $k=0$ and $k=1$ given verbatim in the source.

Find. A minimum-part MSI realization and the complete routing table for all four shift amounts.

Approach. Generalize the source's own two worked examples into the single rule $Q_i=D_{(i-k)\bmod 4}$, tabulate all four columns, then realize each output bit as one 4:1 multiplexer (one MSI package per two outputs) whose four data inputs are wired per that output's column and whose select lines are the shared $S_1S_0$.

1. Part (b), Step 1 — generalize the rotate rule. Rotating $D_3D_2D_1D_0$ left by $k$ positions moves the bit originally at position $j$ to position $(j+k)\bmod4$; equivalently, output position $i$ receives the bit that was $k$ positions to its right (with wraparound): $Q_i = D_{(i-k)\bmod 4}$. Checked against the source's own two examples: $k=0\Rightarrow Q_i=D_i$ (matches "Q3=D3,…,Q0=D0"); $k=1\Rightarrow Q_3=D_2,Q_2=D_1,Q_1=D_0,Q_0=D_3$ (matches verbatim, including "D3 is rotated around to the 0th output position").
2. Part (b), Step 2 — complete routing table. Applying the same rule for $k=2,3$ gives the full 4-shift-amount table below; each row is what one 4:1 MUX's four data inputs must be wired to for that output bit.

   Barrel-shifter routing (rotate left by k = S1S0)

   S1 S0 (k)	Q3	Q2	Q1	Q0
   00 (0)	D3	D2	D1	D0
   01 (1)	D2	D1	D0	D3
   10 (2)	D1	D0	D3	D2
   11 (3)	D0	D3	D2	D1

3. Part (b), Step 3 — MSI realization. Each output bit $Q_i$ is exactly a 4:1 multiplexer: its 4 data inputs are its table row above (in $k=0,1,2,3$ order onto the MUX's $I_0,I_1,I_2,I_3$ inputs) and its select lines are the shared $S_1S_0$. Four MUX channels are needed for the four outputs, realized with two 74LS153 (dual 4:1 MUX, 2 channels/package, common select) ICs — or four 74LS151 (single 8:1, using only 4 of 8 inputs) if only single-channel parts are on hand — with $S_1S_0$ bussed to every package's select pins. This needs zero discrete gates: the entire barrel shifter is two small MSI packages plus wiring, exactly as the question's closing hint suggests.
   Fig. Q5(b) — four 4:1 MUX channels (2× 74LS153), each output $Q_i$ wired per its routing-table row, select lines $S_1S_0$ shared/bussed to all four.