Logic Gates, Combinational Circuits & Minimization

TAKEAWAYS:

• Logic gates are the building blocks of digital circuits, and their combinations form combinational circuits that perform specific functions without memory.
• Decoders, encoders, multiplexers (MUX), and demultiplexers (DEMUX) are fundamental combinational circuits used in data routing, memory addressing, and signal selection.
• Adders (half, full, ripple-carry, carry-lookahead) and subtractors are essential for arithmetic operations in CPUs and calculators.
• Comparators (like the 7485) compare binary numbers and are used in sorting algorithms and memory management.
• Minimization techniques (Boolean algebra, Karnaugh maps) reduce circuit complexity, saving cost, power, and space.
• Real-world applications include eSewa’s payment validation circuits, Khalti’s transaction routing (MUX/DEMUX), and Ncell’s signal processing (adders/comparators).

1. Logic Gates: The Building Blocks

Logic gates are electronic circuits that perform basic logical operations on binary inputs (0 or 1). They are the foundation of all digital systems.

1.1 Basic Logic Gates

The seven fundamental logic gates are:

Gate	Symbol (Standard)	Symbol (IEC)	Boolean Function	Truth Table (A, B → Output)
AND			$Y=A\cdot B$	0,0→0; 0,1→0; 1,0→0; 1,1→1
OR			$Y=A+B$	0,0→0; 0,1→1; 1,0→1; 1,1→1
NOT			$Y=\overline{A}$	0→1; 1→0
NAND			$Y=\overline{A\cdot B}$	0,0→1; 0,1→1; 1,0→1; 1,1→0
NOR			$Y=\overline{A+B}$	0,0→1; 0,1→0; 1,0→0; 1,1→0
XOR			$Y=A\oplus B$	0,0→0; 0,1→1; 1,0→1; 1,1→0
XNOR			$Y=\overline{A\oplus B}$	0,0→1; 0,1→0; 1,0→0; 1,1→1

1.2 Universal Gates

• NAND and NOR gates are universal gates because any logic function can be implemented using only NAND or only NOR gates.
• Example: Implementing an AND gate using NAND gates:

  Y = A · B = NAND(NAND(A, B))
  

  flowchart LR
    A["A"] --> NAND1["NAND"]
    B["B"] --> NAND1
    NAND1 --> NAND2["NAND"]
    NAND2 --> Y["Y = A·B"]

1.3 Gate Delay and Propagation Delay

• Propagation delay (t_pd): Time taken for the output to change after an input change.
  • TTL (Transistor-Transistor Logic): ~10 ns (faster but higher power).
  • CMOS (Complementary Metal-Oxide-Semiconductor): ~5-50 ns (slower but lower power, used in modern chips).
• Fan-out: Number of gates a gate can drive without degradation.
  • TTL: ~10
  • CMOS: ~50 (higher fan-out).

2. Combinational Circuits

Combinational circuits produce outputs only based on current inputs (no memory). Key examples:

2.1 Decoders

Convert n input lines into 2ⁿ output lines, activating one output at a time.

• Example: 2-to-4 line decoder (74139).

  flowchart LR
    A["A"] --> AND1["AND"]
    B["B"] --> AND1
    A --> AND2["AND"]
    B --> NOT["NOT"]
    NOT --> AND2
    AND1 --> Y0["Y0"]
    AND2 --> Y1["Y1"]
    A --> AND3["AND"]
    B --> AND3
    AND3 --> Y2["Y2"]
    NOT --> AND4["AND"]
    A --> AND4
    AND4 --> Y3["Y3"]

• Applications:
  • Memory addressing (e.g., selecting a specific RAM location).
  • Data routing in networks (e.g., Pathao’s ride assignment system uses decoders to route requests to the nearest driver).

2.2 Encoders

Convert 2ⁿ input lines into n output lines, with only one input active at a time.

• Example: 4-to-2 line encoder (priority encoder if multiple inputs are active).

  flowchart LR
    I0["I0"] --> OR1["OR"]
    I1["I1"] --> OR1
    I2["I2"] --> OR2["OR"]
    I3["I3"] --> OR2
    OR1 --> A["A"]
    OR2 --> B["B"]
    I0 --> AND1["AND"]
    NOT["NOT"] --> AND1
    AND1 --> A
    I1 --> AND2["AND"]
    AND2 --> A
    I2 --> AND3["AND"]
    AND3 --> B
    I3 --> AND4["AND"]
    AND4 --> B

• Applications:
  • Keyboard scanning (e.g., laptop keyboards use encoders to detect key presses).
  • NTC’s traffic signal control uses encoders to prioritize signals based on sensor inputs.

2.3 Multiplexers (MUX)

Select one of 2ⁿ data inputs and route it to a single output based on n select lines.

• Example: 4-to-1 MUX (74153).

  flowchart LR
    D0["D0"] --> AND1["AND"]
    D1["D1"] --> AND2["AND"]
    D2["D2"] --> AND3["AND"]
    D3["D3"] --> AND4["AND"]
    S0["S0"] --> NOT1["NOT"]
    S1["S1"] --> NOT2["NOT"]
    NOT1 --> AND1
    NOT2 --> AND1
    S0 --> AND2
    NOT2 --> AND2
    S1 --> AND3
    NOT1 --> AND3
    S0 --> AND4
    S1 --> AND4
    AND1 --> OR1["OR"]
    AND2 --> OR1
    AND3 --> OR1
    AND4 --> OR1
    OR1 --> Y["Y"]

• Applications:
  • Khalti’s payment routing: Uses MUX to select the correct bank or wallet for a transaction based on user input.
  • Daraz’s order processing: MUX selects the fastest delivery route based on inventory and location.

2.4 Demultiplexers (DEMUX)

Route a single input to one of 2ⁿ outputs based on n select lines.

• Example: 1-to-4 DEMUX (74138).

  flowchart LR
    I["I"] --> AND1["AND"]
    AND1 --> Y0["Y0"]
    I --> AND2["AND"]
    AND2 --> Y1["Y1"]
    I --> AND3["AND"]
    AND3 --> Y2["Y2"]
    I --> AND4["AND"]
    AND4 --> Y3["Y3"]
    S0["S0"] --> NOT1["NOT"]
    S1["S1"] --> NOT2["NOT"]
    NOT1 --> AND1
    NOT2 --> AND1
    S0 --> AND2
    NOT2 --> AND2
    S1 --> AND3
    NOT1 --> AND3
    S0 --> AND4
    S1 --> AND4

• Applications:
  • Ncell’s signal broadcasting: DEMUX routes a single signal to multiple base stations.
  • eSewa’s payment notifications: DEMUX sends transaction alerts to different user devices (phone, email, SMS).

2.5 Adders and Subtractors

2.5.1 Half Adder (HA)

Adds two 1-bit numbers and produces sum (S) and carry (C).

flowchart LR
  A["A"] --> XOR["XOR"]
  B["B"] --> XOR
  XOR --> S["S"]
  A --> AND["AND"]
  B --> AND
  AND --> C["C"]

2.5.2 Full Adder (FA)

Adds three inputs (A, B, carry-in) and produces sum (S) and carry-out (C).

flowchart LR
  A["A"] --> XOR1["XOR"]
  B["B"] --> XOR1
  XOR1 --> XOR2["XOR"]
  C["C"] --> XOR2
  XOR2 --> S["S"]
  A --> AND1["AND"]
  B --> AND1
  AND1 --> OR1["OR"]
  A --> AND2["AND"]
  C --> AND2
  AND2 --> OR1
  B --> AND3["AND"]
  C --> AND3
  OR1 --> C["C"]

2.5.3 Ripple-Carry Adder (RCA)

Cascades full adders to add multi-bit numbers.

• Example: 4-bit RCA.

  flowchart LR
    A0["A0"] --> FA1["FA"]
    B0["B0"] --> FA1
    FA1 --> S0["S0"]
    FA1 --> C1["C1"]
    A1["A1"] --> FA2["FA"]
    B1["B1"] --> FA2
    C1 --> FA2
    FA2 --> S1["S1"]
    FA2 --> C2["C2"]
    A2["A2"] --> FA3["FA"]
    B2["B2"] --> FA3
    C2 --> FA3
    FA3 --> S2["S2"]
    FA3 --> C3["C3"]
    A3["A3"] --> FA4["FA"]
    B3["B3"] --> FA4
    C3 --> FA4
    FA4 --> S3["S3"]
    FA4 --> C4["C4"]

• Applications:
  • CPU arithmetic units: All modern CPUs use adders for calculations (e.g., Intel Core i7).
  • Bank loan interest calculation: Adders compute compound interest in real-time systems.

2.5.4 Subtractors

• Half Subtractor (HS): Subtracts two bits, produces difference (D) and borrow (B).

  flowchart LR
    A["A"] --> XOR["XOR"]
    B["B"] --> XOR
    XOR --> D["D"]
    NOT["NOT"] --> AND["AND"]
    A --> AND
    B --> AND
    AND --> B["B"]

• Full Subtractor (FS): Subtracts three bits (A, B, borrow-in).

  flowchart LR
    A["A"] --> XOR1["XOR"]
    B["B"] --> XOR1
    XOR1 --> XOR2["XOR"]
    B["B"] --> XOR2
    XOR2 --> D["D"]
    NOT1["NOT"] --> AND1["AND"]
    A --> AND1
    B --> AND1
    AND1 --> OR1["OR"]
    NOT2["NOT"] --> AND2["AND"]
    A --> AND2
    B --> AND2
    B["B"] --> AND3["AND"]
    AND2 --> OR1
    AND3 --> OR1
    OR1 --> B["B"]

• Applications:
  • NEPSE stock price calculations: Subtractors compute price differences in trading systems.
  • Game consoles: Used in collision detection (e.g., Nintendo Switch physics engines).

2.6 Comparators

Compare two binary numbers and determine if they are equal, A > B, or A < B.

• Example: 4-bit comparator (7485).

  flowchart LR
    A0["A0"] --> XNOR1["XNOR"]
    B0["B0"] --> XNOR1
    XNOR1 --> AND1["AND"]
    A1["A1"] --> XNOR2["XNOR"]
    B1["B1"] --> XNOR2
    XNOR2 --> AND2["AND"]
    AND1 --> OR1["OR"]
    AND2 --> OR1
    OR1 --> AEQB["AEQB"]
    A0 --> XOR1["XOR"]
    B0 --> XOR1
    XOR1 --> AND3["AND"]
    A1 --> XOR2["XOR"]
    B1 --> XOR2
    XOR2 --> AND4["AND"]
    AND3 --> OR2["OR"]
    AND4 --> OR2
    OR2 --> AGTB["AGTB"]
    NOT["NOT"] --> AND5["AND"]
    AEQB --> AND5
    AGTB --> AND5
    AND5 --> ALTB["ALTB"]

• Applications:
  • Sorting algorithms: Comparators are used in quicksort and mergesort.
  • Traffic management: Kathmandu traffic lights use comparators to prioritize vehicles based on sensor data.

3. Minimization Techniques

Minimizing logic circuits reduces cost, power, and complexity. Two key methods:

3.1 Boolean Algebra Simplification

Use algebraic laws to simplify expressions:

• Example: Simplify $Y=A\cdot \overline{A}+B\cdot (A+\overline{A})$.
  • $A\cdot \overline{A}=0$ (Complement law).
  • $A+\overline{A}=1$ (Identity law).
  • Thus, $Y=0+B\cdot 1=B$.

3.2 Karnaugh Maps (K-Maps)

Graphical method to simplify Boolean functions by grouping 1s.

• Example: Simplify $F(A,B,C,D)=\sum m(0,1,2,5,8,10,13,15)$.

  AB\CD	00	01	11	10
  00	1	1	0	1
  01	1	0	0	0
  11	0	0	0	0
  10	1	0	0	1

  • Groups:
    • Group 1: $\overline{A}\overline{B}$ (top-left 1s).
    • Group 2: $\overline{A}C$ (first column 1s).
    • Group 3: $A\overline{B}\overline{D}$ (bottom-left 1s).
    • Group 4: $A\overline{B}D$ (bottom-right 1s).
  • Simplified expression: $F=\overline{A}\overline{B}+\overline{A}C+A\overline{B}\overline{D}+A\overline{B}D$. Further simplification: $F=\overline{A}\overline{B}+\overline{A}C+A\overline{B}$.

## In the Real World

1. eSewa’s Payment Validation

   • Logic Used: Multiplexers (MUX) and Encoders.
   • How: When a user pays via eSewa, the system uses a MUX to select the correct bank or wallet based on the user’s input (e.g., phone number or email). An encoder then converts the selected payment method into a binary code for processing.

2. Khalti’s Transaction Routing

   • Logic Used: Demultiplexers (DEMUX).
   • How: When a transaction is initiated, Khalti’s backend uses a DEMUX to route the payment to the correct destination (e.g., merchant account, user wallet, or bank). This ensures the transaction is processed in the right channel without delays.

3. Ncell’s Signal Broadcasting

   • Logic Used: Decoders and Adders.
   • How: Ncell’s base stations use decoders to select specific frequency channels for different users. Adders are used in the signal processing unit to combine multiple data streams for efficient transmission.

4. Daraz’s Order Processing

   • Logic Used: Comparators and Priority Encoders.
   • How: When an order is placed, Daraz’s system uses comparators to check inventory levels and prioritize orders based on delivery deadlines. A priority encoder then selects the fastest delivery route.

5. Bank Loan Interest Calculation

   • Logic Used: Ripple-Carry Adders.
   • How: Banks use adders to compute compound interest for loans. For example, if a loan of Rs. 100,000 has an annual interest rate of 10%, the adder calculates the interest for each compounding period and adds it to the principal.

## Exam Tip

1. Understand Gate Symbols: Always draw the correct standard/IEC symbols for gates in exams. Mixing them up can cost marks.
2. Practice Truth Tables: For every gate or circuit, be able to draw the truth table from scratch. Examiners often ask for partial truth tables.
3. Minimization is Key: In questions involving K-maps or Boolean simplification, always show grouping steps. Partial credit is given for correct groupings even if the final expression is wrong.
4. Real-World Applications: Expect questions linking circuits to real systems (e.g., "How would you design a traffic light controller using decoders?").
5. TTL vs. CMOS: Know the differences in speed, power, and fan-out. Questions often ask for comparisons or applications.
6. Circuit Design: For combinational circuits, always show the step-by-step design process (e.g., "First, design a decoder, then use it to build a MUX").
7. Common ICs: Memorize the pinouts and functions of 74LS00 (NAND), 74LS08 (AND), 74LS85 (Comparator), 74LS138 (DEMUX), 74LS151 (MUX). Examiners love asking about these.