signed and unsigned arithmetic in VHDL - Time & Space Complexity

Time Complexity: signed and unsigned arithmetic

O(n)

Understanding Time Complexity

We want to understand how the time it takes to do signed and unsigned arithmetic changes as the size of the numbers grows.

How does the number of bits affect the work needed for addition or subtraction?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity ArithmeticExample is
  port(
    a, b : in unsigned(7 downto 0);
    sum : out unsigned(7 downto 0)
  );
end ArithmeticExample;

architecture Behavioral of ArithmeticExample is
begin
  sum <= a + b;
end Behavioral;

This code adds two 8-bit unsigned numbers and outputs the result.

Identify Repeating Operations

In hardware, addition works bit by bit, starting from the least significant bit.

• Primary operation: Adding each bit with carry.
• How many times: Once per bit, so 8 times for 8 bits.

How Execution Grows With Input

As the number of bits increases, the number of bit additions grows linearly.

Input Size (bits)	Approx. Operations
8	8 bit additions
16	16 bit additions
32	32 bit additions

Pattern observation: Doubling the bits doubles the number of bit operations.

Final Time Complexity

Time Complexity: O(n)

This means the time to add numbers grows in a straight line with the number of bits.

Common Mistake

[X] Wrong: "Adding signed numbers takes twice as long as unsigned numbers."

[OK] Correct: Both signed and unsigned addition use the same bit-by-bit process, so their time grows the same way with bit size.

Interview Connect

Knowing how arithmetic operations scale helps you understand hardware design and performance, a useful skill in many tech roles.

Self-Check

"What if we changed addition to multiplication? How would the time complexity change?"

Practice

1. Which VHDL type should you use to correctly represent negative numbers in arithmetic operations?

easy

A. unsigned

B. signed

C. std_logic_vector

D. bit_vector

Solution

1. Step 1: Understand number representation types

   Signed types allow representation of both positive and negative numbers, unlike unsigned which only represent zero and positive numbers.

2. Step 2: Identify correct VHDL type for negatives

   In VHDL, the signed type from numeric_std is used for signed arithmetic, supporting negative values.

3. Final Answer:

   signed -> Option B

4. Quick Check:

   Negative numbers need signed type [OK]

Hint: Use signed type for negatives, unsigned for positives only [OK]

Common Mistakes:

• Using unsigned for negative numbers
• Using std_logic_vector without conversion
• Confusing bit_vector with numeric types

2. Which of the following is the correct way to declare a 4-bit unsigned signal in VHDL using numeric_std?

easy

A. signal data : signed(3 downto 0);

B. signal data : bit_vector(3 downto 0);

C. signal data : std_logic_vector(4 downto 0);

D. signal data : unsigned(3 downto 0);

Solution

1. Step 1: Identify the correct type for unsigned 4-bit signal

   The unsigned type from numeric_std is used for unsigned arithmetic and must have 4 bits indexed from 3 downto 0.

2. Step 2: Check each option

   signal data : signed(3 downto 0); uses signed type, which is for signed numbers. signal data : std_logic_vector(4 downto 0); has 5 bits (4 downto 0). signal data : bit_vector(3 downto 0); uses bit_vector, which is not numeric.

3. Final Answer:

   signal data : unsigned(3 downto 0); -> Option D

4. Quick Check:

   Unsigned 4-bit signal uses unsigned(3 downto 0) [OK]

Hint: Unsigned signals use unsigned type with correct bit range [OK]

Common Mistakes:

• Using signed instead of unsigned
• Incorrect bit range (off by one)
• Using std_logic_vector without conversion

3. Given the following VHDL code snippet, what is the decimal value of result after execution?

signal a : signed(3 downto 0) := "1101"; -- -3 in decimal
signal b : unsigned(3 downto 0) := "0011"; -- 3 in decimal
signal result : signed(4 downto 0);

result <= a + signed(resize(b, 5));

medium

A. 0

B. -6

C. 6

D. -3

Solution

1. Step 1: Convert signals to decimal

   a is signed "1101" which is -3 in decimal. b is unsigned "0011" which is 3 in decimal.

2. Step 2: Resize and add values

   b is resized to 5 bits and converted to signed, so 3 remains 3. Adding -3 + 3 = 0.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   -3 + 3 = 0 [OK]

Hint: Convert both to signed before adding, then add values [OK]

Common Mistakes:

• Adding signed and unsigned directly without conversion
• Misinterpreting binary signed values
• Ignoring resize causing wrong bit width

4. Identify the error in the following VHDL code snippet:

signal x : signed(3 downto 0) := "0110";
signal y : unsigned(3 downto 0) := "0011";
signal z : signed(3 downto 0);
z <= x + y;

medium

A. Cannot add signed and unsigned directly without conversion

B. Signal z is declared with wrong bit range

C. Initialization of x is invalid binary

D. No error, code is correct

Solution

1. Step 1: Check types in addition

   In VHDL, you cannot add a signed and an unsigned type directly without converting one to the other's type.

2. Step 2: Identify missing conversion

   The code adds signed x and unsigned y directly, which causes a type mismatch error.

3. Final Answer:

   Cannot add signed and unsigned directly without conversion -> Option A

4. Quick Check:

   Signed + unsigned needs conversion [OK]

Hint: Convert unsigned to signed before adding to signed [OK]

Common Mistakes:

• Adding signed and unsigned without conversion
• Assuming std_logic_vector works for arithmetic
• Ignoring type mismatch errors

5. You want to subtract an unsigned 4-bit number b from a signed 5-bit number a in VHDL. Which is the correct way to perform this operation and store the result in a signed 6-bit signal result?

hard

A. result <= signed(a) - unsigned(b);

B. result <= a - b;

C. result <= resize(a, 6) - signed(resize(b, 6));

D. result <= resize(a, 5) - resize(b, 5);

Solution

1. Step 1: Understand type and size requirements

   To subtract unsigned b from signed a, both must be the same type and size. The result signal is 6 bits signed.

2. Step 2: Convert and resize operands properly

   Resize a to 6 bits signed, convert and resize b to signed 6 bits, then subtract.

3. Final Answer:

   result <= resize(a, 6) - signed(resize(b, 6)); -> Option C

4. Quick Check:

   Resize and convert unsigned to signed before subtracting [OK]

Hint: Resize both and convert unsigned to signed before subtracting [OK]

Common Mistakes:

• Subtracting without resizing operands
• Not converting unsigned to signed before subtraction
• Assigning result to smaller bit width