UNIT 5: DIGITAL SYSTEM DESIGN - EXAM-FOCUSED SHORT NOTES

Based on rigorous analysis of RGPV past papers (JUN 2025 to NOV 2022).

1. NUMBER SYSTEMS AND CODES

Base Conversion Fundamentals

• Binary → Decimal: Multiply each bit by $$\displaystyle 2^n $$ (n = position from right, starting 0) and sum.

  • Example: $$\displaystyle (1011.1)_2 = 1\times2^3 + 0\times2^2 + 1\times2^1 + 1\times2^0 + 1\times2^{-1} = 11.5_{10} $$

• Decimal → Binary (Integer): Repeated division by 2, collect remainders (LSB first).

• Decimal → Binary (Fraction): Repeated multiplication by 2, collect integer parts (MSB first).

  • Example: $$\displaystyle 0.625 \times 2 = 1.25 $$ → 1, $$\displaystyle 0.25 \times 2 = 0.5 $$ → 0, $$\displaystyle 0.5 \times 2 = 1.0 $$ → 1 ⇒ $$\displaystyle (0.101)_2 $$

• Octal/Hex ↔ Binary: Group binary bits.

  • Binary → Octal: Group 3 bits from point (LSB side). $$\displaystyle (101110.011)_2 = (56.3)_8 $$

  • Binary → Hex: Group 4 bits. $$\displaystyle (101110.011)_2 = (2E.6)_{16} $$

  • Octal/Hex → Binary: Replace each digit with 3/4 binary equivalent.

• Gray Code ↔ Binary

  • Binary → Gray: MSB same. $$\displaystyle G_i = B_i \oplus B_{i+1} $$.

  • Gray → Binary: MSB same. $$\displaystyle B_i = G_i \oplus B_{i+1} $$ (cascade from MSB).

Special Number Systems

• BCD (Binary Coded Decimal): Each decimal digit (0-9) represented by 4-bit binary. Invalid codes: 1010-1111.

• Excess-3 (XS-3): BCD + 3 (0011). Self-complementing property: 9's complement of decimal = 1's complement of XS-3.

• Conversion: Add/subtract 3 (0011) to/from BCD code for each digit.

[!TIP] Exam Alert

• Fractional conversion is frequently asked (e.g., JUN 2025: 314.52₈). Remember: for fractional part, multiply by base repeatedly.

• Gray code conversion is a 4-mark question. Master both directions.

• XS-3 code often appears in code converter design (DEC 2024 context).

2. BOOLEAN ALGEBRA AND LOGIC GATES

De Morgan's Theorem

• Statement:

$$ \overline{A+B} = \bar{A} \cdot \bar{B} $$

$$ \overline{A \cdot B} = \bar{A} + \bar{B} $$

• Proof: Use truth table or logical reasoning.

• Application: Used for gate-level implementation (NAND/NOR as universal gates), simplifying Boolean expressions.

Universal Gates: NAND & NOR

• Definition: A gate is universal if it can implement any Boolean function alone.

• Implementation using NAND:

  • NOT: $$\displaystyle A' = A \text{ NAND } A $$

  • AND: $$\displaystyle A \cdot B = (A \text{ NAND } B)' = (A \text{ NAND } B) \text{ NAND } (A \text{ NAND } B) $$

  • OR: $$\displaystyle A + B = A' \text{ NAND } B' = (A \text{ NAND } A) \text{ NAND } (B \text{ NAND } B) $$

  • NOR: $$\displaystyle (A+B)' = A \text{ NAND } B \text{ NAND } A \text{ NAND } B $$ (using De Morgan)

• Implementation using NOR: Similar process using NOR's properties.

• Cross-Implementation: NOR using NANDS (or vice-versa) requires combining the above primitives.

[!TIP] Common Pitfall

• Forgetting double inversion when implementing AND/OR with NAND/NOR. Remember: NAND is NOT(AND), so to get AND, you need to invert the NAND output again.

3. COMBINATIONAL LOGIC MINIMIZATION

Karnaugh Map (K-Map) Method

• Procedure:

  1. Plot minterms (1s) and don't cares (X/–) on K-map.

  2. Form largest possible groups of 1s/Xs (powers of 2: 1,2,4,8...). Groups can overlap.

  3. Write Prime Implicants (PIs): Each group gives a product term (literal absent if that variable changes within group).

  4. Identify Essential Prime Implicants (EPIs): PIs covering a minterm not covered by any other PI.

  5. Use Petrick's Method or table lookup to select minimal remaining PIs for minimum SOP.

  6. For minimum POS, group maxterms (0s) on K-map.

• Don't Care Handling: Can be included in groups to make them larger, but never excluded if it helps form a larger group.

Quine-McCluskey (Tabulation) Method

• Step-by-Step:

  1. List minterms in binary, group by number of 1s.

  2. Combine adjacent groups (differ by 1 bit) → mark combined terms, generate prime implicants.

  3. Repeat combining until no further combinations → final list of all PIs.

  4. Construct Prime Implicant Chart: Rows = PIs, Columns = Minterms.

  5. Essential PIs: Columns covered by only one row.

  6. Selection of Minimal Cover: Use row/column dominance or Petrick's method to choose minimal set of PIs covering all minterms.

• With Don't Cares: Include don't cares in initial list but do not require them to be covered in final chart.

[!TIP] Exam Strategy

• K-Map (2-4 vars): Fast, visual. Always check for adjacent corners (wraparound). For 4-variable, groups of 8 are possible.

• Quine-McCluskey: Systematic for >4 variables. Essential step: Correctly identifying all PIs in iteration steps. Past papers (DEC 2024, JUN 2024) ask for full tabulation.

4. COMBINATIONAL CIRCUIT DESIGN

Arithmetic Circuits

• Half Adder (HA):

  • Sum = $A \oplus B$, Carry = $A \cdot B$

  • Truth Table: (A,B) → (Sum,Carry): (0,0)→(0,0); (0,1)→(1,0); (1,0)→(1,0); (1,1)→(0,1)

• Full Adder (FA):

  • Using 2 HAs: $$\displaystyle S = A \oplus B \oplus C_{in} $$; $$\displaystyle C_{out} = (A \cdot B) + (C_{in} \cdot (A \oplus B)) $$

  • Design: 2 HA + OR gate.

• Full Subtractor (FS):

  • $$\displaystyle D = A \oplus B \oplus B_{in} $$; $$\displaystyle B_{out} = \bar{A}B + \bar{A}B_{in} + BB_{in} $$

• BCD Adder:

  • Add two BCD digits with 4-bit FA.

  • Correction: If sum > 9 (or $$\displaystyle C_{out}=1 $$), add 6 (0110) using second FA.

  • $$\displaystyle Correction = C_{out} + S_3S_2 + S_3S_1 $$

• Carry Look-Ahead Adder (CLA):

  • Principle: Generate ($$\displaystyle G_i = A_iB_i $$) and Propagate ($$\displaystyle P_i = A_i \oplus B_i $$) signals.

  • $$\displaystyle C_1 = G_0 + P_0C_0 $$, $$\displaystyle C_2 = G_1 + P_1G_0 + P_1P_0C_0 $$, etc.

  • Block Diagram: Shows logic for generating all $$\displaystyle C_i $$ in parallel → reduces propagation delay.

Code Converters

• Excess-3 to Gray:

  1. Get Excess-3 bits: $$\displaystyle E_3 E_2 E_1 E_0 $$.

  2. Convert to BCD: $$\displaystyle B_i = E_i - 3 $$ (subtract 0011).

  3. Convert BCD to Gray: $$\displaystyle G_3 = B_3 $$, $$\displaystyle G_2 = B_3 \oplus B_2 $$, $$\displaystyle G_1 = B_2 \oplus B_1 $$, $$\displaystyle G_0 = B_1 \oplus B_0 $$.

  4. Minimize using K-map (4-variable function).

• BCD to Excess-3: Add 3 (0011) to each BCD digit using 4-bit adder.

Data Processing Circuits

• Multiplexer (MUX):

  • 8:1 MUX: 8 data inputs ($$\displaystyle D_0-D_7 $$), 3 select lines ($$\displaystyle S_2S_1S_0 $$), 1 output Y.

  • $$\displaystyle Y = \sum_{i=0}^{7} D_i \cdot (S_2S_1S_0)'_i $$

  • Implementing F(A,B,C,D): Use B,D as selects ($$\displaystyle S_1,S_0 $$). For each of 4 combinations of B,D, connect A,C or their complements to data inputs based on minterms for that combination.

• Decoder + OR:

  • 2-to-4 Decoder: 2 inputs (A,B), 4 outputs ($$\displaystyle Y_0-Y_3 $$), active high. $$\displaystyle Y_i = \prod M_i $$ (maxterm).

  • Realize $$\displaystyle F = A + A'B $$: Use decoder outputs $$\displaystyle Y_0 $$ (A'B') and $$\displaystyle Y_1 $$ (A'B). $$\displaystyle F = Y_0' + Y_1 = \overline{Y_0} + Y_1 $$.

• 4-bit Priority Encoder:

  • Inputs: $$\displaystyle I_0-I_3 $$ (priority $$\displaystyle I_3 > I_2 > I_1 > I_0 $$).

  • Outputs: 2-bit binary code ($$\displaystyle A_1A_0 $$) for highest-priority 1, and valid signal (V=1 if any input=1).

  • Logic: $$\displaystyle A_1 = I_3 + I_2 $$, $$\displaystyle A_0 = I_3 + \overline{I_2}I_1 $$, $$\displaystyle V = I_3+I_2+I_1+I_0 $$.

• 2-bit Magnitude Comparator:

  • Inputs: $$\displaystyle A_1A_0 $$, $$\displaystyle B_1B_0 $$.

  • Outputs: $$\displaystyle A>B $$, $$\displaystyle A=B $$, $$\displaystyle A<B $$.

  • $$\displaystyle A=B = (A_1 \oplus B_1)' \cdot (A_0 \oplus B_0)' $$

  • $$\displaystyle A>B = A_1\bar{B_1} + (A_1B_1)'A_0\bar{B_0} $$

Parity Generator/Checker

• Even Parity: Generator output = XOR of all data bits. Checker: XOR of all bits (data + parity) = 0 for even parity.

• Odd Parity: Invert even parity generator output.

5. SEQUENTIAL CIRCUIT FUNDAMENTALS

Latches & Flip-Flops

• S-R Flip-Flop (NOR Latch):

  • Truth Table:

    | S | R | Q(t+1) | Comment | |---|---|---|---| | 0 | 0 | Q(t) | Hold | | 0 | 1 | 0 | Reset | | 1 | 0 | 1 | Set | | 1 | 1 | X | Invalid |

  • Characteristic Equation: $$\displaystyle Q(t+1) = S + \bar{R}Q $$ (with $$\displaystyle SR=0 $$ constraint).

• D Flip-Flop:

  • Truth Table: $$\displaystyle D=0 \rightarrow Q=0 $$; $$\displaystyle D=1 \rightarrow Q=1 $$ at clock edge.

  • Characteristic Equation: $$\displaystyle Q(t+1) = D $$.

  • Timing Diagram: Shows $D$ sampled at rising/falling clock edge.

• J-K Flip-Flop:

  • Truth Table:

    | J | K | Q(t+1) | |---|---|---| | 0 | 0 | Q(t) | | 0 | 1 | 0 | | 1 | 0 | 1 | | 1 | 1 | $\bar{Q}(t)$ |

  • Characteristic Equation: $$\displaystyle Q(t+1) = J\bar{Q} + \bar{K}Q $$.

  • Race-Around Condition: For $$\displaystyle J=K=1 $$, output toggles continuously if clock pulse width > FF delay. Output state uncertain.

  • Elimination: Master-Slave Configuration (two latches: Master enabled on CLK=1, Slave on CLK=0). Output changes only at falling edge.

• T Flip-Flop:

  • $$\displaystyle T=0 $$: Hold; $$\displaystyle T=1 $$: Toggle.

  • $$\displaystyle Q(t+1) = T \oplus Q(t) $$.

• Flip-Flop Conversion:

  • Procedure: Use excitation table of target FF. Derive input equations (J,K for JK; D for D; T for T) in terms of present state Q and next state Q⁺.

  • Example: T → JK: $$\displaystyle J = T $$, $$\displaystyle K = T $$ (since JK toggles when J=K=1).

Analysis & Design of Clocked Sequential Circuits

1. State Diagram: Circles (states), arrows (transitions on input).

2. State Table: Columns: Present State, Input, Next State, Output.

3. State Assignment: Binary, Gray (adjacent states differ by 1 bit), One-Hot.

4. Excitation Table: For chosen FF (JK/D/T), add columns for FF inputs needed for each transition.

5. Derive Equations: Use K-map/QM to simplify FF input equations and output equations from excitation table.

6. Logic Diagram: Connect FF inputs with derived combinational logic.

6. COUNTERS AND SHIFT REGISTERS

Counters

• Asynchronous (Ripple) Counter:

  • Design: FF0 toggles on clock pulse. FF1 toggles on FF0's $\bar{Q}$ (negative edge triggered). FF2 on FF1's $\bar{Q}$, etc.

  • Disadvantage: Ripple effect → cumulative propagation delay limits speed. Output changes not simultaneous.

• Synchronous Counter:

  • Design: All FFs clocked by same clock signal.

  • Input Equations: Derived from state table (e.g., for MOD-4 up counter using T FFs: $$\displaystyle T_0=1 $$, $$\displaystyle T_1=Q_0 $$, $$\displaystyle T_2=Q_1Q_0 $$).

  • Advantage: No ripple, faster.

• Modulus (MOD-N) Counter:

  • Counts from 0 to N-1, then resets to 0.

  • Design: Use N flip-flops ($$\displaystyle 2^n \ge N $$). Detect count = N (or N-1) and use asynchronous/synchronous clear to reset.

• Up/Down Counter:

  • Mode Control (M): M=0 → Down (count decrements); M=1 → Up (increments).

  • Using D FFs: $$\displaystyle D_i = Q_i \oplus (M \cdot Q_{i-1}Q_{i-2}...Q_0) $$ for up/down control logic.

Comparison: Synchronous vs Asynchronous

Shift Registers

• Configurations:

  • SISO: Serial In → Serial Out.

  • SIPO: Serial In → Parallel Out.

  • PISO: Parallel In → Serial Out.

  • PIPO: Parallel In → Parallel Out.

• Universal Shift Register:

  • Modes: Shift Left, Shift Right, Hold, Parallel Load.

  • Control: Mode select lines (S1,S0). Multiplexers at each FF D-input to select between: left neighbor, right neighbor, parallel data input, or own output (hold).

• Ring Counter:

  • 4-bit: Initial state e.g., 1000. Connect Q3 to D0 (feedback). Sequence: 1000 → 0100 → 0010 → 0001 → 1000...

  • Cycle Length = number of bits (4). Only one '1' at a time.

• Johnson (Twisted Ring) Counter:

  • 4-bit: Connect $$\displaystyle \bar{Q}_0 $$ to D3 (inverted feedback). Sequence: 0000 → 1000 → 1100 → 1110 → 1111 → 0111 → 0011 → 0001 → 0000...

  • Cycle Length = 2n (8 for n=4).

• Pseudo-Random Binary Sequence (PRBS) Generator:

  • LFSR (Linear Feedback Shift Register): Shift register with XOR/XNOR feedback taps from selected Q outputs to D0.

  • Maximal Length: For n-bit LFSR with proper taps, sequence length = $$\displaystyle 2^n - 1 $$ (e.g., 4-bit → 15 states).

  • Design: Choose primitive polynomial (e.g., for 4-bit: $$\displaystyle x^4 + x^3 + 1 $$ → taps from Q3 and Q2).

7. FINITE STATE MACHINES (FSM)

Synchronous FSM Design Methodology

1. Problem Statement: Define inputs, outputs, sequence.

2. State Diagram: States as circles, transitions labeled input/output.

3. State Table: Present State, Input, Next State, Output.

4. State Reduction:

   • Equivalent States: Two states are equivalent if for all input sequences, they produce identical output sequences.

   • Method: Compare rows of state table. Merge equivalent states.

5. State Assignment: Assign binary codes to reduced states. Gray code preferred for one-transition-per-bit.

6. Excitation/Output Table: Add columns for FF inputs (using JK/D/T excitation tables) and output logic.

7. Simplify Equations: K-map for each FF input and output.

8. Logic Diagram: Draw FFs and combinational logic.

Algorithmic State Machine (ASM) Charts

• Elements:

  • State Box: Oval, contains state name and outputs (Moore-type).

  • Decision Box: Diamond, tests input condition (1-bit).

  • Conditional Output Box: Rectangle with curved sides, outputs depend on path.

• Derivation: From state diagram, each state becomes a state box. Transitions become decision boxes connecting state boxes.

• Design: ASM chart directly yields state table and output equations.

Sequence Detectors

• Mealy Machine: Output depends on present state AND inputs. Output can change immediately with input (no clock wait). May have fewer states.

  • Example: Detect "0011" (overlap allowed: 00110011 → detects at 4th and 8th bits).

  • States: S0 (no match), S1 (got '0'), S2 ('00'), S3 ('001'), S4 ('0011' → output=1).

• Moore Machine: Output depends only on present state. Output changes only on clock edge. More states typically.

  • Same sequence: States represent progress (S0, S1, S2, S3, S4). Output=1 only in S4.

• Implementation: Use D FFs (common). Derive next-state equations from state table, implement with combinational logic.

8. LOGIC FAMILIES AND IMPLEMENTATION TECHNOLOGIES

Bipolar Logic Families

• TTL (Transistor-Transistor Logic):

  • Basic NAND Gate (Totem-Pole Output):

    • Multi-emitter input transistor.

    • Phase splitter (Q2).

    • Totem-pole output: Q3 (pull-down) and Q4 (pull-up, with diode D1 for speed).

    • Operation: Inputs high → Q1 saturates → Q2 off → Q3 off, Q4 on → output low (0). Any input low → Q1 not saturate → Q2 on → Q3 on, Q4 off → output high (1).

  • Tri-State TTL Gate:

    • Adds enable control. When enabled, acts as normal gate. When disabled, output goes to high-impedance (Z) state.

    • Circuit: Extra transistors in output stage controlled by enable. Used for bus systems (multiple devices share same line).

• ECL (Emitter-Coupled Logic):

  • Basic Inverter/NOR:

    • Uses differential amplifier pair. No saturation (transistors operate in active region).

    • Principle: Constant current source, fast switching because transistors never saturate → very high speed (ns range).

    • Disadvantage: High power consumption, negative logic levels.

MOS Logic Families

• CMOS (Complementary MOS):

  • Inverter: P-MOS (top, pull-up) and N-MOS (bottom, pull-down) in series.

    • Input high → N-MOS ON, P-MOS OFF → output low.

    • Input low → N-MOS OFF, P-MOS ON → output high.

  • Advantages: Very low static power (only one transistor ON), high noise margin, wide voltage range.

  • Disadvantages: Slower than ECL, sensitive to electrostatic discharge.

Key Parameters

• Fan-in: Number of inputs a gate can have.

• Fan-out: Number of similar gates a gate output can drive without degradation. Limited by current/power.

• Noise Margin:

  • $$\displaystyle NM_L = V_{IL(max)} - V_{OL(max)} $$ (Low-level)

  • $$\displaystyle NM_H = V_{OH(min)} - V_{IH(min)} $$ (High-level)

  • Higher NM → Better noise immunity.

• Propagation Delay ($$\displaystyle t_{pd} $$): Average time for input change to cause output change. Lower $$\displaystyle t_{pd} $$ → Higher speed.

Programmable Logic Devices

• FPGA (Field-Programmable Gate Array):

  • Architecture:

    • Configurable Logic Blocks (CLBs): Contain LUTs (Look-Up Tables, e.g., 4/5-input) and flip-flops. Implement combinational/sequential logic.

    • Programmable Interconnection Points (PIPs): Switch matrix for routing between CLBs.

    • I/O Blocks (IOBs): Interface with external pins.

  • Configuration Memory: Stores programming bits (SRAM-based, Flash-based) that set LUT functions and PIP connections.

  • Comparison with CPLD: FPGA has finer-grained architecture, more gates, slower but more flexible. CPLD has larger logic blocks, faster, non-volatile.

[!TIP] Exam Focus

• TTL Totem-Pole & Tri-State: Draw and explain operation (JUN 2024, DEC 2024).

• CMOS vs TTL: Compare power, speed, noise margin (DEC 2024).

• FPGA Block Diagram: Must know CLB, PIPs, IOBs (JUN 2024, JUN 2023).

• Noise Margin & Fan-out: Definitions and significance (DEC 2023).