Combinational formulas

Combinational circuits: arithmetic circuits, multiplexers, decoders, code converters. 32 formulas for GATE EC, EE, IN Digital Electronics, each with when to use it. Each is explained in the topic notes.

All 32 Combinational formulas

HALF ADDER

S = A \oplus B, C = A B

Adds two 1-bit inputs and has no carry-in. A full adder with $C_{in} = 0$ reduces to this.

FULL ADDER

S = A \oplus B \oplus C_{in}, C_{o u t} = A B + B C_{in} + A C_{in} = A B + C_{in} (A \oplus B)

$S$ is 1 when an odd number of the three inputs are 1. $C_{o u t}$ is the 3-input majority function. Use the second form of $C_{o u t}$ when the adder is built from two half adders.

HALF SUBTRACTOR (COMPUTES A − B)

D = A \oplus B, B_{o} = \overline{A} B

A borrow occurs only when the minuend $A = 0$ and the subtrahend $B = 1$ .

FULL SUBTRACTOR (A MINUS B MINUS BORROW-IN)

D = A \oplus B \oplus B_{in}, B_{o u t} = \overline{A} B + \overline{A} B_{in} + B B_{in} = \overline{A} B + B_{in} \overline{(A \oplus B)}

Computes $A - B - B_{in}$ . The difference has the same expression as the full-adder sum. The borrow is the majority function of $\overline{A}$ , $B$ and $B_{in}$ . The complement goes on the minuend $A$ .

RIPPLE-CARRY ADDER DELAY

T_{R C A} = (n - 1) t_{c} + max (t_{c}, t_{s})

$t_{c}$ is a stage's delay from $C_{in}$ to $C_{o u t}$ , and $t_{s}$ is its delay from $C_{in}$ to $S$ . $C_{n}$ settles at $n t_{c}$ and $S_{n - 1}$ at $(n - 1) t_{c} + t_{s}$ . The formula assumes all $A_{i}$ , $B_{i}$ and $C_{0}$ are applied at $t = 0$ and each stage's $A_{i} \oplus B_{i}$ is ready before its carry arrives. If stage 0 is slower from $A, B$ than from $C_{in}$ , which is the case in a gate-level full adder, compute arrival times directly (see the worked example).

GENERATE, PROPAGATE, CARRY AND SUM

G_{i} = A_{i} B_{i}, P_{i} = A_{i} \oplus B_{i}, C_{i + 1} = G_{i} + P_{i} C_{i}, S_{i} = P_{i} \oplus C_{i}

Defining $P_{i} = A_{i} + B_{i}$ gives the same carries, but then $S_{i} \neq = P_{i} \oplus C_{i}$ whenever $A_{i} = B_{i} = 1$ . The XOR definition lets the sum reuse $P_{i}$ .

LOOK-AHEAD CARRIES (4-BIT)

C_{1} C_{2} C_{3} C_{4} = G_{0} + P_{0} C_{0} = G_{1} + P_{1} G_{0} + P_{1} P_{0} C_{0} = G_{2} + P_{2} G_{1} + P_{2} P_{1} G_{0} + P_{2} P_{1} P_{0} C_{0} = G_{3} + P_{3} G_{2} + P_{3} P_{2} G_{1} + P_{3} P_{2} P_{1} G_{0} + P_{3} P_{2} P_{1} P_{0} C_{0}

Each carry is a two-level SOP of $P$ , $G$ and $C_{0}$ . $C_{i}$ has $i + 1$ product terms, and the largest has $i + 1$ literals.

CLA DELAY

t_{carry} = 3 gate delays, t_{sum} = 4 gate delays

Measured from the operand inputs: 1 level for $P_{i}, G_{i}$ , 2 levels (AND then OR) for every carry, and 1 XOR for every sum. This assumes every gate, XOR included, has unit delay and unlimited fan-in. The depth does not grow with $n$ , but $C_{n}$ needs $(n + 1)$ -input gates, so wide adders are built from 4-bit CLA blocks.

GROUP GENERATE AND PROPAGATE (4-BIT BLOCK)

G_{3 : 0} = G_{3} + P_{3} G_{2} + P_{3} P_{2} G_{1} + P_{3} P_{2} P_{1} G_{0}, P_{3 : 0} = P_{3} P_{2} P_{1} P_{0}, C_{4} = G_{3 : 0} + P_{3 : 0} C_{0}

$G_{3 : 0} = 1$ when the block produces a carry by itself, and $P_{3 : 0} = 1$ when it passes its carry-in straight through. A second-level look-ahead unit combines the group $G$ and $P$ of four blocks with the same equations as the first level, giving $C_{4}$ , $C_{8}$ , $C_{12}$ and $C_{16}$ without ripple.

ADDER–SUBTRACTOR

Y_{i} = B_{i} \oplus M, C_{0} = M : M = 0 \Rightarrow A + B, M = 1 \Rightarrow A + \overline{B} + 1 = A - B

Signed or unsigned operands use the same hardware. Only the reading of the flags differs.

SIGNED OVERFLOW (2'S COMPLEMENT)

V = C_{n} \oplus C_{n - 1} = \overline{A_{n - 1}} \overline{Y_{n - 1}} S_{n - 1} + A_{n - 1} Y_{n - 1} \overline{S_{n - 1}}

$Y = B \oplus M$ is the operand actually entering the adder, not $B$ itself. Overflow is possible only when both addends have the same sign, and it occurs when the sign of the sum differs from theirs.

NUMBER RANGES (N BITS)

signed: - 2^{n - 1} \leq x \leq 2^{n - 1} - 1, unsigned: 0 \leq x \leq 2^{n} - 1

The sum of two n-bit unsigned numbers can need $n + 1$ bits, because it can reach $2^{n + 1} - 2$ .

UNSIGNED SUBTRACTION FLAG

C_{n} = 1 ⟺ A \geq B

Applies when $A - B$ is computed as $A + \overline{B} + 1$ on unsigned operands. $C_{n} = 0$ means a borrow, and the n-bit result is then the 2's complement of $B - A$ .

BCD ADDER CORRECTION

K = C_{4} + Z_{3} Z_{2} + Z_{3} Z_{1}; K = 1 \Rightarrow add 0110, decimal carry = K

$Z_{3} Z_{2} Z_{1} Z_{0}$ and $C_{4}$ come from a 4-bit binary adder adding two BCD digits and a carry-in. $K$ detects binary sums of 10 to 19. The maximum sum is $9 + 9 + 1 = 19$ . A second 4-bit adder adds $0 K K 0$ to $Z_{3} Z_{2} Z_{1} Z_{0}$ ; its own carry-out is ignored, and the decimal carry is $K$ .

1-BIT COMPARATOR

(A > B) = A \overline{B}, (A < B) = \overline{A} B, (A = B) = \overline{A \oplus B}

Exactly one of the three outputs is 1 for any input.

4-BIT MAGNITUDE COMPARATOR

x_{i} (A > B) (A < B) = \overline{A_{i} \oplus B_{i}}, (A = B) = x_{3} x_{2} x_{1} x_{0} = A_{3} \overline{B_{3}} + x_{3} A_{2} \overline{B_{2}} + x_{3} x_{2} A_{1} \overline{B_{1}} + x_{3} x_{2} x_{1} A_{0} \overline{B_{0}} = \overline{A_{3}} B_{3} + x_{3} \overline{A_{2}} B_{2} + x_{3} x_{2} \overline{A_{1}} B_{1} + x_{3} x_{2} x_{1} \overline{A_{0}} B_{0}

Unsigned operands, with $A_{3}$ and $B_{3}$ as the MSBs. $x_{i} = 1$ when bit $i$ of the two words is equal.

PARITY GENERATOR

P_{E} = D_{n - 1} \oplus \dots \oplus D_{1} \oplus D_{0}, P_{O} = \overline{P_{E}}

$P_{E}$ makes the total count of 1s in data plus parity even. $P_{O}$ makes it odd.

PARITY CHECKER

E = P \oplus D_{n - 1} \oplus \dots \oplus D_{0}

In an even-parity system, $E = 1$ flags an error. In an odd-parity system, $E = 0$ flags one. The check detects any odd number of bit errors, misses any even number, and cannot locate the bit in error.

BINARY TO GRAY

G_{n - 1} = B_{n - 1}, G_{i} = B_{i + 1} \oplus B_{i} (i = n - 2, \dots, 0)

This is the same as XORing the binary word with a copy of itself shifted right by one place. Needs n − 1 XOR gates, all working in parallel.

GRAY TO BINARY

B_{n - 1} = G_{n - 1}, B_{i} = B_{i + 1} \oplus G_{i} = G_{n - 1} \oplus G_{n - 2} \oplus \dots \oplus G_{i}

Each binary bit is the running XOR of the Gray bits from the MSB down. Built as a chain, the delay is up to n − 1 XOR delays.

BCD TO EXCESS-3

E_{3} E_{2} E_{1} E_{0} = B_{3} B_{2} B_{1} B_{0} + 0011

Applied to each BCD digit, valid for digits 0 to 9. Excess-3 is self-complementing: complementing every bit of a digit's Excess-3 code gives the Excess-3 code of its 9's complement.

2:1 AND 4:1 MUX

Y_{2 : 1} = \overline{S} I_{0} + S I_{1}, Y_{4 : 1} = \overline{S_{1}} \overline{S_{0}} I_{0} + \overline{S_{1}} S_{0} I_{1} + S_{1} \overline{S_{0}} I_{2} + S_{1} S_{0} I_{3}

$S_{1}$ is the MSB of the select code.

GENERAL MUX WITH N SELECT LINES

Y = k = 0 \sum 2^{n} - 1 m_{k} I_{k}

$m_{k}$ is the k-th minterm of the select variables and $\sum$ means OR. An enable input E, where present, multiplies the whole expression.

DEMUX WITH N SELECT LINES

Y_{k} = m_{k} \cdot D, k = 0, 1, \dots, 2^{n} - 1

$m_{k}$ is the k-th minterm of the select lines. A 1: $2^{n}$ DEMUX is the same circuit as an n-to- $2^{n}$ decoder whose enable input carries the data.

MUX TREE

N_{MUX} = ⌈ \frac{N - 1}{k - 1} ⌉ (k:1 MUXes to build an N:1 MUX)

N and k are powers of 2. Each k:1 MUX cuts the number of candidate signals by at most k − 1. When N is a power of k the division is exact and the MUXes form a full tree: 16:1 from 4:1 needs 4 + 1 = 5, 8:1 from 2:1 needs 7, 64:1 from 4:1 needs 21. Otherwise the last MUX has unused inputs: 32:1 from 4:1 needs 8 + 2 + 1 = 11. The same count holds for a 1:N DEMUX built from 1:k DEMUXes.

DECODER OUTPUTS

Y_{k} = E \cdot m_{k} (active-high), \overline{Y_{k}} = \overline{E \cdot m_{k}} (active-low)

$m_{k}$ is the k-th minterm of the inputs. With $E = 1$ , an active-low output is the maxterm $M_{k} = \overline{m_{k}}$ .

FUNCTION FROM A DECODER

F = k \in F \sum Y_{k} (active-high outputs, OR gate) = \overline{k \in F \prod \overline{Y_{k}}} (active-low outputs, NAND gate) = k \in / F \prod \overline{Y_{k}} (active-low outputs of the 0-minterms, AND gate)

The decoder must be enabled. $\sum$ means OR, $\prod$ means AND, and $\overline{Y_{k}}$ is the active-low output line. A NOR gate on the active-high outputs of the 0-minterms also gives $F$ . Use the 0-minterm form when $F$ has more 1s than 0s, because the gate then needs fewer inputs.

8:3 ENCODER (OCTAL TO BINARY)

Y_{2} = D_{4} + D_{5} + D_{6} + D_{7}, Y_{1} = D_{2} + D_{3} + D_{6} + D_{7}, Y_{0} = D_{1} + D_{3} + D_{5} + D_{7}

Valid only when exactly one input is 1. $D_{0}$ does not appear, so ' $D_{0}$ active' and 'no input active' both give 000.

4:2 PRIORITY ENCODER (D3 HIGHEST PRIORITY)

Y_{1} = D_{3} + D_{2}, Y_{0} = D_{3} + \overline{D_{2}} D_{1}, V = D_{3} + D_{2} + D_{1} + D_{0}

Active-high inputs and outputs. $V = 0$ means no input is active, and $Y_{1} Y_{0}$ should then be ignored.

ROM SIZE

ROM size = 2^{n} \times m bits

n is the number of input variables (address lines) and m the number of output functions (word length). All $2^{n}$ words count, even if some input combinations never occur.

PLA PROGRAMMABLE CONNECTIONS

N_{links} = 2 nk + k m

For n inputs, k product terms and m outputs. The AND array connects each term to any of the 2n true and complemented literals; the OR array connects each output to any term. Add m if each output has a programmable inverter.

ARRIVAL TIME AND CIRCUIT DELAY

t_{out} = i max (t_{in, i}) + t_{p d}, T = outputs max t_{out}

Apply this gate by gate from the inputs to the outputs. T is the delay along the longest path.

Where this was asked: 2018 (1), 2020 (2), 2022 (2), 2023 (1), 2024 (3), 2025 (2), 2026 (1). See the 12 previous-year questions on Combinational. This shows what was asked, not what will be asked.

KEEP GOING

Combinational: the notes and 12 solved previous-year questions