Multiplexer design in Verilog - Time & Space Complexity

Time Complexity: Multiplexer design

O(n)

Understanding Time Complexity

We want to understand how the time it takes to select data in a multiplexer changes as the number of inputs grows.

How does the selection process scale when we add more input lines?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module mux_4to1(
  input wire [3:0] data_in,
  input wire [1:0] sel,
  output wire data_out
);
  assign data_out = (sel == 2'b00) ? data_in[0] :
                    (sel == 2'b01) ? data_in[1] :
                    (sel == 2'b10) ? data_in[2] : data_in[3];
endmodule

This code selects one bit from four inputs based on a 2-bit selector.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The selection checks each condition in sequence to find the matching input.
• How many times: Up to 4 comparisons in the worst case for 4 inputs.

How Execution Grows With Input

As the number of inputs increases, the number of comparisons grows roughly in proportion.

Input Size (n)	Approx. Operations
4	4 comparisons
8	8 comparisons
16	16 comparisons

Pattern observation: The number of checks grows linearly as inputs increase.

Final Time Complexity

Time Complexity: O(n)

This means the time to select an input grows directly with the number of inputs.

Common Mistake

[X] Wrong: "The multiplexer selects the input instantly no matter how many inputs there are."

[OK] Correct: Each input must be checked against the selector, so more inputs mean more checks and more time.

Interview Connect

Understanding how selection time grows helps you design efficient hardware and explain your reasoning clearly in interviews.

Self-Check

"What if we used a binary tree structure of multiplexers instead of a flat list? How would the time complexity change?"

Practice

1. What is the main purpose of a multiplexer in Verilog design?

easy

A. To select one input from multiple inputs based on selector signals

B. To store data temporarily

C. To perform arithmetic operations

D. To generate clock signals

Solution

1. Step 1: Understand the function of a multiplexer

   A multiplexer routes one of many inputs to a single output based on selector signals.

2. Step 2: Compare with other options

   Other options describe functions unrelated to multiplexers, like storage or arithmetic.

3. Final Answer:

   To select one input from multiple inputs based on selector signals -> Option A

4. Quick Check:

   Multiplexer = Select input [OK]

Hint: Multiplexer chooses one input out of many [OK]

Common Mistakes:

• Confusing multiplexer with memory elements
• Thinking it performs calculations
• Mixing it up with clock generators

2. Which of the following is the correct syntax to define a 2-to-1 multiplexer using a conditional operator in Verilog?

easy

A. assign out = in0 ? sel : in1;

B. assign out = sel & in1 | in0;

C. assign out = sel ? in1 : in0;

D. assign out = sel | in1 & in0;

Solution

1. Step 1: Recall conditional operator syntax

   The conditional operator in Verilog is: condition ? true_value : false_value.

2. Step 2: Match syntax to multiplexer logic

   For a 2-to-1 mux, output is in1 if sel=1, else in0. So, assign out = sel ? in1 : in0; is correct.

3. Final Answer:

   assign out = sel ? in1 : in0; -> Option C

4. Quick Check:

   Conditional operator = condition ? true : false [OK]

Hint: Use condition ? true_val : false_val for mux [OK]

Common Mistakes:

• Using bitwise operators instead of conditional
• Swapping true and false values
• Incorrect operator precedence

3. What is the output of this Verilog code snippet for a 4-to-1 multiplexer when sel = 2'b10 and inputs are in0=0, in1=1, in2=1, in3=0?

module mux4to1(output reg out, input [1:0] sel, input in0, in1, in2, in3);
  always @(*) begin
    case(sel)
      2'b00: out = in0;
      2'b01: out = in1;
      2'b10: out = in2;
      2'b11: out = in3;
    endcase
  end
endmodule

medium

A. 0

B. Error

C. Undefined

D. 1

Solution

1. Step 1: Identify selected input based on sel

   sel = 2'b10 selects input in2 according to the case statement.

2. Step 2: Check value of in2

   in2 is given as 1, so output out = 1.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   sel=2'b10 selects in2=1 [OK]

Hint: Match sel bits to input index [OK]

Common Mistakes:

• Confusing binary selector values
• Ignoring case statement mapping
• Assuming default output without case

4. Identify the error in this Verilog 2-to-1 multiplexer code:

module mux2to1(output reg out, input sel, input in0, in1);
  always @(*) begin
    if (sel == 1) out = in1;
    else if (sel == 0) out = in0;
    else out = 1'bx;
  end
endmodule

medium

A. Using 'else if' instead of 'else' for sel check

B. No default case needed for 1-bit sel

C. Output should be wire, not reg

D. Missing sensitivity list in always block

Solution

1. Step 1: Analyze selector signal type

   sel is 1-bit, so it can only be 0 or 1, no other values possible.

2. Step 2: Check necessity of default case

   Since sel cannot be other than 0 or 1, the 'else out = 1'bx;' is unnecessary.

3. Final Answer:

   No default case needed for 1-bit sel -> Option B

4. Quick Check:

   1-bit sel only 0 or 1, no default needed [OK]

Hint: 1-bit selector has only two values [OK]

Common Mistakes:

• Adding unreachable default cases
• Confusing reg and wire for outputs
• Forgetting sensitivity list is @(*)

5. You need to design an 8-to-1 multiplexer in Verilog using a case statement. Which of the following code snippets correctly implements this multiplexer assuming inputs in0 to in7, selector sel[2:0], and output out?

hard

A. always @(*) begin
case(sel)
3'b000: out = in0;
3'b001: out = in1;
3'b010: out = in2;
3'b011: out = in3;
3'b100: out = in4;
3'b101: out = in5;
3'b110: out = in6;
3'b111: out = in7;
default: out = 1'b0;
endcase
end

B. always @(sel) begin
if(sel == 0) out = in0;
else if(sel == 1) out = in1;
else if(sel == 2) out = in2;
else if(sel == 3) out = in3;
else if(sel == 4) out = in4;
else if(sel == 5) out = in5;
else if(sel == 6) out = in6;
else if(sel == 7) out = in7;
end

C. always @(*) begin
case(sel)
3'b000: out = in7;
3'b001: out = in6;
3'b010: out = in5;
3'b011: out = in4;
3'b100: out = in3;
3'b101: out = in2;
3'b110: out = in1;
3'b111: out = in0;
endcase
end

D. always @(*) begin
case(sel)
3'b000: out = in0;
3'b001: out = in1;
3'b010: out = in2;
3'b011: out = in3;
3'b100: out = in4;
3'b101: out = in5;
3'b110: out = in6;
endcase
end

Solution

1. Step 1: Check completeness of case statement

   always @(*) begin case(sel) 3'b000: out = in0; 3'b001: out = in1; 3'b010: out = in2; 3'b011: out = in3; 3'b100: out = in4; 3'b101: out = in5; 3'b110: out = in6; 3'b111: out = in7; default: out = 1'b0; endcase end covers all 8 selector values (0 to 7) and includes a default case.

2. Step 2: Verify correct input mapping

   always @(*) begin case(sel) 3'b000: out = in0; 3'b001: out = in1; 3'b010: out = in2; 3'b011: out = in3; 3'b100: out = in4; 3'b101: out = in5; 3'b110: out = in6; 3'b111: out = in7; default: out = 1'b0; endcase end maps sel values 3'b000 to 3'b111 to in0 through in7 respectively, which is correct.

3. Step 3: Identify issues in other options

   always @(sel) begin if(sel == 0) out = in0; else if(sel == 1) out = in1; else if(sel == 2) out = in2; else if(sel == 3) out = in3; else if(sel == 4) out = in4; else if(sel == 5) out = in5; else if(sel == 6) out = in6; else if(sel == 7) out = in7; end uses if-else but sensitivity list is only sel, which is acceptable but lacks default. always @(*) begin case(sel) 3'b000: out = in7; 3'b001: out = in6; 3'b010: out = in5; 3'b011: out = in4; 3'b100: out = in3; 3'b101: out = in2; 3'b110: out = in1; 3'b111: out = in0; endcase end reverses input mapping incorrectly. always @(*) begin case(sel) 3'b000: out = in0; 3'b001: out = in1; 3'b010: out = in2; 3'b011: out = in3; 3'b100: out = in4; 3'b101: out = in5; 3'b110: out = in6; endcase end misses case for 3'b111.

4. Final Answer:

   Option A correctly implements 8-to-1 mux with case and default -> Option A

5. Quick Check:

   Complete case with all inputs mapped = always @(*) begin case(sel) 3'b000: out = in0; 3'b001: out = in1; 3'b010: out = in2; 3'b011: out = in3; 3'b100: out = in4; 3'b101: out = in5; 3'b110: out = in6; 3'b111: out = in7; default: out = 1'b0; endcase end [OK]

Hint: Cover all selector values with case and default [OK]

Common Mistakes:

• Missing cases for some selector values
• Incorrect input to selector mapping
• No default case in case statement