UNIT 2: Digital Electronics Logic Design

I. Number Systems and Codes

Base Conversion Techniques

Core Principle: Positional number system. Value = Σ (digit × base^position).

Conversion Steps:

1. Integer Part: Repeated division by new base (remainders give digits, LSB first).

2. Fractional Part: Repeated multiplication by new base (integer parts give digits, MSB first).

3. Non-standard bases (e.g., base 6, 8): Same procedure, ensure digits < base.

[!TIP] Exam Focus: Fractional conversions are very frequent. Practice (53.625)₁₀ → binary and (A69.8)₁₆ → decimal. For non-standard bases (like base 6), remember valid digits are 0-5.

Binary Coded Decimal (BCD)

• Definition: 4-bit binary code representing each decimal digit separately (0000 to 1001). Invalid codes: 1010-1111.

• Key Point: Not a pure binary number. (259)₁₀ in BCD is 0010 0101 1001, not 100000011.

Gray Code

• Definition: Only one bit changes between successive numbers. Cyclic property (last to first also 1-bit change).

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

• Gray → Binary: $$\displaystyle B_n = G_n $$, $$\displaystyle B_{i-1} = B_i \oplus G_{i-1} $$ (work MSB to LSB).

[!TIP] Conversion Shortcut: For Gray→Binary, the first bit is same, subsequent bits are XOR of previous binary bit and current gray bit.

ASCII Code & Parity Error Detection

• ASCII: 7-bit code (A=1000001, B=1000010). Often stored/transmitted as 8-bit byte (MSB=0 or parity bit).

• Parity Bit: Extra bit for odd/even number of 1s in data byte.

  • Even Parity: Parity bit = 1 if data has odd 1s, else 0. Total 1s (data+parity) is even.

  • Odd Parity: Parity bit = 1 if data has even 1s, else 0. Total 1s is odd.

• Error Detection: Receiver counts total 1s. If parity doesn't match expected (even/odd), single-bit error is detected. Cannot correct or detect even-numbered bit errors.

[!EXAMPLE] Letter 'B' in ASCII: 'B' = 1000010₂ (has 2 ones).

Even Parity: Data has even 1s → Parity bit = 0. Transmitted: 0 1000010.

Odd Parity: Data has even 1s → Parity bit = 1. Transmitted: 1 1000010.

II. Boolean Algebra and Minimization

Karnaugh Map (K-Map) Method

• Purpose: Graphical minimization of SOP/POS.

• Rules:

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

  2. Don't Cares (X): Use to enlarge groups if helpful; ignore if not.

  3. Wrap-around: Top/Bottom, Left/Right edges are adjacent.

  4. Minimize literals: Larger groups → fewer literals.

  5. Essential Prime Implicant (EPI): Minterm covered by only one prime implicant. Must be in final expression.

[!TIP] Common Pitfall: Forgetting wrap-around or mis-grouping with don't cares. Always check for EPIs first.

Quine-McCluskey (Tabulation) Method

Algorithm for n>4 variables.

1. List Minterms: Group by number of 1s.

2. Combine: Compare adjacent groups (differs in 1 bit). Combine → mark with '-'. Repeat until no more combinations.

3. Prime Implicants (PIs): Uncombined terms + final combined terms.

4. Prime Implicant Chart:

   • Rows = PIs, Columns = Minterms.

   • Mark 'X' where PI covers minterm.

5. Essential Prime Implicants (EPIs): Column with only one X → corresponding PI is essential.

6. Minimal Cover: Select all EPIs. For remaining uncovered minterms, choose minimal set of remaining PIs (Petrick's method if needed).

[!FORMULA] Minimal Expression: Sum of all EPIs + minimal set of remaining PIs to cover leftover minterms.

De Morgan's Theorems

1. Two Variables: $$\displaystyle (A+B)' = A'B' $$, $$\displaystyle (AB)' = A' + B' $$

2. n Variables: $$\displaystyle \left( \sum_{i=1}^{n} x_i \right)' = \prod_{i=1}^{n} x_i' $$, $$\displaystyle \left( \prod_{i=1}^{n} x_i \right)' = \sum_{i=1}^{n} x_i' $$

3. Generalized: Complement of a function = Replace each variable with its complement, swap AND/OR, invert entire expression.

[!EXAMPLE] Complement $$\displaystyle F = a(b'c' + bc) $$:

Step 1: $$\displaystyle F' = [a(b'c' + bc)]' $$

Step 2: $$\displaystyle = a' + (b'c' + bc)' $$

Step 3: $$\displaystyle = a' + (b'c')' \cdot (bc)' $$

Step 4: $$\displaystyle = a' + (b + c) \cdot (b' + c') $$

III. Combinational Logic Design

Logic Gates & Universal Gates

• NAND/NOR are Universal: Any function can be implemented using only NAND or only NOR.

• Implementation Summary:

[!TIP] Implementation Rule: For NAND-only, convert expression to sum-of-products, then double invert each product term and final sum.

Adders and Subtractors

Half Adder (HA)

• Function: Adds 2 bits (A, B). Outputs: Sum (S), Carry (Cout).

• Truth Table:

  | A | B | S | Cout | |---|---|---|------| | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 0 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 1 |

• Equations: $$\displaystyle S = A \oplus B $$, $$\displaystyle C_{out} = AB $$

Full Adder (FA)

• Function: Adds 3 bits (A, B, Cin). Outputs: S, Cout.

• Equations: $$\displaystyle S = A \oplus B \oplus C_{in} $$, $$\displaystyle C_{out} = AB + BC_{in} + AC_{in} $$

• Implementation: 2 HAs + OR gate.

Half Subtractor (HS)

• Function: Subtracts B from A. Outputs: Difference (D), Borrow (Bout).

• Equations: $$\displaystyle D = A \oplus B $$, $$\displaystyle B_{out} = A'B $$

Full Subtractor (FS)

• Equations: $$\displaystyle D = A \oplus B \oplus B_{in} $$, $$\displaystyle B_{out} = A'B + B_{in}(A \oplus B)' $$

BCD Adder

• Purpose: Add two BCD digits (4-bit each). Output is valid BCD (0-9) or carry to next digit.

• Logic: If sum > 9 or carry_out=1, add 0110 (6) to correct. Correction logic: $$\displaystyle Y = C_{out} + S_3S_2 + S_3S_1 $$.

Multiplexers (MUX)

• Definition: $$\displaystyle 2^n : 1 $$ MUX has $ n $ select lines, $$\displaystyle 2^n $$ data inputs, 1 output. $$\displaystyle Y = \sum_{i=0}^{2^n-1} D_i \cdot m_i(S) $$.

• Design using MUX: Implement any SOP function. Connect minterms to 1, others to 0 (or use enable). Select lines = function variables.

• Example: $$\displaystyle F(A,B,C) = \Sigma m(0,2,5,6) $$ using 8:1 MUX. Connect D₀, D₂, D₅, D₆ = 1; others = 0. S₂=A, S₁=B, S₀=C.

Decoders

• Definition: $$\displaystyle n : 2^n $$ decoder. $ n $ inputs, $$\displaystyle 2^n $$ outputs, one-hot (only one output = 0 or 1 active).

• Binary to Gray Decoder: Gray code outputs = $$\displaystyle G_2 = B_2 $$, $$\displaystyle G_1 = B_2 \oplus B_1 $$, $$\displaystyle G_0 = B_1 \oplus B_0 $$.

• 3×8 Decoder: 3 inputs (A,B,C), 8 outputs (Y₀-Y₇). $$\displaystyle Y_i = m_i(A,B,C) $$. Can implement any 3-variable SOP by ORing relevant minterm outputs.

Encoders & Priority Encoder

• Encoder: $$\displaystyle 2^n : n $$. Reverse of decoder. Assumes only one input is active.

• Priority Encoder: Handles multiple active inputs. Outputs code of highest-priority (highest-numbered) active input. Includes Valid (V) output (0 if no input active) and sometimes Group Signal (GS).

Magnitude Comparators

• 2-bit Comparator: Inputs A₁A₀, B₁B₀. Outputs: A>B, A=B, A<B.

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

• A>B: $$\displaystyle A>B = A_1B_1' + (A_1 \oplus B_1)'A_0B_0' $$

• A<B: $$\displaystyle A<B = A_1'B_1 + (A_1 \oplus B_1)'A_0'B_0 $$

Parity Generators & Checkers

• Even Parity Generator: $$\displaystyle P_{even} = \bigoplus_{i=0}^{n-1} D_i $$ (XOR of all data bits).

• Even Parity Checker: $$\displaystyle Check = P_{received} \oplus \bigoplus_{i=0}^{n-1} D_i $$. Output 0 = no error (even parity), 1 = error.

• Odd Parity: Invert even parity output or generator output.

De-Multiplexers (DEMUX)

• Definition: $$\displaystyle 1 : 2^n $$ DEMUX. 1 data input, $ n $ select lines, $$\displaystyle 2^n $$ outputs. Routes input to one selected output.

• Implementation: $$\displaystyle 1:2^n $$ DEMUX = $ n $ enable lines of a $$\displaystyle (n+1):2^n $$ decoder. Connect data input to decoder enable.

IV. Sequential Logic Fundamentals

Latches vs. Flip-Flops

Flip-Flop Types & Characteristics

Master-Slave & Edge-Triggered

• Master-Slave JK FF:

  1. Master (positive level) active when CLK=1. Outputs change but isolated from slave.

  2. Slave (negative level) active when CLK=0. Master's output transferred to slave's output.

  3. Race-Around Condition: In basic JK FF (transparent when J=K=1), output may toggle multiple times in one clock pulse. Master-Slave prevents this by making output change only on clock edge (transition from 1→0).

• Edge-Triggered: Responds only to clock transition (↑ or ↓). Uses master-slave or dedicated edge-trigger circuit.

Flip-Flop Conversions

General Method: Use excitation table of target FF (JK, D, T) and characteristic equation of given FF (SR) to derive required inputs.

[!EXAMPLE] SR → JK:

From JK FF excitation table, for given (Qₙ, Qₙ₊₁), find required (J,K).

From SR FF characteristic eq: $$\displaystyle Q_{n+1} = S + R'Q_n $$.

Equate and solve: $$\displaystyle S = JQ_n' $$, $$\displaystyle R = K'Q_n $$.

Circuit: Connect J to S input via AND (with Q_n'), K to R input via AND (with Q_n).

V. Sequential Circuit Design Methodology

State Machine Concepts

1. State Diagram: Circles = states, arrows = transitions (label: inputs/outputs).

2. State Table: Lists Present State (PS), Inputs (X), Next State (NS), Outputs (Z).

3. State Equation: Boolean equation for each flip-flop's next state in terms of PS and inputs. $$\displaystyle Q_{A+1} = f(A, B, X) $$.

4. State Assignment: Assign unique binary code to each state. Guidelines: Minimize logic, avoid adjacent states differing in many bits (for one-hot or Gray).

Excitation Tables & Equations

• Purpose: Find required flip-flop inputs (J,K for JK; D for D; T for T) to cause transition from (Qₙ) to (Qₙ₊₁).

• Procedure:

  1. From state table, for each row, note (PS, NS).

  2. Use excitation table of chosen FF to find (J,K) or (D) or (T) for that transition.

  3. Create excitation equations by plotting these required inputs on K-maps (variables = PS bits + inputs).

  4. Draw logic diagram from equations.

Design Procedure (Synchronous)

1. State Diagram/Table from problem statement.

2. State Assignment (binary, Gray, one-hot).

3. Choose FF type (JK/D/T common).

4. Construct Excitation Table: Merge state table with FF excitation table.

5. Simplify excitation equations (K-map/Quine-McCluskey).

6. Draw Logic Diagram: FF inputs from equations, outputs from state/output table.

7. Timing Diagram/Verification.

VI. Counters

Asynchronous (Ripple) vs Synchronous

4-bit Synchronous Up-Down Counter

• Control (M): M=0 → Up, M=1 → Down.

• JK FF Implementation:

  • Up: T inputs = $$\displaystyle T_0=1, T_1=Q_0, T_2=Q_0Q_1, T_3=Q_0Q_1Q_2 $$

  • Down: T inputs = $$\displaystyle T_0=1, T_1=Q_0', T_2=Q_0'Q_1', T_3=Q_0'Q_1'Q_2' $$

  • Combined: $$\displaystyle T_i = M' \cdot (Up\_eq) + M \cdot (Down\_eq) $$

  • Example T₁: $$\displaystyle T_1 = M'Q_0 + M Q_0' = M \oplus Q_0 $$

Design of Custom Sequence Counters (e.g., 0-1-2-4-5-6-0)

1. State Diagram: Draw states 0,1,2,4,5,6 in sequence, back to 0.

2. State Table: PS (3 FFs needed for 6 states), NS.

3. Excitation Equations: Use JK FFs. Derive J,K for each FF from state table.

4. Simplify using K-maps. May get don't cares for unused states (3,7).

5. Check self-starting: Ensure unused states eventually enter valid sequence.

Ring Counter & Johnson Counter

• Ring Counter (n-bit): Shift register with Qₙ output fed to D₀ input. Single '1' circulates. Modulo-n. Self-decoding (only one high).

• Johnson Counter (Twisted Ring): Complement of Qₙ fed to D₀. Sequence length = 2n. States: n zeros, n ones. Example 4-bit: 0000 → 1000 → 1100 → 1110 → 1111 → 0111 → 0011 → 0001 → back to 0000.

BCD Counter (Decade Counter)

• Counts 0000 to 1001 (0-9). Resets to 0000 after 1001.

• Synchronous Design: Use 4 JK FFs. Reset logic: $$\displaystyle Reset = Q_3 Q_1 $$ (when state=1010) or $$\displaystyle Q_3 Q_2 $$. Clear FFs on next clock.

Decoding in Counters

• Purpose: Detect specific count state (e.g., for control signals, display).

• Method: Use decoder or simple gates. For active-low decoder outputs, connect counter outputs to decoder inputs. Output goes low for that state.

• Example: 1-of-10 decoder for BCD counter. Output Y₅ low when count=5 (0101).

VII. Shift Registers

Basic Configurations

4-bit Bidirectional Shift Register with Parallel Load

• Control Lines: S1 S0 (Shift control: 00=hold, 01=shift right, 10=shift left, 11=parallel load), CLK, [D₃ D₂ D₁ D₀] (parallel data).

• Operation:

  • Parallel Load (S1S0=11): $$\displaystyle Q_i = D_i $$ on clock edge.

  • Shift Right (01): $$\displaystyle Q_i = Q_{i+1} $$ (Q₃ gets serial input SI).

  • Shift Left (10): $$\displaystyle Q_i = Q_{i-1} $$ (Q₀ gets serial input SI).

  • Hold (00): $$\displaystyle Q_i = Q_i $$ (no change).

• Implementation: 4 D-FFs with multiplexers at each D input. MUX selects between parallel data, shift direction (neighbor's Q), or hold (feedback Q).

Universal Shift Register

• Definition: Supports all four operations (SISO, SIPO, PISO, PIPO) + hold.

• Block Diagram: 4 D-FFs + 4 multiplexers (4:1 each) at D inputs. Select lines S1 S0 control MUX:

  • 00: Hold (feedback Q)

  • 01: Shift Right (Q₃→Q₂, Q₂→Q₁, Q₁→Q₀, Q₀→SI_out)

  • 10: Shift Left (Q₀→Q₁, Q₁→Q₂, Q₂→Q₃, Q₃→SI_out)

  • 11: Parallel Load (D₃→Q₃, etc.)

VIII. Memory and Programmable Logic Devices

Read-Only Memory (ROM)

• Definition: Non-volatile, read-only after fabrication/programming. Stores fixed data/instructions.

• Organization: $$\displaystyle 2^n $$ address lines → $$\displaystyle 2^n $$ words, each word $ m $ bits. Decoder + OR array.

• Types:

  • PROM: Programmable once (fuse links).

  • EPROM: Erasable by UV light, reprogrammable.

  • EEPROM: Electrically erasable, byte-wise erase.

  • Flash: Fast erase/program, block-wise. Used in USB drives, SSDs.

Random-Access Memory (RAM)

• Definition: Volatile, read/write. Any address accessible in equal time.

• SRAM Cell: 6 transistors (6T) – bistable latch. Fast, used for cache.

• Read Cycle:

  1. Address applied.

  2. CS (Chip Select) and RD (Read) active.

  3. Data appears on output after access time (t_ACC).

• Write Cycle:

  1. Address and data applied.

  2. CS and WR (Write) active.

  3. Data stored after write time (t_WR). WR must be low for > t_WR.

Memory Decoding: Two-Dimensional Scheme

• Problem: Large memory (e.g., 64K x 8) needs 16 address lines. Decoder with 64K outputs is huge.

• Solution: Two-stage decoding.

  1. Split address into row (A₀-A₇) and column (A₈-A₁₅).

  2. Row Decoder: 8:256 decoder. Activates one of 256 row lines.

  3. Column Decoder: 8:256 decoder. Activates one of 256 column lines.

  4. Memory Array: 256 rows × 256 columns = 64K cells. Intersection of active row & column selects one byte.

• Advantage: Reduces decoder size from 2^16 to 2×2^8.

Programmable Logic Array (PLA)

• Structure: Programmable AND array → Programmable OR array.

• Implementation: Both product terms (AND) and sum terms (OR) are programmable.

• Flexibility: High. Can implement any SOP/POS. Product terms can be shared.

• Example: Implement $$\displaystyle F_1 = \Sigma m(3,5,7) $$, $$\displaystyle F_2 = \Sigma m(4,5,7) $$.

  • AND array: Generate minterms 3,4,5,7 as needed.

  • OR array: F1 gets outputs of m3, m5, m7. F2 gets m4, m5, m7.

Programmable Array Logic (PAL)

• Structure: Fixed OR array → Programmable AND array.

• Implementation: Each output has a fixed number of product terms (e.g., 8) ORed together. Product terms are programmable.

• Flexibility: Lower than PLA. Faster, cheaper. Output structure fixed (cannot share PTs between outputs easily).

• Use Case: Simple functions with limited product terms per output.

Sequential PLDs & Basic Microcell

• Sequential PLD: Includes flip-flops on outputs. Can implement both combinational and sequential logic.

• Basic Microcell: One AND-OR logic cell + one flip-flop. Output of OR feeds D input of FF. FF output can be fed back to AND array for state machines.

Data Converters

Digital-to-Analog Converter (DAC): R-2R Ladder

• Principle: Uses two resistors (R, 2R) in ladder network. Each digital bit controls a switch to Vref or GND.

• Operation: Each bit position has Thevenin equivalent of $$\displaystyle V_{out} = -V_{ref} \times \frac{D_{n-1}}{2} + ... $$. For n-bit unsigned, $$\displaystyle V_{out} = -V_{ref} \times \frac{D_{binary}}{2^n} $$.

• Advantages: Only 2 resistor values, excellent matching, monotonic.

Analog-to-Digital Converter (ADC): Successive Approximation

• Components: Successive Approximation Register (SAR), DAC, Comparator, Control logic.

• Procedure (n bits):

  1. Start: SAR = 100...0 (MSB=1).

  2. DAC converts SAR value to analog $$\displaystyle V_{DAC} $$.

  3. Comparator: $$\displaystyle V_{in} $$ vs $$\displaystyle V_{DAC} $$.

  4. If $$\displaystyle V_{in} \geq V_{DAC} $$, keep bit=1; else clear bit=0.

  5. Shift left (next bit=1), repeat step 2-4 for n cycles.

• Result: SAR holds digital approximation after n clock cycles.

• Advantage: Fast (n cycles), moderate cost. Disadvantage: Sample-and-hold required for AC signals.

[!BOX] Key Formula: R-2R Ladder Output (n-bit, unsigned, Vref positive):

$$ V_{out} = -\frac{V_{ref}}{2^n} \left( D_{n-1} \cdot 2^{n-1} + D_{n-2} \cdot 2^{n-2} + ... + D_0 \cdot 2^0 \right) $$

Successive Approximation ADC Time: n clock periods for n-bit conversion.