K-MAP Implemented with a MUX

Date

Date

Date

February 22, 2025

February 22, 2025

February 22, 2025

Author

Author

Author

Abhishek Dasari

Abhishek Dasari

Abhishek Dasari

Question:

For the following Karnaugh map, give the circuit implementation using one 4-to-1 multiplexer and as many 2-to-1 multiplexers as required, but using as few as possible. You are not allowed to use any other logic gate, and you must use a and b as the multiplexer selector inputs, as shown on the 4-to-1 multiplexer below.

Solution:

To implement the given K-map function using only multiplexers, follow these structured steps:

Step 1: Implement a 4-to-1 Multiplexer

The 4-to-1 multiplexer is already implemented in Weekly Blog 1. Before proceeding, ensure that it functions correctly by checking that:

  • Whena = 0 b = 0mux_in[0] is selected

  • Whena = 0 b = 1mux_in[1] is selected

  • Whena = 1 b = 0mux_in[2] is selected

  • Whena = 1 b = 1mux_in[3] is selected

module mux_4X1(
    input i0, i1, i2, i3,  // Four input lines
    input s0, s1,      // Two select lines
    output o1          // Output
);
    wire w1, w2;

    // First stage: Select between A, B and C, D
    mux m1(w1, i0, i1, s0);
    mux m2(w2, i2, i3, s0);

    // Second stage: Select final output
    mux m3(o1, w1, w2, s1);
endmodule
module mux(
    output sel,  // Output of 2x1 MUX
    input a, b,  // Inputs
    input en     // Select line
);
    wire enb, o1, o2;
    
    not n(enb, en);   // Invert the select signal
    and m1(o1, en, a);
    and m2(o2, enb, b);
    or con(sel, o1, o2);  // Final output
endmodule

If you haven't implemented it yet, refer to Weekly Blog 1 for the Verilog code of the 4-to-1 multiplexer.

Step 2: Determine Inputs for 4-to-1 MUX (I0, I1, I2, I3) using K-map


      ab
      00  01  11  10
cd -------------------
00 |  0    0    0    1  
01 |  1    0    0    0  
11 |  1    0    1    0  
10 |  1    0    1    1  

solving the kmap give the expression 
  f= (ab'd') + (abcd) + (a'b'(c+d))
   a and b are select variables

When a = 0, b = 0 : mux_in[0] = c+d

When a = 0, b = 0 : mux_in[1] = 0

When a = 0, b = 0 : mux_in[2] = ~d

When a = 0, b = 0 : mux_in[3] = c

Step 3: Verilog Code for Implementing the Function using MUX

module top_module (
    input wire a, b, c, d,
    output wire f
);
    wire [3:0] mux_in;
         //solving the kmap give the expression 
        // f= (ab'd') + (abcd) + (a'b'(c+d))
        // a and b are select variables
    
    assign mux_in[0]= c ? 1 : (d ? 1 : 0)  ,   // c OR d
        mux_in[1]= 0,	// zero
       mux_in[2]= d ? 0 : 1,		// not D
     mux_in[3]= c ? (d ? 1 : 0) : 0;      // c AND D
    
 

    // 4-to-1 Multiplexer (Assuming already implemented in Weekly Blog 1)
    mux_4X1 mux_final (mux_in[0], mux_in[1], mux_in[2], mux_in[3],b,a,f);

endmodule

Step 4: Verilog Testbench for the MUX-Based Implementation

Now that we have designed our circuit using multiplexers, we need to verify its correctness using a testbench. The testbench will simulate all possible input combinations and ensure the output matches the expected values derived from the K-map.

`timescale 1ns / 1ps

module top_module_tb;
    // Declare input signals
    reg a, b, c, d;
    
    // Declare output signal
    wire f;

    // Instantiate the DUT (Device Under Test)
    top_module uut (
        a,b,c,d,f
    );

    // Apply test cases
    initial begin
        $monitor("Time=%0t | a=%b, b=%b, c=%b, d=%b | f=%b", $time, a, b, c, d, f);
        
        // Apply all 16 possible input combinations
        a = 0; b = 0; c = 0; d = 0; #10;
        a = 0; b = 0; c = 0; d = 1; #10;
        a = 0; b = 0; c = 1; d = 0; #10;
        a = 0; b = 0; c = 1; d = 1; #10;
        
        a = 0; b = 1; c = 0; d = 0; #10;
        a = 0; b = 1; c = 0; d = 1; #10;
        a = 0; b = 1; c = 1; d = 0; #10;
        a = 0; b = 1; c = 1; d = 1; #10;
        
        a = 1; b = 0; c = 0; d = 0; #10;
        a = 1; b = 0; c = 0; d = 1; #10;
        a = 1; b = 0; c = 1; d = 0; #10;
        a = 1; b = 0; c = 1; d = 1; #10;
        
        a = 1; b = 1; c = 0; d = 0; #10;
        a = 1; b = 1; c = 0; d = 1; #10;
        a = 1; b = 1; c = 1; d = 0; #10;
        a = 1; b = 1; c = 1; d = 1; #10;

        $finish; // End the simulation
    end
endmodule

Step 5: View the Waveform (Timing Diagram)

After running the testbench:

Conclusion

In this exercise, we successfully designed and verified a multiplexer-based circuit implementation using one 4-to-1 MUX and multiple 2-to-1 MUXes. The key takeaways from this implementation are:

Understanding Karnaugh Maps (K-maps): We derived the Boolean function from the K-map and implemented it using multiplexers without additional logic gates.

Efficient Multiplexer Usage: Instead of using traditional logic gates, we demonstrated how MUXes alone can implement combinational logic efficiently.

Verilog Implementation & Simulation: We wrote the Verilog code for both the design and testbench and simulated the circuit to verify its correctness.

Timing Diagram Verification: The output f matched the expected truth table values for all 16 input combinations, confirming the correctness of our design.

Related posts

June 6, 2025

🚀 Demystifying Compute-in-Memory: The Next Big Leap in AI Hardware

June 6, 2025

🚀 Demystifying Compute-in-Memory: The Next Big Leap in AI Hardware

June 6, 2025

🚀 Demystifying Compute-in-Memory: The Next Big Leap in AI Hardware

February 28, 2025

Generate for-loop: 100-bit binary Ripple Carry Adder

February 28, 2025

Generate for-loop: 100-bit binary Ripple Carry Adder

February 28, 2025

Generate for-loop: 100-bit binary Ripple Carry Adder

Got questions?

I’m always excited to collaborate on innovative and exciting projects!

E-mail

abhishekdasari1801@gmail.com

Phone

+91 ______________________

Got questions?

I’m always excited to collaborate on innovative and exciting projects!

E-mail

abhishekdasari1801@gmail.com

Phone

+91 ______________________

Got questions?

I’m always excited to collaborate on innovative and exciting projects!

E-mail

abhishekdasari1801@gmail.com

Phone

+91 ______________________

©2024 AbhishekDasari

©2024 AbhishekDasari

©2024 AbhishekDasari