Question 2 of 5: Combinational Divide-by-4 Circuit

Question 2: Combinational Divide-by-4 Circuit (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 4-bit unsigned input A3A2A1A0 (value 0–15) is divided by the fixed constant 4, producing a Quotient and a Remainder such that N = 4·Q + R.

Find. (a) the bit-width of Q and R; (b) the truth table; (c) minimized Boolean equations for every output bit; (d) a minimum-gate implementation.

Approach. Since 4 = 2², dividing by 4 is exactly a 2-bit right shift: the top 2 bits of N form the quotient and the bottom 2 bits form the remainder, with no arithmetic at all. Build the full truth table to confirm this, then K-map each output bit against all four inputs to show each one collapses to a single literal.

1. Part (a) — sizes. N ranges 0–15 (4 bits). Q = ⌊N/4⌋ ranges 0–3, so Quotient needs 2 bits (Q_x1 Q_x0). R = N mod 4 ranges 0–3, so Remainder needs 2 bits (R_y1 R_y0). $$\boxed{\text{Input: 4 bits; Quotient: 2 bits; Remainder: 2 bits}}$$
2. Part (b) — truth table. Tabulating N = 0…15 against Q = ⌊N/4⌋ and R = N mod 4 (full table below) shows every row satisfies Q_x1=A₃, Q_x0=A₂, R_y1=A₁, R_y0=A₀.
3. Part (c) — K-map per output. Plotting Q_x1 on a 4-variable K-map fills exactly the 8 cells where A₃=1 (a straight half-map split, no other variable matters) — the largest possible group, reducing to the single literal A₃. The same half-map pattern recurs for each of the other three outputs against its own source bit: $$\boxed{Q_{x1}=A_3,\ \ Q_{x0}=A_2,\ \ R_{y1}=A_1,\ \ R_{y0}=A_0}$$ Each output depends on exactly one input bit and is already in its simplest possible form (a single literal cannot be reduced further).
4. Part (d) — implement. Because every output equals a single input bit, the “circuit” is four direct wires and needs zero logic gates (Fig. Q2d) — dividing by a power of 2 is bit-repositioning, not computation.