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

Question 3 of 6: 2-bit adder outputs by K-map, implemented in a PAL

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

Notes on this paper

Paper format. National Exams, May 2017 — 16-Elec-A4 Digital Systems & Computers. Three hours, closed book, one approved Casio or Sharp calculator. Six questions, each worth 12 points; any five constitute a complete exam. A flip-flop excitation table and a list of Boolean identities are printed on the last page. Every one of the six questions is solved below, because the set is intended as a study resource rather than an exam script.

Reference texts. M. Morris Mano & M. D. Ciletti, Digital Design (6th ed.), ch. 3 (map simplification, prime implicants, hazards), ch. 4–5 (combinational and sequential design), ch. 6 (counters); J. F. Wakerly, Digital Design: Principles and Practices (5th ed.), §4.4 (timing hazards and consensus terms), ch. 7 (sequential-circuit design); C. Hamacher, Z. Vranesic, S. Zaky & N. Manjikian, Computer Organization and Embedded Systems (6th ed.), ch. 3 (memory-mapped I/O, program-controlled and interrupt I/O); F. M. Cady, Software and Hardware Engineering: Motorola M68HC11, ch. 8–9 (parallel I/O and handshaking).

Question 3: 2-bit adder outputs by K-map, implemented in a PAL (12 points)

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 numbers, X = X₁X₀ and Y = Y₁Y₀ (each 0–3), and their arithmetic sum S = X + Y (0–6). Output E = 1 when S is even; output G = 1 when S > 3.

Find. The minimum SoP expressions for E and G from four-variable K-maps, then a programmable-array-logic (PAL) realisation.

Approach. Tabulate S for all 16 input combinations, mark the even-sum rows for E and the S>3 rows for G, map each output, then map the shared and unique product terms onto fixed-OR PAL macrocells.

Reduce E to a parity relation. The parity (evenness) of X + Y is the XOR of all four bits, but the two high bits contribute an even weight (2 each), so they never change parity. The sum is even exactly when the two least-significant bits agree: $$E = 1 \iff (X_0 + Y_0)\text{ is even} \iff X_0 = Y_0$$ so the minimum SoP is the XNOR $$\boxed{E = X_0 Y_0 + \bar X_0 \bar Y_0 \;=\; X_0 \odot Y_0}$$ On the E-map the eight 1-cells collapse into just these two quads — a clean confirmation that only the LSBs matter.
List the on-set of G. Enumerating X + Y > 3 over the index $m = 8X_1 + 4X_0 + 2Y_1 + Y_0$ gives $$G = \sum m(7,10,11,13,14,15)$$ (for example X=1,Y=3 → S=4 at m7; X=3,Y=3 → S=6 at m15).
Minimise G on its K-map. Three groups cover the six cells: the quad $X_1Y_1$ (both numbers ≥ 2, so S ≥ 4), and two pairs that pick up the S = 4 boundary cases: $$\boxed{G = X_1 Y_1 + X_0 X_1 Y_0 + X_0 Y_0 Y_1}$$ The quad handles every case where both operands have their high bit set; the two triple-literal terms catch the carries where one operand is 3 (both low bits set) and the other supplies the extra weight.

Fig Q3.1 — K-map for E: the two shaded quads are X₀Y₀ and X₀′Y₀′, i.e. E = X₀ XNOR Y₀.

Fig Q3.2 — K-map for G = Σm(7,10,11,13,14,15): quad X₁Y₁ plus the two boundary pairs X₀X₁Y₀ and X₀Y₀Y₁.

Part (b): map onto a PAL. A PAL has a programmable AND array feeding a fixed OR array, so each output is the OR of a bounded set of product terms that cannot be shared between outputs. Allocate the AND terms as follows and blow the fuses to route them:
PAL programming — product terms per output OR
Output Product terms (AND array) OR fan-in

E X₀Y₀, X₀′Y₀′ 2

G X₁Y₁, X₀X₁Y₀, X₀Y₀Y₁ 3

A device with at least three product terms per output OR (e.g. a PAL16L8-class macrocell) suffices. Because no product term is reused between E and G, the fixed-OR PAL structure fits without waste; had a term been shared, a PLA (programmable OR array) would have been the more economical choice.

PAL programming — product terms per output OR
Output	Product terms (AND array)	OR fan-in
E	X₀Y₀, X₀′Y₀′	2
G	X₁Y₁, X₀X₁Y₀, X₀Y₀Y₁	3

Question 3 — final results
Quantity	Result
E (minimum SoP)	E = X₀Y₀ + X₀′Y₀′ = X₀ XNOR Y₀
G on-set	Σm(7, 10, 11, 13, 14, 15)
G (minimum SoP)	G = X₁Y₁ + X₀X₁Y₀ + X₀Y₀Y₁
PAL requirement	2 product terms (E) + 3 product terms (G); no sharing → PAL fits

Topic. Combinational function specification from an arithmetic condition, four-variable K-map minimisation, and the PAL-vs-PLA implementation choice.

Key relations. Parity of a binary sum = XOR of the bits, with even-weight bits irrelevant to the LSB parity; K-map covering; PAL = programmable AND array + fixed OR array (no OR-term sharing), PLA = both arrays programmable.

Why this works. Even/odd depends only on the units bit, so E cannot involve X₁ or Y₁ at all — recognising this before mapping saves half the work and lands the XNOR immediately. G is a threshold on a small integer, so its on-set is found fastest by simply listing the sums rather than by trying to reason bit-by-bit. The PAL fits because the two outputs share no product term; the entire point of part (b) is to notice that a fixed-OR device is adequate here, whereas a design with heavy term-sharing would argue for a PLA.

Common pitfall. Trying to build E from a full four-variable map without first spotting that the two MSBs are parity-irrelevant — the map then looks needlessly busy and invites an over-large cover. For G, forgetting the two boundary (S = 4) cases and quoting only the X₁Y₁ quad under-covers the function.

Source. Mano & Ciletti, Digital Design 6th ed., §3.5 (map minimisation), §4.5 (binary adders) and §7.6–7.7 (PLA and PAL); Wakerly, Digital Design 5th ed., §5.3 (combinational PLDs).

← Question 2 Next: Question 4 →