Combinational Logic: Design, Minimization & Applications

Core Concepts

1. What is a Combinational Circuit?

A combinational circuit is a digital circuit whose output depends only on the current inputs (no memory). It performs a specific logical function like addition, subtraction, or code conversion.

Key Features:

• No feedback loops (unlike sequential circuits).
• Output changes instantly with input changes.
• Built using logic gates (AND, OR, NOT, NAND, NOR, XOR, XNOR).

Example: A half-adder adds two 1-bit numbers and produces a sum and carry. It has no memory—just gates.

2. Design Procedure for Combinational Circuits

To design a combinational circuit, follow these steps:

1. Define the problem (inputs, outputs, logic).
2. Write the truth table (all possible input combinations and outputs).
3. Derive the Boolean expression (using sum-of-products or product-of-sums).
4. Simplify the expression (using Boolean algebra or Karnaugh maps).
5. Draw the logic circuit (using gates).
6. Verify with test cases.

Worked Example: Half-Adder

Problem: Design a half-adder with inputs $A,B$ and outputs $Sum,Carry$.

Step 1: Truth Table

Step 2: Boolean Expressions

• $Sum=A\oplus B=A^{\prime }B+A{B}^{\prime }$
• $Carry=A\cdot B$

Step 3: Logic Circuit (Note: The XOR gate can be built using basic gates.)

Step 4: Implementation with NAND Gates Only Since NAND gates are universal, we can implement XOR and AND using them:

• $A\oplus B=(A\cdot B{)}^{\prime }\cdot (A^{\prime }\cdot B^{\prime }{)}^{\prime }$ (De Morgan’s law)
• $A\cdot B=(A\cdot B{)}^{\prime }$' (NAND of NAND)

3. Karnaugh Maps (K-Maps) for Minimization

Karnaugh maps simplify Boolean expressions by grouping adjacent 1s (or 0s) to reduce gates.

How K-Maps Work

1. List all minterms (rows in truth table where output=1).
2. Plot them on a K-map (2D grid where adjacent cells differ by 1 bit).
3. Group 1s in powers of 2 (2, 4, 8, 16).
4. Write the simplified expression (each group gives a product term).

Example: 3-Variable K-Map

Problem: Simplify $F(A,B,C)=\sum m(0,1,2,5,7)$.

Step 1: Plot on K-Map

   BC\A  00  01  11  10
     0    1   1   0   0
     1    1   0   1   1

Step 2: Group 1s

• Group 1: $m0,m1$ → $B^{\prime }$
• Group 2: $m2,m3$ → $A^{\prime }C$
• Group 3: $m5,m7$ → $AC$

Simplified Expression: $F=B^{\prime }+A^{\prime }C+AC$

Circuit Implementation:

flowchart LR
    A["A"] --> AND1["AND"]
    C["C"] --> AND1
    AND1 --> OR["OR"]
    B["B'"] --> OR
    A --> AND2["AND"]
    C --> AND2
    AND2 --> OR

4. Common Combinational Circuits

(A) Adders & Subtractors

Example: Full-Adder Truth Table

Circuit:

(B) Code Converters

Example: BCD to 7-Segment Decoder

• Input: 4-bit BCD (0000 to 1001).
• Output: 7 segments (a-g) to light up digits 0-9.
• Truth Table: 16 rows (only 10 valid BCD inputs).
• Simplified using K-maps (each segment is a separate function).

5. Multiplexers (MUX) and Demultiplexers (DEMUX)

(A) Multiplexer (MUX)

• Selects one of many inputs and sends it to a single output.
• Inputs: Data lines ($D_0,D_1,...,D_{n-1}$), Select lines ($S_0,S_1,...$).
• Output: $Y=D_{select}$.

Example: 4:1 MUX

flowchart LR
    D0["D0"] --> AND1["AND"]
    S0["S0'"] --> AND1
    D1["D1"] --> AND2["AND"]
    S0 --> AND2
    S1["S1'"] --> AND2
    AND1 --> OR["OR"]
    AND2 --> OR
    D2["D2"] --> AND3["AND"]
    S0 --> AND3
    S1 --> AND3
    AND3 --> OR
    D3["D3"] --> AND4["AND"]
    S0 --> AND4
    S1 --> AND4
    AND4 --> OR

Applications:

• Data routing in Pathao’s ride-hailing app (selects driver location from multiple options).
• Ncell’s network switching (selects best signal source).

(B) Demultiplexer (DEMUX)

• Takes one input and routes it to one of many outputs based on select lines.
• Example: 1:4 DEMUX
  • Input: $D$, Select: $S_0,S_1$.
  • Outputs: $Y_0,Y_1,Y_2,Y_3$.

Circuit:

Applications:

• Daraz’s order routing (sends order to correct warehouse).
• Bank ATMs (routes cash request to correct vault).

6. Comparators

(A) Magnitude Comparator

• Compares two binary numbers ($A$ and $B$) and outputs:
  • $A>B$
  • $A=B$
  • $A<B$

Example: 2-bit Comparator

flowchart LR
    A0["A0"] --> XOR1["XOR"]
    B0["B0"]
    XOR1 --> AND1["AND"]
    A1["A1"]
    B1["B1"] --> XOR2["XOR"]
    XOR2 --> AND2["AND"]
    AND1 --> OR1["OR"]
    AND2 --> OR1
    A0 --> AND3["AND"]
    B0'["B0'"]
    A1 --> AND4["AND"]
    B1'["B1'"]
    AND3 --> OR2["OR"]
    AND4 --> OR2
    OR1 --> AeqB["A=B"]
    OR2 --> AgtB["A>B"]
    B0 --> AND5["AND"]
    A0'["A0'"]
    B1 --> AND6["AND"]
    A1'["A1'"]
    AND5 --> OR3["OR"]
    AND6 --> OR3
    OR3 --> AltB["A<B"]

Applications:

• NEPSE stock price comparison (checks if share price rose/fell).
• Khalti’s transaction validation (compares sender/receiver IDs).

In the Real World

1. eSewa & Khalti (Digital Payments)

   • Idea Used: BCD to 7-Segment Decoder
   • How? When you check your balance on eSewa, the app displays numbers (0-9) using a 7-segment LED (or LCD) screen. The BCD to 7-segment decoder converts the binary-coded decimal (BCD) representation of your balance into signals that light up the correct segments (e.g., "5" lights up segments a, f, g, c, d).

2. Pathao & Daraz (Order Routing)

   • Idea Used: Demultiplexer (DEMUX)
   • How? When you place an order on Daraz, the system uses a DEMUX to route your request to the correct warehouse or delivery agent. The "select lines" could be the order ID or location, and the "outputs" are different warehouses or drivers.

3. NTC Traffic Management

   • Idea Used: Multiplexer (MUX) + Comparator
   • How? Traffic lights at busy intersections (like Thapathali) use comparators to check vehicle density and MUXes to select the best signal timing based on real-time sensor inputs (e.g., cameras detecting cars).

4. Bank Loan Interest Calculation

   • Idea Used: Full-Adder/Subtractor
   • How? When a bank (like NMB or Global IME) calculates monthly interest on a loan, it uses binary addition/subtraction circuits. For example, if your principal is ₹100,000 and the interest rate is 10% per annum, the system breaks this into binary operations to compute the monthly installment.

5. WhatsApp Message Encryption (XOR Gate)

   • Idea Used: XOR Gate (Half-Adder)
   • How? WhatsApp uses XOR operations for simple encryption. When you send a message, it is XORed with a key, and the receiver XORs it again to decode. This is similar to how a half-adder’s XOR gate combines two bits reversibly.

Exam Tip

What Examiners Look For

1. Truth Tables Must Be Complete

   • For $n$ inputs, there must be $2^n$ rows.
   • Example: 3 inputs → 8 rows (no missing combinations).

2. K-Maps Must Be Correctly Grouped

   • Groups must be powers of 2 (2, 4, 8).
   • Overlapping groups are allowed but must cover all 1s.
   • Common Mistake: Forgetting to group $m0,m2,m4,m6$ (they form $A^{\prime }$).

3. Circuit Diagrams Must Be Accurate

   • Use standard gate symbols (no hand-drawn approximations).
   • Label all inputs/outputs clearly.
   • Example: A full-adder must show Sum = A⊕B⊕Cin and Cout = AB + BCin + ACin.

4. Real-World Applications Are Highly Valued

   • Always relate your design to a real system (e.g., "This adder is used in eSewa’s payment processing").
   • Example Answer:

     "The full-subtractor can be used in Khalti’s transaction system to compute the difference between the sender’s balance and the transaction amount, generating a borrow if the balance is insufficient."

5. Minimization is Key

   • Always simplify using K-maps or Boolean algebra before drawing the circuit.
   • Example: Instead of writing $F=A{B}^{\prime }{C}^{\prime }+A{B}^{\prime }C+AB{C}^{\prime }+ABC$, simplify to $F=B^{\prime }(A+C)+BC$.

6. Common Exam Questions

   • Design a half/full adder/subtractor (always show truth table + circuit).
   • Implement a code converter (e.g., Gray to Binary).
   • Use K-maps to minimize a given Boolean function.
   • Explain how a MUX/DEMUX works with a real-world example.

Practice Questions (From Past Exams)

1. Design a combinational circuit that generates the 9’s complement of a BCD number.

   • Hint: Use XOR gates to invert bits and add 1 (like a half-adder).

2. Design a 3-input, 1-output circuit where output=1 if the input is odd.

   • Hint: Use XOR (A⊕B⊕C).

3. Draw a 1:16 DEMUX and explain its working.

   • Hint: Use AND gates with enable signals.

4. Simplify $F(A,B,C,D)=\sum m(0,2,5,7,8,10,13,15)$ using K-map.

   • Hint: Group $m0,m2,m8,m10$ and $m5,m7,m13,m15$.

Final Checklist Before Submission

✅ Truth table has all possible combinations. ✅ Boolean expression is simplified (K-map or algebra). ✅ Circuit diagram uses standard symbols. ✅ Real-world application is mentioned. ✅ All gates are correctly connected (no floating inputs).