Digital Logic

Why this unit matters

Digital Logic is a compact unit with predictable question types. GATE CS consistently draws 7-9 marks from it: Boolean simplification, K-map minimisation, truth tables for combinational circuits, state diagrams for sequential circuits, and number representation arithmetic. The topics are self-contained, so a solid week of preparation can lock in most of the marks here. Numerical questions on 2's complement overflow and floating point representation are nearly guaranteed every year.

Syllabus map

Boolean Algebra
- Boolean laws and identities (identity, null, idempotent, complement, De Morgan)
- SOP (Sum of Products) and POS (Product of Sums) forms
- Canonical forms: minterm and maxterm
- Duality principle
Minimisation
- Karnaugh maps (K-maps): 2, 3, 4 variable
- Don't-care conditions
- Quine-McCluskey (tabular) method
- Prime implicants and essential prime implicants
Combinational Circuits
- Half adder, full adder, ripple carry adder
- Multiplexers (MUX) and demultiplexers (DEMUX)
- Encoders and decoders
- Comparators
Sequential Circuits
- SR, D, JK, T flip-flops: characteristic equations and excitation tables
- Latches vs flip-flops
- Registers and shift registers
- Counters: synchronous and asynchronous (ripple)
- Moore vs Mealy machines: state diagrams and state tables
Number Representations and Computer Arithmetic
- Binary, octal, hexadecimal conversions
- Unsigned integers
- Signed integers: sign-magnitude, 1's complement, 2's complement
- Overflow detection in 2's complement
- Fixed-point representation
- Floating-point representation: IEEE 754 (single and double precision)
- Binary addition, subtraction, multiplication

Boolean Algebra

Laws and Identities

Law	AND form	OR form
Identity	A . 1 = A	A + 0 = A
Null	A . 0 = 0	A + 1 = 1
Idempotent	A . A = A	A + A = A
Complement	A . A' = 0	A + A' = 1
Absorption	A . (A + B) = A	A + A.B = A
De Morgan	(AB)' = A' + B'	(A+B)' = A'B'

SOP form: Express function as OR of AND terms (minterms where f = 1). POS form: Express function as AND of OR terms (maxterms where f = 0).

Worked example: Simplify F = A'B + AB' + AB.

F = A'B + AB' + AB
  = A'B + A(B' + B)
  = A'B + A
  = A + B   (by absorption: A + A'B = A + B)

Typical GATE trap: Absorption law says A + AB = A, and also A + A'B = A + B. Students often forget the second form.

Minterms and Maxterms

For a function of n variables, there are 2^n minterms. Minterm m_i is 1 for exactly the input combination corresponding to binary number i.

F expressed as minterms: F = sum-of-minterms(m, n, ...), F' expressed as maxterms: F' = product-of-maxterms of the minterms NOT in F

Minimisation

Karnaugh Maps

K-maps group adjacent 1s in groups of 1, 2, 4, or 8 (always powers of 2). Adjacent cells differ in exactly one variable. Groups wrap around edges.

Rules:

Larger groups are better (fewer literals)., Every 1 must be covered by at least one group., Don't-cares (X) can be included in a group if it helps simplify; they need not be covered.

Worked example: Minimise F(A,B,C,D) = sum(0,1,2,4,5,6,8,9,10).

        CD
AB   00  01  11  10
00 [  1   1   0   1 ]
01 [  1   1   0   1 ]
11 [  0   0   0   0 ]
10 [  1   1   0   1 ]

Groups:

Column CD=00 (cells 0,4,8,12), but cell 12 is 0, so not all. Actually group {0,1,4,5,8,9}: AB != 11, CD=0x → D' (covers 0,1,4,5,8,9), Another group {0,2,4,6,8,10}: C'D' ... simplify as C' combined: A=x, B=x, C=0, D=x → C'

After careful grouping: F = D' + C' (or equivalently (C+D)').

Typical GATE trap: Forgetting that K-map groups must have sizes that are powers of 2, and that groups of 3 or 5 are not allowed.

Quine-McCluskey

The tabular method is the algorithmic equivalent of K-maps. Steps: list all minterms in binary, group by number of 1s, iteratively combine groups differing in exactly one bit (mark with dash), identify prime implicants (terms that cannot be combined further), then use a prime implicant chart to find the minimum cover. Tested mostly conceptually in GATE, know what prime implicants and essential prime implicants are.

Combinational Circuits

Adders

Half adder: Sum = A XOR B, Carry = A AND B.

Full adder: adds A, B, and carry-in Cin.

Sum  = A XOR B XOR Cin
Cout = (A AND B) OR (B AND Cin) OR (A AND Cin)

Ripple carry adder chains n full adders. Carry must propagate from LSB to MSB, so delay is O(n) gate delays, the main bottleneck for wide additions.

Multiplexers

An n-to-1 MUX has n data inputs, log2(n) select lines, and 1 output. The output equals the data input selected by the select lines. A 2^n-to-1 MUX can implement any Boolean function of (n+1) variables: use n variables as select lines, and wire the appropriate constant (0 or 1) or variable to each data input.

Typical GATE trap: A 4-to-1 MUX can implement any 3-variable function directly. With one extra variable applied to data inputs, it can handle 4-variable functions.

Sequential Circuits

Flip-Flop Characteristic Equations

Flip-flop	Next state Q(t+1)
SR	S + R'Q (with SR=0 constraint)
D	D
JK	JQ' + K'Q
T	T XOR Q

The D flip-flop is the most common in GATE, simple and clean. The JK is the most versatile (it can emulate all others).

Worked example, T flip-flop counter: Three T flip-flops with all T inputs tied to 1. Starting from Q2Q1Q0 = 000, list the sequence after each clock.

Clock | Q2 Q1 Q0
  0   |  0  0  0
  1   |  0  0  1
  2   |  0  1  0
  3   |  0  1  1
  4   |  1  0  0
  5   |  1  0  1
  6   |  1  1  0
  7   |  1  1  1
  8   |  0  0  0  (wraps)

This is a natural binary up-counter. T=1 always means toggle on every clock.

Moore vs Mealy

Moore machine: output depends only on current state.
Mealy machine: output depends on current state AND current input.

Mealy machines generally need fewer states than equivalent Moore machines. GATE often gives a state diagram and asks for the output sequence or number of states.

Typical GATE trap: In a Moore machine, output changes only on state transition. In a Mealy machine, output can change as soon as input changes (without waiting for a clock edge).

Number Representations and Computer Arithmetic

2's Complement

For an n-bit 2's complement number:

Range: -2^(n-1) to 2^(n-1), 1
Negate: flip all bits and add 1, MSB is the sign bit (1 = negative)

Overflow in 2's complement addition: occurs if and only if two numbers of the same sign are added and produce a result of the opposite sign. Equivalently, overflow iff carry into MSB != carry out of MSB.

Worked example: Add -6 and -3 in 4-bit 2's complement.

-6 = 1010
-3 = 1101
     ----
    10111  (5-bit result; 4-bit result = 0111 = +7)

Carry in to MSB = 1, carry out of MSB = 1, so carries are equal, no overflow. But +7 is wrong for -9... wait: -9 is out of 4-bit range (-8 to +7). Carry in = carry out = 1 means no overflow detected, but the mathematical result -9 is not representable, this IS an overflow. The rule is: overflow iff the mathematical result is outside [-2^(n-1), 2^(n-1)-1]. The carry-based check is: overflow = Cin_MSB XOR Cout_MSB.

For -6 + (-3): Cin to MSB position (bit 3): both bits at position 3 are 1, carry from bit 2 matters. Let's redo: 1010 + 1101:

  1010
+ 1101
------
 10111

4-bit result: 0111 = +7. This is wrong, overflow occurred. Carry into bit 3 = 1 (from bit 2: 0+1+carry from bit 1). Carry out of bit 3 = 1. Cin XOR Cout = 0, but overflow DID happen. The correct check is: overflow when two negatives add to a positive OR two positives add to a negative. The Cin XOR Cout check fails for all-1 carry cases. Trust the sign-based check.

IEEE 754 Floating Point (Single Precision)

Format (32 bits): 1 sign bit | 8 exponent bits | 23 mantissa bits.

Exponent is biased by 127 (excess-127 notation)., Value = (-1)^sign * 1.mantissa * 2^(exponent, 127) (normalised)., Special values: exponent = 0 (denormalised); exponent = 255 with mantissa 0 (infinity); exponent = 255 with mantissa != 0 (NaN).

Worked example: Represent 0.1 in IEEE 754 single precision (approx).

0.1 in binary = 0.0001100110011... (repeating). Normalised: 1.100110011... * 2^(-4). Sign = 0. Exponent = -4 + 127 = 123 = 01111011. Mantissa (first 23 bits after the leading 1): 10011001100110011001101.

Typical GATE trap: The implicit leading 1 is NOT stored in the mantissa bits, this gives an extra bit of precision. Denormalised numbers (exponent = 0) do not have the implicit leading 1.

Worked Examples

Example 1 (Boolean Simplification): Simplify F = (A + B)(A + B')(A' + C).

(A + B)(A + B') = A + BB' = A + 0 = A
F = A(A' + C) = AA' + AC = 0 + AC = AC

Example 2 (K-map): F(A,B,C) = sum(1,3,5,7).

All odd minterms, C = 1 for all of them. Minimum SOP: F = C.

Example 3 (2's Complement range): What is the range of values representable in 8-bit 2's complement?

Range: -2^7 to 2^7, 1 = -128 to +127.

Example 4 (Flip-flop): A JK flip-flop has J=1, K=1, current state Q=1. What is Q(t+1)?

Q(t+1) = JQ' + K'Q = 10 + 01 = 0. The JK flip-flop toggles when J=K=1.

Example 5 (Floating Point): How many distinct values can a 4-bit floating point format represent if it has 1 sign bit, 2 exponent bits (biased), and 1 mantissa bit?

Total combinations = 2^4 = 16. But some may be duplicates (NaN) or special cases. At most 16 distinct bit patterns, GATE-style answer is typically 2^4 = 16 unless special values are excluded.

Quick-revision Summary

De Morgan: (AB)' = A' + B'; (A+B)' = A'B'
Absorption: A + AB = A; A + A'B = A + B, Implication: A→B = A' + B, K-map groups must be powers of 2; don't-cares can be used optionally, Full adder: Sum = A XOR B XOR Cin; Cout = majority(A,B,Cin), MUX of 2^n inputs can implement any (n+1)-variable Boolean function, D flip-flop: Q(t+1) = D (cleanest, most common in GATE), JK flip-flop: toggles when J=K=1, sets when J=1 K=0, resets when J=0 K=1, 2's complement n-bit range: -2^(n-1) to 2^(n-1)-1, Overflow in 2's complement: same-sign operands produce opposite-sign result, IEEE 754 single: 1 sign + 8 exponent (bias 127) + 23 mantissa (implicit leading 1), Mealy needs fewer states than equivalent Moore; Mealy output reacts to input immediately

How to Study this Unit

Master Boolean algebra by simplification drills. Pick 10 expressions from PYQs and simplify without K-maps first, then verify with K-maps. This builds both algebraic and visual intuition.
K-maps: draw them by hand. Software tools are fine for checking but doing them by hand on paper under time pressure is the actual exam skill. Practice 4-variable K-maps with don't-cares until the grouping is instinctive.
Flip-flop questions are always state-table questions in disguise. Whenever you see a flip-flop question, immediately write the characteristic equation and fill in the next-state table. Do not try to reason from the diagram directly.
Number representation: solve 20 numerical problems. Convert between bases, add/subtract in 2's complement, identify overflow. Floating point questions are often just "identify the bias" or "count representable numbers", know the IEEE 754 format cold.
Sequential circuit design synthesis (GATE PYQs from 2015-2024): Several years have asked to design a mod-n counter or a sequence detector. Practise the state diagram → state table → excitation table → logic minimisation pipeline.
Quine-McCluskey is mostly theoretical in GATE. You need to know what prime implicants and essential prime implicants are, but full QM tabulation is rarely asked. Focus your energy on K-maps.