Module as the basic building block in Verilog - Time & Space Complexity

Time Complexity: Module as the basic building block

O(N)

Understanding Time Complexity

We want to understand how the time it takes to run a Verilog module changes as the design grows.

How does adding more parts inside a module affect how long it takes to work?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module adder_array #(parameter N = 4) (
  input  wire [N-1:0] a,
  input  wire [N-1:0] b,
  output wire [N-1:0] sum
);
  
  genvar i;
  generate
    for (i = 0; i < N; i = i + 1) begin : adders
      assign sum[i] = a[i] + b[i];
    end
  endgenerate
endmodule

This module adds two N-bit numbers bit by bit using a loop to create multiple adders.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The generate-for loop creates N adders that each perform one addition.
• How many times: The addition operation is repeated N times, once per bit.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (N)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: As the number of bits N grows, the number of addition operations grows linearly.

Final Time Complexity

Time Complexity: O(N)

This means the time to perform all additions grows directly in proportion to the number of bits.

Common Mistake

[X] Wrong: "The module runs in constant time no matter how many bits it has."

[OK] Correct: Each bit requires its own addition, so more bits mean more work and more time.

Interview Connect

Understanding how module size affects time helps you design efficient hardware and explain your design choices clearly.

Self-Check

"What if we replaced the generate loop with a single adder that handles all bits at once? How would the time complexity change?"

Practice

1.

What is the main purpose of a module in Verilog?

easy

A. It defines a reusable block of hardware design.

B. It runs software programs inside the chip.

C. It stores data permanently like a hard drive.

D. It controls the power supply of the circuit.

Solution

1. Step 1: Understand what a module represents

   A module in Verilog is a block that describes hardware behavior or structure.

2. Step 2: Identify the purpose of modules

   Modules help organize and reuse hardware design parts, not software or power control.

3. Final Answer:

   It defines a reusable block of hardware design. -> Option A

4. Quick Check:

   Module = reusable hardware block [OK]

Hint: Modules are like building blocks for hardware [OK]

Common Mistakes:

• Thinking modules run software code
• Confusing modules with memory storage
• Assuming modules control power

2.

Which of the following is the correct way to start and end a Verilog module named my_module?

?

easy

A. start my_module; finish

B. module my_module(); endmodule

C. begin my_module() end

D. module: my_module() endmodule:

Solution

1. Step 1: Recall Verilog module syntax

   A module starts with the keyword module followed by the module name and ends with endmodule.

2. Step 2: Check each option

   module my_module(); endmodule uses correct keywords and syntax. Others use invalid keywords or punctuation.

3. Final Answer:

   module my_module(); endmodule -> Option B

4. Quick Check:

   module ... endmodule = correct syntax [OK]

Hint: Modules always start with 'module' and end with 'endmodule' [OK]

Common Mistakes:

• Using wrong keywords like start or finish
• Missing parentheses after module name
• Adding colons or semicolons incorrectly

3.

What will be the output of the following Verilog module when input_a = 1 and input_b = 0?

module simple_and(input input_a, input input_b, output reg out);
  always @(*) begin
    out = input_a & input_b;
  end
endmodule

medium

A. out = input_b

B. out = 1

C. out = input_a

D. out = 0

Solution

1. Step 1: Understand the operation inside the module

   The module assigns out as the AND of input_a and input_b.

2. Step 2: Calculate the AND of inputs

   Given input_a = 1 and input_b = 0, 1 & 0 = 0.

3. Final Answer:

   out = 0 -> Option D

4. Quick Check:

   1 AND 0 = 0 [OK]

Hint: AND output is 1 only if both inputs are 1 [OK]

Common Mistakes:

• Assuming output equals one input directly
• Confusing AND with OR operation
• Ignoring that output is reg type

4.

Identify the error in this Verilog module code:

module faulty_module(input a, input b, output reg c);
  always @(*) begin
    c = a | b
  end
endmodule

medium

A. Wrong sensitivity list in always block.

B. Incorrect use of 'reg' for output.

C. Missing semicolon after assignment inside always block.

D. Module name should be capitalized.

Solution

1. Step 1: Check syntax inside always block

   The assignment c = a | b is missing a semicolon at the end.

2. Step 2: Verify other parts

   Using reg for output is correct; sensitivity list @(*) is valid; module names can be lowercase.

3. Final Answer:

   Missing semicolon after assignment inside always block. -> Option C

4. Quick Check:

   Statements inside always need semicolons [OK]

Hint: Always end statements inside always block with semicolon [OK]

Common Mistakes:

• Forgetting semicolon after assignment
• Thinking output cannot be reg
• Believing sensitivity list must list signals explicitly

5.

You want to create a Verilog module named counter that counts from 0 to 3 repeatedly using a 2-bit output count. Which module header and port declaration is correct?

hard

A. module counter(input clk, output reg [1:0] count); endmodule

B. module counter(output reg [2:0] count, input clk); endmodule

C. module counter(input clk, output [1:0] count); endmodule

D. module counter(input clk, output reg count[1:0]); endmodule

Solution

1. Step 1: Identify correct port order and types

   The clock input clk should be input, and count is a 2-bit register output, declared as output reg [1:0] count.

2. Step 2: Check each option

   module counter(input clk, output reg [1:0] count); endmodule correctly declares ports and types. module counter(output reg [2:0] count, input clk); endmodule has wrong bit width. module counter(input clk, output [1:0] count); endmodule misses reg for output assigned inside always block. module counter(input clk, output reg count[1:0]); endmodule uses incorrect syntax for bus declaration.

3. Final Answer:

   module counter(input clk, output reg [1:0] count); endmodule -> Option A

4. Quick Check:

   Output reg [1:0] count with input clk = correct [OK]

Hint: Use 'output reg [bits]' for outputs assigned in always blocks [OK]

Common Mistakes:

• Forgetting 'reg' for output assigned in always block
• Incorrect bus declaration syntax
• Swapping input and output order