Decoder design in Verilog - Time & Space Complexity

Time Complexity: Decoder design

O(2^n)

Understanding Time Complexity

When designing a decoder in Verilog, it is important to understand how the time to process inputs grows as the number of input bits increases.

We want to know how the number of operations changes when the input size changes.

Scenario Under Consideration

Analyze the time complexity of the following decoder code snippet.

module decoder(
  input  wire [3:0] in,
  output reg  [15:0] out
);

  always @(*) begin
    out = 16'b0;
    out[in] = 1'b1;
  end
endmodule

This code takes a 4-bit input and sets one bit high in a 16-bit output based on the input value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Setting the output bits, especially the assignment out[in] = 1'b1;.
• How many times: The output is assigned once per input change, but internally the output vector size grows exponentially with input bits.

How Execution Grows With Input

As the number of input bits n increases, the output size doubles for each added bit.

Input Size (n)	Approx. Output Size
2	4 output bits
4	16 output bits
8	256 output bits

Pattern observation: The number of output bits grows exponentially as 2 to the power of input bits, so operations grow quickly.

Final Time Complexity

Time Complexity: O(2^n)

This means the work needed doubles every time you add one more input bit.

Common Mistake

[X] Wrong: "The decoder only does one operation regardless of input size because it sets only one output bit."

[OK] Correct: Even though one bit is set, the output vector size grows exponentially with input bits, so the hardware must handle all output bits, making complexity grow with output size.

Interview Connect

Understanding how decoder size and complexity grow helps you design efficient hardware and explain your design choices clearly in interviews.

Self-Check

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

Practice

1. What is the main function of a decoder in Verilog?

easy

A. Add two binary numbers

B. Convert binary inputs into one-hot outputs

C. Store data temporarily

D. Generate clock signals

Solution

1. Step 1: Understand decoder purpose

   A decoder takes binary inputs and activates exactly one output line corresponding to the input value.

2. Step 2: Compare options

   Only Convert binary inputs into one-hot outputs describes converting binary inputs into one-hot outputs, which matches the decoder function.

3. Final Answer:

   Convert binary inputs into one-hot outputs -> Option B

4. Quick Check:

   Decoder = binary to one-hot [OK]

Hint: Remember: decoder activates one output per input [OK]

Common Mistakes:

• Confusing decoder with adder
• Thinking decoder stores data
• Mixing decoder with clock generator

2. Which of the following is the correct syntax to start a 2-to-4 decoder module in Verilog?

easy

A. module decoder2to4(input [1:0] in, output reg [3:0] out);

B. module decoder2to4(output [1:0] in, input [3:0] out);

C. module decoder2to4(input in[1:0], output out[3:0]);

D. module decoder2to4(input [3:0] in, output [1:0] out);

Solution

1. Step 1: Check input and output declaration

   Inputs and outputs must be declared with direction and bit width inside square brackets before the variable name.

2. Step 2: Validate syntax correctness

   module decoder2to4(input [1:0] in, output reg [3:0] out); correctly declares input as 2 bits and output as 4 bits with proper syntax.

3. Final Answer:

   module decoder2to4(input [1:0] in, output reg [3:0] out); -> Option A

4. Quick Check:

   Correct module header syntax = module decoder2to4(input [1:0] in, output reg [3:0] out); [OK]

Hint: Inputs before outputs, use [msb:lsb] notation [OK]

Common Mistakes:

• Swapping input and output directions
• Placing bit width after variable name
• Using wrong bit widths

3. Given this Verilog code snippet for a 2-to-4 decoder:

always @(*) begin
  case(in)
    2'b00: out = 4'b0001;
    2'b01: out = 4'b0010;
    2'b10: out = 4'b0100;
    2'b11: out = 4'b1000;
    default: out = 4'b0000;
  endcase
end

What is the value of out when in = 2'b10?

medium

A. 4'b0100

B. 4'b0010

C. 4'b0001

D. 4'b1000

Solution

1. Step 1: Locate matching case for input

   Input 2'b10 matches the third case line: 2'b10: out = 4'b0100;

2. Step 2: Determine output value

   Output is assigned 4'b0100 for input 2'b10.

3. Final Answer:

   4'b0100 -> Option A

4. Quick Check:

   Input 2'b10 maps to 4'b0100 [OK]

Hint: Match input bits to case labels exactly [OK]

Common Mistakes:

• Confusing binary values
• Ignoring default case
• Misreading bit order

4. Identify the error in this 3-to-8 decoder Verilog code snippet:

always @(*) begin
  case(in)
    3'b000: out = 8'b00000001;
    3'b001: out = 8'b00000010;
    3'b010: out = 8'b00000100;
    3'b011: out = 8'b00001000;
    3'b100: out = 8'b00010000;
    3'b101: out = 8'b00100000;
    3'b110: out = 8'b01000000;
    // Missing case for 3'b111
  endcase
end

medium

A. Case statement syntax is invalid

B. Output width is incorrect

C. Input width should be 4 bits

D. Missing default case to cover all inputs

Solution

1. Step 1: Check case coverage

   The case statement covers inputs 3'b000 to 3'b110 but misses 3'b111.

2. Step 2: Importance of default case

   Without a default case, input 3'b111 leads to undefined output, which is an error.

3. Final Answer:

   Missing default case to cover all inputs -> Option D

4. Quick Check:

   Always include default case in decoders [OK]

Hint: Always add default case for full input coverage [OK]

Common Mistakes:

• Forgetting default case
• Assuming all inputs covered without default
• Incorrect input or output widths

5. You want to design a 4-to-16 decoder in Verilog using a case statement. Which approach correctly handles all inputs and ensures only one output bit is high at a time?

hard

A. Use if-else statements checking each bit of input separately to assign outputs

B. Use a case statement with only 8 cases and assign outputs for the rest as zeros

C. Use a case statement with 16 cases for inputs 4'b0000 to 4'b1111, assigning one-hot outputs, plus a default output of all zeros

D. Use a for loop inside always block to assign outputs based on input value

Solution

1. Step 1: Understand decoder requirements

   A 4-to-16 decoder must cover all 16 input combinations with one-hot outputs.

2. Step 2: Evaluate options for completeness and correctness

   Use a case statement with 16 cases for inputs 4'b0000 to 4'b1111, assigning one-hot outputs, plus a default output of all zeros uses a case statement with all 16 input cases plus a default, ensuring exactly one output bit is high per input.

3. Final Answer:

   Use a case statement with 16 cases for inputs 4'b0000 to 4'b1111, assigning one-hot outputs, plus a default output of all zeros -> Option C

4. Quick Check:

   Complete case coverage with one-hot outputs = Use a case statement with 16 cases for inputs 4'b0000 to 4'b1111, assigning one-hot outputs, plus a default output of all zeros [OK]

Hint: Cover all inputs explicitly with one-hot outputs [OK]

Common Mistakes:

• Missing cases causing undefined outputs
• Using incomplete case statements
• Trying to assign outputs with if-else inefficiently