Logic Gates, Combinational Circuits & Design

TAKEAWAYS:

• Logic gates are the building blocks of digital circuits, with NAND and NOR as universal gates.
• Combinational circuits have no memory—output depends only on current inputs (e.g., adders, multiplexers).
• Design steps: Analyze → Simplify → Implement → Verify (using truth tables, K-maps, or Boolean algebra).
• Real-world use: E-sewa’s transaction validation (AND gates for approval logic), Khalti’s OTP verification (XOR for parity checks), and Daraz’s order prioritization (priority encoders).
• Key circuits: Half/Full adders (for arithmetic), multiplexers (for data selection), decoders (for memory addressing).
• Exam focus: Design circuits from truth tables, implement gates using NAND/NOR only, and differentiate combinational vs. sequential.

---

1. Logic Gates: The Digital Building Blocks

Logic gates perform Boolean operations on binary inputs (0/1) to produce a single output. They are the fundamental components of all digital circuits.

1.1 Basic Gates (AND, OR, NOT)

These are the primitive gates from which all others are derived.

Truth Tables:

Real Picture:

---

1.2 Universal Gates (NAND, NOR)

• NAND and NOR are universal—any logic function can be built using only them.
• NAND Gate: Output is NOT (A AND B).
• NOR Gate: Output is NOT (A OR B).

Worked Example: Implement AND using NAND To build an AND gate using only NAND gates:

1. Feed inputs A and B into a NAND gate.
2. The output of the first NAND is ¬(A ∧ B).
3. Feed this output into a second NAND gate with itself (short-circuit).
   • Output = ¬(¬(A ∧ B)) = A ∧ B.

Circuit:

   A ----|>|----\
          NAND    \
   B ----|>|-------> NAND ---> AND
          NAND    /
   (Output)-------/

Exam Tip: Always verify by checking all input combinations!

---

1.3 Derived Gates (XOR, XNOR)

• XOR (Exclusive OR): Output is 1 if inputs differ.
• XNOR: Output is 1 if inputs are the same.

Real-World Use:

---

2. Combinational Circuits: No Memory, Pure Logic

Combinational circuits lack memory—their output depends only on current inputs. Examples:

• Adders (half, full, ripple-carry)
• Multiplexers (data selectors)
• Decoders (address selectors)
• Encoders (priority encoders)
• Comparators

2.1 Half Adder vs. Full Adder

Half Adder Circuit:

   A ----|>|----\
          AND    \
   B ----|>|-------> C (Carry)
          AND    /
   A ----|>|----\
          XOR    \
   B ----|>|-------> S (Sum)
          XOR    /

Full Adder Circuit (uses 2 half adders + OR gate):

   A ----|>|----\
          AND    \
   B ----|>|-------> C1 (Partial Carry)
          AND    /
   A ----|>|----\
          XOR    \
   B ----|>|-------> S (Sum)
          XOR    /
   C_in ----|>|----\
               OR    \
   C1 -------|>|-------> C_out (Final Carry)
               OR    /

Worked Example: Add 1101₂ + 1011₂

1. Break into 4 full adders (one per bit).
2. Propagate carries from LSB to MSB.
3. Final sum: 11000₂ (24 in decimal).

Real-World Tie-In:

---

2.2 Multiplexers (MUX)

A multiplexer (MUX) selects one of many inputs based on a select line.

4:1 MUX Truth Table:

Circuit:

   I0 ----|>|----\
          AND    \
   ¬S1 ----|>|-------> Y
          AND    /
   I1 ----|>|----\
          AND    \
   ¬S1 ----|>|-------> (OR with others)
          AND    /
   ... (repeat for I2, I3 with S1, S0)

Real-World Use:

---

2.3 Decoders

A decoder converts n inputs into 2ⁿ outputs, activating one line at a time.

2:4 Decoder Truth Table:

Circuit:

   A ----|>|----\
          NOT    \
   ¬A ----|>|-------> Y0 (AND with ¬B)
          AND    /
   B ----|>|----\
          NOT    \
   ¬B ----|>|-------> (Repeat for Y1-Y3)
          AND    /

Real-World Use:

---

3. Design Procedure for Combinational Circuits

Follow these 5 steps to design any combinational circuit:

1. Analyze the Problem:

   • Define inputs/outputs.
   • Write a truth table (e.g., for a majority voter: if ≥2 inputs are 1, output is 1).

2. Simplify the Logic:

   • Use Boolean algebra or Karnaugh Maps (K-maps) to minimize gates.
   • Example: Simplify $F=AB+A^{\prime }C+BC$ to $F=AB+C(A+B)$.

3. Implement the Circuit:

   • Draw using standard gate symbols.
   • Use universal gates (NAND/NOR) if required.

4. Verify the Design:

   • Check all input combinations.
   • Use logic simulators (e.g., Logisim, Proteus).

5. Optimize (if needed):

   • Reduce gate count using De Morgan’s laws.
   • Replace gates with equivalent forms (e.g., AND using NAND).

Worked Example: Majority Voter Circuit Truth Table:

K-map Simplification:

   AB\C | 0 1
   -----+---
   00   | 0 0
   01   | 0 1
   11   | 1 1
   10   | 0 1

• Groups: $AB+BC+AC$ → Simplified to $AB+C(A+B)$.

Circuit:

   A ----|>|----\
          AND    \
   B ----|>|-------> Y
          AND    /
   C ----|>|----\
          AND    \
   (A+B) ----|>|-------> (OR with AB)
          OR    /

---

4. Combinational vs. Sequential Circuits

Real-World Analogy:

---

In the Real World

1. E-sewa’s Transaction Validation

   • Uses AND gates to ensure both user credentials and payment approval are valid before processing.
   • Example: Output = (Username_Match ∧ Password_Correct) ∧ Payment_Approved.

2. Khalti’s One-Time Password (OTP) Verification

   • Employs XOR gates for parity checks to detect errors in OTP transmission.
   • Example: If OTP bits are 1010, the parity bit (XOR of all bits) ensures no bit flip during transfer.

3. Daraz’s Order Prioritization System

   • Uses a priority encoder (combinational) to assign delivery routes based on order urgency.
   • Example: High-priority orders (e.g., same-day) bypass lower-priority queues via priority MUX logic.

4. NTC’s Network Traffic Routing

   • Decoders map IP addresses to specific network paths, ensuring data reaches the correct destination.

5. Bank Loan Interest Calculation

   • Ripple-carry adders compute monthly interest by adding principal + (principal × rate).
   • Example: For a loan of 10000₹ at 5% annual interest, the adder computes 10000 + (10000 × 0.05/12).

---

Exam Tip

1. Design Questions:

   • Always start with a truth table for any circuit (adder, MUX, decoder).
   • Simplify using K-maps if the problem mentions optimization.
   • Label all inputs/outputs clearly in your diagram.

2. Gate Implementation:

   • If asked to use only NAND/NOR gates, show the step-by-step conversion (e.g., AND → NAND + NAND).
   • Example: A AND B = NAND(NAND(A,B), NAND(A,B)).

3. Differentiation Questions:

   • For combinational vs. sequential, focus on:
     • Memory (sequential has flip-flops).
     • Output dependency (combinational = current inputs only).
   • Example answer:

     "Combinational circuits lack memory and produce outputs based solely on current inputs (e.g., adders). Sequential circuits use flip-flops to retain state, making outputs dependent on both inputs and past states (e.g., counters)."

4. Common Pitfalls:

   • Forgetting carry propagation in adders (always include C_in and C_out).
   • Mislabeling select lines in MUX (e.g., S0 is LSB, S1 is MSB).
   • Skipping verification—always check 2-3 test cases in your answer.

5. High-Score Strategy:

   • Draw circuits neatly with standard symbols (use the IEC 60617 gate shapes).
   • Show intermediate steps (e.g., truth table → K-map → simplified Boolean → circuit).
   • Relate to real-world examples (e.g., "This adder is used in E-sewa’s payment processing").

---

Final Visual Summary: