Encoder design in Verilog - Time & Space Complexity

Time Complexity: Encoder design

O(n)

Understanding Time Complexity

We want to understand how the time needed to run an encoder changes as the number of inputs grows.

Specifically, how does the work increase when the input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module encoder(
  input wire [7:0] in,
  output reg [2:0] out
);
  integer i;
  always @(*) begin
    out = 3'b000;
    for (i = 0; i < 8; i = i + 1) begin
      if (in[i]) out = i[2:0];
    end
  end
endmodule

This code finds the position of the highest set bit in an 8-bit input and outputs its index.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that checks each bit of the input.
• How many times: It runs once for each input bit, so 8 times here.

How Execution Grows With Input

As the input size grows, the loop runs more times, checking each bit once.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The number of operations grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the highest set bit grows in a straight line as the input gets bigger.

Common Mistake

[X] Wrong: "The encoder checks all bits instantly, so time doesn't grow with input size."

[OK] Correct: The code explicitly loops through each bit one by one, so more bits mean more checks and more time.

Interview Connect

Understanding how loops affect time helps you explain how hardware or code scales, a key skill in design and debugging.

Self-Check

"What if we used a priority encoder module instead of a loop? How would the time complexity change?"

Practice

1.

What is the primary function of an encoder in digital design?

easy

A. Store multiple bits of data temporarily

B. Convert binary code into decimal numbers

C. Amplify the input signal strength

D. Convert one active input line into a binary code output

Solution

1. Step 1: Understand the role of an encoder

   An encoder takes multiple input lines but only one is active at a time and converts that active input into a binary code output.

2. Step 2: Compare options with the definition

   Convert one active input line into a binary code output matches the definition exactly, while others describe different components or functions.

3. Final Answer:

   Convert one active input line into a binary code output -> Option D

4. Quick Check:

   Encoder function = binary code output from active input [OK]

Hint: Remember: Encoder outputs binary code for one active input [OK]

Common Mistakes:

• Confusing encoder with decoder
• Thinking encoder stores data
• Assuming encoder amplifies signals

2.

Which of the following is the correct Verilog syntax to start a casez statement for a 4-input encoder?

module encoder(input [3:0] in, output reg [1:0] out);
  always @(*) begin
    casez(____)
      4'b0001: out = 2'b00;
      4'b0010: out = 2'b01;
      4'b0100: out = 2'b10;
      4'b1000: out = 2'b11;
    endcase
  end
endmodule

easy

A. out

B. in

C. in[3:0]

D. out[1:0]

Solution

1. Step 1: Identify the signal to check in the casez

   The casez statement should check the input signals to decide the output.

2. Step 2: Match the input vector name

   The input vector is named 'in', so casez(in) is correct syntax.

3. Final Answer:

   in -> Option B

4. Quick Check:

   casez checks input vector 'in' [OK]

Hint: Use input signal name inside casez parentheses [OK]

Common Mistakes:

• Using output signal in casez
• Using bit slices incorrectly
• Confusing input and output signals

3.

Given this Verilog snippet for a 4-to-2 encoder, what is the output out when in = 4'b0100?

module encoder(input [3:0] in, output reg [1:0] out);
  always @(*) begin
    casez(in)
      4'b0001: out = 2'b00;
      4'b0010: out = 2'b01;
      4'b0100: out = 2'b10;
      4'b1000: out = 2'b11;
      default: out = 2'bxx;
    endcase
  end
endmodule

medium

A. 2'b10

B. 2'b01

C. 2'b00

D. 2'b11

Solution

1. Step 1: Match input pattern to casez branches

   The input is 4'b0100, which matches the third case in the casez statement.

2. Step 2: Identify output for matched case

   For 4'b0100, the output is assigned 2'b10.

3. Final Answer:

   2'b10 -> Option A

4. Quick Check:

   Input 0100 maps to output 10 [OK]

Hint: Match input bits exactly to casez patterns [OK]

Common Mistakes:

• Confusing input bit positions
• Choosing default output incorrectly
• Misreading binary literals

4.

Identify the error in this Verilog encoder code snippet:

module encoder(input [3:0] in, output reg [1:0] out);
  always @(*) begin
    case(in)
      4'b0001: out = 2'b00;
      4'b0010: out = 2'b01;
      4'b0100: out = 2'b10;
      4'b1000: out = 2'b11;
      default: out = 2'bxx;
    endcase
  end
endmodule

What is the main problem?

medium

A. Output out should be declared as wire, not reg

B. Input in should be 2 bits, not 4 bits

C. Using case instead of casez causes incorrect matching with 'x' or 'z'

D. Missing sensitivity list in always block

Solution

1. Step 1: Understand difference between case and casez

   The case statement matches exact bits, but casez allows 'z' and 'x' as wildcards, useful in encoders.

2. Step 2: Identify why casez is preferred here

   Using case can cause mismatches if inputs have unknown bits; casez handles this gracefully.

3. Final Answer:

   Using case instead of casez causes incorrect matching with 'x' or 'z' -> Option C

4. Quick Check:

   Use casez for wildcard matching in encoders [OK]

Hint: Use casez to handle unknown bits in inputs [OK]

Common Mistakes:

• Confusing reg and wire for outputs
• Wrong input width
• Forgetting sensitivity list (@(*) is correct here)

5.

You want to design a 8-to-3 priority encoder in Verilog that outputs the binary code of the highest priority active input. Which approach is best to implement this?

hard

A. Use a casez statement with input patterns ordered from highest to lowest priority

B. Use multiple if statements checking inputs from lowest to highest priority

C. Use a for loop to assign output based on input index without priority checks

D. Use a case statement with unordered input patterns

Solution

1. Step 1: Understand priority encoder requirements

   A priority encoder outputs the code of the highest priority active input among many inputs.

2. Step 2: Choose method to implement priority

   Using casez with patterns ordered from highest to lowest priority ensures the first matched input is the highest priority.

3. Final Answer:

   Use a casez statement with input patterns ordered from highest to lowest priority -> Option A

4. Quick Check:

   Priority encoder needs ordered casez for correct output [OK]

Hint: Order casez patterns by priority for correct encoding [OK]

Common Mistakes:

• Checking inputs in wrong priority order
• Using unordered case statements
• Ignoring priority in loops