Truncated match.
PICList
Thread
'Complements (no not thanks) PART II'
1997\01\21@063137
by
fastfwd

This is the second part of my "Everything you always wanted to
know, expressed in painstaking detail, about two'scomplement
binary math". As before, scroll down to the bottom of this
message and make sure you can read the line:
"If you can read this, you got the whole message".
REVIEW:

By walking through the tedious steps required to build an 8bit
adder, we've seen what a thankless job microprocessor ALU designers
have: They need to build circuits to perform relativelycomplex
mathematical functions, they're given only the most rudimentary
building blocks (twoinput logic gates) to work with, and their
employers insist that every circuit be constructed using the
absolute minimum number of those gates.
What we HAVEN'T done yet is explain what "1'scomplement" and
"2'scomplement" mean, and what they're good for.
Here goes.
SUBTRACTION: ADDITION'S EVIL TWIN

We've already built an 8bit adder; it takes two 8bit numbers and a
carryin bit, adds them all together, and produces an 8bit result
plus a carryout.
Unfortunately, this won't fully satisfy our customers; the ungrateful
buggers want SUBTRACTION, too.
Our first thought is that we'll just build a separate binary
"subtractor". After all, addition didn't require too many gates;
maybe subtraction won't take many, either.
If we build that subtractor, however, we introduce a new problem:
Subtracting a large number from a smaller one gives a NEGATIVE
result. So far, we've been treating 8bit numbers as positive
values in the range [0255]; building a subtractor will require us to
decide on some way to represent negative numbers, as well.
A moment's thought shows how we can turn this requirement to our
advantage: If we can come up with a way to represent negative
numbers, we can perform subtraction by simply negating the subtrahend
and ADDING it to the minuend. That is:
"A  B" is equal to "A + (B)".
This is an Exceedingly Good Thing; it means that we can use our
existing 8bitadder circuit to perform both addition AND
subtraction.
All we have to do is find a way to represent negative numbers...
SIGN/MAGNITUDE

Obviously, we won't be able to represent the full range of integers
from 255 to 255 in only 8 bits; 8 bits is sufficient for only 256
discrete values.
We can live with this, though... So we'll first try using only the
low (rightmost) 7 bits of each number to represent the magnitude, and the
leftmost bit of each number (the "Most Significant Bit", or "MSB") to
represent the number's sign (0 = positive, 1 = negative).
This means that an 8bit number will be able to represent values in
the range [127  +127]:
Decimal: Sign/Magnitude:
 
1 = 00000001
1 = 10000001
2 = 00000010
2 = 10000010
127 = 01111111
127 = 11111111
0 = 00000000
0 = 10000000
Uhoh. "Negative zero"? What's THAT?
Let's gloss over it for now and see whether our math works:
Decimal: Sign/Magnitude:
 
3  1 = 3 + (1) 00000011
= 2 +10000001

10000100 (4) NOT CORRECT!
1  3 = 1 + (3) 00000001
= 2 +10000011
_________
10000100 (4) NOT CORRECT!
3  1 = 3 + (1) 10000011
= 4 +10000001

Cout + 00000100 (4) NOT CORRECT! (but sorta close)
3  (1) = 3 + 1 10000011
= 2 +00000001

10000100 (4) NOT CORRECT!
That's enough... I think we can give up on the "sign/magnitude"
representation now.
ONE'S COMPLEMENT

Ok... Let's try something else. Rather than simply setting the MSB
to 1 to represent negative numbers, let's try inverting the entire
byte. This is the "one's complement" representation of signed binary
values.
Like the "sign/magnitude" representation, "one'scomplement" will
allow an 8bit number to represent values in the range [127  +127}.
It looks like this:
Decimal: 1's complement:
 
1 = 00000001
1 = 11111110
2 = 00000010
2 = 11111101
127 = 01111111
127 = 10000000
0 = 00000000
0 = 11111111
We still have the same 0/0 problem, but again, we can gloss over it
temporarily. Let's try some math:
Decimal: One's complement:
 
3  1 = 3 + (1) 00000011
= 2 +11111110

Cout + 00000001 (1) NOT CORRECT!
1  3 = 1 + (3) 00000001
= 2 +11111100
_________
11111101 (2) CORRECT!
3  1 = 3 + (1) 11111100
= 4 +11111110

Cout + 11111010 (5) NOT CORRECT!
3  (1) = 3 + 1 11111100
= 2 +00000001

11111101 (2) CORRECT!
This is more promising than the "sign/magnitude" representation we
first tried... If you look closely, you'll see that the results that
DON'T set the Cout bit are correct, while the results that DO set the
Cout bit are only off by one.
Maybe we can add a little circuitry to add the Cout bit to the sum?
Let's try some more examples before we do that.
Decimal: One's complement:
 
3  3 = 3 + (3) 00000011
= 0 +11111100

11111111 (0) CORRECT! (more or less)
3  2 = 3 + (2) 11111100
= 5 +11111101
_________
Cout + 00000001 (1) NOT CORRECT! (and not just "off
by one", either)
These last two examples indicate that using the one'scomplement
representation is likely to cause problems. While we may get the
correct results for MANY of the possible combinations of inputs, we
won't get the correct results for ALL of them.
Correcting the results that don't work will require a fair amount of
circuitry; it's obvious now that we can't correct the result by
simply adding the carryout bit to it. Besides, that "negativezero"
thing is sort of annoying, anyway.
So... Now what?
Well, for starters, let's get rid of the "negative zero".
To accomplish this, we'll use something called the "two's
complement".
TWO'S COMPLEMENT

To generate the 2'scomplement of a number, you first find the
1'scomplement (by inverting the entire byte), then add 1.
Zero is still represented by "00000000", but something interesting
happens when you calculate its two's complement: Inverting the byte
gives "11111111", and adding 1 to that gives "00000000" again.
Voila! No "negative zero"!
Now, since an 8bit number can represent 256 unique values and
"zero" takes only one of those values, this means that we can
represent numbers in the range [128  +127] in our two'scomplement
number system:
Decimal: 2's complement:
 
1 = 00000001
1 = 11111111
2 = 00000010
2 = 11111110
127 = 01111111
127 = 10000001
0 = 00000000
0 = 00000000 (the same as 0)
128 = 10000000
Just for kicks, let's try some math:
Decimal: Two's complement:
 
3  1 = 3 + (1) 00000011
= 2 +11111111

Cout + 00000010 (2) CORRECT!
1  3 = 1 + (3) 00000001
= 2 +11111101
_________
11111110 (2) CORRECT!
3  1 = 3 + (1) 11111101
= 4 +11111111

Cout + 11111100 (4) CORRECT!
3  (1) = 3 + 1 11111101
= 2 +00000001

11111110 (2) CORRECT!
3  3 = 3 + (3) 00000011
= 0 +11111101

Cout + 00000000 (0) CORRECT!
3  2 = 3 + (2) 11111101
= 5 +11111110
_________
Cout + 11111011 (5) CORRECT!
Wow.
It looks as though the two's complement representation is the way to
go... There's only one representation for "zero", all the positive
numbers look the way they used to, the math seems to work (if we
ignore the carryout), and we even get an extra negative number
(128) to play with.
Unfortunately, this is all for naught if we can't build the
appropriate circuitry with only a small number of gates.
Let's see what it takes.
BULDING A CHEAP TWO'SCOMPLEMENTOR

Remember that the two's complement is obtained by inverting the
original number and adding 1 to it.
The inversion part is easy; a NOT gate for each of the eight bits
accomplishes it.
Adding 1, however, is more difficult. As we saw earlier, addition
requires 40 gates... We don't want to practically double our
gatecount just to do this one simple operation.
So what can we do?
Well, let's see... We're trying to calculate A  B, and this is
equivalent to A + (B). In our two'scomplement notation, B is
equal to (NOT B) + 1, so we need to calculate A + ((NOT B) + 1).
Since addition is associative, this is the same as (A + (NOT B)) + 1.
Hmm... What if we use our existing "A + B + Cin" 40gate adder, but
we explicitly set the Cin bit to 1 and run the B input through an
inverter? We'll end up calculating A + (NOT B) + 1, exactly what we
want!
So...
By adding only eight NOT gates and requiring the user to set the
carryin before performing a subtraction (a la the 6502 and other
microprocessors) or just setting the carryin internally (a la the
PIC), we've made our adder do doubleduty as a subtractor.
Ok... At this point, I KNOW you're thinking, "So we saved a few
gates... Big deal," but for an ALU designer, saving 30odd gates is
cause for a major celebration.
Sad but true.
Anyway...
MULTIBYTE ARITHMETIC

Ok, so let's say that the guy who buys our microprocessor will want
to add numbers larger than 8 bits. Specifically, let's say that he
wants to add two 16bit numbers. How does that work?
It's easy... He clears the carryin, adds the two loworder
(rightmost, or "leastsignificant") bytes, then adds the two
highorder (leftmost, or "mostsignificant") bytes; any carryout
that's generated by the first addition will become the second
addition's carryin.
For example:
Decimal: Binary:
 
1000 + 1000 = 2000 00000011 11101000 (1000)
+00000011 11101000 (1000)

1 11010000 (adding the two low
bytes gives 11010000,
plus a "1" Cout)
00000111 (The lowbyte's Cout is
used as the highbyte's
Cin; adding it to the
two high bytes gives
00000111, with no Cout)

00000111 11010000 (2000) CORRECT!
What about multibyte SUBTRACTION? Will the two'scomplement
representation still work there? What about that "set the Cin to 1"
trick? Will it affect the results?
Let's try it and see...
Decimal: Binary:
 
2000  1000 00000111 11010000 (2000)
= 2000 + (1000) +11111100 00010111 (NOT 1000)
= 2000+(NOT 1000)+1 + 00000001 (Cin = 1)
= 1000 
0 11101000 (adding the two low
bytes, plus the "1"
Cin, gives 11101000,
with a "0" Cout)
1 00000111 (The lowbyte's Cout (0)
is used as the high
byte's Cin; adding it to
the two high bytes gives
00000011, with Cout = 1)

Cout + 00000011 11101000 (1000) CORRECT!
It works.
Note that we always ignore the final carryout when we're performing
two'scomplement math.
OVERFLOW, UNDERFLOW, AND OTHER ESOTERICA

Ok... Two's complement DOES have some problems. I've avoided them
here so far, but you can get an idea by adding 64 to 65:
Decimal: Two's complement:
 
64 + 65 = 129 01000000 (64)
+01000001 (65)
_________
10000001 (127) NOT CORRECT!
A similar thing happens when you subtract, say, 65 from 64:
Decimal: Two's complement:
 
64  65 = 64 + (65) 11000000 (64)
= 129 +10111111 (65)
_________
Cout + 01111111 (127) NOT CORRECT!
Damn... And just when things were going so well, too.
In both cases, the correct result is too large to fit in 8 bits, so
our 8bit result appears incorrect.
Fortunately, most microprocessors include an "overflow" bit that can
alert you to this situation.
Unfortunately, no PICs except the 17Cxx series include that
"overflow" bit.
Oh, well... If you're ever lucky enough to use a micro that contains
an "Overflow" flag, you should know that it signals one of the
following two conditions, each of which indicates that the result is
too large to fit in eight bits:
Overflow Condition #1:
There was an internal carry generated between bit 6 (second from
the left) and bit 7 (leftmost) of the result, but NO carry was
generated out of bit 7 of the result.
Overflow Condition #2:
There was NO internal carry generated between bit 6 and bit 7 of
the result, but there WAS a carry generated out of bit 7.
If neither of these conditions is true, the overfow flag is not set
and the carryout of the result may be safely ignored. If one or the
other is true, your software needs to recognize the overflow (or
"underflow" if the toolarge result is a negative number), and
compensate somehow.
Note, by the way, that the overflow flag is simply an XOR of bit 6's
Cout and bit 7's Cout... That's the extra gate that I mentioned in my
last message  the one that turns our 40gate adder into a 41gate
adder.
Ok... I'm tired now. Hope this helped, Tim.
Andy
If you can read this, you got the whole message.
=== Andrew Warren  spam_OUTfastfwdTakeThisOuTix.netcom.com ===
=== Fast Forward Engineering  Vista, California ===
=== ===
=== Did the information in this post help you? Consider ===
=== contributing to the PICLIST Fund. Details are at: ===
=== http://www.geocities.com/SiliconValley/2499/fund.html ===
1997\01\21@132156
by
Tim Kerby
I'm certainly not going to reply to the message and quote the original!
Thanks very much for this and for helping in the past too. The information
is really useful. The pseudo random system you sent me earlier is also
working with only one modification  as the device will be reset quite often
the timer value is used as a seed which is called checking the POR bit
(resets in the product are POR) so seeding only happens once. This gives
great results.
Thanks again
Tim
My web pages are at http://web.ukonline.co.uk/members/tim.kerby/
My PIC site is at web.ukonline.co.uk/members/tim.kerby/pic/
It needs your projects!
1997\01\21@132410
by
Jonathan King
To all,
Once Andrew's emails have been digested, try these articles in
EDN magazine:
"A minus B = A + not(B) + 1 (Part 1)" EDN Dec 5 1996, p199204
"A minus B = A + not(B) + 1 (Part 2)" EDN Jan 2 1997, p119128

Jonathan King  .....kingKILLspam@spam@uicc.com
Unitrode Corp.  http://www.unitrode.com
7 Continental Blvd  (603) 4298715
Merrimack, NH 03054  (603) 4243460
1997\01\21@143901
by
fastfwd

Tim Kerby <PICLISTKILLspamMITVMA.MIT.EDU> wrote:
> I'm certainly not going to reply to the message and quote the
> original! Thanks very much for this and for helping in the past too.
No problem, Tim... I live to serve.
By the way, I forgot to mention that the PIC16's Carry flag is
actually a combination of the Cout bit and an internal "overflow"
bit... This means that, after an addition or subtraction, you
can use the state of the Carry flag as an under/overflow
indicator.
Also, the PIC16 has no "Add with Carry" or "Subtract with Borrow"
instructions, so setting the Carry flag before a PIC16 addition
or subtraction has no effect; the Carry flag is NOT used as the
first adder stage's "Cin". This means that if you're doing
multibyte arithmetic, you have to manually adjust (in your
software) the higherorder bytes based on the Carry state after
the lowerorder additions or subtractions.
I have to go to a meeting now, so I can't explain further; if
anyone needs assistance with this concept, let me know and I'll
try to post an explanation later.
Andy
=== Andrew Warren  .....fastfwdKILLspam.....ix.netcom.com ===
=== Fast Forward Engineering  Vista, California ===
=== ===
=== Did the information in this post help you? Consider ===
=== contributing to the PICLIST Fund. Details are at: ===
=== http://www.geocities.com/SiliconValley/2499/fund.html ===
1997\01\22@062904
by
fastfwd

Earlier today, I wrote:
> the PIC16's Carry flag is actually a combination of the Cout bit
> and an internal "overflow" bit... This means that, after an
> addition or subtraction, you can use the state of the Carry flag as
> an under/overflow indicator.
Please forget that I said that... It's not accurate. Everything
else in that message is fine, though.
Also, Jonathan King suggested reading the following two articles:
> "A minus B = A + not(B) + 1 (Part 1)" EDN Dec 5 1996, p199204
> "A minus B = A + not(B) + 1 (Part 2)" EDN Jan 2 1997, p119128
I took Honathan's advice and read those articles today... They're
pretty good. The author doesn't explain two'scomplement math in
much detail, but he does give an interesting overview of ALU
design.
Andy
=== Andrew Warren  EraseMEfastfwdspam_OUTTakeThisOuTix.netcom.com ===
=== Fast Forward Engineering  Vista, California ===
=== ===
=== Custodian of the PICLIST Fund  For more info, see: ===
=== http://www.geocities.com/SiliconValley/2499/fund.html ===
More... (looser matching)
 Last day of these posts
 In 1997
, 1998 only
 Today
 New search...