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

I. NUMBER SYSTEMS AND CODE CONVERSIONS

Core Number Systems

Conversion Methods

1. Integer Part: Repeated division by target base.

2. Fractional Part: Repeated multiplication by target base.

   [!TIP] For fractional conversions, multiply until fractional part becomes zero or desired precision is reached.

Example: Octal 314.52 to other bases

• To Binary: Split each octal digit → 3 binary bits.

  3→011, 1→001, 4→100, 5→101, 2→010 → 011001100.101010

• To Decimal:

$$ (314.52)_8 = 3×8^2 + 1×8^1 + 4×8^0 + 5×8^{-1} + 2×8^{-2} = 204.65625_{10} $$

• To Hex: Convert binary to hex (group 4 bits).

  011001100.101010 → 0110 0110 0.1010 10 → 66.54₁₆

Special Codes

• Gray Code: Only 1 bit changes between consecutive numbers.

  • Binary to Gray: MSB same; each next bit = XOR(prev Gray bit, current binary bit).

$$ G_i = B_i \oplus B_{i+1} \quad (\text{with } B_{n+1}=0) $$

• Gray to Binary: MSB same; each next bit = XOR(prev binary bit, current Gray bit).

$$ B_i = G_i \oplus B_{i+1} $$

• BCD (Binary Coded Decimal): Each decimal digit → 4-bit binary.

  • Valid codes: 0000 to 1001; 1010-1111 are invalid.

• Excess-3 (XS-3): BCD + 0011 (3).

  • BCD to XS-3: Add 0011 to each 4-bit BCD digit.

  • XS-3 to BCD: Subtract 0011; watch for borrow across digits.

II. BOOLEAN ALGEBRA AND LOGIC MINIMIZATION

Boolean Algebra Laws (Key Theorems)

[!TIP] De Morgan's: Break the bar, change the operator.

Karnaugh Map (K-Map) Method

• Purpose: Visual minimization of SOP/POS.

• Rules:

  1. Group powers of 2 (1,2,4,8,...).

  2. Groups must be rectangular.

  3. Wrap-around allowed (edges/toroidal).

  4. Don't cares (X) can be included if helpful.

  5. Largest possible groups, then fewest groups.

  6. Essential Prime Implicant (EPI): Minterm covered by only one PI.

Steps:

1. Plot minterms/don't cares.

2. Identify all Prime Implicants (PIs).

3. Mark Essential Prime Implicants (EPIs).

4. Use Petrick's method if needed for remaining minterms.

Example for 4-variable:

$$ F(A,B,C,D) = \sum m(0,5,7,9,11,13) + d(10,15) $$

• Groups: m0 alone? Check if covered by other PIs.

• EPIs: m5,7,13 form group? → BD'? Let's compute:

  • Quad m8,9,10,11 → A'C? Actually: A'C covers m8,9,10,11 but m8 not in function → use A'C with d(10)? Better to list all PIs.

[!TIP] POS from K-map: Group maxterms (0s) or use complement of SOP of F'.

Quine-McCluskey (Tabulation) Method

Algorithm:

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

2. Compare adjacent groups (differs by 1 bit). Mark combined terms with -.

3. Repeat until no more combinations.

4. Prime Implicants = unmarked terms.

5. Prime Implicant Chart:

   • Rows: PIs.

   • Columns: Minterms.

   • Mark covered minterms.

6. Selection:

   • Essential PIs (columns with single ✓) must be chosen.

   • For remaining, use Petrick's method or row/column dominance.

Example with Don't Cares:

$$ F(u,v,x,y,z) = \sum m(0,1,3,9,10,12,13,14) + \sum d(2,5,6,11) $$

• Treat don't cares as optional in final cover.

• Don't cares can help form larger PIs but are not required to be covered.

[!TIP] In QM, don't cares are included in combination step but not in final chart columns unless they are minterms? Actually: Don't cares are not listed as columns in prime implicant chart. They only help form larger PIs.

III. COMBINATIONAL LOGIC CIRCUITS

Universal Gates

• NAND is universal:

  • NOT: A' = A NAND A

  • AND: A·B = (A NAND B)'

  • OR: A+B = (A' NAND B')

• NOR is universal:

  • NOT: A' = A NOR A

  • OR: A+B = (A NOR B)'

  • AND: A·B = (A' NOR B')

[!TIP] Implement NOR using NAND:

$$ A+B = \overline{\overline{A+B}} = \overline{\overline{A}·\overline{B}} = (A \text{ NAND } A) \text{ NAND } (B \text{ NAND } B) $$

Arithmetic Circuits

Half Adder (HA)

• Inputs: A, B

• Outputs: Sum = $A \oplus B$, Carry = $A·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)

• Inputs: A, B, $$\displaystyle C_{in} $$

• Outputs: Sum = $$\displaystyle A \oplus B \oplus C_{in} $$, Carry = $$\displaystyle AB + BC_{in} + AC_{in} $$

• Using HAs:

  
  HA1: (A,B) → S1, C1
  
  HA2: (S1, Cin) → Sum, C2
  
  Carry = C1 + C2
  
  

Half Subtractor (HS)

• Inputs: A, B

• Outputs: Diff = $A \oplus B$, Borrow = $\overline{A}·B$

Full Subtractor (FS)

• Inputs: A, B, $$\displaystyle B_{in} $$

• Outputs: Diff = $$\displaystyle A \oplus B \oplus B_{in} $$, Borrow = $$\displaystyle \overline{A}B + \overline{A}B_{in} + BB_{in} $$

BCD Adder

• Adds two BCD digits (4-bit each).

• If sum > 9 or carry out = 1, add 0110 (6) to correct.

• Logic: $$\displaystyle C_{out} + S_3S_2 + S_3S_1 = 1 $$ → add 6.

• Excess-3 Adder: Just add two XS-3 numbers; no correction needed because XS-3 codes are self-complementing.

Carry Look-Ahead Adder (CLA)

• Generate $$\displaystyle G_i = A_iB_i $$

• Propagate $$\displaystyle P_i = A_i \oplus B_i $$

• Carry: $$\displaystyle C_{i+1} = G_i + P_iC_i $$

• Parallel carry calculation → faster than ripple.

• 4-bit CLA:

$$ \begin{aligned} C_1 &= G_0 + P_0C_0 \\ C_2 &= G_1 + P_1G_0 + P_1P_0C_0 \\ C_3 &= G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0 \\ C_4 &= G_3 + P_3G_2 + P_3P_2G_1 + P_3P_2P_1G_0 + P_3P_2P_1P_0C_0 \end{aligned} $$

Code Converters

• Binary 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 $$.

• Gray to Binary: $$\displaystyle B_3 = G_3 $$, $$\displaystyle B_2 = G_2 \oplus B_3 $$, $$\displaystyle B_1 = G_1 \oplus B_2 $$, $$\displaystyle B_0 = G_0 \oplus B_1 $$.

• Excess-3 to BCD: Subtract 0011 from each 4-bit XS-3 digit. For digit ≥ 1011 (11), borrow from next higher digit.

Multiplexers (MUX)

• Definition: $$\displaystyle 2^n:1 $$ MUX has $n$ select lines, $$\displaystyle 2^n $$ data inputs, 1 output.

$$ Y = \sum_{i=0}^{2^n-1} D_i \cdot S_i' \cdot S_{i-1}' ... $$

• Implementation of Boolean Function:

  • Connect select lines to input variables.

  • Connect data inputs to 0, 1, or variables (or their complements) based on K-map.

  • For $n$-variable function, use $$\displaystyle 2^n:1 $$ MUX or smaller MUX with external gates.

Example: 8:1 MUX for 4-var function:

• Connect B,C,D to S2,S1,S0 (3 selects).

• For each minterm $$\displaystyle m_i $$, set $$\displaystyle D_i = A $$ if $A$ appears in minterm, else $$\displaystyle D_i = A' $$ or constant.

• Or use two 4:1 MUXes with A as select between them.

Design Larger MUX from Smaller:

• 16:1 from 2:1: Use 15 2:1 MUXes in tree: 8 → 4 → 2 → 1.

• 8:1 from 4:1: Two 4:1 MUXes (LSB selects), output to 2:1 MUX (MSB select).

Demultiplexers & Decoders

• Decoder: $n$ inputs → $$\displaystyle 2^n $$ outputs (one-hot).

  • 2-to-4 Decoder: $E$ (enable), $$\displaystyle A_1A_0 $$ → $$\displaystyle Y_0 $$ to $$\displaystyle Y_3 $$.

$$ Y_i = E \cdot A_1' \cdot A_0' \text{ (for } i=0\text{)} $$

etc.

• Implementing Functions:

  • For SOP: OR outputs of decoder corresponding to minterms.

  • For POS: NAND outputs corresponding to maxterms.

• Priority Encoder: $$\displaystyle 2^n:1 $$ inputs → $n$-bit binary output + valid signal.

  • 4-bit Priority Encoder: Inputs $$\displaystyle I_3 $$ (highest) to $$\displaystyle I_0 $$.

    • If $$\displaystyle I_3=1 $$ → output 11 regardless of others.

    • Logic: $$\displaystyle Y_1 = I_3 + I_2 $$, $$\displaystyle Y_0 = I_3 + I_2'I_1 $$, $$\displaystyle V = I_3+I_2+I_1+I_0 $$.

Other Combinational Circuits

• 2-bit Binary Multiplier:

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

  • Outputs: $$\displaystyle P_3P_2P_1P_0 $$.

  • POS form: Often simpler. $$\displaystyle P_0 = A_0B_0 $$, $$\displaystyle P_1 = A_1B_0 \oplus A_0B_1 $$, etc.

• Parity Generator/Checker:

  • Even Parity: XOR all bits.

  • Odd Parity: Invert even parity output.

• 2-bit Magnitude Comparator:

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

  • $$\displaystyle A>B = A_1B_1' + A_1'A_0B_1'B_0' + A_1A_0B_1'B_0' $$? Simplify using K-map.

IV. SEQUENTIAL LOGIC CIRCUITS

Flip-Flops & Latches

[!TIP] Master-Slave JK FF: Two FFs in series. Master triggered on positive edge, slave on negative edge. Solves race-around condition (when J=K=1, output toggles continuously during clock high).

Flip-Flop Conversion

• T to JK: Use T as J and K inputs? Actually: JK to T: connect J=K=T. Reverse: $$\displaystyle J = T $$, $$\displaystyle K = T $$? No: For T FF, $$\displaystyle T = J \oplus K $$? Let's derive:

  • JK: $$\displaystyle Q^+ = J\overline{Q} + \overline{K}Q $$

  • T: $$\displaystyle Q^+ = T \oplus Q = T\overline{Q} + \overline{T}Q $$

  • So: $$\displaystyle J = T $$, $$\displaystyle K = T $$? Then $$\displaystyle Q^+ = T\overline{Q} + \overline{T}Q $$ → matches. So JK with J=K=T acts as T FF.

  • T to JK: $$\displaystyle J = K = T $$.

Shift Registers

• Universal Shift Register: Has parallel load, shift left/right, hold. Uses MUXes at each FF input.

• Ring Counter: $n$-bit shift register with output of last FF fed to first. Mod-n counter. Only one '1' at a time.

• Johnson Counter (Twisted Ring): Complement of last FF output fed to first. Mod-2n counter. Has $n$ states with 2 '1's adjacent.

Counters

Asynchronous (Ripple) Counter

• FFs triggered by previous FF's output.

• Advantage: Simple.

• Disadvantage: Propagation delay accumulates → slow.

Synchronous Counter

• All FFs triggered by same clock.

• Faster, more complex logic.

MOD-N Counter Design (JK FF)

1. Determine number of FFs: $$\displaystyle n = \lceil \log_2 N \rceil $$.

2. Draw state diagram for 0 to N-1.

3. Make state table (present state → next state).

4. Use excitation table of FF (JK: J=Q', K=1 for toggle; etc.).

5. Simplify J,K expressions using K-maps.

6. Draw circuit.

Example: MOD-6 (0→1→2→3→4→5→0) using JK:

• States: 000,001,010,011,100,101.

• Unused: 110,111 → treat as don't cares to simplify.

• JK excitation: For toggle (0→1 or 1→0): J=K=1; For hold: J=K=0; For set: J=1,K=0; Reset: J=0,K=1.

• K-maps for J2,J1,J0 with don't cares for 110,111.

Up/Down Counter

• Mode M: M=0 → down, M=1 → up.

• For synchronous: $$\displaystyle Q^+ = Q \oplus (M \cdot \text{control}) $$? Actually:

  • Up: $$\displaystyle Q^+ = Q + 1 $$

  • Down: $$\displaystyle Q^+ = Q - 1 $$

  • Use M to select between up/down logic for each FF.

Frequency Division

• n-bit ripple counter: Divide by $$\displaystyle 2^n $$.

• To get non-power-of-2 division (e.g., 120Hz → 20Hz, divide by 6):

  • Use MOD-6 counter and take output from appropriate FF.

  • Or use reset when count reaches N-1.

Pseudo-Random Binary Sequence (PRBS) Generator

• Uses linear feedback shift register (LFSR).

• XOR of certain FFs' outputs fed back to input.

• Maximal length: $$\displaystyle 2^n - 1 $$ states for n-bit LFSR with primitive polynomial.

• Example 4-bit: Feedback taps at $$\displaystyle x^4 + x^3 + 1 $$ → XOR Q3 and Q2 to D0.

Finite State Machines (FSM)

Types

• Moore: Outputs depend only on state.

• Mealy: Outputs depend on state and inputs.

Design Steps (Synchronous FSM):

1. State Diagram (with outputs).

2. State Table: Present state, inputs → next state, outputs.

3. State Assignment: Binary, Gray, one-hot.

4. Excitation Table: Add FF excitation (D, JK, T).

5. Simplify each FF input and output using K-maps.

6. Draw circuit.

ASM Chart Elements

• State Box: Represents state (outputs inside).

• Decision Box: Tests input condition (1 or 0 path).

• Conditional Output Box: Outputs that depend on input.

Sequence Detector (Mealy Example: 0011)

• Overlap allowed: e.g., 00110011 detects two sequences.

• States:

  • S0: no bits matched.

  • S1: last bit 0.

  • S2: last two 00.

  • S3: last three 001.

  • S4: detected 0011 (output 1) → next depends on last bit.

• Mealy: Output 1 when in S3 and input=1 → go to S2? Actually: after 0011, if next input=0 → state S2 (last 0), if 1 → S1? Let's trace:

  • 0011: S0→S1→S2→S3→S4 (output 1 at transition S3→S4 on input=1).

  • From S4: if input=0 → last bit is 0 → S1? But sequence 0011 ends with 1, so after 00110, we have last 0 → S1. After 00111, last 1 → S1? Actually: after 00111, the last two bits 11 don't match prefix of 0011 → should go to S0? But last bit is 1 → no match → S0. However, 00111 contains 0011 starting at bit 1? Overlap: 00111 → positions: bits 1-4: 0111 no; bits 2-5: 111 no; so only one detection at bits 1-4. So from S4 (detected), if input=0 → we have ...00110 → last bit 0 → S1. If input=1 → ...00111 → no prefix → S0.

• So: S4 on 0→S1, on 1→S0.

V. LOGIC FAMILIES AND CHARACTERISTICS

TTL (Transistor-Transistor Logic)

• Basic NAND Gate:

  • Input transistor: multi-emitter (for each input).

  • Phase splitter: single transistor.

  • Output: totem-pole (pull-up and pull-down).

• Operation:

  • Any input low → input transistor saturates → phase splitter off → output high (via pull-up).

  • All inputs high → input transistor cut-off → phase splitter on → output low (pull-down conducts).

• Tri-state TTL:

  • Adds enable control.

  • When enable low → high-impedance (Z).

  • Used for bus systems.

CMOS (Complementary MOS)

• Inverter: PMOS (pull-up) and NMOS (pull-down) in series.

  • Input high → NMOS on, PMOS off → output low.

  • Input low → PMOS on, NMOS off → output high.

• NAND: Series NMOS, parallel PMOS.

• NOR: Parallel NMOS, series PMOS.

• Advantages over TTL:

  • Low static power (only one transistor on at a time).

  • High noise margin.

  • Wide voltage range.

  • High fan-out.

  • Disadvantage: Slower than ECL, sensitive to static discharge.

ECL (Emitter-Coupled Logic)

• Basic Inverter:

  • Uses differential amplifier with constant current source.

  • No saturation → very fast (sub-ns).

  • Outputs: wired-OR possible (open-emitter).

• High-speed because transistors never saturate → small storage time.

• Disadvantage: High power dissipation, negative logic levels.

Key Parameters

VI. ADVANCED DIGITAL SYSTEMS AND PROGRAMMABLE DEVICES

FPGA (Field-Programmable Gate Array)

• Architecture:

  • Configurable Logic Blocks (CLBs): Each contains LUTs (lookup tables, usually 4-6 input), flip-flops, carry chain.

  • Programmable Interconnects: Switch matrix, routing channels.

  • I/O Blocks (IOBs): Configurable input/output.

• Block Diagram:

  
  [CLBs] -- [Routing Channels] -- [CLBs]
  
     |                          |
  
  [IOBs]                    [IOBs]
  
  

• Configuration: Stored in SRAM (volatile) → reloaded on power-up.

• Advantages: Reconfigurable, high density, short design cycle.

PLDs Overview

• PAL (Programmable AND Array, Fixed OR Array): Faster, one-time programmable.

• PLA (Programmable AND & OR Arrays): More flexible, slower.

• Difference: PAL has fixed OR plane → faster; PLA both programmable → more flexible.

Design Applications

Pulse Train Generator

• Design FSM that outputs a sequence of pulses with specific timing.

• Example: Generate 101010... → Toggle FF.

• Or use counter with decoder: e.g., 3-bit counter, decode 001,010,100 → pulse train.

Sequence Generation

• Use shift register with feedback (LFSR for PRBS).

• Or FSM with state diagram for specific sequence (e.g., 1101001).

EXAM STRATEGY & COMMON PITFALLS

1. Number System Conversions:

   • Fractional part: Multiply repeatedly; carry integer part each time.

   • Hex to Octal: Convert hex → binary → octal (group 3 bits).

2. K-map vs QM:

   • K-map: Up to 6 variables (but 5-6 messy). Use for exam problems.

   • QM: Systematic for many variables; don't cares are optional in final cover.

3. MUX Implementation:

   • If function has n variables, use $$\displaystyle 2^n:1 $$ MUX.

   • If using smaller MUX (e.g., 4:1 for 4-var function), connect 2 selects to 2 variables, data inputs from K-map for other 2 variables.

4. Counter Design:

   • Always draw state diagram first.

   • Use don't cares for unused states to simplify logic.

   • For MOD-N, ensure self-starting? Not always required in exam.

5. FSM Design:

   • Mealy vs Moore: Mealy can have fewer states but output may glitch.

   • State reduction: Use implication table or row matching.

   • ASM chart: State box (outputs), decision box (input test), conditional output box.

6. Flip-Flop Conversions:

   • Use characteristic equation and excitation table.

   • Example: T to D: $$\displaystyle D = T \oplus Q $$.

7. Logic Families:

   • TTL: Multi-emitter input, totem-pole output.

   • CMOS: Complementary pair, low power.

   • ECL: Differential pair, no saturation, fast.

[!TIP] Past Paper Focus:

• Always: Code conversions (fractional!), K-map with don't cares, QM with don't cares, full adder/subtractor, BCD adder, priority encoder, MUX implementation, master-slave JK, synchronous FSM (Mealy detector), MOD-6/7 counter, TTL/CMOS/ECL basics, FPGA block diagram.

• High Frequency: MOD-N counter design (14m), sequence detector (14m), QM (14m), BCD adder (7m), 16:1 MUX from 2:1 (6-8m).

Final Note: Practice derivations step-by-step as shown in past papers. For design questions, draw circuit diagrams clearly and label all signals. For minimization, list all prime implicants and mark essential ones.