# x-y on page 37

9 messages
Open this post in threaded view
|

## x-y on page 37

 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
Open this post in threaded view
|

## Re: x-y on page 37

 Administrator 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
Open this post in threaded view
|

## Re: x-y on page 37

 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]
Open this post in threaded view
|

## Re: x-y on page 37

 Administrator 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
Open this post in threaded view
|

## Re: x-y on page 37

 Ah! I understand now. Thanks very much :D
Open this post in threaded view
|

## Re: x-y on page 37

 In reply to this post by cadet1620 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.
Open this post in threaded view
|

## Re: x-y on page 37

 Administrator 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.