Digital Electronics Logic Design (EX-403) - Unit 5 Short Notes

UNIT 5: Digital Electronics Logic Design - Comprehensive Short Notes

I. Number Systems and Code Conversions

Base Conversion Techniques

• Decimal to Binary (Integer): Repeated division by 2. Remainders read bottom-up.

  • Example: $$\displaystyle (53)_{10} $$ → $$\displaystyle (110101)_2 $$

• Decimal to Binary (Fractional): Repeated multiplication by 2. Integer parts read top-down.

  • Example: $$\displaystyle (0.625)_{10} $$ → $$\displaystyle 0.101_2 $$ (0.625×2=1.25→1, 0.25×2=0.5→0, 0.5×2=1.0→1)

• Hexadecimal to Binary: Convert each hex digit to its 4-bit binary equivalent.

  • Example: $$\displaystyle (3FD)_{16} $$ → $$\displaystyle 0011\ 1111\ 1101_2 $$ → $$\displaystyle (1111111101)_2 $$

• Hexadecimal to Decimal: Multiply each digit by $$\displaystyle 16^n $$ (n=position from right, starting 0) and sum.

  • Example: $$\displaystyle (A69.8)_{16} = 10×16^2 + 6×16^1 + 9×16^0 + 8×16^{-1} = 2665.5_{10} $$

• Octal to Decimal: Multiply each digit by $$\displaystyle 8^n $$ and sum.

  • Example: $$\displaystyle (726.56)_8 = 7×8^2 + 2×8^1 + 6×8^0 + 5×8^{-1} + 6×8^{-2} = 470.359375_{10} $$

• Conversion between Non-Standard Bases (e.g., base-6, base-8): Use decimal as intermediate or grouping method if bases are powers (e.g., octal↔binary: 3 bits per octal digit).

Binary to Other Code Conversions

• Binary to Octal: Group bits in 3s from right (integer) / left (fraction). Pad with zeros if needed.

  • Example: $$\displaystyle (101.1011)_2 $$ → $$\displaystyle (5.54)_8 $$

• Binary to Gray Code:

  1. MSB same as binary MSB.

  2. Each subsequent Gray bit = XOR of current binary bit and previous binary bit.

  • Example: Binary $110101.101101$ → Gray $101111.111110$

[!TIP] Exam Alert: For fractional conversions, be meticulous with the point position. Always verify by converting back.

II. Boolean Algebra and Logic Minimization

Boolean Algebra Postulates & Theorems

• De Morgan's Theorems (for n variables):

$$\overline{A_1 + A_2 + ... + A_n} = \overline{A_1} \cdot \overline{A_2} \cdot ... \cdot \overline{A_n}$$

$$\overline{A_1 \cdot A_2 \cdot ... \cdot A_n} = \overline{A_1} + \overline{A_2} + ... + \overline{A_n}$$

> **For 2 variables:** $$\displaystyle \overline{A+B} = \overline{A}\cdot\overline{B} $$ ; $$\displaystyle \overline{A\cdot B} = \overline{A}+\overline{B} $$

• Complement of Boolean Expression: Apply De Morgan's repeatedly, changing OR to AND, AND to OR, and complementing each literal.

  • Example: $$\displaystyle F = a(b'c' + bc) $$

  • $$\displaystyle \overline{F} = \overline{a(b'c' + bc)} = \overline{a} + \overline{(b'c' + bc)} = \overline{a} + (\overline{b'c'} \cdot \overline{bc}) $$

  • $$\displaystyle = \overline{a} + ((b+c) \cdot (b'+c')) $$

Karnaugh Map (K-Map) Minimization

• SOP (Sum of Products): Group 1s (minterms). Groups must be $$\displaystyle 2^n $$ size (1,2,4,8...). Wrap-around allowed.

• POS (Product of Sums): Group 0s (maxterms). Result is product of sum terms.

• Don't Care Conditions (d): Can be treated as 1 or 0 to maximize group size. Mark with 'X' or 'd'.

• Prime Implicant (PI): Largest possible group of 1s/don't cares not contained in any larger group.

• Essential Prime Implicant (EPI): A PI that covers at least one minterm not covered by any other PI. Must be included in final expression.

Quine-McCluskey (Tabulation Method)

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

2. Combine adjacent groups (differ by 1 bit). Mark combined terms with '-'. Repeat until no more combinations.

3. Prime Implicants: Unmarked terms from final table.

4. Prime Implicant Chart: Rows = minterms, Columns = PIs. Mark 'X' where PI covers minterm.

5. Essential PIs: Columns with single 'X'. Cover remaining minterms with minimal set of PIs (Petrick's method if needed).

6. With Don't Cares: Include don't cares in initial list but do not list them as minterms to be covered in the final chart.

[!TIP] Common Pitfall: In K-maps, avoid groups of size 1 if a larger group is possible. In Quine-McCluskey, ensure all possible combinations are done (including across groups).

III. Combinational Logic Circuits

Arithmetic Circuits

Data Processing Circuits

• Encoder: $$\displaystyle 2^n $$ inputs → n outputs. Active-High/Low must be specified. Priority Encoder: If multiple inputs active, output code of highest-priority input.

• Decoder: n inputs → $$\displaystyle 2^n $$ outputs. Each output = minterm. Binary-to-Gray Decoder: Outputs are Gray codes corresponding to binary input.

• Multiplexer (MUX): $$\displaystyle 2^n $$ data inputs, n select lines, 1 output. $$\displaystyle Y = \Sigma m_i(D_i \cdot S_i) $$.

  • Implementation: Express F as SOP. Each product term → one data input. Select lines = remaining variables.

• Demultiplexer (DEMUX): 1 data input, n select lines, $$\displaystyle 2^n $$ outputs. $$\displaystyle O_i = D \cdot S_i' $$.

Comparators

• Magnitude Comparator (2-bit):

  • $$\displaystyle A>B $$: $$\displaystyle A_1\overline{B_1} + A_1A_0\overline{B_1B_0} + A_0\overline{B_0} $$

  • $$\displaystyle A=B $$: $$\displaystyle (A_1 \odot B_1)(A_0 \odot B_0) $$

  • $$\displaystyle A<B $$: $$\displaystyle \overline{A_1}B_1 + \overline{A_1A_0}B_1B_0 + \overline{A_0}B_0 $$

Error Detection: Parity

• Parity Generator: Adds extra bit to data to make total 1s even (even parity) or odd (odd parity).

• Parity Checker: At receiver, count 1s. If parity doesn't match, error detected.

• Example (ASCII 'B' = 0100010, odd parity):

  • Data bits: 0100010 → has 2 ones (even).

  • For odd parity, add 1 as parity bit → Transmitted: 1 0100010 (now 3 ones, odd).

  • Receiver checks total 1s. If even → error.

IV. Sequential Logic Fundamentals

Latches vs. Flip-Flops

Flip-Flop Types

• SR Flip-Flop:

  • Truth Table: S=1,R=1 → Invalid/Forbidden (Q=Q'=1).

  • Clocked: Changes only on clock edge/pulse.

• D Flip-Flop:

  • Positive Edge: Output Q follows D at rising edge.

  • Negative Edge: Output Q follows D at falling edge.

  • Circuit: Basic D latch + 2 NAND gates for edge-triggering (or use master-slave).

• JK Flip-Flop:

  • Master-Slave: Two latches (master on CLK=1, slave on CLK=0). Prevents race-around condition (output toggling multiple times when J=K=1).

  • Truth Table: J=K=1 → Toggle ($$\displaystyle Q_{next} = \overline{Q} $$).

• T Flip-Flop: T=1 → Toggle, T=0 → Hold. $$\displaystyle Q_{next} = T \oplus Q $$.

Flip-Flop Excitation Tables (Required inputs for given transition)

Flip-Flop Conversion (e.g., SR to JK)

1. Write excitation table for target FF (JK).

2. Write characteristic table for given FF (SR).

3. Create combined truth table for $J,K$ inputs and $$\displaystyle Q_n, Q_{n+1} $$.

4. Derive input equations for given FF (S,R) in terms of J,K,$$\displaystyle Q_n $$ using K-map.

5. Draw circuit using given FF with derived equations.

   • For SR→JK: $$\displaystyle S = J\overline{Q_n}' $$, $$\displaystyle R = KQ_n $$ (Ensure S=R=1 never occurs).

V. State Machine Design and Analysis

State Diagrams & State Tables

• State Diagram: Circles = states, arrows = transitions labeled input/output (Mealy) or output only (Moore).

• State Table: Columns: Present State (PS), Input (x), Next State (NS), Output (z).

• State Equation: Boolean equation for each flip-flop input (e.g., $$\displaystyle J_A, K_A $$) and output z, in terms of current state variables and inputs.

State Assignment

• Assign unique binary codes to each state.

• Guidelines: Minimize flip-flop input equations. Use Gray code for adjacency if possible.

Design Procedure (Synchronous Sequential Circuit)

1. Specification → State Diagram/Table.

2. State Assignment (choose binary codes).

3. Expand State Table: For each (PS, Input), write NS (binary) and Output.

4. Excitation Table: For each flip-flop (e.g., JK), use excitation table to find required inputs (J,K) for PS→NS transition.

5. K-Maps: Plot J,K (and z) as functions of PS variables and inputs. Minimize.

6. Logic Diagram: Draw FF with derived input equations.

7. Timing Diagram: Verify operation.

Sequential Circuit Analysis (Given Circuit)

1. Write characteristic equations for each FF (e.g., D: $$\displaystyle Q^+=D $$; JK: $$\displaystyle Q^+=J\overline{Q}+ \overline{K}Q $$).

2. Write output equation (z) in terms of inputs and state variables.

3. Derive state equations by substituting FF input equations into characteristic equations.

4. Construct state table from state equations.

5. Draw state diagram from state table.

VI. Counters

Asynchronous (Ripple) Counters

• Operation: FF0 toggles on clock edge. FF1 toggles on FF0's 1→0 transition (negative edge of Q0). Propagation delay cumulative (ripple).

• Waveform: Q0 frequency = $$\displaystyle f_{clk}/2 $$, Q1 = $$\displaystyle f_{clk}/4 $$, etc.

• Disadvantage: Unreliable at high speed due to ripple delay.

Synchronous Counters

• All FFs clocked simultaneously by same clock.

• Design (JK FF):

  1. Draw state diagram/table for desired sequence.

  2. Use excitation table for JK FF to find required J,K for each flip-flop for all transitions.

  3. Simplify J,K equations using K-maps.

  4. Implement.

Up, Down, Up-Down Counters (4-bit)

• Up: $$\displaystyle Q_{n+1} = Q_n + 1 $$. For JK: $$\displaystyle J=K=Q_0'Q_1'...Q_{n-1}' $$ (toggle when all lower bits are 1).

• Down: $$\displaystyle Q_{n+1} = Q_n - 1 $$. For JK: $$\displaystyle J=K=Q_0Q_1...Q_{n-1} $$ (toggle when all lower bits are 0).

• Up-Down: Use mode control (M). $$\displaystyle J=K = M \cdot (\text{lower bits all 1}) + \overline{M} \cdot (\text{lower bits all 0}) $$.

Special Counters

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

• Johnson (Twisted Ring) Counter: Complement of last FF output fed to first. Sequence length = 2n. States: n '0's followed by n '1's.

  • Example 4-bit: 0000, 1000, 1100, 1110, 1111, 0111, 0011, 0001 → back to 0000.

• BCD Counter (Decade): Counts 0000 to 1001 (0-9). Resets to 0000 after 1001. Use reset logic (e.g., $$\displaystyle Q_C Q_A $$ for reset to 0).

Decoding in Counters (One-Hot)

• Each state has unique output line active (high). For n states, need n decoders.

• Advantage: Output is asynchronous to state (no glitches if properly decoded).

• Application: Used in state machines for output generation.

VII. Registers and Shift Registers

Register Types (Based on I/O)

Shift Operations

• Shift Left (Logical): MSB lost, LSB filled with 0. $$\displaystyle Q_i^+ = Q_{i-1} $$ (for i>0).

• Shift Right (Logical): LSB lost, MSB filled with 0. $$\displaystyle Q_i^+ = Q_{i+1} $$.

• Arithmetic Shift: Preserve sign bit (MSB). Left: MSB preserved, LSB=0. Right: MSB preserved, LSB lost.

• Bidirectional: Mode control (M). M=0 → Shift Right, M=1 → Shift Left.

Universal Shift Register (4-bit)

• Features: Parallel load, Shift Left, Shift Right.

• Control Inputs: $$\displaystyle M_1, M_0 $$ (Mode: 00=Hold, 01=Shift Right, 10=Shift Left, 11=Parallel Load), $CLK$, Parallel Data Inputs $$\displaystyle D_3...D_0 $$, Serial Inputs $$\displaystyle S_L, S_R $$.

• Operation: Uses 4 multiplexers (one per FF) to select between parallel data, shift-right neighbor, shift-left neighbor, or hold current state.

VIII. Memory and Programmable Logic Devices

Read-Only Memory (ROM)

• Organization: $n$ address lines → $$\displaystyle 2^n $$ locations, each $m$ bits wide. Fixed AND array (decoder), programmable OR array.

• Types:

  • PROM: Programmable OR array only (once).

  • EPROM: Erasable with UV light, reprogrammable.

  • EEPROM: Electrically erasable, byte-wise.

  • Flash: Block-wise erase, non-volatile, high density.

Random-Access Memory (RAM)

• SRAM (Static): Uses 6-transistor (6T) cell (bistable latch). Fast, no refresh needed, expensive, larger area.

• DRAM (Dynamic): Uses 1-transistor + 1-capacitor (1T1C) cell. Charge leaks → needs periodic refresh (every few ms). Slower, dense, cheaper.

• Read/Write Cycles:

  • Write: $$\displaystyle CS=0 $$, $$\displaystyle R/W=0 $$, Address stable, Data stable → write data to addressed cell.

  • Read: $$\displaystyle CS=0 $$, $$\displaystyle R/W=1 $$, Address stable → data from cell appears on output after access time ($$\displaystyle t_{ACCESS} $$).

Memory Decoding

• Linear Decoding: Use $n$ address lines to generate $$\displaystyle 2^n $$ chip select signals directly. Wastes lines (e.g., 16 addresses need 4 lines, but 16 CS lines).

• Two-Dimensional Decoding: Split address into row (A) and column (B). Use row decoder ($$\displaystyle 2^{r} $$ outputs) and column decoder ($$\displaystyle 2^{c} $$ outputs). Intersection ($r×c$) selects one cell. Efficient for large memories.

Programmable Logic Devices (PLDs)

• Programmable Logic Array (PLA):

  • Structure: Both AND and OR arrays are programmable.

  • Implementation: Inputs & complements → Programmable AND plane (forms product terms) → Programmable OR plane (sums PTs to outputs).

  • Example (Full Adder): $$\displaystyle S = \overline{A}\overline{B}C_i + \overline{A}B\overline{C_i} + A\overline{B}\overline{C_i} + ABC_i $$; $$\displaystyle C_{out} = AB + AC_i + BC_i $$. Share PTs.

• Programmable Array Logic (PAL):

  • Structure: Programmable AND array, fixed OR array. Each OR gate input from a subset of AND outputs. Faster, cheaper than PLA.

• Sequential Programmable Devices (e.g., PAL with flip-flops):

  • Basic Microcell Logic: Output from OR array → D input of embedded flip-flop. Output can be combinational (from OR) or registered (from FF). Enables state machine implementation.

IX. Data Conversion Circuits

Digital-to-Analog Converter (DAC)

• R-2R Ladder DAC:

  • Operation: Uses two resistors (R and 2R) in ladder network. Each digital bit switches a 2R resistor to either $$\displaystyle V_{REF} $$ or GND.

  • Advantage: Only two resistor values, excellent accuracy.

  • Output: $$\displaystyle V_o = -\frac{V_{REF}}{2^n} \left( D_{n-1}2^{n-1} + D_{n-2}2^{n-2} + ... + D_0 2^0 \right) $$ (for inverting op-amp configuration).

Analog-to-Digital Converter (ADC)

• Successive Approximation ADC:

  • Working:

    1. SAR (Successive Approximation Register) sets MSB to 1, others 0 → DAC output.

    2. Comparator: If $$\displaystyle V_{in} > V_{DAC} $$, bit remains 1; else, cleared.

    3. Repeat for next bit (MSB-1, etc.) until LSB.

  • Conversion Time: n clock cycles for n-bit (fixed, independent of $$\displaystyle V_{in} $$).

  • Advantages: Fast, good accuracy, no integration.

  • Disadvantages: Glitches during bit switching, requires precise DAC.

X. Error Detection and Correction (Overview)

Parity Method

• Even Parity: Parity bit = 1 if odd number of 1s in data; else 0. Total 1s (data+parity) is even.

• Odd Parity: Parity bit = 1 if even number of 1s in data; else 0. Total 1s is odd.

• Detection: Receiver counts total 1s. If parity doesn't match expected → single-bit error detected.

• Limitation: Cannot correct error, only detect. Cannot detect even number of bit errors.

• Application (ASCII 'B'): 'B' = 0100010 (2 ones). For odd parity, send 1 as parity bit → 1 0100010 (3 ones). Receiver expects odd count.