2
\$\begingroup\$

I have what I think to be a working implentation for finding the sum of two signed 32 bit (std_logic_vector) vectors in which I chose to expand the result to always have 33 bits so as to preserve the sign bit while being able to check for carry out with the expanded bit.

My method seems incredibly dirty and I was wondering if there was a cleaner way of accomplishing my goal, for future reference.

sum <= std_logic_vector(resize(signed(std_logic_vector(signed(a_alu32) + signed(b_alu32))), 33));
c_alu32 <= sum(31);
--overflow--
if ((a_alu32(31)='0' and b_alu32(31)='0' and sum(31)='1') or (a_alu32(31)='1' and b_alu32(31)='1' and sum(31)='0')) then 
  ov_alu32<='1'; --logic to check for overflow
else
  ov_alu32<='0';
end if;

--removing the extra bit through concatenation to achieve my 32 bit sum
o_alu32 <= sum(32) & sum(30 downto 0);
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Your implementation is not correct:

  • You must perform the sign extension before the addition of a and b.
  • A signed addition has no carry Flag, only overflow (it can be calculated but it's not valid); unsigned addition produces a carry flag but has no valid overflow.
  • The sign-bit is -- per definition -- always store in the highest bit

This could be a more or less nice rewriting, which is more generic. It only depends on a, b and c's length. So you could reuse this code for 16 or 64 bit, or whatever.

-- create locale signals with suffix '_s' for signed
-- both signals have one more bit than the original
signal a_alu32_s   : SIGNED(a_alu32'length downto 0);
signal b_alu32_s   : SIGNED(b_alu32'length downto 0);
signal sum_alu32_s : SIGNED(a_alu32'length downto 0);
signal temp        : std_logic_vector(2 downto 0);

-- convert type and perform a sign-extension
a_alu32_s <= resize(signed(a_alu32), a_alu32_s'length);
b_alu32_s <= resize(signed(b_alu32), b_alu32_s'length);

-- addition of two 33 bit values
sum_alu32_s <= a_alu32_s + b_alu32_s;

-- resize to require size and type conversion
o_alu32 <= std_logic_vector(resize(sum_alu32_s, o_alu32'length));

-- flag calculations
--c_alu32  <= sum_32_s(sum_alu32_s'high);

-- concat the three relevant sign-bits from a,b and sum to one vector
temp     <= a_alu32_s(a_alu32_s'high) & b_alu32_s(b_alu32_s'high) & sum_alu32_s(sum_alu32_s'high);
ov_alu32 <= (temp = "001") or (temp = "110");
\$\endgroup\$
4
  • \$\begingroup\$ The lightbulb went on for everything up until the method you used to find the overflow. I'm curious as to how you simplified down my process into yours, as it seems like a valuable skill to have, (does it involve KMAPS)? Thanks for the help. \$\endgroup\$ Commented Dec 12, 2014 at 20:54
  • \$\begingroup\$ Look at the assignment to "temp". Then the test becomes clear : two positive numbers sum to a negative (or vice-versa)... \$\endgroup\$
    – user16324
    Commented Dec 12, 2014 at 21:55
  • \$\begingroup\$ What is KMAPS? Google doesn't know it. -- the calculation for ov is the same as yours, but I didn't use a if-then-else statement. I converted your a_alu32(31)='0' and b_alu32(31)='0' ... to not a_alu32(31) and not b_alu32(31) .... Then I thought it's a very long line and the bit access to a_alu32 and Co is needed twice. So I collected all needed bits into temp. Now it's possible to do a simple case testing for 001 and 110. This means 'pos+pos=neg -> error' or 'neg+neg=pos -> error'. The original overflow detection would be calculated by ov := \$C_n\$ xor \$C_{n-1}\$. \$\endgroup\$
    – Paebbels
    Commented Dec 13, 2014 at 8:40
  • \$\begingroup\$ Sorry, I finally found K-maps. In Germany this is known as 'Karnaugh-Veitch-Diagram' or KV-diagram :) \$\endgroup\$
    – Paebbels
    Commented Dec 13, 2014 at 8:49
2
\$\begingroup\$

This answer considers Paebbels answer first then gives another (correct) approach.

The OP has two 32 bits numbers which he wants to add. Asking for a 33 bits number to have to ability to detect an overflow. Since 1 bit is used to signal the "has overflowed - yes/no question", the result is again a 32 bits number. In other words: 32 bits number + 1 bit overflow flag = 33 bits. Which is conceptually different than a 33 bits number (which would be a strange design). Also note that sum(32) & sum(30 downto 0) are 32 bits (the end result).

Now considering Paebbels' answer: Suppose a_alu32 and b_alu32 are a 2 bits signed, one bit for the quantity (absolute number), 1 bit for the sign. Then resize them to 3 bits (1 sign bit, 2 quantity bits) for a_alu32_s and b_alu32_s. Example:

  • input numbers: 01 and 01 (both 1 in decimal)
  • extent to 3 bits: 001 and 001
  • sum: 001 + 001 = 010
  • take highest bits of a, b and sum: 000
  • is 000 equal to 001 or 110? no .. thus has not overflowed (according to the logic of Paebbels)
  • However what does Paebbels do to get the final result back to 32 bits (and in this example thus 2 bits)? o_alu32 <= std_logic_vector(resize(sum_alu32_s, o_alu32'length));. How does 010 get resized back to two bits? Take sign bit 0, take the remainder 10, cut off msb of the remainder 10 -> 0, glue sign bit + remainder-with-1-bit-less -> 00. 00 is 0 in signed. So 1 + 1 = 0 and no overflow occured. Strange .. strange.

The solution this answer proposes is to look at the 2 highest bits of the sum. Making it a 2-way AND instead of a 3-way AND (saving logic as well). When the highest bit of the quantity part has been "activated" then an overflow has occured (that is the absolute number has increased one extra bit). "active" can be 0 or 1 depending on the sign bit. Example: 010 is a positive number with in the quantity part the highest bit is "active" (1), 101 is a negative number with the highest quantity-bit "active" (0) (101 (-3) is smaller than 110 (-2) and smaller than 111 (-1) in two-complements).

Here is a table where:

  • in1 and in2 are the input numbers
  • resized1 and resized2 and the temporary resized versions
  • sum is the sum of the resized versions
  • ov1 is whether an overflow has occured with the Paebbels method
  • ov2 is whether an overflow has occured by looking at the two msb bits of the sum (sign bit + msn of quantity-part) which should be either 01 or 10

table:

╔═════╦═════╦══════════╦══════════╦════════════╦═════╦═════╗
║ in1 ║ in2 ║ resized1 ║ resized2 ║    sum     ║ ov1 ║ ov2 ║
╠═════╬═════╬══════════╬══════════╬════════════╬═════╬═════╣
║  00 ║  00 ║      000 ║      000 ║ 000        ║ no  ║ no  ║
║  00 ║  01 ║      000 ║      001 ║ 001        ║ no  ║ no  ║
║  00 ║  10 ║      000 ║      110 ║ 110        ║ no  ║ no  ║
║  00 ║  11 ║      000 ║      111 ║ 111        ║ no  ║ no  ║
║  01 ║  00 ║      001 ║      000 ║ 001        ║ no  ║ no  ║
║  01 ║  01 ║      001 ║      001 ║ 010        ║ no  ║ yes ║
║  01 ║  10 ║      001 ║      110 ║ 111        ║ no  ║ no  ║
║  01 ║  11 ║      001 ║      111 ║ 110        ║ no  ║ no  ║
║  10 ║  00 ║      110 ║      000 ║ 110        ║ no  ║ no  ║
║  10 ║  01 ║      110 ║      001 ║ 111        ║ no  ║ no  ║
║  10 ║  10 ║      110 ║      110 ║ 1100 (100) ║ no  ║ yes ║
║  10 ║  11 ║      110 ║      111 ║ 1101 (101) ║ no  ║ yes ║
║  11 ║  00 ║      111 ║      000 ║ 111        ║ no  ║ no  ║
║  11 ║  01 ║      111 ║      001 ║ 1000 (000) ║ no  ║ no  ║
║  11 ║  10 ║      111 ║      110 ║ 1101 (101) ║ no  ║ yes ║
║  11 ║  11 ║      111 ║      111 ║ 1110 (110) ║ no  ║ yes ║
╚═════╩═════╩══════════╩══════════╩════════════╩═════╩═════╝

Note that sum can itself overflow, but this is okay because we only care about the overflow of the original two numbers we would like to add. This code causes the sum overflow sum_alu32_s <= a_alu32_s + b_alu32_s;. In this example adding 2 3-bits numbers yield another 3 bits number and the msb is lost, you can see this effect in the sum-column.

Conclusion: perhaps it's me and i didn't understand Paebbels' solution. But when running the numbers i get a result where Paebbels' method doesn't detect an overflow at all!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.