Question 4 of 5: JK-from-D Flip-Flop Conversion and a 4-Bit Barrel Shifter

Question 4: JK-from-D Flip-Flop Conversion and a 4-Bit Barrel Shifter (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.

Given. A D flip-flop with characteristic equation $Q^{+}=D$; the standard JK characteristic table (hold, reset, set, toggle); a 4-bit data word $D_3D_2D_1D_0$ to be left-shifted by $0$–$3$ positions, selected by a 2-bit amount.

Find. (a) A combinational network plus a D flip-flop that behaves exactly like a JK flip-flop; (b) a minimum-multiplexer 4-bit left barrel shifter.

Approach. Write the JK characteristic equation algebraically from its truth table, then feed that expression into $D$ (since the D-FF always sets $Q^{+}=D$) with $Q$ fed back into the network. For the shifter, cascade $\log_2 4=2$ stages of 2:1 multiplexers — a shift-by-1 stage and a shift-by-2 stage — which realizes any of the 4 shift amounts with the fewest total multiplexers (a "logarithmic" or true barrel shifter).

1. Part (a) — derive the JK characteristic equation. The JK truth table gives $Q^{+}=Q$ (hold) for $JK=00$, $Q^{+}=0$ for $JK=01$, $Q^{+}=1$ for $JK=10$, and $Q^{+}=Q'$ (toggle) for $JK=11$. Reading the K-map for $Q^{+}$ in terms of $J,K,Q$ gives $$Q^{+} = J\,Q' + K'\,Q$$.
2. Part (a) — drive a D flip-flop with this expression. Because a D-FF always produces $Q^{+}=D$ at the next active clock edge, tying $$D = J\,Q' + K'\,Q$$ into its D input — built from an inverter on $Q$ (giving $Q'$), an inverter on $K$ (giving $K'$), two AND gates ($J\cdot Q'$ and $K'\cdot Q$) and one OR gate combining them, with $Q$ fed back from the flip-flop's own output — makes the D flip-flop reproduce the JK flip-flop's behaviour exactly on every clock edge.

3. Part (b) — choose a two-stage logarithmic shifter. Any left-shift amount from 0 to 3 is the binary sum of a shift-by-1 (controlled by select bit $S_0$) and a shift-by-2 (controlled by select bit $S_1$): shift amount $=2S_1+S_0$. Stage 1 uses four 2:1 muxes, each choosing between "pass bit $i$ through" ($S_0=0$) or "take bit $i-1$" ($S_0=1$, i.e. shift left by 1, shifting in a 0 at the vacated LSB). Stage 2 uses four more 2:1 muxes choosing between "pass through" ($S_1=0$) or "take the bit two positions lower from stage 1's output" ($S_1=1$, shift left by 2).
4. Part (b) — verify all four shift amounts. $S_1S_0=00$: both stages pass through, net shift 0. $S_1S_0=01$: stage 1 shifts by 1, stage 2 passes, net shift 1. $S_1S_0=10$: stage 1 passes, stage 2 shifts by 2, net shift 2. $S_1S_0=11$: stage 1 shifts by 1 then stage 2 shifts that result by 2, net shift 3. All four required amounts are produced.
5. Part (b) — confirm this is the minimum mux count. Two stages of four 2:1 muxes use $2\times4=8$ two-input muxes total. Building the same function directly with one 4:1 mux per output bit would need only 4 mux packages, but each 4:1 mux is internally about three 2:1-mux-equivalents (extra select decoding), so the direct approach costs roughly $4\times3=12$ 2:1-mux-equivalents — more than the 8 used by the staged (barrel) design. The staged, log-depth structure is therefore both the conventional "barrel shifter" architecture and the lower-cost one here.