Design of combinational circuits

Why it exists

All the earlier pages of this subject are tools: Boolean algebra to rewrite, K-maps to minimise, gates to build. A design procedure puts them in order so that any specification, from "add two bits" to "convert a BCD digit to excess-3", ends in a correct, cheap circuit. The reverse, the analysis procedure, takes a circuit and finds what it computes, and is the usual form of a GATE question: "what does this circuit do", "how many gates", "what is the delay". The adders, multiplexers and decoders in the next pages are all instances of this procedure.

Prerequisites

You need K-map minimisation from Karnaugh maps and the NAND/NOR conversions from logic gates.

Precise definitions

Combinational circuit. A network of gates with no feedback and no memory. Every output is a Boolean function of the present inputs only. (A circuit whose outputs also depend on past inputs is sequential; it needs flip-flops.) A circuit with $n$ inputs and $m$ outputs is described by $m$ Boolean functions of $n$ variables, that is a truth table with $2^n$ rows and $m$ output columns.

Analysis procedure. (1) Label the gate outputs. (2) Write the Boolean function at each gate output, working from the inputs to the outputs. (3) Substitute to obtain each output as a function of the inputs, or simply compute the truth table row by row. (4) Describe the function (for example "majority", "parity", "adder").

Design procedure.

1. Specify the inputs, the outputs and what each output must be. Choose the number of bits and the coding.
2. Build the truth table. Mark input combinations that can never occur as don't cares for every output.
3. Minimise each output (K-map for up to 4 or 5 variables, tabular method beyond), using the don't cares. Look for terms shared between outputs: a product term used by two outputs is built once, which can lower the total cost even if one output is no longer minimal alone.
4. Implement with the required gate type (AND-OR, NAND-NAND, NOR-NOR, or a mix) and check the fan-in and the number of inverters.
5. Verify by simulation or by recomputing the truth table of the final circuit.

Cost. The usual measures are the number of gates, the number of gate inputs (equal to literals plus the number of terms in a two-level circuit), and the number of levels. Unless the question says otherwise, inverters on inputs are counted as gates only when the complemented inputs are not available. Many GATE questions say "using only 2-input gates", which turns the cost into a gate count of a tree.

Delay. The propagation delay of a gate is the time from an input change to the output change. The delay of a circuit is the sum of the gate delays along its critical path, the longest path from any input to any output. Levels are only a proxy: gates differ (an XOR is slower than a NAND).

Two-level and multi-level. A two-level circuit (AND-OR, NAND-NAND, and so on) has the smallest delay but may be large. Factoring (using the distributive law to share work) gives a multi-level circuit with fewer gates and more delay. For example $AC + AD + BC + BD$ needs 4 AND gates and a 4-input OR (8 literals) while $(A + B)(C + D)$ needs 2 OR gates and 1 AND gate (4 literals), at the same two-level depth in this example (OR-AND instead of AND-OR).

Standard functions worth knowing.

• Majority of three: $M = AB + BC + AC = (A+B)(B+C)(A+C)$, 1 when at least two inputs are 1 (this is the carry of a full adder).
• Parity: the XOR of all inputs. An even-parity generator produces a bit $P = A \oplus B \oplus C$ so that the total number of 1s including $P$ is even. A parity checker XORs all the received bits including $P$; the output 1 signals an error (a single bit flip).
• Code converters, for example BCD to excess-3: the output is the 4-bit binary code of $d + 3$ for the digit $d$ (0 to 9). The six codes 1010 to 1111 never occur as BCD input and are don't cares.

How it works

Follow one complete design. BCD to excess-3. Inputs $A B C D$ are a BCD digit (0 to 9), outputs $w x y z$ are the 4-bit binary code of $d + 3$.

For rows 10 to 15 all outputs are don't care. The animation minimises output $x$ (ones at digits 1, 2, 3, 4, 9).

The four minimised outputs, each with the six don't cares used, are

$w = A + BC + BD,\quad x = B'C + B'D + BC'D',\quad y = CD + C'D',\quad z = D'.$

The C program below implements exactly these equations and checks them against $d + 3$ for all ten digits.

Worked examples

#include <stdio.h>
 
/* BCD digit (A B C D, A most significant) to excess-3 (w x y z) with the minimised equations */
static unsigned excess3(int a, int b, int c, int d) {
    int w = a || (b && d) || (b && c);
    int x = (!b && d) || (!b && c) || (b && !c && !d);
    int y = (!c && !d) || (c && d);
    int z = !d;
    return (unsigned)(w << 3 | x << 2 | y << 1 | z);
}
 
int main(void) {
    int wrong = 0;
    for (int digit = 0; digit < 10; digit++) {
        unsigned code = excess3((digit >> 3) & 1, (digit >> 2) & 1, (digit >> 1) & 1, digit & 1);
        printf("%d -> %u%u%u%u\n", digit, (code >> 3) & 1, (code >> 2) & 1, (code >> 1) & 1, code & 1);
        wrong += code != (unsigned)(digit + 3);
    }
    printf("rows different from digit + 3: %d\n", wrong);
    int maj_bad = 0, par_bad = 0, fac_bad = 0;
    for (int i = 0; i < 8; i++) {
        int a = (i >> 2) & 1, b = (i >> 1) & 1, c = i & 1;
        maj_bad += ((a && b) || (b && c) || (a && c)) != (a + b + c >= 2);
        par_bad += (a ^ b ^ c) != ((a + b + c) % 2);
    }
    for (int i = 0; i < 16; i++) {
        int a = (i >> 3) & 1, b = (i >> 2) & 1, c = (i >> 1) & 1, d = i & 1;
        fac_bad += ((a && c) || (a && d) || (b && c) || (b && d)) != ((a || b) && (c || d));
    }
    printf("majority wrong on %d rows, parity wrong on %d rows, factoring wrong on %d rows\n", maj_bad, par_bad, fac_bad);
    return 0;
}

0 -> 0011
1 -> 0100
2 -> 0101
3 -> 0110
4 -> 0111
5 -> 1000
6 -> 1001
7 -> 1010
8 -> 1011
9 -> 1100
rows different from digit + 3: 0
majority wrong on 0 rows, parity wrong on 0 rows, factoring wrong on 0 rows

Cheat box

Traps and GATE patterns

Connections

The adder circuits in adders and subtractors are the first complete designs from this procedure; multiplexers and decoders are standard building blocks that can implement any function. A ROM or a PLA is a table-driven way to build many outputs at once (ROM, PLA and PAL). Glitches in two-level circuits are the topic of hazards. When the output must also depend on history, the circuit becomes sequential: flip-flops.

PYQs

The line in the following figure is permanently
connected to the ground.

Which of the following inputs (X1 X2 X3 X4)
will detect the fault?

The majority function is a Boolean function
f(x,y,z)that takes the value 1 whenever a majority of
the variables x, y, z are 1. In the circuit diagram for

DIGITAL LOGIC
the majority function shown below, the logic gates
for the boxes  labeled P and Q are, respectively.

Self-check

Revision card

References