Case statement for multiplexing in Verilog - Time & Space Complexity

Time Complexity: Case statement for multiplexing

O(log n)

Understanding Time Complexity

We want to understand how the propagation delay of a case statement for multiplexing changes as the number of inputs grows.

In hardware, how does the critical path delay scale with the number of choices?

Scenario Under Consideration

Analyze the time complexity (propagation delay) of the following code snippet after synthesis.

module mux_case(
  input  wire [2:0] sel,
  input  wire [7:0] in0, in1, in2, in3, in4, in5, in6, in7,
  output reg  [7:0] out
);
  always @(*) begin
    case(sel)
      3'd0: out = in0;
      3'd1: out = in1;
      3'd2: out = in2;
      3'd3: out = in3;
      3'd4: out = in4;
      3'd5: out = in5;
      3'd6: out = in6;
      3'd7: out = in7;
      default: out = 8'd0;
    endcase
  end
endmodule

This code implements an 8:1 multiplexer using a case statement, which synthesizes to combinational logic.

Identify Repeating Operations

No loops or recursion; it's combinational logic synthesized to a mux tree.

• Primary operation: Parallel one-hot decoding and selection, implemented as a tree of 2:1 muxes.
• Critical path: Logarithmic number of logic levels.

How Execution Grows With Input

Synthesis tools implement large muxes as balanced trees, so delay grows logarithmically.

Input Size (n)	Approx. Logic Levels (Delay)
8	~3 levels
16	~4 levels
32	~5 levels

Pattern observation: Delay grows as O(log n) with the number of inputs.

Final Time Complexity

Time Complexity (Delay): O(log n)

The propagation delay grows logarithmically as the number of inputs increases due to the mux tree structure.

Common Mistake

[X] Wrong: "The case statement checks sequentially like software, taking O(n) time."

[OK] Correct: In hardware, all paths are evaluated in parallel; synthesis optimizes to O(log n) delay mux tree, not sequential logic.

Interview Connect

Distinguishing software-like thinking from hardware synthesis is key in digital design interviews. Explain how case synthesizes to mux trees.

Self-Check

"How does using LUTs in FPGAs affect mux delay for larger n? (Often O(1) per LUT, but still log n levels across LUTs)"

Practice

1.

What is the main purpose of using a case statement in Verilog for multiplexing?

easy

A. To declare variables for storage

B. To create a loop that repeats operations

C. To define timing delays in the circuit

D. To select one input from many based on a selector signal

Solution

1. Step 1: Understand multiplexing concept

   Multiplexing means choosing one input out of many based on a selector signal.

2. Step 2: Role of case statement

   The case statement in Verilog is used to pick one input depending on the selector value.

3. Final Answer:

   To select one input from many based on a selector signal -> Option D

4. Quick Check:

   Multiplexer selection = case statement use [OK]

Hint: Case picks input based on selector signal [OK]

Common Mistakes:

• Confusing case with loops
• Using case for variable declaration
• Thinking case defines timing

2.

Which of the following is the correct syntax to start a case statement for a 2-bit selector sel in Verilog?

?

easy

A. case(sel) begin

B. case sel {

C. case(sel)

D. switch(sel) {

Solution

1. Step 1: Recall Verilog case syntax

   The correct syntax to start a case statement is case(expression) without extra keywords or braces.

2. Step 2: Check options

   case(sel) matches the correct syntax exactly: case(sel).

3. Final Answer:

   case(sel) -> Option C

4. Quick Check:

   Verilog case syntax = case(expression) [OK]

Hint: Use parentheses around selector in case [OK]

Common Mistakes:

• Adding 'begin' after case
• Using braces {} like other languages
• Using 'switch' instead of 'case'

3.

Given the following Verilog code, what is the value of out when sel = 2'b10?

module mux_example(input [1:0] sel, input a, b, c, d, output reg out);
  always @(*) begin
    case(sel)
      2'b00: out = a;
      2'b01: out = b;
      2'b10: out = c;
      default: out = d;
    endcase
  end
endmodule

medium

A. Value of input b

B. Value of input c

C. Value of input a

D. Value of input d

Solution

1. Step 1: Identify selector value

   The selector sel is 2'b10, which matches the third case.

2. Step 2: Match case to output

   For 2'b10, the output out is assigned the value of input c.

3. Final Answer:

   Value of input c -> Option B

4. Quick Check:

   sel=2'b10 selects c [OK]

Hint: Match selector bits to case labels [OK]

Common Mistakes:

• Choosing default instead of matching case
• Mixing up input variables
• Ignoring binary selector format

4.

Identify the error in this Verilog case statement used for multiplexing:

always @(*) begin
  case(sel)
    2'b00: out = a;
    2'b01: out = b;
    2'b10: out = c;
  endcase
end

medium

A. Missing default case for unmatched selector values

B. Incorrect use of always block sensitivity list

C. Wrong assignment operator used

D. Selector signal sel is not declared

Solution

1. Step 1: Check case completeness

   The case statement covers 2'b00, 2'b01, and 2'b10 but misses 2'b11.

2. Step 2: Importance of default case

   Without a default case, the output out may hold previous value or be undefined for unmatched selectors.

3. Final Answer:

   Missing default case for unmatched selector values -> Option A

4. Quick Check:

   Always include default in case [OK]

Hint: Always add default case in multiplexers [OK]

Common Mistakes:

• Forgetting default case
• Using wrong sensitivity list (@posedge instead of @(*) )
• Using '=' instead of '<=' in combinational logic

5.

You want to design a 4-to-1 multiplexer using a case statement in Verilog. Which of the following code snippets correctly implements this with inputs a, b, c, d, selector sel, and output out?

?

hard

A. always @(*) begin
case(sel)
2'b00: out = a;
2'b01: out = b;
2'b10: out = c;
2'b11: out = d;
default: out = 1'b0;
endcase
end

B. always @(sel) begin
case(sel)
2'b00: out = a;
2'b01: out = b;
2'b10: out = c;
default: out = d;
endcase
end

C. always @(*) begin
if(sel == 2'b00) out = a;
else if(sel == 2'b01) out = b;
else if(sel == 2'b10) out = c;
else out = d;
end

D. always @(*) begin
case(sel)
0: out = a;
1: out = b;
2: out = c;
3: out = d;
endcase
end

Solution

1. Step 1: Check sensitivity list

   always @(*) begin case(sel) 2'b00: out = a; 2'b01: out = b; 2'b10: out = c; 2'b11: out = d; default: out = 1'b0; endcase end uses always @(*), which is correct for combinational logic multiplexers.

2. Step 2: Verify case labels and default

   always @(*) begin case(sel) 2'b00: out = a; 2'b01: out = b; 2'b10: out = c; 2'b11: out = d; default: out = 1'b0; endcase end covers all 4 selector values (2'b00 to 2'b11) and includes a default case to avoid latches.

3. Step 3: Compare other options

   always @(sel) begin case(sel) 2'b00: out = a; 2'b01: out = b; 2'b10: out = c; default: out = d; endcase end misses 2'b11 case explicitly and uses always @(sel) which is less recommended. always @(*) begin if(sel == 2'b00) out = a; else if(sel == 2'b01) out = b; else if(sel == 2'b10) out = c; else out = d; end uses if-else, not case. always @(*) begin case(sel) 0: out = a; 1: out = b; 2: out = c; 3: out = d; endcase end uses decimal labels without binary format and misses default.

4. Final Answer:

   Option A code snippet -> Option A

5. Quick Check:

   Complete case with default and always @(*) = always @(*) begin case(sel) 2'b00: out = a; 2'b01: out = b; 2'b10: out = c; 2'b11: out = d; default: out = 1'b0; endcase end [OK]

Hint: Use always @(*) and include default case [OK]

Common Mistakes:

• Omitting default case
• Using incomplete case labels
• Wrong sensitivity list
• Mixing if-else with case question