Calculating the Overflow Flag in an ALU

Question

First of all, forgive me if this isn't the right place to post this question, but I wasn't sure where it should go. I am currently working on simulating an ALU in Xilinx with VHDL. The ALU has the following inputs and outputs:

Inputs

• A and B: two 8-bit operands
• Ci: single-bit carry in
• Op: 4-bit opcode for the multiplexers

Outputs

• Y: 8-bit output operands
• Co: single-bit carry out
• V: overflow flag (1 if there is overflow, 0 otherwise)
• Z: zero flag (1 if zero, 0 otherwise)
• S: sign flag (1 if -ve, 0 if +ve)

The ALU performs the operations detailed in the table below:

I have implemented it using multiplexers and an adder, as illustrated in the diagram below:

My question is:

How do I calculate the value of the overflow flag, V?

I am aware that:

• If adding a positive to a negative, overflow will not occur
• If there is no carry/borrow, then the overflow can be calculated by evaluating the expression

(not A(7) and not B(7) and Y(7)) or (A(7) and B(7) and not Y(7))

where A(7), B(7) and Y(7) are the 8th bit of A, B and Y respectively.

• In the case of a carry/borrow, There is an overflow if and only if the carry-in and carry-out of the most significant bit are different.

I don't know how to implement this logically in VHDL code however - especially in the case of a carry.

Answer 1

The solution you have posted

v <= (not A(7) and not B(7) and Y(7)) or (A(7) and B(7) and not Y(7))

is correct for addition of signed operands and independent of the carry.

EDIT To use this also for your substraction, you have to use the actual adder inputs instead, i.e.:

v <= (not add_A(7) and not add_B(7) and Y(7)) or (add_A(7) and add_B(7) and not Y(7))

The above will work both for addition and substraction is independent of carry or borrow. (By the way, for the real implementation you should use add_Y instead of Y to shorten critical paths.)

If you want to implement it by XOR'ing the carry-in and carry-out of the most-signifcant sum bit, then you have to calculate a partial sum of the lowest 7 bit first. This gives you access to carry-out of bit 6 which is the carry-in of bit 7. Then just append a full-adder to get bit 7 and the carry-out. Here is the code:

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

entity adder_overflow is
  port (
    a  : in  unsigned(7 downto 0);
    b  : in  unsigned(7 downto 0);
    y  : out unsigned(7 downto 0);
    v  : out std_logic;
    co : out std_logic);
end;

architecture rtl of adder_overflow is
  signal psum   : unsigned(7 downto 0); -- partial sum
  signal c7_in  : std_logic;
  signal c7_out : std_logic;
begin

  -- add lowest 7 bits together
  psum <= ("0" & a(6 downto 0)) + b(6 downto 0);

  -- psum(7) is the carry-out of bit 6 and will be the carry-in of bit 7
  c7_in         <= psum(7);
  y(6 downto 0) <= psum(6 downto 0);

  -- add most-signifcant operand bits and carry-in from above together using a full-adder
  y(7)   <= a(7) xor b(7) xor c7_in;
  c7_out <= ((a(7) xor b(7)) and c7_in) or a(7);

  -- carry and overflow
  co <= c7_out;
  v  <= c7_in xor c7_out;
end rtl;

Answer 2

Your solution

(not A(7) and not B(7) and Y(7)) or (A(7) and B(7) and not Y(7))

and the text below it only apply to signed addition; it's not correct for subtraction. The two rules are:

1. Signed integer overflow of the expression x+y+c (where c is 0 or 1) occurs if and only if x and y have the same sign and the result has sign opposite to that of the operands (this is your equation), and
2. Signed integer overflow of the expression x-y-c (where c is again 0 or 1) occurs if and only if x and y have opposite signs, and the sign of the result is opposite to that of x (or, equivalently, the same as that of y).

Note that these are true whatever the value of the carry/borrow. You can see that the first rule doesn't apply for subtraction with a simple 4-bit example: 4 minus (-4), for example, must overflow because the answer should be +8, which isn't representable in 4 bits. In binary, this is 0100 - 1100 = 1000. This is an overflow acording to (2), but not (1).

The good news is that xor-ing the carry into the sign bit and the carry out of the sign bit always works - it's correct for addition and subtraction, and whether or not there's a carry- or a borrow-in, so you can use Martin's code.

You should get a copy of Henry Warren's Hacker's Delight if you're going to do much arithmetic. He covers all this, and much more.