22-Elec-A4 Digital Systems and Computers · May 2015

Question 3 of 6: Two-bit subtractor

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

Paper format. National Exams, May 2015 — 07-Elec-A4 Digital Systems & Computers. Three hours, closed book, one approved Casio or Sharp calculator. Six questions are printed and five constitute a complete exam; every question is worth 12 marks, with the per-part split printed in the marking scheme on page 1. A flip-flop excitation table and a Boolean-identity sheet are attached to the paper. All six questions are solved below, so that the set works as a complete study resource.

Reference texts.

M. M. Mano and M. D. Ciletti, Digital Design, 5th ed. — Ch. 2 (Boolean algebra and gate-level minimisation), Ch. 3 (K-maps, NAND/NOR implementation), Ch. 4 (combinational design: adders and subtractors), Ch. 5 (synchronous sequential logic, state tables and diagrams, Moore vs Mealy).
J. F. Wakerly, Digital Design: Principles and Practices, 4th ed. — Ch. 4 (combinational design practices, bubble-to-bubble logic), Ch. 7 (latches, flip-flops and their excitation tables).
C. Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. — Ch. 2 (byte order, stacks), Ch. 3 (I/O, interrupt-driven serial transfer).
Freescale/Motorola, M68HC11 Reference Manual (rev. 6) — stack operation of PSHX/PSHY, big-endian storage of 16-bit operands, SCI registers.
TIA/EIA-232-F, Interface Between Data Terminal Equipment and Data Circuit-Terminating Equipment Employing Serial Binary Data Interchange — signal-level definitions used in Question 5(b).

Question 3 (12 marks) — Two-bit subtractor

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. Two 2-bit unsigned operands, $N_1=AB$ with $A$ the most significant bit and $N_2=CD$ with $C$ the most significant bit; the difference is reported as a three-bit two's-complement word $XYZ$ with $X$ the sign bit. One half-subtractor and one full-subtractor block are supplied, each with the pin names listed in the question.

Find. (a) the 16-row truth table for $X$, $Y$ and $Z$; (b) minimal sum-of-products expressions for all three; (c) the wiring that produces $XYZ$ from the two supplied blocks.

Approach. Evaluate $N_1-N_2$ for all sixteen input combinations, encode each signed result in three-bit two's complement, then minimise on 4-variable K-maps in $ABCD$ and finally recognise the resulting expressions as the standard borrow-ripple structure so the block diagram wires itself.

Establish the range and the encoding. With $0\le N_1\le 3$ and $0\le N_2\le 3$, the difference lies in $-3\le N_1-N_2\le 3$, which three-bit two's complement covers exactly (its range is $-4$ to $+3$). The encoding is $N_1-N_2=-4X+2Y+Z$, so $X$ is the sign bit and is 1 precisely when the subtraction borrows out of the most significant stage.
Build the truth table (part a). Enumerating the sixteen combinations gives the table below; each row was computed as $N_1-N_2$ and then masked to three bits.

Question 3(a) — truth table for the two-bit subtractor. The difference is shown both as a signed decimal value and as the three-bit two's-complement word $XYZ$.
$m$	$A$	$B$	$C$	$D$	$N_1$	$N_2$	$N_1-N_2$	$X$	$Y$	$Z$
0	0	0	0	0	0	0	+0	0	0	0
1	0	0	0	1	0	1	-1	1	1	1
2	0	0	1	0	0	2	-2	1	1	0
3	0	0	1	1	0	3	-3	1	0	1
4	0	1	0	0	1	0	+1	0	0	1
5	0	1	0	1	1	1	+0	0	0	0
6	0	1	1	0	1	2	-1	1	1	1
7	0	1	1	1	1	3	-2	1	1	0
8	1	0	0	0	2	0	+2	0	1	0
9	1	0	0	1	2	1	+1	0	0	1
10	1	0	1	0	2	2	+0	0	0	0
11	1	0	1	1	2	3	-1	1	1	1
12	1	1	0	0	3	0	+3	0	1	1
13	1	1	0	1	3	1	+2	0	1	0
14	1	1	1	0	3	2	+1	0	0	1
15	1	1	1	1	3	3	+0	0	0	0

Extract the minterm lists. Indexing minterms as $m=8A+4B+2C+D$, the tables give $X=\sum m(1,2,3,6,7,11)$, $Y=\sum m(1,2,6,7,8,11,12,13)$ and $Z=\sum m(1,3,4,6,9,11,12,14)$.
Minimise $X$ (part b). The map for $X$ has one four-cell group and two two-cell groups, giving $\boxed{X=\overline{A}C+\overline{A}\,\overline{B}D+\overline{B}CD}$ — the classic borrow-out expression for a two-bit subtraction.

Question 3(b) — K-map for the sign bit $X$: three prime implicants, six minterms.

Minimise $Z$. The $Z$ map splits cleanly into two four-cell groups, $\boxed{Z=\overline{B}D+B\overline{D}}$, which is just $Z=B\oplus D$ — the difference bit of the least significant stage, independent of $A$ and $C$ as it must be.

Question 3(b) — K-map for $Z$, two four-cell groups forming an exclusive-OR.

Minimise $Y$. $Y$ is the middle bit, and it is an exclusive-OR of three quantities, so it resists grouping: no two of its eight minterms that would merge into a large cube share a common product. A minimum cover needs six product terms, $$Y=\overline{A}\,\overline{B}\,\overline{C}D+\overline{A}C\overline{D}+\overline{A}BC+A\overline{C}\,\overline{D}+A\overline{B}CD+AB\overline{C}.$$ The compact equivalent, and the form worth quoting alongside, is $\boxed{Y=A\oplus C\oplus(\overline{B}D)}$, where $\overline{B}D$ is the borrow generated by the least significant stage.

Question 3(b) — K-map for $Y$. The checkerboard pattern of an exclusive-OR is why six product terms are needed.

Wire the blocks (part c). The compact forms name the connections directly. The least significant stage subtracts $B-D$, which is exactly a half-subtractor: $\mathrm{M}=B$, $\mathrm{S}=D$, so $\mathrm{Diff}=B\oplus D=Z$ and $\mathrm{B_{out}}=\overline{B}D$. That borrow feeds the full-subtractor's $\mathrm{B_{in}}$, and the full-subtractor takes $\mathrm{M}=A$, $\mathrm{S}=C$, giving $\mathrm{Diff}=A\oplus C\oplus\mathrm{B_{in}}=Y$. Finally the full-subtractor's own borrow-out is the sign bit, $\mathrm{B_{out}}=\overline{A}C+\overline{A}\mathrm{B_{in}}+C\,\mathrm{B_{in}}=X$.
Confirm the sign convention. A borrow out of the top stage means $N_1<N_2$, and in two's complement a negative result has its sign bit set — so tying $X$ directly to $\mathrm{B_{out}}$ is correct with no inverter. Checking one row, $N_1=00$, $N_2=01$ gives $Z=1$, $\mathrm{B_{out(HS)}}=1$, $Y=0\oplus0\oplus1=1$ and $X=1$, i.e. $111_2=-1$, as required.

Question 3(c) — completed connections. The half-subtractor handles the least significant bits, its borrow ripples into the full-subtractor, and the full-subtractor's borrow-out is the two's-complement sign bit.

Question 3 — final results
Output	Minimal sum of products	Compact form	Source in part (c)
$X$ (sign)	$\overline{A}C+\overline{A}\,\overline{B}D+\overline{B}CD$	borrow-out of the FS	FS $\mathrm{B_{out}}$
$Y$	$\overline{A}\,\overline{B}\,\overline{C}D+\overline{A}C\overline{D}+\overline{A}BC+A\overline{C}\,\overline{D}+A\overline{B}CD+AB\overline{C}$	$A\oplus C\oplus\overline{B}D$	FS $\mathrm{Diff}$
$Z$ (LSB)	$\overline{B}D+B\overline{D}$	$B\oplus D$	HS $\mathrm{Diff}$
HS borrow	$\overline{B}D$	—	drives FS $\mathrm{B_{in}}$

Topic. Binary subtraction by borrow propagation, and the equivalence between a ripple-borrow chain and the sign-extended two's-complement result.

Key relations. Half-subtractor: $\mathrm{Diff}=M\oplus S$, $\mathrm{B_{out}}=\overline{M}S$. Full-subtractor: $\mathrm{Diff}=M\oplus S\oplus \mathrm{B_{in}}$, $\mathrm{B_{out}}=\overline{M}S+\overline{M}\mathrm{B_{in}}+S\,\mathrm{B_{in}}$. Two's-complement value of a three-bit word: $-4X+2Y+Z$.

Why this works. Subtracting two $n$-bit numbers and keeping the final borrow gives an $(n{+}1)$-bit word that is already the two's-complement representation of the signed difference, because a borrow out of the top stage is arithmetically a loan of $2^{n}$ — precisely the weight that the two's-complement sign bit carries as $-2^{n}$. No correction stage and no inverter is needed. This is why the six-term sum-of-products for $Y$ and the three-term expression for $X$, which look unrelated when derived from K-maps, collapse to one half-subtractor and one full-subtractor in cascade.

Common pitfall. Assuming that the minimal SoP for $Y$ must be small because $X$ and $Z$ were. Exclusive-OR functions have no adjacent 1-cells that merge, so their minimal covers grow with the number of variables; a candidate answer for $Y$ with two or three terms is simply wrong. The second pitfall is inverting the borrow before using it as the sign bit, which produces $+1$ where the answer should be $-1$.

Source. Mano & Ciletti, Digital Design, 5th ed., §1.5–1.6 (signed binary numbers, two's complement) and §4.4–4.5 (half and full adders/subtractors, ripple carry and borrow); Wakerly, Digital Design, 4th ed., §2.5–2.6 and §6.10 (adders and subtractors).

← Question 2 Next: Question 4 →

$m$	$A$	$B$	$C$	$D$	$N_1$	$N_2$	$N_1-N_2$	$X$	$Y$	$Z$
0	0	0	0	0	0	0	+0	0	0	0
1	0	0	0	1	0	1	-1	1	1	1
2	0	0	1	0	0	2	-2	1	1	0
3	0	0	1	1	0	3	-3	1	0	1
4	0	1	0	0	1	0	+1	0	0	1
5	0	1	0	1	1	1	+0	0	0	0
6	0	1	1	0	1	2	-1	1	1	1
7	0	1	1	1	1	3	-2	1	1	0
8	1	0	0	0	2	0	+2	0	1	0
9	1	0	0	1	2	1	+1	0	0	1
10	1	0	1	0	2	2	+0	0	0	0
11	1	0	1	1	2	3	-1	1	1	1
12	1	1	0	0	3	0	+3	0	1	1
13	1	1	0	1	3	1	+2	0	1	0
14	1	1	1	0	3	2	+1	0	0	1
15	1	1	1	1	3	3	+0	0	0	0

$m$	$A$	$B$	$C$	$D$	$N_1$	$N_2$	$N_1-N_2$	$X$	$Y$	$Z$
0	0	0	0	0	0	0	+0	0	0	0
1	0	0	0	1	0	1	-1	1	1	1
2	0	0	1	0	0	2	-2	1	1	0
3	0	0	1	1	0	3	-3	1	0	1
4	0	1	0	0	1	0	+1	0	0	1
5	0	1	0	1	1	1	+0	0	0	0
6	0	1	1	0	1	2	-1	1	1	1
7	0	1	1	1	1	3	-2	1	1	0
8	1	0	0	0	2	0	+2	0	1	0
9	1	0	0	1	2	1	+1	0	0	1
10	1	0	1	0	2	2	+0	0	0	0
11	1	0	1	1	2	3	-1	1	1	1
12	1	1	0	0	3	0	+3	0	1	1
13	1	1	0	1	3	1	+2	0	1	0
14	1	1	1	0	3	2	+1	0	0	1
15	1	1	1	1	3	3	+0	0	0	0

$m$	$A$	$B$	$C$	$D$	$N_1$	$N_2$	$N_1-N_2$	$X$	$Y$	$Z$
0	0	0	0	0	0	0	+0	0	0	0
1	0	0	0	1	0	1	-1	1	1	1
2	0	0	1	0	0	2	-2	1	1	0
3	0	0	1	1	0	3	-3	1	0	1
4	0	1	0	0	1	0	+1	0	0	1
5	0	1	0	1	1	1	+0	0	0	0
6	0	1	1	0	1	2	-1	1	1	1
7	0	1	1	1	1	3	-2	1	1	0
8	1	0	0	0	2	0	+2	0	1	0
9	1	0	0	1	2	1	+1	0	0	1
10	1	0	1	0	2	2	+0	0	0	0
11	1	0	1	1	2	3	-1	1	1	1
12	1	1	0	0	3	0	+3	0	1	1
13	1	1	0	1	3	1	+2	0	1	0
14	1	1	1	0	3	2	+1	0	0	1
15	1	1	1	1	3	3	+0	0	0	0