Comparator design in Verilog - Time & Space Complexity

Time Complexity: Comparator design

O(n)

Understanding Time Complexity

When designing a comparator in Verilog, it is important to understand how the time it takes to compare values changes as the size of the inputs grows.

We want to know how the number of operations needed to decide which input is larger changes when the input bit width increases.

Scenario Under Consideration

Analyze the time complexity of the following Verilog comparator code.

module comparator #(parameter WIDTH = 8) (
  input  wire [WIDTH-1:0] a,
  input  wire [WIDTH-1:0] b,
  output wire gt
);
  assign gt = (a > b);
endmodule
    

This code compares two WIDTH-bit inputs and outputs 1 if a is greater than b, otherwise 0.

Identify Repeating Operations

In this comparator design, the main operation is the bit-by-bit comparison done internally by the hardware.

• Primary operation: Comparing each bit of the two inputs starting from the most significant bit.
• How many times: Once for each bit, so WIDTH times.

How Execution Grows With Input

As the input size (WIDTH) increases, the comparator checks more bits one by one.

Input Size (WIDTH)	Approx. Operations (bit comparisons)
10	10
100	100
1000	1000

Pattern observation: The number of operations grows directly with the input size. Double the bits, double the comparisons.

Final Time Complexity

Time Complexity: O(n)

This means the time to compare grows linearly with the number of bits in the inputs.

Common Mistake

[X] Wrong: "Comparing two numbers always takes the same time, no matter how big they are."

[OK] Correct: Actually, the hardware compares bit by bit, so bigger numbers with more bits take more steps to compare.

Interview Connect

Understanding how comparison time grows with input size helps you design efficient hardware and explain your reasoning clearly in interviews.

Self-Check

"What if the comparator was designed to compare inputs in parallel instead of bit-by-bit? How would the time complexity change?"

Practice

1.

What is the main purpose of a comparator in Verilog?

easy

A. To store data temporarily

B. To check if one number is greater, less, or equal to another

C. To add two numbers together

D. To generate clock signals

Solution

1. Step 1: Understand comparator function

   A comparator compares two values to determine their relationship.

2. Step 2: Identify correct purpose

   Only To check if one number is greater, less, or equal to another describes comparing numbers, which is the comparator's job.

3. Final Answer:

   To check if one number is greater, less, or equal to another -> Option B

4. Quick Check:

   Comparator = Compare numbers [OK]

Hint: Comparator compares values, not adds or stores [OK]

Common Mistakes:

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

2.

Which of the following is the correct way to start an always block for a comparator that reacts to changes in inputs a and b?

easy

A. always @(a, b) begin

B. always @(posedge clk) begin

C. always @(a and b) begin

D. always @(a or b) begin

Solution

1. Step 1: Understand sensitivity list syntax

   In Verilog, sensitivity list uses 'or' to list signals that trigger the block.

2. Step 2: Check options

   always @(a or b) begin uses 'or' correctly. always @(a, b) begin uses comma which is not valid in Verilog sensitivity lists.

3. Final Answer:

   always @(a or b) begin -> Option D

4. Quick Check:

   Sensitivity list uses 'or' between signals [OK]

Hint: Use 'or' between signals in sensitivity list [OK]

Common Mistakes:

• Using commas instead of 'or' in sensitivity list
• Using 'and' instead of 'or'
• Using clock edge when not needed

3.

Given the following Verilog code snippet, what will be the output signals gt, lt, and eq if a = 5 and b = 3?

module comp(input [3:0] a, b, output reg gt, lt, eq);
  always @(a or b) begin
    if (a > b) begin
      gt = 1; lt = 0; eq = 0;
    end else if (a < b) begin
      gt = 0; lt = 1; eq = 0;
    end else begin
      gt = 0; lt = 0; eq = 1;
    end
  end
endmodule

medium

A. gt=0, lt=0, eq=1

B. gt=0, lt=1, eq=0

C. gt=1, lt=0, eq=0

D. gt=1, lt=1, eq=0

Solution

1. Step 1: Compare values a=5 and b=3

   Since 5 is greater than 3, the condition 'a > b' is true.

2. Step 2: Determine output signals

   For 'a > b', gt=1, lt=0, eq=0 as per code.

3. Final Answer:

   gt=1, lt=0, eq=0 -> Option C

4. Quick Check:

   5 > 3 means gt=1 [OK]

Hint: Check which condition is true first [OK]

Common Mistakes:

• Mixing up greater than and less than
• Setting multiple outputs to 1 incorrectly
• Ignoring else conditions

4.

Identify the error in this comparator code snippet:

module comp(input [3:0] a, b, output reg gt, lt, eq);
  always @(a, b) begin
    if (a > b)
      gt = 1; lt = 0; eq = 0;
    else if (a < b)
      gt = 0; lt = 1; eq = 0;
    else
      gt = 0; lt = 0; eq = 1;
  end
endmodule

medium

A. Missing begin-end blocks after if and else if

B. Incorrect sensitivity list syntax

C. Output signals should be wires, not regs

D. Using non-blocking assignments instead of blocking

Solution

1. Step 1: Check if-else statement structure

   Multiple statements after if need to be grouped with begin-end blocks.

2. Step 2: Identify missing begin-end

   Here, multiple assignments after if and else if lack begin-end, causing syntax errors.

3. Final Answer:

   Missing begin-end blocks after if and else if -> Option A

4. Quick Check:

   Multiple statements need begin-end [OK]

Hint: Use begin-end for multiple statements in if blocks [OK]

Common Mistakes:

• Forgetting begin-end with multiple statements
• Confusing sensitivity list syntax
• Wrong data type for outputs

5.

You want to design a 4-bit comparator that sets gt high if a > b, lt high if a < b, and eq high if equal. However, you also want to ignore the comparison if either a or b is zero (all bits zero), setting all outputs low in that case. Which Verilog code snippet correctly implements this?

hard

A. always @(a or b) begin
if (a == 0 || b == 0) begin
gt = 0; lt = 0; eq = 0;
end else if (a > b) begin
gt = 1; lt = 0; eq = 0;
end else if (a < b) begin
gt = 0; lt = 1; eq = 0;
end else begin
gt = 0; lt = 0; eq = 1;
end
end

B. always @(a or b) begin
if (a == 0 && b == 0) begin
gt = 0; lt = 0; eq = 0;
end else if (a > b) begin
gt = 1; lt = 0; eq = 0;
end else if (a < b) begin
gt = 0; lt = 1; eq = 0;
end else begin
gt = 0; lt = 0; eq = 1;
end
end

C. always @(a or b) begin
if (a != 0 && b != 0) begin
if (a > b) begin
gt = 1; lt = 0; eq = 0;
end else if (a < b) begin
gt = 0; lt = 1; eq = 0;
end else begin
gt = 0; lt = 0; eq = 1;
end
end else begin
gt = 0; lt = 0; eq = 0;
end
end

D. always @(a or b) begin
if (a == 0 || b == 0) begin
gt = 1; lt = 1; eq = 1;
end else if (a > b) begin
gt = 1; lt = 0; eq = 0;
end else if (a < b) begin
gt = 0; lt = 1; eq = 0;
end else begin
gt = 0; lt = 0; eq = 1;
end
end

Solution

1. Step 1: Understand the zero check condition

   The requirement is to ignore comparison if either a or b is zero, so use 'a == 0 || b == 0'.

2. Step 2: Verify output assignments

   always @(a or b) begin if (a == 0 || b == 0) begin gt = 0; lt = 0; eq = 0; end else if (a > b) begin gt = 1; lt = 0; eq = 0; end else if (a < b) begin gt = 0; lt = 1; eq = 0; end else begin gt = 0; lt = 0; eq = 1; end end sets all outputs low when either input is zero, then compares normally otherwise.

3. Final Answer:

   Option A code snippet -> Option A

4. Quick Check:

   Use '||' to check either zero, outputs low [OK]

Hint: Use '||' to check either zero, set outputs low [OK]

Common Mistakes:

• Using '&&' instead of '||' for zero check
• Setting outputs high when inputs are zero
• Not handling zero inputs separately