UNIT 2: DIGITAL SYSTEM DESIGN

1.0 NUMBER SYSTEMS & CONVERSIONS

1.1 Conversion Between Bases

• Core Principle: Positional number system. Value = $$\displaystyle \sum_{i=-k}^{n} d_i \times base^i $$, where $$\displaystyle d_i $$ is digit.

• Integer Conversion (Base A → Base B):

  1. Repeated division by B for integer part. Remainders in reverse order give result.

  2. For fractional part: repeated multiplication by B. Integer parts in forward order.

• Base Conversion to/from Decimal: Most common. Use division/multiplication method.

• Direct Conversion (e.g., Hex → Bin): Convert each digit to its 4-bit binary equivalent.

• Example: $$\displaystyle (426)_8 \rightarrow (100010110)_2 \rightarrow (278)_{10} \rightarrow (10A)_{16} $$.

• [!TIP] For fractional conversions, multiply until fractional part becomes zero or desired precision. Trailing zeros in binary may indicate repeating fraction.

1.2 Binary ↔ Gray Code Conversion

• Binary to Gray (Reflective Code):

  • MSB of Gray = MSB of Binary.

  • $$\displaystyle G_i = B_{i+1} \oplus B_i $$ (XOR of consecutive binary bits).

• Gray to Binary:

  • MSB of Binary = MSB of Gray.

  • $$\displaystyle B_i = B_{i+1} \oplus G_i $$ (Cumulative XOR).

• Property: Only one bit changes between successive Gray codes.

2.0 BOOLEAN ALGEBRA & SIMPLIFICATION TECHNIQUES

2.1 Boolean Algebra Postulates & Theorems

• De Morgan's Theorem (High Frequency):

  • Statement: $$\displaystyle \overline{A+B} = \bar{A} \cdot \bar{B} $$; $$\displaystyle \overline{A \cdot B} = \bar{A} + \bar{B} $$.

  • Proof: Via truth table or set theory.

  • Application: Used to convert between SOP and POS, implement NAND/NOR logic.

  • [!TIP] "Break the bar, change the sign." Complement of sum is product of complements.

2.2 Karnaugh Map (K-Map) Minimization (Extremely High Frequency)

• Rules for Grouping:

  • Groups must be powers of 2 (1, 2, 4, 8, ...).

  • Groups must be adjacent (horizontally/vertically, wrap-around allowed).

  • Don't Care (Σd) conditions can be included to form larger groups or excluded.

  • Aim for largest possible groups, then minimum number of groups.

• Key Terms:

  • Prime Implicant (PI): Largest possible group (power of 2) that cannot be combined further.

  • Essential Prime Implicant (EPI): PI that covers a minterm not covered by any other PI.

• Minimization Process:

  1. Plot K-map (2-variable: 2x2; 3-variable: 2x4; 4-variable: 4x4 with Gray code ordering).

  2. Group 1s for SOP (minterms). Group 0s for POS (maxterms).

  3. Write product terms: variable included if constant within group; complemented if 0; omitted if both 0/1 appear.

• Example SOP: Group with A=1, B varies, C=0, D=1 → Term = $A\bar{C}D$.

• [!TIP] Always check for overlapping groups to ensure all minterms covered. Use Petrick's method for minimal cover if multiple solutions.

2.3 Quine-McCluskey (Tabular) Method (High Frequency)

• Steps:

  1. List Minterms: Sort minterms in ascending order. Group by number of 1s in binary.

  2. Combine Adjacent Minterms: Compare groups i and i+1. Combine if differ by one bit (position marked with -). Repeat until no further combination.

  3. Identify Prime Implicants: Uncombined terms from all iterations are PIs.

  4. Prime Implicant Chart: Rows = PIs, Columns = Minterms. Mark X if PI covers minterm.

  5. Selection of Essential PIs: Columns with single X → corresponding PI is essential.

  6. Reduce Chart: Remove covered minterms. For remaining, use Petrick's method or trial-and-error for minimal cover.

• Handling Don't Cares:

  • Treat d as either 0 or 1 to maximize combination.

  • Do not include d in final cover (they are optional).

• Advantage: Systematic for >4 variables. Disadvantage: Tedious, exponential growth.

• [!TIP] In step 2, only compare adjacent groups. Mark combined terms with - and keep track of which minterms are combined.

3.0 COMBINATIONAL LOGIC DESIGN

3.1 Arithmetic Circuits

• Half Adder:

  • Inputs: A, B.

  • Outputs: Sum = $A \oplus B$, Carry = $A \cdot B$.

  • Truth Table: 4 rows.

• Full Adder (Very High Frequency):

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

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

  • Design using Two Half Adders: $$\displaystyle S = HA_1(A,B) \oplus C_{in} $$; $$\displaystyle C_{out} = HA_1(Carry) + (HA_1(Sum) \cdot C_{in}) $$.

• Half Subtractor:

  • Inputs: A, B.

  • Outputs: Diff = $A \oplus B$, Borrow = $\bar{A}B$.

• Full Subtractor:

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

  • Outputs: Diff = $$\displaystyle A \oplus B \oplus B_{in} $$, $$\displaystyle B_{out} = \bar{A}B + \bar{A}B_{in} + BB_{in} $$.

• BCD Adder (Very High Frequency):

  • Need: Add two BCD digits (0-9). If sum >9 or carry out, add 6 (0110) for correction.

  • Correction Logic: $$\displaystyle C_{out} = S_3(S_2 + S_1) + S_3S_2 $$ (for 4-bit sum $$\displaystyle S_3S_2S_1S_0 $$).

  • Circuit: Two 4-bit binary adders. First adds BCD inputs. Second adds 6 if correction needed ($$\displaystyle C_{out} $$ or $$\displaystyle S_3(S_2+S_1) $$).

• Carry Look-Ahead Adder:

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

  • $$\displaystyle C_{i+1} = G_i + P_i C_i $$. Compute carries in parallel → faster than ripple carry.

  • Advantage: Reduced propagation delay, $O(\log n)$ vs $O(n)$.

3.2 Code Converters

• Excess-3 to Gray (Design Example):

  1. Create truth table (Excess-3 inputs A,B,C,D → Gray outputs G3,G2,G1,G0).

  2. Minimize each output using K-map/QM.

  3. Implement with gates.

3.3 Encoders & Decoders

• Priority Encoder (4-bit) (Very High Frequency):

  • Inputs: $$\displaystyle I_3, I_2, I_1, I_0 $$ ($$\displaystyle I_3 $$ highest priority).

  • Outputs: $$\displaystyle Y_1, Y_0 $$ (binary code of highest priority 1), $V$ (valid, =1 if any input 1).

  • Truth Table: 16 rows. $$\displaystyle V = I_3 + I_2 + I_1 + I_0 $$.

  • Equations: $$\displaystyle Y_1 = I_3 + I_2I_1' $$; $$\displaystyle Y_0 = I_3 + I_2I_1 + I_1I_0' $$ (example, verify).

• Multiplexers (MUX):

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

  • Implementation as Universal Gate: Tie $$\displaystyle S_1=S_0=0 $$ → $$\displaystyle Y=D_0 $$ (buffer); $$\displaystyle D_0=1, D_1=0 $$ → NOT; etc.

  • Implementing Boolean Functions:

    • Connect n variables to select lines (for 2^n:1 MUX).

    • Connect data inputs to 0/1 or complemented variables based on K-map values for each select combination.

  • 16:1 MUX using 2:1 MUX:

    • Hierarchical design. 16 inputs → 8 MUXes (2:1) → 4 MUXes → 2 MUXes → 1 MUX.

    • Total 15 2:1 MUXes. Select lines distributed.

• Demultiplexers (DEMUX): Reverse of MUX. 1 input → multiple outputs based on select.

3.4 Comparators & Parity Circuits

• Magnitude Comparator (2-bit):

  • Inputs: A1A0, B1B0.

  • Outputs: A>B, A=B, A<B.

  • Equations: $$\displaystyle A>B = A_1\bar{B_1} + A_1A_0\bar{B_0} + A_0\bar{B_1}\bar{B_0} $$ (simplify via K-map).

• Parity Generator/Checker:

  • Even Parity: XOR of all data bits + parity bit = 0.

  • Generator: $$\displaystyle P = D_n \oplus D_{n-1} \oplus ... \oplus D_0 $$.

  • Checker: At receiver, XOR all bits (including P). Output 0 if even parity correct.

3.5 Universal Gate Implementation

• Using NAND Only:

  • NOT: Input tied together.

  • AND: NAND + NAND (invert output).

  • OR: De Morgan → $(A' \cdot B')'$ (NAND inputs inverted via NOT).

  • NOR: $$\displaystyle (A+B)' = (A' \cdot B')' $$ (invert inputs first).

  • XOR: $$\displaystyle A \oplus B = (A \cdot B')' + (A' \cdot B)' $$ (4 NANDs).

• Using NOR Only (Dual of NAND).

• [!TIP] Always minimize number of gates. For XOR, standard 4-NAND or 5-NOR implementation.

4.0 SEQUENTIAL LOGIC FUNDAMENTALS: FLIP-FLOPS & LATCHES

4.1 Basic Latch (SR Latch)

• NOR SR Latch:

  • Equations: $$\displaystyle Q_{next} = S + \bar{R}Q $$ (with $$\displaystyle S \cdot R = 0 $$ constraint).

  • Invalid State: $$\displaystyle S=R=1 $$ → $$\displaystyle Q=\bar{Q}=0 $$ (unstable).

• NAND SR Latch (Active Low): $$\displaystyle S'=R'=0 $$ invalid.

4.2 Edge-Triggered Flip-Flops

• General: Synchronous, changes on clock edge (positive/negative).

• S-R Flip-Flop (Clocked):

  • Characteristic Table: $$\displaystyle S=R=0 $$: no change; $$\displaystyle S=1,R=0 $$: set; $$\displaystyle S=0,R=1 $$: reset; $$\displaystyle S=R=1 $$: invalid.

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

• J-K Flip-Flop (Extremely High Frequency):

  • Truth Table: $$\displaystyle J=K=0 $$: no change; $$\displaystyle J=1,K=0 $$: set; $$\displaystyle J=0,K=1 $$: reset; $$\displaystyle J=K=1 $$: toggle.

  • Characteristic Equation: $$\displaystyle Q_+ = J\bar{Q} + \bar{K}Q $$.

  • Race-Around Condition:

    • Cause: When $$\displaystyle J=K=1 $$, output toggles continuously during clock high level if propagation delay < clock pulse width.

    • Elimination: Use Master-Slave (two FFs, negative edge triggered slave) or edge-triggered design.

  • Master-Slave J-K FF:

    • Construction: Master (positive level) → Slave (negative edge). Output changes on negative edge.

    • Working: Master follows inputs during clock high; slave updates on clock low. Prevents race-around.

    • Waveform: Output changes only at negative edge.

• D Flip-Flop:

  • Equation: $$\displaystyle Q_+ = D $$.

  • Use: Single data input, avoids invalid state. Used in registers, FSM.

• T Flip-Flop:

  • Equation: $$\displaystyle Q_+ = T \oplus Q $$ or $$\displaystyle Q_+ = T\bar{Q} + \bar{T}Q $$.

  • Use: Toggle counter. $$\displaystyle T=1 $$ toggles on each clock.

4.3 Flip-Flop Conversion

• Procedure: Use excitation table of target FF. Derive input equations from present state (Q) and next state ($$\displaystyle Q_+ $$) using K-maps.

• Example: T to J-K:

  • J = T, K = T (since J-K toggles when J=K=1).

  • Verify with excitation table.

5.0 COUNTERS & SHIFT REGISTERS

5.1 Counters

• Synchronous vs Asynchronous (Ripple):

  | Feature | Synchronous | Asynchronous | |---|---|---| | Clock | All FFs same clock | FF outputs clock next FF | | Speed | Fast (no ripple delay) | Slow (cumulative delay) | | Glitches | Minimal | Possible due to ripple | | Design | Complex (logic for each FF input) | Simple (connect FF outputs) |

• Design of Synchronous Counters (Using J-K FFs):

  1. State Diagram: Define sequence (e.g., 0→1→2→3→0 for MOD-4).

  2. State Table: Present state (Q1Q0) → Next state.

  3. Excitation Table: For each FF, determine J,K from present and next state.

  4. K-Maps: For J1,K1 and J0,K0. Minimize.

  5. Logic Diagram: Implement J,K equations with gates.

• MOD-N Counter: Counts 0 to N-1. Uses $$\displaystyle \lceil \log_2 N \rceil $$ FFs. Unused states must transition to valid states (self-correcting).

• Pseudo-Random Binary Sequence (PRBS) Generator:

  • Concept: Shift register with feedback XOR taps based on primitive polynomial.

  • Maximal Length: For n-bit, sequence length $$\displaystyle 2^n - 1 $$.

  • Example: 4-bit PRBS with taps at $$\displaystyle x^4 + x^3 + 1 $$ → feedback = $$\displaystyle Q_3 \oplus Q_2 $$.

• Pulse Train Generator: Divide input frequency by N. Use counter to generate single pulse after N counts.

5.2 Shift Registers

• Basic Types:

  • SISO: Serial In, Serial Out.

  • SIPO: Serial In, Parallel Out.

  • PISO: Parallel In, Serial Out.

  • PIPO: Parallel In, Parallel Out.

• Universal Shift Register (High Frequency):

  • Modes: Hold (00), Shift Left (01), Shift Right (10), Parallel Load (11).

  • Design: Use 2:1 MUX at each D input of FF. Select lines control mode. For shift left/right, connect adjacent FF outputs.

• Ring Counter:

  • Connection: Output of last FF fed to input of first.

  • 4-bit: States: 1000 → 0100 → 0010 → 0001 → 1000...

  • States: n bits → n states. Needs initialization (single 1).

• Johnson (Twisted Ring) Counter:

  • Connection: Inverted output of last FF fed to input of first.

  • 4-bit: States: 0000 → 1000 → 1100 → 1110 → 1111 → 0111 → 0011 → 0001 → 0000...

  • States: 2n states.

• Applications: Serial-parallel conversion, time delay, pattern generation.

6.0 FINITE STATE MACHINES (FSM) & ASM CHARTS

6.1 FSM Fundamentals

• Moore Machine:

  • Outputs depend only on present state.

  • Advantage: Glitch-free outputs. Disadvantage: More states for same function.

• Mealy Machine:

  • Outputs depend on present state and inputs.

  • Advantage: Fewer states. Disadvantage: Output may glitch if inputs change asynchronously.

• State Diagram: Circles (states), arrows (transitions labeled input/output).

• State Table: Present state, input → next state, output.

• State Assignment: Binary, Gray (adjacent states differ by 1 bit), One-Hot (one FF per state).

• State Reduction:

  • Implication Table Method: Two states equivalent if for all inputs, next states and outputs are equivalent.

  • Goal: Minimize number of states.

• Capabilities & Limitations:

  • Capable: Recognize regular languages, sequence detection, control units.

  • Limitation: Cannot count arbitrarily high (unbounded memory) → need counters/registers.

6.2 ASM (Algorithmic State Machine) Charts

• Basic Elements:

  • State Box: Represents a state. Contains outputs (Moore) and register operations.

  • Decision Box: Diamond shape. Tests input condition (1 bit). Branches to states.

  • Conditional Output Box: Oval. Outputs dependent on path (Mealy).

• Construction: Convert state diagram → ASM chart (each state becomes box, transitions with conditions). Or vice-versa.

• Design from ASM:

  1. Derive state table from ASM (each path through decision boxes).

  2. Assign state codes.

  3. Design FF input equations (like synchronous counter).

  4. Output equations (Moore from state bits; Mealy from state and inputs).

6.3 FSM Design Examples

• Sequence Detector (Overlapping):

  • Example: Detect 0011 (Mealy).

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

  • Overlapping: After detecting 0011, last 11 can be start of new sequence → from S4 on next 1 go to S3.

  • Design Steps: State diagram → table → assign (e.g., binary) → K-maps for D/J/T inputs and output.

7.0 LOGIC FAMILIES & CHARACTERISTICS

7.1 TTL (Transistor-Transistor Logic)

• Standard TTL NAND Gate:

  • Circuit: Multi-emitter input transistor, phase splitter, totem-pole output.

  • Operation: Input high → current into emitter → transistor on → output low. Input low → transistor off → output high via pull-up.

  • Voltage Levels: $$\displaystyle V_{IL} \approx 0.8V $$, $$\displaystyle V_{IH} \approx 2.0V $$, $$\displaystyle V_{OL} \approx 0.2V $$, $$\displaystyle V_{OH} \approx 3.4V $$ (for 5V supply).

  • Fan-out: ~10 (TTL loads).

  • Propagation Delay: ~10ns.

• Tri-State TTL Gate (Very High Frequency):

  • Circuit: Standard TTL gate + enable control (active low EN'). When EN'=0, output enabled (high-Z when EN'=1).

  • Operation: Enable controls output transistors via additional gates.

  • Application: Bus systems (multiple devices share line, only one enabled at a time).

7.2 ECL (Emitter-Coupled Logic)

• Basic ECL Inverter/OOR:

  • Circuit: Differential pair with constant current source. Reference voltage $$\displaystyle V_{ref} $$ set by resistor divider.

  • Operation: Input high → transistor on → output low (via collector). Input low → opposite transistor on → output high.

  • Advantages: Very high speed (ns), constant current (low power noise), no saturation → no storage delay.

  • Disadvantages: High power consumption, negative logic (-5.2V supply), poor noise margins.

7.3 CMOS (Complementary MOS)

• CMOS Inverter:

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

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

  • Static Power: Near zero (only leakage, no direct path VDD-GND).

  • Noise Margins: High ($$\displaystyle NM_H \approx 2.9V $$, $$\displaystyle NM_L \approx 2.9V $$ for 5V).

• CMOS NAND/NOR: Series/parallel combinations of transistors.

• Advantages over TTL: Low static power, high noise margin, high density, wide supply range (3-15V).

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

7.4 Key Parameters

• Fan-in: Number of inputs a gate can have. Increases input capacitance → slower.

• Fan-out: Number of identical gates a gate can drive. Limited by input current/ capacitance.

• Noise Margin:

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

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

  • Significance: Maximum noise voltage that can be tolerated without erroneous logic.

• Propagation Delay: Average of $$\displaystyle t_{PLH} $$ (low→high) and $$\displaystyle t_{PHL} $$ (high→low). Determines speed.

• Power Dissipation: $$\displaystyle P = V_{CC} \times I_{CC} $$ (static + dynamic).

8.0 PROGRAMMABLE LOGIC DEVICES (PLDs)

8.1 FPGA (Field-Programmable Gate Array) (Very High Frequency)

• Basic Architecture:

  • Configurable Logic Blocks (CLBs): Look-Up Tables (LUTs, typically 4-6 input) + flip-flops.

  • Programmable Interconnects: Switch matrix and routing tracks (programmed via configuration memory).

  • I/O Blocks (IOBs): Programmable input/output buffers (often support multiple standards).

• Configuration Memory:

  • SRAM-based: Volatile, reprogrammable (most common). Loaded at power-up from external memory.

  • Anti-fuse: One-time programmable, non-volatile, faster, lower power.

• Advantages: High density, reprogrammability, short design cycle, suitable for prototyping and low-volume.

• Applications: Digital signal processing, prototyping ASICs, communication systems.

8.2 CPLD (Complex PLD)

• Architecture: Sea-of-gates (AND-OR) based. Macrocells with product terms.

• Comparison with FPGA:

  | Feature | CPLD | FPGA | |---|---|---| | Architecture | AND-OR | LUT-based | | Density | Lower | Higher | | Speed | Predictable (deterministic) | Variable (depends on routing) | | Volatility | Often non-volatile | Usually volatile | | Use | Simple glue logic, small designs | Complex, high-density designs |

8.3 PAL & PLA

• PAL (Programmable Array Logic): Programmable AND array, fixed OR array. Faster, less flexible.

• PLA (Programmable Logic Array): Both AND and OR arrays programmable. Most flexible, but slower and larger.

• Difference: PAL has fixed OR, PLA both programmable. PAL faster, PLA more general.

BOXED KEY FORMULAS & EQUATIONS

• De Morgan's Theorem: $$\displaystyle \boxed{\overline{A+B} = \bar{A} \cdot \bar{B} \quad ; \quad \overline{A \cdot B} = \bar{A} + \bar{B}} $$

• Full Adder: $$\displaystyle \boxed{Sum = A \oplus B \oplus C_{in} \quad ; \quad C_{out} = AB + AC_{in} + BC_{in}} $$

• BCD Adder Correction: $$\displaystyle \boxed{Correction = C_{out} + S_3(S_2 + S_1)} $$

• J-K Flip-Flop: $$\displaystyle \boxed{Q_+ = J\bar{Q} + \bar{K}Q} $$

• D Flip-Flop: $$\displaystyle \boxed{Q_+ = D} $$

• T Flip-Flop: $$\displaystyle \boxed{Q_+ = T \oplus Q} $$

• Noise Margin: $$\displaystyle \boxed{NM_H = V_{OH(min)} - V_{IH(min)} \quad ; \quad NM_L = V_{IL(max)} - V_{OL(max)}} $$

• Carry Look-Ahead: $$\displaystyle \boxed{C_{i+1} = G_i + P_i C_i \quad \text{where} \quad G_i = A_iB_i, \quad P_i = A_i \oplus B_i} $$

EXAM TIPS & COMMON PITFALLS

• K-Map: Always verify all minterms covered. Don't cares are optional – use them to enlarge groups but don't rely on them for essential primes.

• Quine-McCluskey: In prime implicant chart, if no essential primes, use Petrick's method or iterative selection. Don't forget to include all PIs.

• Counter Design: For MOD-N, ensure unused states transition to valid states (self-correcting). Check excitation table carefully.

• FSM: Clearly distinguish Moore (outputs from state box) vs Mealy (outputs from decision/conditional box). Overlapping sequence detection requires careful state design.

• Flip-Flops: Master-slave J-K avoids race-around but is still level-triggered. Modern designs use edge-triggered master-slave or positive edge with two-stage delay.

• Logic Families: Remember TTL uses multi-emitter input; CMOS has near-zero static power; ECL is fastest but power-hungry.

• Number Systems: Fractional binary to octal/hex: group bits in 3s/4s from binary point outward. Pad with zeros if needed.

• MUX Implementation: For 2^n:1 MUX, n select lines. If function has n variables, connect n-1 to selects, use data inputs for remaining variable combinations.