Home  www.playhookey.com  Mon, 11232020 

Direct Current

Alternating Current

Semiconductors

Digital

Logic Families

Digital Experiments

Computers

 Analog  Analog Experiments  Oscillators  Optics  HTML Test  

 Combinational Logic  Sequential Logic  Alternate FlipFlop Circuits  Counters  Registers  The 555 Timer   

Basic Gates

Derived Gates

The XOR Function

Boolean Algebra

Binary Addition

Negative Numbers and Binary Subtraction

 TwoInput Multiplexer  FourInput Multiplexer  OnetoTwo Line Decoder/Demultiplexer  TwotoFour Line Decoder/Demultiplexer  
Negative Numbers and Binary Subtraction 

We have seen how simple logic gates can perform the process of binary addition. It is only logical to assume that a similar circuit could perform binary subtraction.
If we look at the possibilites involved in subtracting one 1bit number from another, we can quickly see that three of the four possible combinations are easy and straightforward. The fourth one involves a bit more:
0  0 = 0 1  0 = 1 1  1 = 0 0  1 = 1, with a borrow bit.
That borrow bit is just like a borrow in decimal subtraction: it subtracts from the next higher order of magnitude in the overall number. Let's see what the truth table looks like.
INPUTS  OUTPUTS 
This is an interesting result. The difference, AB, is still an ExclusiveOR function, just as the sum was for addition. The borrow is still an AND function, but is A'B instead of AB. What we'd like to do, now, is find an easy way to use the binary adder to perform subtraction as well. We already have half of it working: the difference output. Can we simply invert the A input so the AND gate will have the right signals? No, we can't, because that would invert the sense of the ExclusiveOR function. What would be really nice is to convert B to the negative equivalent of its value, and then use the basic adder just as it stands. To see if we can do that, let's consider negative binary numbers below. 


A  B  BORROW  A  B  
0  0  0  0  
0  1  1  1  
1  0  0  1  
1  1  0  0 
As we can see if we look at binary counters, once a full count is obtained, the next clock pulse will cause the counter to read zero again. Likewise if we set up a counter to count backwards, the first clock pulse will cause the count to go from all zeroes to all ones. Thinking along these lines, we can see that the binary number 1111 might represent the decimal number 15, or it could represent the number 1. On the right is the counting sequence for a 4bit binary number, with decimal equivalents expressed in two ways. First we have the unsigned counting sequence, where all numbers are assumed to be positive. Then we see the signed sequence, which includes both positive and negative numbers. Looking at the two decimal counting sequences, we note two factors right away:
Because positive numbers are the same in both sequences, they can be used together without difficulty. We only need to keep track of how we want to define the system. And the fact that negative numbers all have the binary MSB = 1 is helpful because the MSB can immediately be used to identify the sign of the number. Indeed, the binary MSB is commonly known as the sign bit. The use of this bit to distinguish between positive and negative numbers also allows us to divide the counting sequence evenly between positive and negative numbers. Now we need to look at the relationship between the binary numbers for positive and negative versions of the same magnitude. Suppose we invert each bit of 0001 (+1) to get 1110 (2). If we then increment the result, we get 1111 (1), which is what we wanted. Will this relationship hold for all negative numbers? In fact, it does work, as you can determine for yourself. To form the negative of any number, first complement all bits of the number. The result is the one's complement of the original number. Then, add 1 to the result, thus forming the two's complement of the original number. Arithmetic involving such signed numbers is known generally as two's complement arithmetic. To check the validity of this process, let's take the two's complement of 0. We should logically get a result of 0. So, we start with 0000, and form the one's complement (1111). Now add 1 to the result (10000). But this won't fit in a 4bit number, so the extra 1bit is lost, leaving a result of (0000). Sure enough, 0 = 0, as it should. Remember to discard the carry from the highestorder bit. Two's complement arithmetic always works this way. Note: It is not possible to represent +8 as a 4bit signed number. Therefore it is not possible to correctly take the two's complement of 8. It will come back again as 8. 
Binary 
Unsigned Decimal 
Signed Decimal 

0000  0  0  
0001  1  1  
0010  2  2  
0011  3  3  
0100  4  4  
0101  5  5  
0110  6  6  
0111  7  7  
1000  8  8  
1001  9  7  
1010  10  6  
1011  11  5  
1100  12  4  
1101  13  3  
1110  14  2  
1111  15  1 
Now that we have an easy way to obtain the negative of any number, we can convert our original 4bit adder circuit to an adder/subtractor. By leaving the inputs unchanged, we get the result of A + B. But if we invert B and add 1 with the loworder C_{in}, we get the result of A  B.
We can use ExclusiveOR gates, as shown to the right, to control whether we will add or subtract on any given occasion. With a control input of 0, the XOR gates will leave the B input number unchanged, and will also apply a logic 0 as the initial input carry. This is exactly what we want in order to add the two numbers. However, if we apply a logic 1 to the control input, the XOR gates will invert the B input number to form its one's complement, and will also add 1 through the initial input carry. This changes B to its two's complement. Thus, the output result will actually be A  B. (Note that in two's complement addition, the output carry is ignored. You can also think of it as an inverted "borrow" bit rather than as a carry, so that a carry of 1 corresponds to a borrow of 0. That logic also holds for the input carry, which also represents an input borrow bit of 0.)
When we add or subtract signed numbers, we need to introduce a new concept: overflow. Overflow occurs when the result has the wrong sign bit for the operation that was performed. For example, if we add two positive numbers (7 and 6), we should get a positive result (13). However, using 4bit binary numbers, we would add 0111 to 0110 and get 1101 as the result. In signed notation, this is a result of 3, not +13. Therefore, an overflow has occurred, where the result would have to have more bits than the original two numbers.
This is not as much of a problem as you might think. An 8bit number can have signed values in the range 128 to +127. A 16bit signed number may hold any value from 32,768 to +32,767. These ranges are sufficient for most practical applications. Where they are not, modern computers can easily use 32bit numbers (±2.14 × 10^{9}) or 64bit numbers (±9.22 × 10^{18}) for the purpose.
If we add a positive number to a negative number, overflow cannot occur. Likewise, if we are subtracting two numbers of the same sign, overflow is impossible. But if we add likesigned numbers or subtract unlikesigned numbers, we must be aware of the possibility of overflow, and recognize when it occurs.
Modern microprocessors are designed to recognize and report when overflow occurs in any arithmetic operation.


 
All pages on www.playhookey.com copyright © 1996, 20002015 by
Ken Bigelow Please address queries and suggestions to: webmaster@playhookey.com 