Short notes: Digital Logic
Every topic in revision form: the key ideas, formulas, the question types GATE asks, and the traps. Read it the night before.
Quick marks: range of an n-bit representation, 2's complement conversion, and spotting overflow. Almost never anything harder than that.
- Positional number systems and base conversion. A digit string dₙ…d₁d₀.d₋₁… in base r has value Σ dᵢ·rⁱ. Integer to base r: divide repeatedly by r and read remainders bottom to top. Fraction to base r: multiply repeatedly by r and read the integer parts top to bottom. Binary ↔ octal groups 3 bits, binary ↔ hex groups 4 bits, counted outward from the radix point. A decimal fraction like 0.1 has no finite binary form. Unknown-base puzzles such as (121)ᵣ = (144)₈ are solved by writing both sides as polynomials in r.→ Value = sum of digit × base^position; group bits by 3 for octal and 4 for hex.
- Signed numbers: sign-magnitude, 1's and 2's complement. With n bits: sign-magnitude and 1's complement cover −(2ⁿ⁻¹ − 1) … +(2ⁿ⁻¹ − 1) and both have two zeros. 2's complement covers −2ⁿ⁻¹ … +(2ⁿ⁻¹ − 1) with a single zero, so there is one extra negative number. To negate in 2's complement: invert all bits and add 1 (or copy bits up to and including the first 1 from the right, invert the rest). Sign-extend by copying the MSB. The weight of the MSB is −2ⁿ⁻¹.→ Only 2's complement has a single zero and an extra negative number.
- Binary addition, subtraction and overflow. A − B is computed as A + (2's complement of B) with carry-in 1 added to the inverted B. Signed (2's complement) overflow happens iff the carry into the MSB differs from the carry out of the MSB, or equivalently when two operands of the same sign give a result of the opposite sign. Adding operands of opposite signs can never overflow. For unsigned numbers the carry out of the MSB signals the error (for subtraction, the absence of a carry means a borrow). In 1's complement the end-around carry is added back.→ Overflow = C_in(MSB) ⊕ C_out(MSB); opposite-sign additions never overflow.
- Codes: BCD, Gray, excess-3 and bit counting. BCD uses 4 bits per decimal digit (patterns 1010 to 1111 are invalid); after adding two BCD digits, add 6 (0110) if the sum exceeds 9 or there was a carry. Excess-3 is BCD + 3 and is self-complementing. Gray code changes exactly one bit between consecutive numbers: g = b ⊕ (b ≫ 1); binary from Gray: b₀ = g₀, bᵢ = bᵢ₋₁ ⊕ gᵢ. The number of bits to represent N distinct values is ⌈log₂ N⌉; a decimal number with d digits needs about ⌈d·log₂10⌉ ≈ 3.32 d bits.→ Gray: one bit changes per step; BCD digits stop at 9, add 6 to fix a sum over 9.
Formulas
What GATE asks
- ★★★Range or count of values in an n-bit representation. Which representation has two zeros, what is the most negative value, how many distinct values.
- ★★★Add or subtract in 2's complement and detect overflow. Do the addition on bit patterns, then compare the carries into and out of the MSB.
- ★★★Base conversion and unknown-base equations. Convert between bases or solve for the base r in an arithmetic identity.
- ★★★Representation conversions (sign-extension, comparison of patterns). Interpret a given bit pattern under a chosen representation and compare.
Traps
The core of the subject: simplify an expression, count minterms, minimise with a K-map or build everything from NAND. Several marks every year.
- Boolean laws, duality and De Morgan. Identity, null, idempotent (A + A = A), complement (A·A′ = 0), involution, commutative, associative, distributive in both directions (A + BC = (A + B)(A + C)). Absorption: A + AB = A, A(A + B) = A. Consensus: AB + A′C + BC = AB + A′C. A + A′B = A + B. De Morgan: (A + B)′ = A′B′, (AB)′ = A′ + B′. Duality: swap + with · and 0 with 1; every valid identity stays valid. The complement of F is found by dualising and complementing each literal.→ Absorb, redundancy, consensus, De Morgan: four tools cover nearly every simplification.
- Minterms, maxterms and canonical forms. With n variables there are 2ⁿ minterms (a product containing every variable once; mᵢ = 1 only on row i) and 2ⁿ maxterms (a sum; Mᵢ = 0 only on row i, and Mᵢ = mᵢ′). F = Σm(rows where F = 1) = ΠM(rows where F = 0). The sum of all minterms is 1. The canonical SOP of F′ uses the rows missing from F. A function with k minterms has 2ⁿ − k maxterms. XOR of n variables has 2ⁿ⁻¹ minterms (the odd-parity rows).→ Σm lists the 1 rows, ΠM lists the 0 rows; together they cover all 2ⁿ rows.
- K-map minimisation with don't cares. A K-map lists the truth table in Gray-code order so physical neighbours differ in one variable (edges wrap around). Group 1s (for SOP) in rectangles of size 1, 2, 4, 8, 16 (powers of two), as large as possible; a group of 2ᵏ cells eliminates k variables. Don't-care cells may be used to enlarge groups but need not be covered. Prime implicant: a group that cannot be enlarged. Essential: covers a 1 that no other prime implicant covers. For POS, group the 0s and complement the result of each group. The Quine–McCluskey method does the same by tabulation.→ Group 1s (or 0s for POS) in powers of two; edges wrap; X cells are optional helpers.
- Universal gates: NAND and NOR. NAND alone (or NOR alone) can build every Boolean function, so each is functionally complete. NAND: NOT = NAND(A, A); AND = NOT(NAND); OR = NAND(A′, B′); XOR needs 4 NAND gates. NOR: NOT = NOR(A, A); OR = NOT(NOR); AND = NOR(A′, B′); XOR needs 5 NOR gates. Convert an SOP expression to NAND-NAND (two levels) and a POS expression to NOR-NOR. AND, OR are associative; NAND and NOR are not associative. XOR is associative and commutative; XNOR = (A ⊕ B)′ = A ⊕ B′.→ NAND and NOR are each functionally complete; XOR costs 4 NANDs or 5 NORs.
- Counting functions, self-dual functions and completeness. There are 2^(2ⁿ) distinct Boolean functions of n variables (16 for n = 2, 256 for n = 3). A function is self-dual if F(x₁…xₙ) = F′(x₁′…xₙ′): the rows i and 2ⁿ − 1 − i must have opposite values, so there are 2^(2ⁿ⁻¹) of them. A set of operations is functionally complete if it contains functions that are non-monotone, non-self-dual, non-linear, and neither 0-preserving nor 1-preserving. {AND, NOT}, {OR, NOT}, {NAND}, {NOR} are complete; {AND, OR} and {XOR, AND} (without constants) are not.→ 2^(2ⁿ) functions, 2^(2ⁿ⁻¹) self-dual; NAND or NOR alone is complete.
Formulas
What GATE asks
- ★★★Simplify an expression or find its minimal SOP/POS. K-map with don't cares, or algebra with absorption/consensus.
- ★★★Count minterms, prime implicants or essential prime implicants. Fill the K-map and count groups; watch the wrap-around edges.
- ★★★Which function does the given circuit/expression compute?. Write the truth table and match; recognise XOR, majority, parity.
- ★★★Universal gates and functional completeness. How many NAND gates for XOR; which sets of gates are complete.
- ★★★Number of distinct (self-dual) functions. 2^(2ⁿ) and 2^(2ⁿ⁻¹).
Traps
Adders, multiplexers and decoders are asked almost every year: implement a function with a MUX or decoder, or count gates and delay.
- Half adder, full adder and subtractors. Half adder: S = A ⊕ B, C = AB (1 XOR + 1 AND). Full adder: S = A ⊕ B ⊕ Cin, Cout = AB + Cin(A ⊕ B) = majority(A, B, Cin); built from 2 half adders + 1 OR, so 2 XOR + 2 AND + 1 OR = 5 gates. Half subtractor: D = A ⊕ B, Bout = A′B. Full subtractor: D = A ⊕ B ⊕ Bin, Bout = A′B + (A ⊕ B)′Bin. An adder/subtractor uses XOR gates on B controlled by a mode input M and sets Cin = M.→ Sum = XOR of the three inputs; carry-out = majority of the three inputs.
- Ripple-carry and carry look-ahead adders. A ripple-carry adder of n bits has delay ≈ n × (carry delay of one full adder), roughly 2n gate delays. Carry look-ahead defines generate Gᵢ = AᵢBᵢ and propagate Pᵢ = Aᵢ ⊕ Bᵢ; then Cᵢ₊₁ = Gᵢ + PᵢCᵢ, expanded so every carry comes from Gs, Ps and C₀ in two more gate levels: delay is constant (about 4 gate delays) but fan-in grows with n, so large adders use groups (4-bit blocks with block P and G). Carry-select and carry-skip adders are other speed-ups.→ Ripple: delay proportional to n. Look-ahead: Cᵢ₊₁ = Gᵢ + PᵢCᵢ expanded, constant delay.
- Multiplexers as function generators. A 2ⁿ:1 MUX has n select lines and implements F = Σ mᵢ·Iᵢ. To implement an (n + 1)-variable function with a 2ⁿ:1 MUX, connect n variables to the selects and set each data input to 0, 1, the last variable X or X′ (look at the pair of rows). A 4:1 MUX can be built from three 2:1 MUXes (2 + 1); a 2ⁿ:1 MUX needs 2ⁿ − 1 MUXes of 2:1. A MUX is also a universal element: with constants and inverters any function can be made. Tri-state buses are an alternative to MUXes.→ Pair the rows that differ in the last variable: 00 → 0, 11 → 1, 01 → X, 10 → X′.
- Decoders and encoders. An n:2ⁿ decoder produces all 2ⁿ minterms (one output high); any function is then an OR of the right outputs, and many functions can share one decoder. With active-low outputs (74138) use a NAND for the OR. A larger decoder is built from smaller ones using enable inputs (4:16 from two 3:8 plus the MSB as enable select). A demultiplexer is a decoder whose enable is the data input. An encoder does the reverse (2ⁿ inputs, n outputs); a priority encoder resolves several active inputs by picking the highest priority and adds a valid output.→ Decoder = all the minterms; function = OR of its minterm lines.
- ROM, PLA, PAL and comparators. A ROM with k address lines and m data bits stores 2ᵏ × m bits and is a fixed AND plane (full decoder) feeding a programmable OR plane. A PLA has a programmable AND plane (only the product terms needed) and a programmable OR plane, so it is smaller than a ROM for sparse functions. A PAL programs only the AND plane. A magnitude comparator for n bits uses per-bit equality Eᵢ = (Aᵢ ⊕ Bᵢ)′; A = B is the AND of all Eᵢ; A > B is the first bit from the MSB where Aᵢ = 1 and Bᵢ = 0 with all higher bits equal. A parity generator is a chain/tree of XOR gates (n − 1 gates for n bits).→ ROM: fixed AND, programmable OR. PLA: both programmable. ROM size = 2^address × width.
- Static hazards. A static-1 hazard is a momentary 0 glitch when the output should stay 1; it appears in a two-level SOP when two adjacent 1s on the K-map are covered by different groups (e.g. F = AB + A′C when B = C = 1 and A changes). Fix it by adding the redundant consensus term (BC). A static-0 hazard is the dual in POS. A dynamic hazard is several glitches while the output should change once and needs three or more levels of logic. A fully redundant-free SOP built from all prime implicants is hazard-free for single-input changes.→ Adjacent 1s in different groups cause a static-1 hazard; add the consensus term to fix it.
Formulas
What GATE asks
- ★★★Implement a function with a MUX or decoder. Find the data inputs of a 4:1 or 8:1 MUX, or the OR of decoder outputs.
- ★★★What does this combinational circuit compute?. Trace the gates, build the truth table, recognise adder/subtractor/parity/comparator.
- ★★★Delay or gate count of adders. Ripple versus look-ahead, number of gates, critical path through the carry chain.
- ★★★Hazards, ROM/PLA size, encoder behaviour. Spot the glitch, size a ROM, read a priority encoder table.
Traps
Characteristic equations, excitation tables and flip-flop conversion are direct, predictable questions; the next-state tables feed every counter problem.
- SR latch: the basic memory cell. Two cross-coupled NOR gates form an SR latch: S = 1 sets Q = 1, R = 1 resets Q = 0, S = R = 0 holds, and S = R = 1 is forbidden (both outputs 0, and releasing both together causes a race). The NAND version has active-low inputs: S′ = 0 sets, R′ = 0 resets, 11 holds, 00 is forbidden. Adding an enable (clock) gives a gated latch. Characteristic equation: Q⁺ = S + R′Q with SR = 0. A latch is level sensitive; a flip-flop changes only on a clock edge.→ NOR latch: forbidden 11. NAND latch: forbidden 00 (inputs are active low).
- D, JK and T flip-flops. D: Q⁺ = D (stores the input). JK: Q⁺ = JQ′ + K′Q; 00 hold, 01 reset, 10 set, 11 toggle (no forbidden input). T: Q⁺ = T ⊕ Q; T = 1 toggles, T = 0 holds; with T = 1 the output frequency is half the clock. SR flip-flop: as for the latch, 11 not allowed. JK with J = K = 1 acts as a T flip-flop, and JK with K = J′ acts as a D flip-flop.→ D copies, T toggles when 1, JK has all four behaviours, SR forbids 11.
- Excitation tables and flip-flop conversion. The excitation table tells which inputs are needed for a wanted transition Q → Q⁺. SR: 0→0: S=0 R=x; 0→1: S=1 R=0; 1→0: S=0 R=1; 1→1: S=x R=0. JK: 0→0: 0x; 0→1: 1x; 1→0: x1; 1→1: x0. D: input = Q⁺. T: input = Q ⊕ Q⁺. Conversion: to build flip-flop X from flip-flop Y write a table of (Q, X inputs) → Q⁺, find Y's inputs from its excitation table, minimise. Examples: T from JK: J = K = T. D from JK: J = D, K = D′. JK from T: T = JQ′ + KQ. T from D: D = T ⊕ Q.→ Excitation: JK 0x, 1x, x1, x0; D = Q⁺; T = Q ⊕ Q⁺. J = K = T makes a T FF.
- Triggering: level, edge, master-slave and race-around. A level-triggered JK/T latch with J = K = 1 toggles repeatedly while the clock is high: the race-around problem if the clock pulse is longer than the propagation delay. Cures: edge triggering or a master-slave arrangement (master follows the input while the clock is high, slave copies on the falling edge), or keeping the pulse shorter than t_pd. In a master-slave JK the inputs are sampled during the high level, so "1s catching" can occur. Edge-triggered flip-flops sample only at the active edge. Asynchronous PRESET/CLEAR override the clock.→ Race-around: level-triggered, J = K = 1, pulse longer than t_pd; edge or master-slave fixes it.
Formulas
What GATE asks
- ★★★Next state / output sequence of a circuit of flip-flops. Apply the characteristic equations edge by edge; a short sequence of Q values.
- ★★★Flip-flop conversion and excitation inputs. Which gates make a T flip-flop out of a JK, what are J and K for a transition.
- ★★★Latch behaviour and forbidden states. What happens for S = R = 1 in NOR or NAND latches.
- ★★★Race-around and master-slave. Why level-triggered JK fails; how master-slave fixes it.
Traps
A counter or sequential circuit shows up in almost every paper: find the modulus, the sequence of states, the number of flip-flops or the machine behaviour.
- Shift registers, ring and Johnson counters. An n-bit shift register moves data one place per clock; a serial bit takes n clocks to travel through. A ring counter feeds Q₍ₙ₋₁₎ back to D₀ and, with one 1 preloaded, cycles through n states. A Johnson (twisted ring) counter feeds Q′₍ₙ₋₁₎ back and cycles through 2n states (0000, 1000, 1100, 1110, 1111, 0111, 0011, 0001). A ring counter wastes 2ⁿ − n states, a Johnson 2ⁿ − 2n. Johnson states decode with only 2-input gates.→ Ring: n states. Johnson: 2n states (invert the fed-back bit).
- Asynchronous (ripple) counters and mod-n design. In a ripple counter each flip-flop is clocked by the previous output, so Q0 has frequency f/2, Q1 f/4 and so on; n flip-flops make a mod-2ⁿ counter. For mod N (N not a power of two) use ⌈log₂ N⌉ flip-flops and an asynchronous clear when the count reaches N, through a NAND of the 1-bits; the state N appears for a moment (glitch). Down counters clock from Q′. Delay accumulates, so the maximum clock frequency is roughly 1/(n·t_pd) and the outputs are valid only after all stages settle; decoding gates can show glitches.→ n flip-flops give modulus ≤ 2ⁿ; ripple delay = n · t_pd.
- Synchronous counter design. In a synchronous counter all flip-flops share one clock. Procedure: write the sequence, choose the flip-flop type, list for each state the transition and the required inputs from the excitation table, and minimise each input with a K-map using the unused states as don't-cares. Check that unused states lead back into the cycle (self-starting). Example: mod-8 up counter with T flip-flops has T₀ = 1, T₁ = Q₀, T₂ = Q₁Q₀. The number of flip-flops is ⌈log₂ N⌉ for N states.→ Excitation table + K-map + unused states as don't-cares; check self-starting.
- Mealy and Moore machines. In a Moore machine the output depends only on the present state; in a Mealy machine it depends on the state and the current input, so it can react one clock earlier and usually needs fewer states (a sequence detector for 1011 needs 4 Mealy states but 5 Moore states). The next state function is the same kind in both. A Mealy output can change when the input changes between clock edges. With k states you need ⌈log₂ k⌉ flip-flops. An overlapping detector reuses the end of the previous match as the start of the next.→ Moore: output = f(state). Mealy: output = f(state, input), often fewer states.
- State minimisation. Two states are equivalent if they produce the same output for every input and their next states are equivalent. Use partition refinement (or the implication table): first group states with identical outputs, then split any group whose members move to different groups, repeat until stable. Equivalent states are merged, which can reduce the number of flip-flops. In an incompletely specified machine compatible (not equivalent) states are merged, which is harder.→ Partition by outputs, split by next-state groups, merge what survives.
Formulas
What GATE asks
- ★★★Modulus or state sequence of a counter circuit. Trace a ring/Johnson/ripple counter with feedback and read the cycle length.
- ★★★Next state and output of a clocked sequential circuit. Given flip-flops and gates, give the state after a few clocks or the output sequence.
- ★★★Design a synchronous counter / detector. Find the flip-flop inputs, the number of states or flip-flops.
- ★★★Mealy vs Moore and state minimisation. Count states, identify equivalent states, decide which machine type is described.
Traps
6. ⏳ Timing, Delay & Clock Frequency
Medium ●●A few GATE questions ask for the maximum clock frequency or the critical path of a circuit with flip-flops and gate delays; it is a formula plus careful reading.
- Propagation delay and the critical path. Propagation delay t_pd is the time from an input change to the output change. The critical path is the slowest path between two registers (or input and output); its delay sets the speed. Add up the delays of the gates along each path (an output that feeds several paths counts on each); the contamination delay t_cd is the shortest path, used for hold checks. A gate in a chain counts once even if its output also feeds other gates. Reducing the critical path (more parallel logic, look-ahead) is how a circuit is made faster.→ Circuit delay = delay of the longest path; hold uses the shortest.
- Setup, hold and the maximum clock frequency. Between two flip-flops the clock period must satisfy T ≥ t_clk→Q + t_logic(max) + t_setup + t_skew, so f_max = 1/T. The hold condition is t_clk→Q + t_logic(min) ≥ t_hold + t_skew; it does not depend on the clock period (only a faster path or an added delay fixes it). The clock pulse width must be at least the minimum pulse width. For a ripple counter the clock period must exceed n·t_pd plus setup. For a single flip-flop with feedback (like a counter) T ≥ t_clk→Q + t_logic + t_setup.→ T ≥ t_clk→Q + t_logic(max) + t_setup (+ skew); hold does not depend on T.
- Clock skew, metastability and pipelining. Clock skew is the arrival-time difference of the clock at two flip-flops; skew that delays the capturing flip-flop gives extra setup time but may violate hold. Metastability occurs when an asynchronous input changes inside the setup/hold window, leaving the output at an indeterminate level for an unpredictable time; it is handled with two-flip-flop synchronisers, not removed. Pipelining inserts registers to split a long path: the clock period drops to the slowest stage plus register overhead, throughput rises, but latency grows by the register delays.→ Pipelining raises throughput, not latency; metastability is reduced, never eliminated.
Formulas
What GATE asks
- ★★★Maximum clock frequency of a sequential circuit. Add clock-to-Q, the longest gate path and setup time; take the reciprocal.
- ★★★Critical path and delay of a combinational circuit. Find the longest path through a given circuit with given gate delays.
- ★★★Hold violations, skew and metastability (concept). True/false statements on what fixes a hold violation or what a synchroniser does.