D.Sc.(Tech.) J. Birgitta Martinkauppi, Janne
Koljonen
two’s complement
Digital Electronics
Electrical Engineering and Energy Technology
Faculty of Technology
Learning goals
computer
• How negative numbers are
coded?
• Substraction operation in a
computer
2
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement
• In earlier lecturers, we
studied different number
systems as well as gate
circuits. Now we combine
these two. – Let’s design using basic
gates a digital circuit which
numbers
3
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement
• Let’s add up the following binary numbers:
s = x + y = 10102 + 00102 = ?
• One possibility is to convert the number first to
decimal numbers, do the adding operation and
convert the result back to a binary :
– 10 + 2 = 12 = 11002
– This is not helpful in the design of a digital circuit.
However, it provides an independent way to verify
functioning of the digital circuit.
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 4
• Let’s add up the following binary numbers :
s = x + y = 10102 + 00102 = ?
• Another option is to do the addition directly with
binary numbers by paper and pencil calculations:
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 5
i 3 2 1 0
Number in
memory, ci
x 1 0 1 0
y 0 0 1 0
s
• The addition operation starts from the right
• First, we add up the two least significant bits (the
rightmost bits)
• s0 = x0 + y0 = 02 + 02 = 02
number in memory (Carry) is now c1 = 02
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 6
i 3 2 1 0
Carry, ci 0
x 1 0 1 0
y 0 0 1 0
s 0
• The addition operation continues to the next bits
(from right to left). After the first LSB, we add up now
three bits
• s1 = c1 + x1 + y1 = 02 + 12 + 12 = 102 = 210
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 7
i 3 2 1 0
Carry, ci
1 0
x 1 0 1 0
y 0 0 1 0
s 0 0
• Again we add up three bits
• s2 = c2 + x2 + y2 = 12 + 02 + 02 = 012 = 110
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 8
i 3 2 1 0
Carry, ci 0 1 0
x 1 0 1 0
y 0 0 1 0
s 1 0 0
• The last bits to add up are MSBs
• If c4 were 1, then an overflow would happen
– This results would require 5 bits instead of 4 bits available
• s3 = c3 + x3 + y3 = 02 + 12 + 02 = 012 = 110
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 9
i 3 2 1 0
Carry, ci 0 1 0
x 1 0 1 0
y 0 0 1 0
s 1 1 0 0
No overflow
• Result is …
• s = x + y = 11002 = 1210
– Both binary and decimal addition produce the same
results
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 10
i 3 2 1 0
Carry, ci 0 1 0
x 1 0 1 0
y 0 0 1 0
s 1 1 0 0
numbers
• Let’s add up now the following binary numbers :
s = x + y = 11102 + 01112 = ?
• s = x + y = 11102 + 01112 = 01012 = 510???
– 14 + 7 = 21 = 5???
– Overflow
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 11
i 4 3 2 1 0
Carry, ci
1 1 1 0
x 1 1 1 0
y 0 1 1 1
s 0 1 0 1
• s = x + y = 11102 + 01112 = 01012 = 510???
– 14 + 7 = 21 = 5???
– If five bit were available for result binary number, its
value would be s = 10101 = 16 + 4 + 1 = 21
JBirgitta Martinkauppi, Janne Koljonen | University
of Vaasa | Adder circuit, two’s complement 12
i 4 3 2 1 0
Muistinumero,
ci
1 1 1 0
x 1 1 1 0
y 0 1 1 1
s 0 1 0 1
Example: Modular Arithmetic
• In many programming languages, the basic
assumption is that when the sum of the addition
exceeds the variable's maximum value, the result
will start again increasing from zero
– With four bits the maximum value of the variable is
2
4–1 = 15
• Thus, for example,10 + 5 = 15, but 10 + 6 = 0
• And 10 + 7 = 1; and 10 + 11 + 11 = 0
– This is called as modular arithmetic
• This is familiar from clocks:
If time is now 11, then after four
hours it is 3
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 13
• If you want to avoid overflow in the addition of two
numbers, you need to allocate one bit more than
the bit amount of these numbers.
– However, this is not always necessary or possible
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 14
• The added circuit can be
implemented, as above, as
numbers
– You need to add up first
two LSBs and after that
always three bits (one is
carry bit)
15 Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement
• Kahden bitin yhteenlasku tehdään puolisummaimella
• Totuustaulu summalle s0
ja muistinumerolle c1
:
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 16
x0 y0 c1 s0 SOP term
0 0 0 0 x0
'y0
'
0 1 0 1 x0
'y0
1 0 0 1 x0y0
'
1 1 1 0 x0y0
• Equations for sum s0 and carry are c1
:
c1 = x0y0
s0 = x0
'y0 + x0y0
’ = x0  y0
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 17
x0 y0 c1 s0 SOP-term
0 0 0 0 x0
'y0
'
0 1 0 1 x0
'y0
1 0 0 1 x0y0
'
1 1 1 0 x0y0
HA
x0 y0
s0
c1
• Truth table for the sum si and carry ci+1:
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 18
xi yi ci Sum (in decimal system) ci+1 si SOP-term
0 0 0 0 0 0 xi
'yi
’ci
'
0 0 1 1 0 1 xi
'yi
’ci
0 1 0 1 0 1 xi
'yi
ci
'
0 1 1 2 1 0 xi
'yi
ci
1 0 0 1 0 1 xiyi
’ci
'
1 0 1 2 1 0 xiyi
’ci
1 1 0 2 1 0 xiyi
ci
'
1 1 1 3 1 1 xiyi
ci
• ci+1 = xi
'yi
ci + xiyi
’ci + xiyi
ci
' + xiyi
ci
• si = xi
'yi
’ci + xi
'yi
ci
' + xiyi
’ci
' + xiyi
ci
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 19
xi yi ci Summa desimaalilukuna ci+1 si SOP-termi
0 0 0 0 0 0 xi
'yi
’ci
'
0 0 1 1 0 1 xi
'yi
’ci
0 1 0 1 0 1 xi
'yi
ci
'
0 1 1 2 1 0 xi
'yi
ci
1 0 0 1 0 1 xiyi
’ci
'
1 0 1 2 1 0 xiyi
’ci
1 1 0 2 1 0 xiyi
ci
'
1 1 1 3 1 1 xiyi
ci
FA
xi yi
si
ci+1 ci
The number of full-adders depends on the amount
of bits per input variable.
– Here is an example of an adder circuit for two 4-bit
numbers
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 20
HA
x0 y0
s0
c1
FA
x1 y1
s1
c2
FA
x2 y2
s2
c3
FA
x3 y3
s3
c4
Negative numbers
There are many was to
present
/code negative
numbers in computer
science. – In this lecture, we go
through one method
• 2’s complement is the
most common method to
present negative numbers – It is suitable for
substraction operation,
too.
21 Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement
s complement
• The 2-complement is a binary representation,
where the first bit indicates the sign of the number
– If the first bit is 0 -> a positive number
– If the first bit is 1 -> a negative number
• The sign is changed or the number is converted to
its opposite numbers as follows:
– Invert all bits
• Add +1 to the inverted number using binary
addition (which was learned at the beginning of the
lecture)
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 22
2´s complement - example
• Let’s present –2 using 2’s complement
– First, find out the corresponding positive value
x = +2 = 0010
– Invert all the bits: x’ = 1101
– Then add +1 using binary addition x = 1110 = –2
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 23
i 3 2 1 0
Ci 0 0 1
x’ 1 1 0 1
+1 0 0 0 1
x 1 1 1 0
2´s complement - example
• What is the opposite number of –2 = 1110?
– Invert all the bits: y’ = 0001
– Then add +1 using binary addition: y = 0o10 = 2
– So we got the original number
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 24
i 3 2 1 0
ci 0 0 1
y’ 0 0 0 1
+1 0 0 0 1
x 0 0 1 0
Example: subtraction
operation
• Let’s compute 3–4 using binary numbers and 2’s
complement
– The subtraction can be done with the help of
addition: z = 3–4 = 3 + (–4) = 0011 + 1100
• 2’s complement is –4 = 1100
– z = 1111
• Because first bit = 1,
z is negative
• Invert the nits: z’ = 0000
–z = 00012 = +1dec
• So, the final result is z = –1dec
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 25
i 3 2 1 0
ci 0 0 0
3 0 0 1 1
–4 1 1 0 0
z 1 1 1 1
Summary of 2’s
complement numbers
• The first bit indicates
the sign (0
–positive, 1
negative)
• Numbering
follows the
modular arithmetic
according to the
illustration on the right
direction of rotation is
counter clockwise
• In subtraction, the
direction is clockwise
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 26
Summary of 2’s
complement numbers
• For example, with four
bits:
• 7 + 1 = –8 (overflow)
• –1 + 2 = +1
• –5 – 2 = –7
• –4 + 16 = –4 (overflow)
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 27
–1 + 2 = +1
7 + 1 = –8
–5 – 2 = –7
In this lecture,
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 28
• When addition operation is implemented as a digital
circuit, the sum is calculated as one bit at a time
starting from the right
– Use of the memory number (carry) when necessary
– These adders are daisy chained
• Negative figures are most often presented as the 2’s
complement
– Procedure: (1) inverted bits, (2) more +1
• 2’s complement can be used in subtraction operations
like x-y = x + (-y) where -y is the 2’s complement of y
Exercise 6:
simulations and
laboratory work
• Make an adder circuit with
HA and FA components
– Simulation
29 Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement
References
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 30
• http://mathforum.org/mathimages/index.php/Mo
dular_arithmetic
Birgitta Martinkauppi, Janne Koljonen | University of
Vaasa | Adder circuit, two’s complement 31

2017-11-12

D.Sc.(Tech.) J. Birgitta Martinkauppi, Janne Koljonen Adder circuit, twos complement Digital Electronics Electrical Engineering and Energy Technology Faculty of Technology Learning goals Addition operation in a computer How negative numbers