Combinational Logic: Design, Minimization & Applications

TAKEAWAYS:

• Definition: Combinational circuits produce outputs only from current inputs (no memory), designed using logic gates, truth tables, and Boolean algebra.
• Key Steps: For any design, follow input → truth table → Boolean expression → minimization → logic diagram (with real gate symbols).
• Minimization: Karnaugh maps (K-maps) visually group 1s to reduce gates (e.g., 4-variable maps group 8, 4, 2, or 1 cells).
• Applications: Used in BCD converters (eSewa’s transaction validation), subtractors (Khalti’s payment routing), and multiplexers (Ncell’s signal switching).
• Design Rules: Always verify with input combinations (e.g., test all 16 cases for 4 inputs) and draw real gate symbols (not abstract blocks).
• Exam Focus: 60% of questions ask for truth tables + logic diagrams (e.g., "Design a 2’s complement circuit for 4-bit inputs").

---

1. What Are Combinational Circuits?

Combinational circuits are logic circuits with no memory—their outputs depend only on current inputs. Unlike sequential circuits (e.g., counters), they have no feedback loops or clock signals.

Key Features:

• Inputs/Outputs: Fixed number of binary inputs/outputs (e.g., 4 inputs → 1 output).
• No Memory: Output changes instantly with input (no stored state).
• Building Blocks: Logic gates (AND, OR, NOT, NAND, NOR, XOR, XNOR), multiplexers, decoders, encoders.
• Design Process:
  1. Define inputs/outputs.
  2. Create a truth table (all possible input combinations).
  3. Derive Boolean expressions (sum-of-products or product-of-sums).
  4. Minimize using Karnaugh maps or Boolean algebra.
  5. Draw the logic diagram (using real gate symbols).

---

2. Designing Combinational Circuits: Step-by-Step

Example 1: Majority Function (4 inputs → 1 output)

Problem: Design a circuit where output = 1 if:

• All 4 inputs are 1, or
• None of the inputs are 1, or
• An odd number of inputs are 1.

Step 1: Truth Table

(Full truth table has 16 rows; only extremes shown.)

Step 2: Boolean Expression

From the truth table, identify minterms (rows where Y=1):

• M0 (A’B’C’D’), M15 (ABCD), M2 (A’B’CD’), M7 (ABC’D), M10 (AB’CD’), M13 (AB’C’D).
• Sum-of-products (SOP): $Y=\sum m(0,2,7,10,13,15)$.

Step 3: Karnaugh Map Minimization

Groups:

• Group 1: M0, M2, M8, M10 (4-cell group, $B’D’$).
• Group 2: M7, M15, M13, M11 (4-cell group, $ACD$).
• Group 3: M1, M3, M12, M14 (not used here).

Simplified Expression: $Y=B’D’+ACD$.

Step 4: Logic Diagram

Circuit:

• Use NAND gates to implement $B’D’$ (De Morgan’s: $(B+D)’$).
• Use AND gate for $ACD$.
• Combine with an OR gate.

---

3. Real-World Applications

In the Real World

1. eSewa Transaction Validation (BCD to Excess-3 Converter)

   • Idea Used: BCD (8421) to Excess-3 code conversion (used in error-checking).
   • How: eSewa’s backend validates transaction amounts by converting BCD inputs to Excess-3 for checksum calculations.
   • Circuit: A 4-input BCD → Excess-3 converter (truth table + K-map minimized to 3 gates).

2. Khalti Payment Routing (Multiplexer)

   • Idea Used: 4-to-1 multiplexer selects payment gateway (e.g., IME, Fonepay, Khalti Wallet).
   • How: Inputs = user choice (A=00, B=01, C=10, D=11); output = selected gateway’s API.
   • Circuit:

     flowchart LR
       A["Sel0"] --> MUX["4:1 MUX"]
       B["Sel1"] --> MUX
       C["Sel2"] --> MUX
       D["Sel3"] --> MUX
       MUX -->|"Y"| API["Gateway API"]

3. Ncell Signal Switching (Decoder)

   • Idea Used: 2-to-4 decoder routes calls to towers based on binary input (e.g., 00 → Tower 1, 01 → Tower 2).
   • How: Input = user’s location code; output = active tower signal.
   • Circuit:

---

4. Common Combinational Circuits

A. Adders and Subtractors

1. Half-Subtractor

   • Inputs: A, B (minuend, subtrahend).
   • Outputs: Difference (D), Borrow (B).
   • Truth Table:

     A	B	D	B
     0	0	0	0
     0	1	1	0
     1	0	1	0
     1	1	0	1

   • Logic Diagram:
   • Real Use: Used in Daraz’s order processing (subtracting discounts from prices).

2. Full-Subtractor

   • Adds a borrow-in (B_in) input.
   • Expression: $D=A\oplus B\oplus B_{in}$ $B_{out}=(A’B+A’B_{in}+B{B}_{in})$

B. Code Converters

1. BCD to Excess-3 Converter
   • BCD: 8421 code (0000=0, 0001=1, ..., 1001=9).
   • Excess-3: Add 3 to BCD (e.g., 0000 → 0011, 0001 → 0100).
   • Design Steps:
     • Truth table for all 10 BCD inputs (0–9).
     • Minimize using K-map (groups of 2 or 4).
   • Example: For input 0100 (4 in BCD), output = 0111 (Excess-3).
   • Real Use: NTC’s electricity billing converts meter readings (BCD) to error-checked codes (Excess-3).

C. Multiplexers (MUX)

• Definition: Selects one of many inputs based on a select line.
• 4:1 MUX Truth Table:

  S1	S0	I0	I1	I2	I3	Y
  0	0	0	1	2	3	I0
  0	1	0	1	2	3	I1
  1	0	0	1	2	3	I2
  1	1	0	1	2	3	I3

• Logic Diagram:

• Real Use: Pathao’s ride allocation uses a 3:1 MUX to choose between driver A, B, or C based on traffic data.

D. Decoders

• Definition: Converts binary inputs to a single active output line.
• 2-to-4 Decoder Truth Table:

  A	B	Y0	Y1	Y2	Y3
  0	0	1	0	0	0
  0	1	0	1	0	0
  1	0	0	0	1	0
  1	1	0	0	0	1

• Real Use: NEPSE stock exchange uses decoders to activate specific stock lines based on binary codes.

---

5. Minimization Techniques

A. Boolean Algebra Laws

Use these to simplify before K-maps:

• Idempotent: $A+A=A$, $A\cdot A=A$.
• Complement: $A+A’=1$, $A\cdot A’=0$.
• Associative: $(A+B)+C=A+(B+C)$.
• Distributive: $A(B+C)=AB+AC$.

B. Karnaugh Maps (K-Maps)

• Rules:
  1. Draw a map with $2^n$ cells (n = number of variables).
  2. Fill 1s/0s from the truth table.
  3. Group adjacent 1s in powers of 2 (2, 4, 8, etc.).
  4. Write the simplified term for each group.
• Example: Simplify $F=\sum m(0,1,2,5,7,8,10,15)$. Groups:
  • 8-cell: M0, M1, M2, M3 (not possible; max 4).
  • 4-cell: M0, M1, M8, M9 (but M9 is 0 → invalid).
  • Valid Groups:
    • M0, M2, M8, M10 → $B’D’$.
    • M5, M7, M13, M15 → $ACD$. Simplified: $F=B’D’+ACD$.

---

6. Worked Example: 2’s Complement Circuit

Problem: Design a 4-bit circuit to output the 2’s complement of a 4-bit input.

Step 1: Truth Table

Step 2: Boolean Expressions

• 1’s Complement: Invert each bit ($Y_i=A_i’$).
• Add 1 to LSB: Use a half-adder on $Y_0$ and 1.
  • $Y_0=A_0’\oplus 1=A_0$.
  • Carry $C_1=A_0’\cdot 1=A_0’$.
• Propagate Carry: Use full-adders for higher bits.
  • $Y_1=A_1’\oplus C_1$, $C_2=(A_1’\cdot C_1)+(A_1\cdot C_1’)$.
  • Repeat for $Y_2,Y_3$.

Step 3: Logic Diagram

Real Use: Bank Loan Interest Calculation

• Banks use 2’s complement to handle negative values (e.g., subtracting interest from principal).
• Example: Input = 0101 (5), 2’s complement = 1011 (-5).

---

7. Comparisons: Key Circuits

---

8. Exam Tip

1. Truth Tables Are Mandatory:

   • Always show a complete truth table (even if not asked) for full marks.
   • Example: For a 3-input circuit, list all 8 rows.

2. K-Maps > Boolean Algebra:

   • Examiners prefer K-maps for minimization (faster, fewer errors).
   • Pro Tip: Group powers of 2 (e.g., 8 > 4 > 2 > 1). Never leave single 1s ungrouped.

3. Logic Diagrams Must Use Real Gates:

   • Use standard symbols (not blocks). Example:
   • Label all inputs/outputs clearly.

4. Common Pitfalls:

   • Forgetting Don’t-Care Terms: If inputs are restricted (e.g., BCD), mark unused rows as X in K-maps.
   • Incorrect Grouping: Groups must wrap around (e.g., M0 and M8 can group vertically).
   • Missing Carries: In adders/subtractors, always show carry propagation.

5. Real-World Tie-Ins:

   • Link your design to a Nepali app/company (e.g., "This BCD converter is used in eSewa’s transaction logs").
   • Example Answer Starter:

     "The 2’s complement circuit designed here is analogous to how banks represent negative loan amounts in digital ledgers, ensuring accurate arithmetic operations in financial software."

---

9. Practice Questions (Exam-Style)

1. Design a 3-input combinational circuit where output = 1 if:

   • Exactly two inputs are 1, or
   • All inputs are 0. (Hint: Use K-map to group M0, M1, M2, M3, M5, M6.)

2. Convert the following Boolean expression to its minimized form using a K-map: $F=\sum m(0,2,5,7,8,10,13,15)$.

3. Design a BCD to Gray Code converter with:

   • Truth table for inputs 0–9.
   • Simplified logic diagram.

4. Explain how a 4:1 multiplexer can be used to implement a 2-variable Boolean function. Draw the circuit.

---

10. Summary Checklist

Before submitting your answer, verify: ✅ Truth table: All input combinations covered. ✅ K-map: Groups are powers of 2, no overlaps. ✅ Logic diagram: Uses real gate symbols, labeled correctly. ✅ Real-world link: Ties to a Nepali app (eSewa, Khalti, etc.). ✅ Exam format: Clear headings, no handwritten-style text.