x-y on page 37

[Joel]

Hi, I've been successful in understanding chapter 2 up until now - however, my problem lies in the ALU's table of functions on page 37... particularly with the subtractions. Previously it said that subtraction is performed like so:
x - y = x + (-y)

where -y = two's complement of y; involving inverting its bits and adding 1. But the ALU seems to use a completely different method - invert x's bits, add them to y, and invert the result...? Apologies if I'm missing something, but it doesn't appear to describe this anywhere else, leaving me wondering how they actually came up with this method and why it's used instead... help please? :P

[cadet1620]

It's not particularly obvious how the ALU computes its various functions.

ybakos created a great worksheet to help understand the ALU.

As you observe, the ALU operation for x - y has nx, f, and no set, so the actual computation is
    out = NOT( (NOT x) + y)

You can use the definition of two's complement:
    -n = (NOT n) + 1
to algebraically prove that the ALU's computation is equivalent to x - y.


It is quite elegant that such a simple structure as the TECS ALU can compute all the required functions.  A brute force design to do these functions would have resulted in a rather more complex design.

--Mark

[Joel]

Could you show me how it could be proved that way? I've tried but I don't seem to be getting anywhere :S

Here is what I've attempted:
x - y

x + (NOT y) + 1

x + (NOT y) - x - (NOT x) [if -n = (NOT n) + 1 then 1 = -n - (NOT n)]

(NOT y) - (NOT x)

NOT(y-x)

NOT((NOT x) + 1 + y) [Almost there! But there's a 1 messing it up]

[cadet1620]

It's easier to work the other direction.

Solve the two's complement equation for !n

           -n = !n + 1
           !n = -n - 1

Substitute into the ALU computation with n = x

    !(!x + y) = !((-x - 1) + y)
              = !(-x - 1 + y)

Here's the tricky bit: substitute again with n = (-x - 1 + y)

           !n = -n - 1
!(-x - 1 + y) = -(-x - 1 + y) - 1
              = x + 1 - y - 1
              = x - y
    !(!x + y) = x - y

Q.E.D.

Here's where you went wrong:

(NOT y) - (NOT x)
NOT(y-x)

This is not an equivalence; try !1 - !2 vs. !(1-2).

--Mark

[Joel]

Ah! I understand now. Thanks very much :D

[merit]

It's easy to get " !(!x+y) = x-y " from leftvalue to rightvalue, but it's hard from right to left.

Just like the first designer who doesn't know how to compute "x-y", how could he get the answer
"!(!x+y)" ?

We should not deduce the origin "x-y" from the answer "!(!x+y)" that is a mystery, if no one told us.

[WBahn]

That you can get x-y using the adder (without a Carry-In) and bitwise inversions is not intuitively obvious, but you CAN get there from the goal and what capabilities you have.

If we have proven that, in two's complement, the relationship between the additive inverse of n and the bitwise inverse is

-n = ~n + 1

then we can solve for ~n to get

~n = -(n+1)

With this relation, we can proceed as follows:

Z = x - y
Z = x - y + 1 - 1  // We know we need some +1 in there to use our relation
Z = -(y - x - 1 + 1) // We know we need a minus out front to use our relation
Z = -((y - x - 1) + 1) // This is the form of our relation with n = (y-x-1)
Z = ~(y - x - 1) // Applying our relation
Z = ~(-(x + 1) + y) // Getting part of the interior into the form of our relation
Z = ~(~x + y) // Applying our relation

Q.E.D.

[merit]

Thanks, I know the reasoning.

[WBahn]

No problem.

In the interests of full disclosure, I didn't come up with that derivation the way I would love to be able to claim. I basically walked the proof that the logic circuit performs the subtraction backwards and then figured out a plausible motivation for making each forward step.

I seriously doubt I would have every come up with that design on my own, though I would not be surprised to discover that it's been around for decades.

It's extremely clever and I like elegance of it, but I imagine using the carry-in is the better way to go in a real design.

But understanding how the forward design could have been arrived at does tend to flesh out the set of thinking tools in your kit, and that's seldom a wasted of effort.