22-Mec-A5 Electrical and Electronics Engineering · December 2013

Question 2 of 8: Exclusive-OR Synthesis and Analysis of a Gated Logic Array

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

Question 2: Exclusive-OR Synthesis and Analysis of a Gated Logic Array (20 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. Part I supplies exactly six 2-input NOR gates and nothing else — no inverters, no complemented inputs. Part II supplies the six-gate array of Figure 2, whose gates are drawn with the flat-backed AND body and an output bubble, i.e. NAND gates: $G_1$ takes $K_0$ and $A$; $G_2$ takes $B$ and $K_1$; $G_3$ takes the outputs of $G_1$ and $G_2$; $G_4$ takes $G_1$ and $G_3$; $G_5$ takes $G_3$ and $G_2$; and $G_6$ takes $G_4$ and $G_5$ to produce $C$.

Find. The exclusive-OR truth table and Boolean expression, a NOR-only gate array realising it within the six-gate budget, and then the general expression for $C$, its DeMorgan reduction, and its four reduced forms over the control pair $(K_0,K_1)$.

Part I — Truth table, expression, and NOR-only realisation

The exclusive-OR asserts its output when the two inputs disagree:

Reading the two rows that produce a 1 gives the sum-of-products form directly:

Approach for the realisation. The NOR gate is functionally complete, so the design reduces to expressing $Y$ in a form built only from ORs and complements. Manipulate the sum of products into a NOR-of-NORs shape and read the gates off.

1. Recast the expression so that only NOR operations appear. Start from the complement of the sum-of-products and apply DeMorgan: $$\overline{Y}=\overline{\bar{A}B+A\bar{B}}=\overline{(\bar{A}B)}\cdot\overline{(A\bar{B})}$$ Each of the two product terms $\bar{A}B$ and $A\bar{B}$ can itself be produced by a NOR gate fed with one raw input and the term $\overline{A+B}$, because $$\overline{A+\overline{(A+B)}}=\bar{A}\cdot(A+B)=\bar{A}B$$ and symmetrically $\overline{B+\overline{(A+B)}}=A\bar{B}$. This is the key identity: one shared NOR output supplies both product terms.
2. Allocate the gates. Four gates now generate the exclusive-NOR: $$G_1=\overline{A+B},\qquad G_2=\overline{A+G_1}=\bar{A}B,\qquad G_3=\overline{B+G_1}=A\bar{B}$$ $$G_4=\overline{G_2+G_3}=\overline{\bar{A}B+A\bar{B}}=\overline{A\oplus B}$$
3. Invert to obtain the exclusive-OR. A NOR gate with both inputs tied to the same signal is an inverter, since $\overline{X+X}=\bar{X}$. Therefore $$G_5=\overline{G_4+G_4}=\overline{\overline{A\oplus B}}=A\oplus B=Y$$ $$\boxed{\;Y \text{ is realised with five 2-input NOR gates; the sixth is spare.}\;}$$

It is worth noting that the examiner's allowance of six gates is generous by exactly one. A candidate who stops at $G_4$ has built the exclusive-NOR and has answered the wrong question; a candidate who uses a sixth gate has almost certainly built a redundant inverter somewhere upstream. Five is the correct count for a NOR-only exclusive-OR with true inputs only.

Part II — Analysis of the Figure 2 array

[Figure not reproduced: Figure 2 redrawn with the internal nodes labelled. The gates are NAND gates. $G_1$ and $G_2$ gate each data input with its own control bit; $G_3$–$G_6$ form the classic four-NAND exclusive-OR acting on those two gated signals. See the official exam paper.]

[a] General expression. Write each gate output in turn, working left to right:

1. Input gates. $G_1$ and $G_2$ each combine one data input with one control bit: $$G_1=\overline{A\,K_0},\qquad G_2=\overline{B\,K_1}$$
2. Middle gate. $G_3$ takes both of those: $$G_3=\overline{G_1\,G_2}$$
3. Cross-coupled pair and output gate. $G_4$ and $G_5$ each recombine $G_3$ with one of the two input-gate outputs, and $G_6$ merges them: $$G_4=\overline{G_1\,G_3},\qquad G_5=\overline{G_3\,G_2},\qquad C=\overline{G_4\,G_5}$$ Substituting all the way back gives the general expression asked for: $$\boxed{\;C=\overline{\;\overline{\overline{A K_0}\cdot\overline{\left(\overline{A K_0}\cdot\overline{B K_1}\right)}}\;\cdot\;\overline{\overline{\left(\overline{A K_0}\cdot\overline{B K_1}\right)}\cdot\overline{B K_1}}\;}\;}$$

[b] DeMorgan reduction. The nested form above is unusable as it stands, so peel it apart one layer at a time.

1. Open the output gate. By DeMorgan, $\overline{XY}=\bar{X}+\bar{Y}$, so $$C=\overline{G_4\,G_5}=\overline{G_4}+\overline{G_5}=\left(G_1 G_3\right)+\left(G_3 G_2\right)=G_3\left(G_1+G_2\right)$$ because $\overline{G_4}=\overline{\overline{G_1G_3}}=G_1G_3$ and likewise for $G_5$. Factoring out the shared $G_3$ is the step that makes the rest easy.
2. Substitute the middle gate. Since $G_3=\overline{G_1G_2}=\overline{G_1}+\overline{G_2}$, $$C=\left(\overline{G_1}+\overline{G_2}\right)\left(G_1+G_2\right)=\overline{G_1}G_1+\overline{G_1}G_2+\overline{G_2}G_1+\overline{G_2}G_2$$ The first and last products vanish, leaving $$C=\overline{G_1}G_2+G_1\overline{G_2}=G_1\oplus G_2$$ The array is therefore an exclusive-OR of its two internal signals — which is exactly what the $G_3$–$G_6$ sub-network is famous for.
3. Substitute the input gates. With $G_1=\overline{AK_0}$ and $G_2=\overline{BK_1}$, and using the identity $\bar{X}\oplus\bar{Y}=X\oplus Y$ (complementing both operands of an exclusive-OR leaves it unchanged), $$C=\overline{AK_0}\oplus\overline{BK_1}=AK_0\oplus BK_1$$ $$\boxed{\;C=(A\,K_0)\oplus(B\,K_1)=A K_0\overline{B K_1}+\overline{A K_0}\,B K_1\;}$$

[c] The four control combinations. With the expression in the compact form $C=(AK_0)\oplus(BK_1)$, each control setting simply gates one operand to zero, and $X\oplus 0 = X$ collapses the result immediately.

All sixteen input combinations of $(A,B,K_0,K_1)$ were evaluated gate-by-gate against the reduced expression and agree exactly, which is the safest check available on a hand reduction of this size. Functionally the circuit is a small programmable logic cell: the two control bits select between a constant zero, either data input passed straight through, and the exclusive-OR of the pair. That is precisely the arithmetic primitive needed at the heart of a one-bit adder/subtractor slice, where the control bits choose whether an operand participates.