Combinational Logic: Design, Decoders, MUX, Adders & Converters

What is a Combinational Logic Circuit?

A combinational logic circuit is a digital circuit whose output depends only on the current inputs, with no memory elements (like flip-flops). Examples include adders, decoders, and multiplexers.

Key Characteristics:

• No memory: Outputs change instantly with inputs.
• Synchronous operation: No clock signal needed (unlike sequential circuits).
• Applications: Used in ALUs, memory decoders, data selectors, and code converters.

Design Procedure for Combinational Circuits

Follow these steps to design any combinational circuit:

1. Define inputs/outputs: List variables and their meanings.
2. Write truth table: Enumerate all possible input combinations and corresponding outputs.
3. Derive Boolean expressions: Use Karnaugh Maps (K-Maps) or algebraic simplification.
4. Draw logic diagram: Implement using gates (AND, OR, NOT, NAND, NOR).
5. Verify: Cross-check with truth table.

Worked Example: Half Adder

A half adder adds two single-bit inputs $A$ and $B$ and produces a sum ($S$) and carry ($C$).

Step 1: Truth Table

Step 2: Boolean Expressions

• Sum: $S=A^{\prime }B+A{B}^{\prime }$ (XOR)
• Carry: $C=AB$

Step 3: Logic Diagram

Step 4: Real-World Use

Half adders are the building blocks of full adders, which are used in arithmetic logic units (ALUs) of CPUs (e.g., in Intel’s processors for binary addition).

Key Combinational Circuits

1. Decoders

A decoder converts $n$ input lines into $2^n$ output lines, activating one output at a time.

Example: 2-to-4 Line Decoder

Logic Diagram

Real-World Use:

• Memory addressing: Decoders in RAM/ROM chips select specific memory locations (e.g., in a 16MB RAM, a 24-to-64K decoder maps addresses to memory cells).
• 7-segment displays: A BCD-to-7-segment decoder (like the 74LS47) drives digital clocks and calculators.

2. Multiplexers (MUX)

A multiplexer selects one of $2^n$ inputs and routes it to a single output based on select lines.

Example: 4:1 MUX

Logic Diagram

flowchart LR
    I0["I0"] --> A["AND"]
    I1["I1"] --> B["AND"]
    I2["I2"] --> C["AND"]
    I3["I3"] --> D["AND"]
    S0["S0"] --> E["AND"]
    S1["S1"] --> F["AND"]
    A --> OR1["OR"]
    B --> OR1
    C --> OR1
    D --> OR1
    OR1 --> Y["Y"]
    E --> A
    E --> B
    F --> C
    F --> D

Real-World Use:

• Data buses: In computers, MUXes select data from multiple sources (e.g., CPU, RAM, or I/O devices) onto the system bus.
• Pathao’s ride allocation: A MUX-like system selects the nearest available driver for a user’s request based on GPS inputs (select lines).

3. Adders

Half Adder vs. Full Adder

Full Adder Truth Table

Logic Diagram

Real-World Use:

• eSewa transactions: When you pay a bill, the system uses a ripple-carry adder (chain of full adders) to sum your account balance and the bill amount.
• Ncell’s billing: SIM card data usage is calculated using adders to accumulate bytes used over time.

4. Binary to Octal Converter

Converts a 3-bit binary input to a 3-bit octal output (each group of 3 binary digits = 1 octal digit).

Truth Table

Logic Diagram

flowchart LR
    B0["B0"] --> AND1["AND"]
    B1["B1"] --> AND2["AND"]
    B2["B2"] --> AND3["AND"]
    AND1 --> OR1["OR"]
    AND2 --> OR1
    AND3 --> OR1
    OR1 --> Y0["Y0"]
    B0 --> OR2["OR"]
    B1 --> OR2
    OR2 --> Y1["Y1"]
    B2 --> Y2["Y2"]

Real-World Use:

• NTC’s traffic signal controllers: Binary counters (with BCD-to-octal converters) manage timing sequences for red/yellow/green lights in Kathmandu’s traffic systems.

In the Real World

1. Khalti’s Payment Processing:

   • When you transfer money, Khalti’s servers use adders (in their ALUs) to verify transaction amounts and update account balances in real time. A single-bit error in addition could cause a mismatch, so full adders with carry propagation ensure accuracy.

2. Daraz’s Order Queue:

   • Daraz’s backend uses priority encoders (a type of decoder) to assign orders to delivery agents based on urgency (e.g., "same-day" vs. "standard"). The encoder selects the highest-priority order from multiple inputs and routes it to the next stage.

3. NEPSE Stock Exchange:

   • Stock prices are displayed in hexadecimal or binary for high-frequency trading algorithms. A binary-to-BCD converter translates these values into readable formats for traders. For example, a stock price of 0x1F4 (500 in decimal) is converted to 0001 1111 0100 (BCD) for display.

Exam Tip

1. Truth Tables Are King:

   • Always start with a complete truth table for any design question. Partial tables lose marks.
   • Example: For a full adder, if you miss $C_{in}=1$ cases, your Boolean expressions will be incorrect.

2. Simplify Using K-Maps:

   • Karnaugh Maps (K-Maps) are faster than algebraic simplification for 4+ variables. Group adjacent 1s (including wrap-around) to minimize terms.
   • Example: For $F(A,B,C,D)=\sum m(0,1,2,5,7,8,10,13,14,15)$, the K-Map groups show $F=B^{\prime }D+AD+B{C}^{\prime }{D}^{\prime }$.

3. Draw Logic Diagrams Clearly:

   • Use standard gate symbols (NAND = AND + bubble, NOR = OR + bubble).
   • Label all inputs/outputs with their variables (e.g., don’t just write "Gate 1"; write $A\cdot B^{\prime }$).

4. Common Pitfalls:

   • Forgetting to include carry inputs in adders (half adders vs. full adders).
   • Misinterpreting decoder outputs (e.g., thinking $Y_0$ is active-high when it’s active-low).
   • Not verifying your design with the original truth table.

5. Shortcut for Decoders/MUX:

   • For a 3-to-8 decoder, the output equation for $Y_i$ is simply the minterm corresponding to its input combination (e.g., $Y_5=A^{\prime }{B}^{\prime }{C}^{\prime }$).

Practice Question (From Past Exams)

Design a BCD to Decimal decoder with its block diagram, truth table, and logic diagram. Solution Outline:

1. Truth Table: List all 4-bit BCD inputs (0000 to 1001) and their corresponding 7-segment outputs (e.g., 0000 → ABCDEF = 1111110 for digit "0").
2. K-Map Simplification: Simplify each segment’s Boolean expression (e.g., for segment A, group 1s for inputs 0, 2, 3, 5, 6, 7, 8, 9).
3. Logic Diagram: Use AND gates for each segment, driven by the simplified BCD inputs.
4. Block Diagram:

   flowchart LR
       BCD["BCD Input"] --> Decoder["BCD to 7-Segment Decoder"]
       Decoder --> SegA["Segment A"]
       Decoder --> SegB["Segment B"]
       Decoder --> SegC["Segment C"]
       Decoder --> SegD["Segment D"]
       Decoder --> SegE["Segment E"]
       Decoder --> SegF["Segment F"]
       Decoder --> SegG["Segment G"]

Real-World Tie-In: This is exactly how digital watches (like Casio’s) display time—each digit is driven by a BCD-to-7-segment decoder.