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

Question 3 of 6: Analysis of a Combinational MSI Circuit

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

Notes on this paper

Paper format. National Exams, May 2014 — 07-Elec-A4 Digital Systems & Computers. Three hours, closed book (one approved Casio or Sharp calculator). Six questions are printed; any five constitute a complete exam and every question is worth 12 marks, with the per-part split given in the page-1 marking scheme (Q1 is 3+3+3+3; Q2 is 6+3+3; Q3 is 6+6; Q4 is 3+3+6; Q5 and Q6 are 4+4+4). A flip-flop excitation table for the RS/JK/T/D types and a table of 22 basic Boolean identities are supplied on the last page. All six questions are solved below, because this set is a study resource rather than a timed sitting.

Reference texts.

M. M. Mano and M. D. Ciletti, Digital Design: With an Introduction to the Verilog HDL, VHDL, and SystemVerilog, 6th ed. — Boolean algebra, canonical forms and K-maps (Ch. 2–3), combinational MSI decoders and demultiplexers (Ch. 4), synchronous sequential design and flip-flop excitation (Ch. 5), registers and counters (Ch. 6).
J. F. Wakerly, Digital Design: Principles and Practices, 5th ed. — minimisation and static timing hazards (Ch. 3–4), counters and shift registers (Ch. 8).
C. Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. — the four essential subsystems and bus structure (Ch. 1–3), serial interfaces and UART framing (§3.5), the processor register set and addressing modes (Ch. 2).
M. A. Mazidi, R. McKinlay and D. Causey, PIC Microcontroller and Embedded Systems — port-driven multiplexed seven-segment displays and LED current limiting (Ch. 12).

Notation used throughout. A bar and a prime both denote complement: $\overline{A}$ in the mathematics and A′ in the figures, where SVG text cannot carry an overbar. In every K-map the leftmost variable is the most significant bit, so the minterm indices printed in the cells match the question’s own variable ordering.

Question 3: Analysis of a Combinational MSI Circuit (12 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 gate-level network with three inputs — control lines $A$ and $B$ and a data line In — and four outputs numbered 0 to 3. It contains two inverters and four three-input AND gates. Input In reaches one input of every AND gate; $A$ reaches the gates for outputs 2 and 3 directly and the gates for outputs 0 and 1 through an inverter; $B$ reaches the gates for outputs 1 and 3 directly and the gates for outputs 0 and 2 through an inverter.

Find. The output truth table as a function of $A$, $B$ and In, and the name of the standard MSI function the network performs.

[Figure not reproduced: The circuit redrawn from the exam paper. Each AND gate receives a distinct decoded combination of A and B together with the shared data line In. See the official exam paper.]

Approach. Write the output equation of each AND gate directly from its input connections, recognise the pattern formed by the four control terms, and tabulate.

Write the four output equations. Reading the connections gate by gate:$$O_0=\overline{A}\,\overline{B}\cdot \mathit{In},\qquad O_1=\overline{A}B\cdot \mathit{In},\qquad O_2=A\overline{B}\cdot \mathit{In},\qquad O_3=AB\cdot \mathit{In}$$The four control products $\overline{A}\,\overline{B}$, $\overline{A}B$, $A\overline{B}$ and $AB$ are the four minterms of two variables, so exactly one of them is 1 for any $(A,B)$ — they form a complete, mutually exclusive decode.
Tabulate the behaviour (part a). Because the control minterms are mutually exclusive, at most one output can ever be active, and it simply copies In:
Output truth table. The selected output follows the data line; the other three are forced to 0.
A B In O₀ O₁ O₂ O₃ Selected line
0 0 0 0 0 0 0 O₀
0 0 1 1 0 0 0 O₀
0 1 0 0 0 0 0 O₁
0 1 1 0 1 0 0 O₁
1 0 0 0 0 0 0 O₂
1 0 1 0 0 1 0 O₂
1 1 0 0 0 0 0 O₃
1 1 1 0 0 0 1 O₃
Condensing the eight rows into four, the behaviour is stated compactly as $O_i=\mathit{In}$ for $i=2A+B$ and $O_j=0$ for $j\neq i$.
Identify the function (part b). A single data input is routed to one of four output lines chosen by a two-bit address:$$\boxed{\text{a 1-to-4 demultiplexer, i.e. a 2-to-4 decoder enabled by In}}$$The dual reading is worth stating in an exam answer: if In is regarded as an enable rather than as data, the same silicon is a 2-to-4 line decoder, which is why catalogue parts such as the 74HC139 are sold as “dual 2-to-4 decoder/demultiplexer”.

Output truth table. The selected output follows the data line; the other three are forced to 0.
A	B	In	O₀	O₁	O₂	O₃	Selected line
0	0	0	0	0	0	0	O₀
0	0	1	1	0	0	0	O₀
0	1	0	0	0	0	0	O₁
0	1	1	0	1	0	0	O₁
1	0	0	0	0	0	0	O₂
1	0	1	0	0	1	0	O₂
1	1	0	0	0	0	0	O₃
1	1	1	0	0	0	1	O₃

Question 3 — final results
Part	Quantity	Result
(a)	Output equations	$O_0=\overline{A}\,\overline{B}\mathit{In}$, $O_1=\overline{A}B\,\mathit{In}$, $O_2=A\overline{B}\mathit{In}$, $O_3=AB\,\mathit{In}$
(a)	Compact statement	$O_i=\mathit{In}$ where $i=2A+B$; all other outputs 0
(b)	Function	1-to-4 demultiplexer ≡ 2-to-4 decoder enabled by In

Topic. Decoders and demultiplexers as minterm generators.

Key relations. An $n$-to-$2^n$ decoder asserts output $i$ exactly when the address equals $i$, i.e. output $i$ realises minterm $m_i$ of the address variables; adding an enable $E$ makes $O_i=m_i\cdot E$, and interpreting $E$ as data turns the decoder into a demultiplexer.

Why this works. The circuit is a minterm generator, and that observation is what makes decoders so useful beyond address selection. Because each output is a distinct minterm of the control variables, any Boolean function of those variables can be synthesised by ORing the appropriate decoder outputs — the standard “decoder plus OR gate” realisation. In a computer, the same structure performs memory chip-select decoding: high-order address bits drive the control lines and the enable comes from a bus-valid strobe, so exactly one memory device answers each access. The demultiplexer reading matters in serial data distribution, where one time-shared line feeds several destinations in turn.

Common pitfall. Confusing this with a multiplexer, which does the opposite: many data inputs, one output, and one AND gate per data input rather than per output. A quick discriminator is the gate count against the input count — here there are four AND gates and only one data line, so data must be fanning out, not in. A second slip is forgetting that all four outputs are 0 when In is 0, so “the selected output” is not necessarily HIGH.

Source. Mano & Ciletti, Digital Design 6th ed., §4.9 (decoders) and §4.11 (multiplexers/demultiplexers).

← Question 2 Next: Question 4 →

Part	Quantity	Result
(a)	Output equations	\(O_0=\overline{A}\,\overline{B}\mathit{In}\), \(O_1=\overline{A}B\,\mathit{In}\), \(O_2=A\overline{B}\mathit{In}\), \(O_3=AB\,\mathit{In}\)
(a)	Compact statement	\(O_i=\mathit{In}\) where \(i=2A+B\); all other outputs 0
(b)	Function	1-to-4 demultiplexer ≡ 2-to-4 decoder enabled by In