Subtractor design in Verilog - Time & Space Complexity

Time Complexity: Subtractor design

O(n)

Understanding Time Complexity

We want to understand how the time to perform subtraction grows as the size of the numbers increases.

How does the design handle larger inputs and how does that affect speed?

Scenario Under Consideration

Analyze the time complexity of the following Verilog subtractor design.

module subtractor #(parameter N = 8) (
  input  wire [N-1:0] a, b,
  output wire [N-1:0] diff,
  output wire borrow_out
);
  wire [N:0] borrow;
  assign borrow[0] = 0;
  genvar i;
  generate
    for (i = 0; i < N; i = i + 1) begin : subtract_bit
      assign diff[i] = a[i] ^ b[i] ^ borrow[i];
      assign borrow[i+1] = (~a[i] & b[i]) | ((~a[i] | b[i]) & borrow[i]);
    end
  endgenerate
  assign borrow_out = borrow[N];
endmodule

This code implements an N-bit subtractor using a ripple borrow method, processing each bit in sequence.

Identify Repeating Operations

Look for repeated steps that affect time.

• Primary operation: The for-loop that processes each bit of the inputs.
• How many times: Exactly N times, once per bit.

How Execution Grows With Input

Each additional bit adds one more step in the chain of borrow calculations.

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

Pattern observation: The number of steps grows directly with the number of bits.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete subtraction grows linearly with the number of bits.

Common Mistake

[X] Wrong: "The subtraction happens all at once, so time does not depend on input size."

[OK] Correct: Each bit depends on the borrow from the previous bit, so the steps happen one after another, making time grow with input size.

Interview Connect

Understanding how hardware operations scale helps you explain design choices clearly and shows you grasp how circuits work step-by-step.

Self-Check

"What if we used a carry-lookahead style subtractor instead? How would the time complexity change?"

Practice

1.

What is the main function of a subtractor in digital circuits?

easy

A. To multiply two binary numbers

B. To add two binary numbers

C. To find the difference between two binary numbers

D. To store binary data

Solution

1. Step 1: Understand the subtractor's purpose

   A subtractor is designed to calculate the difference between two binary inputs.

2. Step 2: Compare with other operations

   Adders add, multipliers multiply, and storage units store data, so these are not subtractors.

3. Final Answer:

   To find the difference between two binary numbers -> Option C

4. Quick Check:

   Subtractor = Difference finder [OK]

Hint: Subtractor always calculates difference, not sum or product [OK]

Common Mistakes:

• Confusing subtractor with adder
• Thinking subtractor stores data
• Mixing subtractor with multiplier

2.

Which of the following is the correct Verilog module header for a 1-bit subtractor?

module subtractor(

easy

A. module subtractor(input a, input b, output diff, output borrow);

B. module subtractor(input a, b, output diff, borrow);

C. module subtractor(a, b, diff, borrow);

D. module subtractor(input a, input b, input diff, output borrow);

Solution

1. Step 1: Check correct input/output declaration

   Inputs must be declared with 'input' keyword and outputs with 'output'.

2. Step 2: Verify syntax correctness

   module subtractor(input a, input b, output diff, output borrow); correctly declares inputs and outputs with proper keywords and commas.

3. Final Answer:

   module subtractor(input a, input b, output diff, output borrow); -> Option A

4. Quick Check:

   Correct input/output syntax = module subtractor(input a, input b, output diff, output borrow); [OK]

Hint: Always declare inputs and outputs explicitly with keywords [OK]

Common Mistakes:

• Omitting input/output keywords
• Listing inputs and outputs without keywords
• Declaring outputs as inputs

3.

What is the output difference and borrow when inputs a=1 and b=0 are applied to this 1-bit subtractor module?

assign diff = a ^ b ^ borrow_in;
assign borrow_out = (~a & b) | (borrow_in & (~a ^ b));

Assume borrow_in = 0.

medium

A. diff = 0, borrow_out = 0

B. diff = 0, borrow_out = 1

C. diff = 1, borrow_out = 1

D. diff = 1, borrow_out = 0

Solution

1. Step 1: Calculate diff with given inputs

   diff = a ^ b ^ borrow_in = 1 ^ 0 ^ 0 = 1

2. Step 2: Calculate borrow_out with given inputs

   borrow_out = (~a & b) | (borrow_in & (~a ^ b)) = (0 & 0) | (0 & (0 ^ 0)) = 0

3. Final Answer:

   diff = 1, borrow_out = 0 -> Option D

4. Quick Check:

   1 - 0 = 1, no borrow needed [OK]

Hint: XOR inputs and borrow_in for diff; borrow if a < b [OK]

Common Mistakes:

• Forgetting borrow_in in diff calculation
• Misapplying borrow logic
• Mixing up a and b in borrow expression

4.

Identify the error in this Verilog code for a 1-bit subtractor:

module subtractor(input a, input b, output diff, output borrow);
  assign diff = a - b;
  assign borrow = (b > a);
endmodule

medium

A. Using '-' operator for bitwise subtraction is incorrect in Verilog

B. 'borrow' should be declared as 'output reg' instead of 'output'

C. The module lacks a clock input for synchronous operation

D. The borrow calculation logic is incorrect

Solution

1. Step 1: Check arithmetic operator usage

   Verilog '-' operator performs arithmetic subtraction but does not produce borrow output directly.

2. Step 2: Understand borrow signal generation

   Borrow must be calculated using logic expressions, not by comparing b and a with '>' operator.

3. Final Answer:

   Using '-' operator for bitwise subtraction is incorrect in Verilog -> Option A

4. Quick Check:

   Subtractor needs logic for borrow, not '-' operator [OK]

Hint: Use logic expressions for borrow, not '-' operator [OK]

Common Mistakes:

• Using arithmetic '-' expecting borrow output
• Ignoring borrow logic
• Assuming '>' operator works for borrow

5.

Design a 2-bit subtractor using two 1-bit subtractor modules connected in series. Which of the following correctly describes the borrow connection?

hard

A. The borrow input of the least significant bit subtractor connects to the borrow output of the most significant bit subtractor

B. The borrow output of the least significant bit subtractor connects to the borrow input of the most significant bit subtractor

C. The borrow outputs of both subtractors are connected together to form a single borrow output

D. The borrow inputs of both subtractors are tied to 0

Solution

1. Step 1: Understand borrow chaining in multi-bit subtractors

   Borrow from the lower bit subtractor must feed into the higher bit subtractor's borrow input.

2. Step 2: Verify connection direction

   The least significant bit's borrow output connects to the most significant bit's borrow input to propagate borrow correctly.

3. Final Answer:

   The borrow output of the least significant bit subtractor connects to the borrow input of the most significant bit subtractor -> Option B

4. Quick Check:

   Borrow chains from LSB to MSB [OK]

Hint: Borrow flows from lower to higher bits in subtractors [OK]

Common Mistakes:

• Connecting borrow inputs to zero for all bits
• Connecting borrow outputs together incorrectly
• Reversing borrow input/output connections