Unit 5 — Digital Electronics, Programmable Logic & HDL: Complete Exam Notes

§ 5.1Logic Gates

• Basic gates: AND (Y = A·B), OR (Y = A+B), NOT (Y = Ā).
• Universal gates: NAND and NOR — each alone can realize any Boolean function. Counting classics: NOT = 1 NAND; AND = 2; OR = 3; XOR = 4 NAND (5 NOR); XNOR = 5 NAND (4 NOR); half adder = 5 NAND; full adder = 9 NAND.
• XOR: Y = A⊕B = A B̄ + ĀB — "1 when inputs differ"; odd-1s detector for many inputs. Identities: A⊕0 = A, A⊕1 = Ā, A⊕A = 0, A⊕Ā = 1; associative and commutative; controlled inverter (one input as control) — basis of adder/subtractor sharing and parity logic.
• XNOR: equivalence gate, Y = 1 when inputs match; A⊙B = \(\overline{A\oplus B}\).
• Multi-input behaviour: n-input XOR = parity (1 for odd number of 1s); enable/inhibit use of AND (gate open when control = 1) and OR (control = 0).
• Positive vs negative logic: a positive-logic AND is a negative-logic OR (De Morgan duality in hardware).
• Special outputs: open-collector/open-drain (wired-AND, level shifting, shared bus with pull-up), tri-state (0, 1, high-Z — bus multiplexing; enable pin).

§ 5.2Boolean Algebra

• Canonical forms: Sum of Products (SOP, minterms mᵢ, Σm notation) and Product of Sums (POS, maxterms Mᵢ, ΠM); Mᵢ = m̄ᵢ; complement of Σm(list) = Σm(remaining) = ΠM(list).
• n variables → 2ⁿ minterms → \( 2^{2^n} \) possible functions (n = 2 → 16).
• Shannon expansion: f = x·f(x=1) + x̄·f(x=0) — the theoretical basis of MUX-based implementation (§5.6) and FPGA LUTs (§5.15).
• Functionally complete sets: {AND, OR, NOT}, {NAND}, {NOR}, {AND, XOR, 1} (Reed–Muller).

§ 5.3Minimization: K-Maps & Quine–McCluskey

Karnaugh map

• Truth table folded so adjacent cells differ in one variable (Gray-code ordering 00, 01, 11, 10); groups of 2ᵏ adjacent 1s eliminate k variables. Map edges wrap (left–right, top–bottom; the four corners are mutually adjacent).
• Procedure: cover every 1 with the largest possible power-of-two groups (octets → quads → pairs), as few groups as possible; overlap allowed; read each group as the product of unchanging variables.
• Prime implicant (PI): a group not contained in any larger group; essential PI (EPI): covers at least one 1 no other PI covers — EPIs must appear in every minimal cover (counting PIs/EPIs is a standard MCQ).
• Don't-cares (X/d): output irrelevant for unused input combinations (e.g., BCD codes 1010–1111) — include in groups when they enlarge a group, ignore otherwise.
• POS minimization: group the 0s, read as maxterms (or minimize f̄ and complement).
• Practical limit ~4–5 variables (5-var = two linked 4-var maps).
• Hazards link: a static-1 hazard exists where two adjacent groups are not bridged; add the consensus (redundant) group to kill the glitch — full story in §5.17.

Quine–McCluskey (tabular) method

• Algorithmic, computer-suitable, any number of variables: (1) list minterms grouped by 1-count; (2) repeatedly combine pairs differing in one bit (mark with −) until no more → prime implicants; (3) PI chart: select essential PIs, cover the rest minimally (Petrick's method for cyclic charts).
• Guaranteed minimal SOP; cost: exponential table growth — heuristics (Espresso) used in real EDA.

§ 5.4Logic Families

• TTL internals: multi-emitter input transistor, phase splitter, totem-pole output (never parallel totem-poles!); open-collector variant for wired-AND/bus; tri-state for buses. Floating TTL input reads HIGH (but never rely on it). Subfamilies: L, H, S (Schottky clamp prevents saturation), LS (the classic 2 mW/10 ns), AS, ALS, F.
• CMOS: complementary pair per §2.16 — static power ≈ 0, dissipation = αfC_LV²; unused inputs must be tied (floating gates drift, both devices conduct); handle ESD; 74HCT = HC with TTL-compatible thresholds (the interface family).
• ECL: differential current switch biased away from saturation → no storage delay; complementary outputs free; constant supply current (quiet supplies, but hot); used where raw speed mattered (mainframes, instrumentation, fiber front ends).
• Interfacing: TTL→CMOS (5 V): pull-up resistor to lift V_OH; CMOS→TTL: HC can drive LS directly (current check); level shifters between 3.3/5 V domains.
• Speed–power champions: lowest power = CMOS; fastest = ECL; best speed–power product historically = ALS/HC era; modern deep-submicron CMOS wins everything.

§ 5.5Combinational Circuits: Adders & Arithmetic

• Half adder: S = A⊕B, C = AB. Full adder: S = A⊕B⊕C_in; C_out = AB + C_in(A⊕B) — built from two HAs + OR; 1-of-9-NAND classic.
• Half subtractor: D = A⊕B, Borrow = ĀB; full subtractor analogous. Adder-as-subtractor: XOR each B bit with a SUB control and set C_in = SUB → 2's-complement subtraction with the same hardware (the controlled-inverter payoff).
• Ripple-carry adder: n cascaded FAs; worst-case delay ∝ n (carry ripples). Carry-lookahead (CLA): generate \(G_i = A_iB_i\), propagate \(P_i = A_i\oplus B_i\); \( C_{i+1} = G_i + P_iC_i \) expanded in parallel → ~constant 2-level carry per 4-bit block (74182 unit); delay O(log n) with block lookahead.
• BCD adder: binary sum > 9 or carry → add 6 (0110) correction; detection logic S = C_out + S₃S₂ + S₃S₁.
• Magnitude comparator (7485): A>B, A=B, A<B outputs; equality = AND of XNORs; cascadable.
• Parity generator/checker (74180/280): XOR tree → even/odd parity bit; single-error detection.
• Code converters: binary↔Gray — the two formulas every paper expects:
  Gray-code conversions $$ \textbf{Bin→Gray: } G_{n-1} = B_{n-1},\ \ G_i = B_{i+1} \oplus B_i \qquad \textbf{Gray→Bin: } B_{n-1} = G_{n-1},\ \ B_i = B_{i+1} \oplus G_i $$
  BCD↔excess-3 (self-complementing code), BCD→7-segment (7447 active-low/7448 active-high decoders).
• Combinational = output depends only on present inputs (no memory) — contrast with §5.7 onward.

§ 5.6MUX, DEMUX, Encoders & Decoders

Multiplexer (data selector)

• 2ⁿ inputs → 1 output via n select lines: \( Y = \sum_{i} m_i(\text{select})\,D_i \). ICs: 74151 (8:1), 74153 (dual 4:1), 74157 (quad 2:1).
• Function implementation (guaranteed exam item): any n-variable function on a 2ⁿ:1 MUX directly (minterm per input), or on a 2ⁿ⁻¹:1 MUX using n−1 variables as selects and feeding each data input with 0, 1, the residual variable or its complement (Shannon expansion in hardware).
• Tree expansion: two 8:1 + one 2:1 → 16:1; MUX = universal logic element.
• Applications: data routing, parallel→serial conversion, time-division multiplexing.

Demultiplexer / Decoder

• DEMUX: 1 input → 2ⁿ outputs (select-steered); a decoder with enable used as data = DEMUX (74138 = 3:8 decoder/DEMUX, 74155).
• Decoder: n inputs → activates one of 2ⁿ outputs (minterm generator). Function realization: decoder + OR gates sums required minterms — multi-output friendly (e.g., FA from one 74138 + two OR gates). Address decoding in memory systems (§5.10).

Encoders

• 2ⁿ → n inverse of decoder; ordinary encoder fails for multiple simultaneous inputs → priority encoder (74147 decimal→BCD, 74148 octal) outputs the highest-priority active line + valid flag.

§ 5.7Flip-Flops

• Latch vs flip-flop: latch = level-sensitive (transparent while enabled); flip-flop = edge-triggered (samples on clock edge only).
• SR latch: cross-coupled NORs (S=R=1 forbidden) or NANDs (S̄R̄, 0-active, S=R=0 forbidden); clocked SR adds gating. Switch-debouncer application.
• D (data/delay): Q⁺ = D — the storage workhorse; D latch transparent, D-FF edge-clocked.
• JK: resolves the SR forbidden state — J=K=1 toggles. Characteristic equation:
  Characteristic equations $$ Q^{+}_{JK} = J\bar Q + \bar K Q, \qquad Q^{+}_{D} = D, \qquad Q^{+}_{T} = T \oplus Q, \qquad Q^{+}_{SR} = S + \bar R Q\ (SR = 0) $$
• Race-around: level-triggered JK with J=K=1 toggles repeatedly while CLK is high (t_pulse > t_pd) → unpredictable. Cures: master–slave (master latches on CLK high, slave copies on low — pulse-triggered; beware 1's-catching) or edge triggering (modern standard, e.g., 7474 D, 74112 JK negative-edge).
• T (toggle): JK with J=K=T; divide-by-2 when T=1 — the counter cell.
• Excitation tables (design direction: given Q→Q⁺, find inputs):

  Excitation table — memorize whole

  Q→Q⁺	S R	J K	D	T
  0→0	0 X	0 X	0	0
  0→1	1 0	1 X	1	1
  1→0	0 1	X 1	0	1
  1→1	X 0	X 0	1	0

• Conversions: wire via characteristic/excitation match — JK→D: J = D, K = D̄; JK→T: J = K = T; D→JK: D = JQ̄ + K̄Q; D→T: D = T⊕Q; T→D: T = D⊕Q.
• Timing parameters: setup t_su (data stable before edge), hold t_h (after edge), propagation t_pd, recovery (async release); violation → metastability (output hovers; resolve with synchronizer chains). Max clock \( f_{max} = 1/(t_{pd} + t_{su} + t_{comb}) \). Asynchronous PRESET/CLEAR override the clock.

§ 5.8Shift Registers

• Cascade of D flip-flops sharing one clock; data moves one stage per edge. Four I/O modes: SISO, SIPO, PISO, PIPO — serial load of n bits takes n clocks; parallel load takes 1.
• Universal shift register (74194): mode controls S₁S₀ select hold / shift-right / shift-left / parallel-load.
• Bidirectional shifting via MUX at each D input. 74164 = SIPO, 74165 = PISO, 7495 = 4-bit universal predecessors.
• Applications: serial↔parallel conversion (UART core), time delay (n/f_clk), multiplication/division by 2 per left/right shift (arithmetic shift preserves sign), keyboard scanning, pseudo-random sequence generation:
  • LFSR: feedback = XOR of taps → maximal-length (PN) sequence of \( 2^n - 1 \) states (all-zeros excluded); CRC, scramblers, BIST.
• Counter cousins (ring/Johnson) in §5.9.

§ 5.9Counters: Ripple, Synchronous, Ring & Johnson

Asynchronous (ripple) counters

• T/JK FFs in toggle; each stage clocked by the previous stage's output — count propagates serially.
  Ripple-counter limits $$ n = \lceil \log_2 N \rceil \ \text{FFs for mod-}N; \qquad f_{max} = \frac{1}{n\,t_{pd}}\ \ (\text{delays add}); \qquad \text{output stage } k \text{ divides } f \text{ by } 2^k $$
• Mod-N (truncated): NAND-decode state N → asynchronous CLEAR (e.g., decade 7490 resets at 1010). Transient decoding glitches/spikes during ripple — why ripple counters can't drive decoders safely at speed.
• Up-counter: clock from Q (negative-edge FFs); down-counter: from Q̄ (or invert clocking convention).

Synchronous counters

• All FFs share the clock; next-state logic (from excitation tables — the §5.16 design procedure) feeds J/K or T inputs: stage toggles when all lower stages = 1 → \( T_k = Q_{k-1}Q_{k-2}\cdots Q_0 \).
• f_max set by one FF delay + gating: \( f_{max} = 1/(t_{pd} + t_{su} + t_{gate}) \) — fast and glitch-aligned. ICs: 74160–163 (sync decade/binary, sync load), 74190/191/193 (up–down).
• Arbitrary-sequence and self-correcting counters via unused-state analysis (lockout check: ensure stray states re-enter the main loop).

Shift-register counters

Both waste states vs binary (need self-correction logic for stray states) but trade efficiency for speed and clean decoding.

§ 5.10Semiconductor Memories

• Hierarchy of terms: capacity = words × bits (e.g., 1K × 8); address lines n ↔ 2ⁿ words; access time, cycle time; volatile (RAM) vs non-volatile (ROM/flash).

• ROM family: mask ROM (factory) → PROM (fuse, one-time) → EPROM (UV-erase whole chip, quartz window, floating-gate FAMOS) → EEPROM (electrical byte-erase, Fowler–Nordheim tunneling) → Flash (electrical block-erase; NOR = code/XIP, random access; NAND = data storage, serial pages, cheapest/densest; wear ~10³–10⁵ cycles → wear leveling).
• Memory expansion (favourite numericals): word-length expansion = parallel chips sharing addresses (two 1K×4 → 1K×8); capacity expansion = decoder on upper address lines selects chips via CS (four 1K×8 + 2:4 decoder → 4K×8). Chips needed = (target words/chip words)×(target bits/chip bits).
• Memory class map: RWM (SRAM/DRAM), NVRAM (battery/FeRAM/MRAM), sequential (FIFO), CAM (associative — tag lookup).
• ROM as logic: address = input, stored word = truth-table output — fixed-AND PLD view (§5.13); lookup tables, character generators, code conversion, microprogram store.

§ 5.11D/A Converters

• Weighted-resistor DAC: summing amp with R, 2R, 4R … 2ⁿ⁻¹R branches — simple but needs a 2ⁿ⁻¹:1 range of precise resistors (impractical beyond ~4–6 bits).
• R–2R ladder (the standard): only two values; each node sees R looking either way → binary current/voltage division; switches steer 2R branches to V_ref or ground. Output \( V_o = -\dfrac{R_f}{2R}\cdot\dfrac{V_{ref}\,D}{2^{n-1}} \)-form (inverted-ladder current-mode is fastest). Monotonicity by construction; trimming easy.
• Switched current-source DACs (high speed, comms), PWM + filter (cheap), sigma-delta (audio precision); multiplying DAC (MDAC): output ∝ digital code × analog V_ref → programmable attenuator.
• Specifications: resolution (bits), full-scale, accuracy; INL (deviation from ideal line), DNL (step-size error; DNL < 1 LSB ⇒ monotonic ⇒ no missing interaction with ADC codes), offset/gain errors, settling time, glitch energy at major-code transitions (0111→1000), deglitcher = track/hold.

§ 5.12A/D Converters

• SAR walk-through (the standard numerical): set MSB, compare via internal DAC, keep/clear, proceed bitwise — n comparisons total; e.g., 8-bit, 1 MHz clock → 8 µs.
• Sample-and-hold precedes SAR/flash so the input is frozen during conversion; aperture jitter limits SNR at high f_in; anti-alias filter before everything (Unit-3 §3.17).
• Specs: resolution, conversion time/throughput (SPS), INL/DNL, missing codes (DNL ≤ −1 LSB), ENOB = (SINAD − 1.76)/6.02.
• Counting comparators: flash n-bit needs 2ⁿ − 1 (8-bit → 255); two-step/pipeline ADCs split the flash to economize.

§ 5.13Programmable Logic Devices: PROM, PAL, PLA

All three are AND-array → OR-array structures realizing SOP functions; they differ only in which array is programmable — the definitive table:

• Programming technologies: fuse/antifuse (OTP), EPROM/EEPROM cells (erasable — GAL16V8 replaces PALs), SRAM (FPGA-style, volatile).
• PAL nomenclature: PAL16L8 = 16 inputs, 8 active-low outputs; PAL16R8 = registered (D-FF) outputs → first sequential PLDs (§5.15).
• Design flow: minimize to SOP → map products to AND lines → dot/X fuse maps (exam asks you to read or mark a fuse map).
• Sizing arithmetic: PLA spec "n × k × m" = n inputs, k product terms, m outputs; PROM for n inputs needs 2ⁿ words.

§ 5.14CPLD

• Complex PLD = several PAL-like macrocell blocks (each: programmable AND plane → OR → XOR polarity → D/T flip-flop → feedback) + a central programmable interconnect matrix + I/O blocks.
• Traits: non-volatile (EEPROM/flash — live at power-up, no boot stream), deterministic, predictable pin-to-pin timing (fixed routing crossbar), modest capacity (~10²–10⁴ macrocells), instant-on; in-system programmable via JTAG.
• Sweet spot: glue logic, address decoders, state machines, bus interfaces, power sequencing, FPGA configuration controllers.
• Classic families: Xilinx XC9500/CoolRunner, Altera MAX 7000/MAX II, Lattice ispMACH.
• Architecture lineage: SPLD (single PAL/GAL) → CPLD (many PALs + crossbar) → FPGA (sea of LUTs + segmented routing) — the granularity/volatility/timing trade tabled in §5.15.

§ 5.15Sequential PLDs & FPGA

Sequential PLDs

• Registered PAL/GAL macrocells (e.g., 16R8, 22V10): D flip-flop on each output, Q fed back into the AND plane → Mealy/Moore FSMs directly in one chip; output-enable and polarity programmable per macrocell. The 22V10's "versatile" macrocell (registered/combinational selectable) became the generic standard.
• Design = §5.16 procedure with excitation logic mapped onto product terms.

FPGA architecture

• Field-Programmable Gate Array: 2-D fabric of configurable logic blocks (CLBs) in a sea of programmable segmented routing, ringed by I/O blocks (IOBs); modern devices add block RAM, DSP (multiply–accumulate) slices, clock managers (PLL/DLL/DCM), high-speed serial transceivers, even hard CPU cores (SoC-FPGA).
• CLB/logic cell = LUT + FF: a k-input look-up table (k = 4 classic, 6 modern) is a tiny 2ᵏ×1 SRAM holding the truth table — implements any k-variable function in identical delay (Shannon/§5.2 made physical) — plus carry chain and a D flip-flop with bypass mux.
• Configuration: SRAM cells (dominant — reprogrammable, volatile → boot from external flash; SEU consideration), antifuse (OTP, rad-hard), flash-based (non-volatile, live-at-power-up).
• Design flow: HDL → synthesis → technology mapping → place & route → static timing analysis → bitstream. Timing depends on routing → reported post-P&R (contrast CPLD determinism).

• FPGA vs ASIC: no NRE/mask cost, instant iteration, field updates ↔ higher unit cost, power, and lower f_max; structured-ASIC/hard-copy as midpoints. FPGAs dominate prototyping, low/medium volume, accelerators (and Ravindra-style lab instrumentation).

§ 5.16Synchronous State Machines: Mealy & Moore

Design procedure (the algorithm to internalize)

1. Word statement → state diagram (bubbles = states, arcs = input/output).
2. State table (present state, input → next state, output).
3. State reduction: merge equivalent states (same outputs and equivalent next states — partition/implication-chart method).
4. State assignment (binary codes; ⌈log₂S⌉ FFs; one-hot in FPGAs trades FFs for simpler logic).
5. Choose FF type → apply excitation tables (§5.7) → K-map the FF-input and output equations.
6. Check unused states: confirm they transition into the valid loop (self-starting; no lockout) or add reset logic.

• Worked archetypes the exam draws from: sequence detector ("detect 1011", overlapping vs non-overlapping → different transition arcs), serial adder (1 FF carries the carry), vending machine, up/down mod-N controllers (§5.9 synchronous counters are FSMs with no input).
• Analysis = reverse: from circuit → excitation expressions → next-state/state table → diagram → behaviour.
• Maximum clock from the timing budget \( f_{max} = 1/(t_{pd,FF} + t_{comb,max} + t_{su}) \).

§ 5.17Fundamental-Mode (Asynchronous) State Machines

No clock — state is held in feedback delays/latches; the circuit responds directly to input edges. Fundamental-mode assumptions: only one input changes at a time, and the circuit reaches a stable state (next state = present state) before the next change.

Analysis & design vocabulary

• State variables y (fed-back secondary variables) and excitation variables Y (their next values): stable ⟺ Y = y.
• Primitive flow table: one stable state per row (circled entries stable); merge compatible rows (using don't-cares) → reduced flow table → assign secondary variables → excitation maps → hazard-free SOP logic.

Races

• A transition requiring two or more state variables to change "simultaneously" — unequal delays decide the order. Non-critical race: all orders converge to the same stable state. Critical race: different orders → different stable states — a design failure.
• Cures: race-free (adjacent) state assignment — consecutive states differ in one variable (Gray-like; add cycle states or extra variables if needed); one-hot assignments.

Hazards

• Static-1 hazard: output momentarily drops 0 during a transition between two input states both giving 1 (two K-map groups not bridged) — kill with the consensus/redundant term. Static-0: dual (POS). Dynamic hazard: output bounces (1→0→1→0) during a single transition — arises in multi-level logic with multiple paths; eliminated by removing static hazards in two-level form.
• Essential hazard: a race between an input change and the fed-back state change (inherent in the flow table — detectable: state reached after 1 input change ≠ after 3 changes); cured only by inserting delay in the feedback path, not by added logic.
• In synchronous machines, hazards are harmless between clock edges (sampling waits) — one reason clocked design dominates; asynchronous design survives in latches themselves, arbiters/synchronizers, ripple counters, and ultra-low-power niches.

§ 5.18Digital Design Using HDL

• HDLs describe hardware, not sequential software: statements imply concurrent circuits. The two standards: Verilog (C-like) and VHDL (Ada-like, strongly typed: entity/architecture). SystemVerilog extends Verilog.
• Modeling styles: structural / gate-level (netlist of primitives), dataflow (continuous assignments: assign y = a & b;), behavioral (always/process blocks describing function); RTL = register-transfer level, the synthesizable middle.
• Verilog essentials: module … endmodule; nets (wire) driven by assign/ports vs variables (reg) assigned in always; 4-value logic 0, 1, x (unknown), z (high-impedance); vectors [7:0]; parameterization.
• Combinational vs sequential templates (the exam's favourite discrimination):
  • Combinational: always @(*) with blocking (=) assignments; cover all branches or an unintended latch is inferred (the classic trap).
  • Sequential: always @(posedge clk) with non-blocking (<=) assignments — models all FFs updating together; mixing styles causes simulation/synthesis races.
• Reference snippets:
  D flip-flop with async reset (Verilog) always @(posedge clk or posedge rst)
  if (rst) q <= 1'b0; else q <= d;
  4:1 MUX — dataflow assign y = sel[1] ? (sel[0] ? d3 : d2) : (sel[0] ? d1 : d0);
  Counters: q <= q + 1; in a clocked block; FSMs: state register (sequential block) + next-state/output logic (combinational block) + case on the state — the two-process idiom.
• Flow: HDL → testbench simulation (functional; testbenches use delays/initial blocks — non-synthesizable) → synthesis to gates/LUTs → place & route → timing closure (§5.15). Not everything simulatable is synthesizable (delays, initial, file I/O).
• VHDL mirror: entity/architecture, process(sensitivity), signals (<= concurrent) vs variables (:= inside process), std_logic 9-value type.

§ 5.19Unit-5 Formula Sheet

§ 5.20Quick Revision Notes — Unit 5 in 25 Points

↑ Back to top of Unit 5