Digital Circuits and Computer Organization (GATE EC)

GATE EC syllabus for digital circuits, with number representations, Boolean minimisation, CMOS gates, arithmetic circuits, multiplexers and decoders, flip-flops, counters, FSMs, timing (setup, hold, critical path), data converters, memories and basic computer organization, with solved examples.

Syllabus

Number representations (binary, integer and floating-point); Boolean algebra, Karnaugh maps, logic gates and static CMOS implementations, arithmetic circuits, code converters, multiplexers, decoders; latches and flip-flops, counters, shift registers, finite state machines, propagation delay, setup and hold time, critical path delay; sample and hold, ADCs and DACs; ROM, SRAM, DRAM; machine instructions and addressing modes, ALU, data path and control unit, instruction pipelining.

Key concepts and formulas

Numbers. n-bit 2's complement range: −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1. IEEE 754 single precision: 1 sign bit, 8 exponent bits (bias 127), 23 fraction bits. (The Digital Logic track covers number systems in depth.)

Logic and CMOS. NAND and NOR are universal. A static CMOS gate has a pull-down network of nMOS and a complementary pull-up of pMOS: a k-input NAND has k nMOS in series and k pMOS in parallel (2k transistors). Dynamic power P = αCV_DD²f.

Combinational circuits. A half adder gives S = A ⊕ B, C = AB; a full adder S = A ⊕ B ⊕ C_in, C_out = AB + C_in(A ⊕ B). A ripple-carry adder's delay grows linearly with n; carry look-ahead reduces it. A 2ⁿ:1 MUX can implement any function of n + 1 variables. An n-to-2ⁿ decoder produces all minterms.

Sequential circuits.

Flip-flop	Characteristic equation
D	Q⁺ = D
T	Q⁺ = T ⊕ Q
JK	Q⁺ = JQ̄ + K̄Q
SR	Q⁺ = S + R̄Q (SR = 0)

A mod-N counter needs ⌈log₂N⌉ flip-flops; a ring counter of n flip-flops has n states and a Johnson (twisted ring) counter 2n states. Moore FSM outputs depend only on the state; Mealy outputs also on the inputs.

Timing. For a register-to-register path: T_clk ≥ t_clk-to-q + t_logic,max + t_setup, so f_max = 1/T_clk,min. Hold constraint: t_clk-to-q + t_logic,min ≥ t_hold. The longest such path is the critical path.

Data converters. n-bit resolution V_ref/2ⁿ; a flash ADC needs 2ⁿ − 1 comparators; a successive approximation ADC needs n clock cycles. Quantisation SNR ≈ 6.02n + 1.76 dB for a full-scale sine.

Memories. SRAM (6 transistors per cell, fast, no refresh), DRAM (1 transistor + 1 capacitor, dense, needs refresh), ROM (non-volatile). A memory with A address lines and D data lines stores 2ᴬ × D bits.

Computer organization. Addressing modes (immediate, direct, indirect, register, indexed); pipelining speed-up for k stages and n instructions: nk/(k + n − 1) ideally; hazards (structural, data, control). (The Computer Organization track covers this in depth.)

Worked example

A path has t_clk-to-q = 0.3 ns, logic delay 2.2 ns and setup time 0.5 ns: find the maximum clock frequency. Simulate a 3-bit Johnson counter, and count the transistors in a static CMOS 4-input NAND.

Python

Open in playground

tcq, tlogic, tsu = 0.3, 2.2, 0.5
T = tcq + tlogic + tsu
print(f"Tmin = {T:.1f} ns, fmax = {1000 / T:.2f} MHz")
state = [0, 0, 0]
seen = []
while tuple(state) not in seen:
    seen.append(tuple(state))
    state = [1 - state[-1]] + state[:-1]    # inverted last bit shifts into the first
print("Johnson counter states:", ["".join(map(str, s)) for s in seen], "->", len(seen), "states")
print("static CMOS 4-input NAND transistors:", 2 * 4)
print(f"SQNR of an 8-bit ADC = {6.02 * 8 + 1.76:.2f} dB")

Output

Tmin = 3.0 ns, fmax = 333.33 MHz
Johnson counter states: ['000', '100', '110', '111', '011', '001'] -> 6 states
static CMOS 4-input NAND transistors: 8
SQNR of an 8-bit ADC = 49.92 dB