Multilevel function and NOR-only synthesis: 22-Elec-A4 Digital Systems and Computers, December 2017, Q3

Question 3: Multilevel function and NOR-only synthesis (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. $f = A(BC+DE) + \overline{A}(FG+\overline{B}\,\overline{E})$ over seven inputs $A\ldots G$, with complemented literals available.

Find. (a) a direct AND/OR/NOT circuit, (b) a NOR-only version, and (c) a six-gate NOR realisation justified by the double-complement identity.

Approach. Draw the expression as written, then flatten it to a two-level sum of products and complement twice so the outer OR and the four product gates become NOR gates.

(a) AND–OR–NOT circuit

Direct multilevel realisation: four product gates feed two OR gates, gated by $A$ and $\overline{A}$, then a final OR.

(b) NOR-only conversion

Expanding the brackets gives the two-level form

$$f = ABC + ADE + \overline{A}FG + \overline{A}\,\overline{B}\,\overline{E}.$$

A gate-by-gate NOR conversion keeps this topology and inserts back-to-back inverters at each wire so that every AND and every OR becomes a NOR. Using the identity that an AND of literals equals a NOR of their complements, $XYZ=\overline{\overline{X}+\overline{Y}+\overline{Z}}$, each product term is one NOR gate; the final OR of the four products becomes a NOR followed by an inverter. Done mechanically this yields a valid NOR-only network (four product NORs, one combining NOR, one output inverter, plus the input inverters already assumed available). Part (c) shows this is already the minimum.

(c) Six-NOR realisation via $f=\overline{\overline{f}}$

Write each product as a NOR of complemented literals. $ABC=\overline{\overline{A}+\overline{B}+\overline{C}}$, $ADE=\overline{\overline{A}+\overline{D}+\overline{E}}$, $\overline{A}FG=\overline{A+\overline{F}+\overline{G}}$, $\overline{A}\,\overline{B}\,\overline{E}=\overline{A+B+E}$ — four NOR gates $G_1\ldots G_4$.
Complement the whole sum once. $\overline{f}=\overline{ABC+ADE+\overline{A}FG+\overline{A}\,\overline{B}\,\overline{E}} = \overline{G_1+G_2+G_3+G_4}$ — one NOR gate $G_5$ whose inputs are the four product outputs.
Complement again for the output. $f=\overline{\overline{f}}$, so a single NOR used as an inverter, $G_6=\overline{G_5+G_5}$, restores $f$: $$\boxed{f\ \text{needs exactly }6\text{ NOR gates: }G_1,\ldots,G_4\ (\text{products}),\ G_5\ (\overline{f}),\ G_6\ (\text{inverter}).}$$

Six-NOR synthesis: four product NORs $\to$ a four-input NOR ($\overline{f}$) $\to$ a NOR inverter ($f$).

Question 3 gate count
Stage	Gates
Product terms $ABC,ADE,\overline{A}FG,\overline{A}\,\overline{B}\,\overline{E}$	4 NOR
$\overline{f}$ (combine)	1 NOR
Output inverter	1 NOR
Total	6 NOR

Topic. NOR-only (functionally complete) synthesis.

Key relations. $f=\overline{\overline{f}}$; De Morgan $\overline{X+Y}=\overline{X}\,\overline{Y}$ and $\overline{XY}=\overline{X}+\overline{Y}$; AND-as-NOR $XYZ=\overline{\overline{X}+\overline{Y}+\overline{Z}}$.

Why this works. NOR is functionally complete, so any function has a NOR-only form. Writing $f$ as a flat SoP and complementing twice pushes the outer inversion onto the product gates: each AND term collapses to a single NOR fed by complemented literals, the summing OR becomes one NOR (producing $\overline{f}$), and one more NOR inverts back to $f$ — six gates for four product terms.

Common pitfall. Trying to build each two-input AND and OR separately, which balloons the count; the economy comes from letting the product gates be NOR gates on complemented inputs.

Source. Wakerly, Digital Design, §3 (NAND/NOR conversion); Roth & Kinney ch. 7.

Question 3 of 6: Multilevel function and NOR-only synthesis

Question 3: Multilevel function and NOR-only synthesis (12 marks)

(a) AND–OR–NOT circuit

(b) NOR-only conversion

(c) Six-NOR realisation via $f=\overline{\overline{f}}$