Module 9: Electronics · Lesson 9.5 · about 45 min
Combinational logic
Combinational logic at GATE depth: Boolean algebra and De Morgan, NAND and NOR as universal gates, minterms and maxterms, four-variable Karnaugh maps with don't-cares, prime and essential implicants, half and full adders, ripple-carry and carry look-ahead, two's complement subtraction, comparators, multiplexers as function generators, decoders and encoders, hazards, and logic-family numbers: noise margins, fan-out and CMOS power.
Module 9 · about 45 minutes. The JAM digital logic lesson introduces gates, truth tables and number systems. GATE expects fast minimisation with Karnaugh maps, the arithmetic circuits, multiplexer tricks and a few numbers about real logic families. A combinational circuit has no memory: its outputs depend only on its present inputs. Circuits with memory come in lesson 9.6.
1. Boolean algebra
The laws that do most of the work:
De Morgan lets any AND-OR circuit be built from NAND gates alone (NAND-NAND = AND-OR) and any OR-AND circuit from NOR gates alone: NAND and NOR are universal. An inverter is a NAND with its inputs tied; an XOR needs four NANDs.
A function can be written as a sum of minterms (one product term per 1 in the truth table, ) or a product of maxterms (one sum term per 0, ). The two lists are complementary: for three variables.
2. Karnaugh maps
Lay out the map. For four variables, rows AB and columns CD both run 00, 01, 11, 10 (Gray order). The map wraps round: the left column is adjacent to the right, the top row to the bottom, and the four corners form one group.
Draw groups. Rectangles of 1, 2, 4, 8 or 16 cells containing only 1s and don’t-cares (X). A group of 2ᵏ cells gives a product of 4 − k literals: the variables that stay constant over the group.
Prime implicants. Make every group as large as possible. A group that cannot be enlarged is a prime implicant.
Essential primes first. A prime implicant is essential if it alone covers some 1. Take all of them, then cover the remaining 1s with the fewest extra primes. Don’t-cares are used only when they make a group bigger; they never need to be covered.
Worked example 1. . The four corners (0, 2, 8, 10) all have : the term . The central square (5, 7, 13, 15) has : . So , an XNOR of two of the four inputs. This is the figure’s starting map.
Worked example 2. . The column (3, 7, 11, 15) gives , which is essential. Minterm 1 is left; it can join the top row (0, 1, 2, 3, using two don’t-cares) as , or the block 1, 3, 5, 7 (using don’t-care 5) as . Both give a minimal answer with two terms and four literals: or . Minimal covers need not be unique.
Hazards. In , when and changes, one term turns off just before the other turns on, and the output can glitch to 0 (a static-1 hazard). Adding the redundant consensus term covers the transition. On a K-map: any two adjacent 1s not inside a common group can glitch.
3. Arithmetic circuits
Adders. A half adder gives , . A full adder adds a carry in:
A ripple-carry adder chains full adders, and the worst case is a carry generated in bit 0 that must ripple through all of them, so the delay grows as . Carry look-ahead defines generate and propagate , so that , and expands the recursion:
Every carry is then a two-level function of the inputs, computed in parallel; in hierarchical form the delay grows as .
Subtraction uses two’s complement: is + 1, so , which is an adder with XOR gates on the inputs and carry-in 1. With bits the range is to . Overflow happens when two numbers of the same sign give a result of the other sign, which is when the carries into and out of the sign bit differ.
Comparators. Bit equality is XNOR; for words is the AND of the bit XNORs. For magnitude, is decided by the most significant bit where they differ.
4. Multiplexers, decoders and encoders
| Block | Inputs → outputs | What it does |
|---|---|---|
| multiplexer | data, select → 1 | passes the selected data input |
| demultiplexer | 1 data, select → | routes the input to one output |
| decoder | → | one output per minterm; with an OR gate, any function |
| encoder / priority encoder | → | the code of the active (highest-priority) input |
A multiplexer is a universal function generator. Put the variables on the select lines and the truth table on the data inputs, and a mux implements any function of variables. Better: use of variables as selects and put 0, 1, the last variable or its complement on each data input. A 4:1 mux with selects gives with inputs , , , .
5. Real logic families
- noise margins
- `$NM_H = V_{OH} - V_{IH}$` and `$NM_L = V_{IL} - V_{OL}$`: how much noise a valid output can pick up and still be read correctly. Standard TTL: `$V_{OH} = 2.4$`, `$V_{IH} = 2.0$`, `$V_{IL} = 0.8$`, `$V_{OL} = 0.4$` V, so both margins are 0.4 V. CMOS margins are close to `$0.3V_{DD}$` or more.
- fan-out
- how many inputs one output can drive: the smaller of `$I_{OH}/I_{IH}$` and `$I_{OL}/I_{IL}$` for TTL; for CMOS it is limited by speed, since each input adds capacitance
- propagation delay
- time from an input change to the output change; sets the speed of every path
- dynamic power
- `$P = \alpha CV_{DD}^2f$`: each 0 → 1 transition takes `$CV_{DD}^2$` from the supply. CMOS draws almost no static current, so this dominates, and lowering the supply voltage is the strongest lever.
Worked example. A chip switches an effective 1 nF at 2 GHz with activity at 1.0 V: W. At 1.2 V the same work costs 0.29 W.
“The minimal sum of products is unique, and you get it by grouping the biggest blocks first.” Biggest-first can leave you with a redundant group: take essential primes first, then choose among the rest. And many functions have several equally small covers (example 2 above), so an exam asks for the number of terms or literals, or gives options of which more than one may be correct.
- De Morgan; NAND and NOR are universal; consensus .
- K-map: Gray order, wrap-round, groups of 2ᵏ drop variables; essential primes first; don’t-cares only when they help.
- Full adder , ; ripple delay ∝ , look-ahead ∝ .
- Two’s complement: range to ; .
- mux implements any -variable function with inputs 0, 1, x, x′.
- , ; CMOS .
Practise: exam questions on this lesson
Next: lesson 9.6 adds memory: latches, flip-flops, counters and shift registers. The logic simplifier minimises functions of more variables than a K-map can handle.
Check yourself
Sources
- M. M. Mano and M. D. Ciletti, Digital Design, 5th ed. (2013), chapters 1 to 4
- R. J. Tocci, N. S. Widmer and G. L. Moss, Digital Systems, 12th ed. (2017), chapters 3, 4, 6 and 9
- J. F. Wakerly, Digital Design: Principles and Practices, 4th ed. (2006), chapters 3 to 6
- GATE Physics (PH) syllabus, Electronics section, published by the organising IIT each year
Your ticks stay in this browser. Save them as a file on the course home.
Updated 2026-11-22. Not affiliated with the IITs, IISc or the GATE organising institute. The general aptitude part of GATE is not covered here. Check the official GATE website for the current pattern. All questions are original.