Combinational Circuit Design

A combinational circuit computes outputs from current inputs only: no memory, no clocks. Design means turning a worded specification into a gate network (or a chip-level connection of MSI blocks) whose truth table matches the specification. Analysis is the reverse: reading a given network back into equations and a truth table.

This note covers the design and analysis procedures, propagation delay and the critical path, and the standard small designs that GATE uses as exercises: comparators, parity generators and checkers, and code converters. Adders, multiplexers and decoders are specialised instances treated in their own notes.

Model every gate $g$ with a delay $t_g$. The delay of a path is the sum of the gate delays along it, and the circuit's delay is the longest input-to-output path, the critical path. In the unit-delay model every gate costs 1, so the delay equals the number of gate levels on the deepest path.

Convention used in all Gate CS Mastery DL notes. Unless a question gives other values, gate delays are counted in the unit-delay model, and complemented inputs are assumed available (no inverter level).

Analysis starts from a diagram and produces equations or a truth table: label every gate output, write each as a function of its inputs, and substitute from the inputs forward. Design goes the other way. Both are used in this note.

A ROM is a decoder (fixed AND array generating all minterms) followed by a programmable OR array, so its size does not depend on how simple the functions are. A PLA pays only for the distinct product terms the minimized outputs use, so multi-output sharing matters.

Gates: $t_1 = (ab)'$, $t_2 = (bc)'$, $t_3 = (ca)'$, $f = (t_1 t_2 t_3)'$. Substituting and applying De Morgan once, $f = ab + bc + ca$: the majority function. A two-level NAND-NAND network is always the SOP obtained by reading every NAND as an AND in the first level and as an OR in the second.

For $n$-bit unsigned $A$ and $B$, let $x_i = a_i b_i + a_i' b_i'$ ($a_i \odot b_i$, bit $i$ equal). For $n = 2$:

The pattern extends to $n$ bits: $A > B$ when, at the most significant position where they differ, $a_i = 1$ and $b_i = 0$. So $GT = \sum_{i} a_i b_i' \prod_{j > i} x_j$. Exactly one of $EQ$, $GT$, $LT$ is 1 on every row, so any one of them can be derived from the other two: $LT = (EQ + GT)'$.

An even-parity generator for data bits $d_1, \ldots, d_n$ outputs $P = d_1 \oplus \cdots \oplus d_n$, so that the $n + 1$ transmitted bits contain an even number of 1s. The checker recomputes $C = P \oplus d_1 \oplus \cdots \oplus d_n$; $C = 1$ signals an error.

Odd parity uses $P'$ instead of $P$.

Inputs $ABCD$ (a BCD digit, $A$ the MSB), outputs $wxyz$ equal to the digit plus 3. The six codes 1010 to 1111 never occur, so they are don't-cares. Minimizing each output with them:

Note $y = (C \oplus D)'$ and $z = D'$. If every output is forced to 0 on invalid inputs, the example $w$ becomes $AB'C' + A'BC + A'BD$ (9 literals instead of 5).

$g_{n-1} = b_{n-1}$ and $g_i = b_{i+1} \oplus b_i$: $n - 1$ XOR gates in one level, delay 1. The Gray-to-binary converter $b_i = b_{i+1} \oplus g_i$ is a chain, so its delay is $n - 1$ XOR levels (see the Binary Codes note).

Pseudocode uses <- for assignment; a circuit is a directed acyclic graph of gates.

COMB-DESIGN takes $\Theta(2^n)$ rows to fill the table, plus the minimization cost. CRITICAL-PATH is a longest-path computation on a DAG: $\Theta(V + E)$ time for $V$ gates and $E$ wires.

Counting circuits by behaviour. An $n$-input, $m$-output combinational circuit computes a map $\{0,1\}^n \to \{0,1\}^m$. There are $(2^m)^{2^n} = 2^{m\,2^n}$ such maps, and a ROM with $n$ address bits and $m$-bit words can hold any one of them, which is why its size is $2^n \times m$ bits regardless of the function.

ROM sizing. A 4-bit by 4-bit unsigned multiplier has 8 inputs and an 8-bit product (the largest product is $15 \cdot 15 = 225 < 256$), so a ROM realization needs $2^8 \times 8 = 2048$ bits. A 4-bit adder with carry-in has 9 inputs and 5 outputs: $2^9 \times 5 = 2560$ bits.

Why parity misses even errors. Flipping bit $i$ toggles $C$ because $C$ is the XOR of all received bits. Flipping $k$ bits toggles $C$ $k$ times, so $C$ ends at $k \bmod 2$.

$f(a,b,c)=1$ when at least two inputs are 1. Minterms $m(3,5,6,7)$. K-map: $f=ab+bc+ca$. Three 2-input ANDs and one 3-input OR; delay 2 levels.

Given $f=(a+b)(a'+c)$. Expanding, $f=aa'+ac+a'b+bc = ac + a'b + bc = ac + a'b$, since $bc$ is the consensus of $ac$ and $a'b$. The minterms are $\{2, 3, 5, 7\}$. It is not the majority function: at $a = b = 1, c = 0$ the majority is 1 but $f = 0$.

A three-input function is 1 on $m(0,2,5,7)$ and don't-care on $m(1,3)$. As in Karnaugh Maps, the don't-cares give $f = A' + C$ (2 literals) instead of $A'C' + AC$ (4 literals).

Network: $g_1 = ab$ (AND, 2 ns), $g_2 = g_1 + c$ (OR, 2 ns), $g_3 = g_2'$ (NOT, 1 ns), $f = g_3 \oplus d$ (XOR, 3 ns). Arrival times: $g_1$ at 2, $g_2$ at 4, $g_3$ at 5, $f$ at 8 ns. The critical path is $a$ (or $b$) through all four gates, 8 ns; the path from $d$ is only 3 ns. In the unit-delay model the depth is 4.

For $A = 10_2$ and $B = 01_2$: $x_1 = 0$, $x_0 = 0$, so $EQ = 0$; $GT = a_1 b_1' = 1$; $LT = 0$. For $A = B = 11_2$: $x_1 = x_0 = 1$, $EQ = 1$, $GT = LT = 0$. Over all 16 input rows the three outputs are 1 on 4, 6 and 6 rows respectively.

Outputs $F_1 = ab + a'c$ and $F_2 = ab + bc'$. A PLA needs only the three distinct products $ab$, $a'c$, $bc'$ (the product $ab$ is shared), while two separate two-level circuits would build four AND gates.

Common misconceptions.