CS 2204: Digital Circuits
Lecture 7
Base-n representations
Base 2 (Binary) Representation
Base 8 (Octal) Representation
Numbers in range 0,1,2,…7
Example:
Base 16 (Hex) Representation
Numbers in range 0,1..9,A,B..F
Example:
Hex used as shorthand for binary
Computers used binary representations. For examples, “ints”
in C are 32-bit binary numbers.
But writing down 32-bits is tedious, so we often use a
hexadecimal representation instead.
Q: How many hexadecimal numbers needed to represent a 32-bit
binary value? Hint: how many binary numbers do you need for
a single hex number?
Example
Convert the following binary value to hexadecimal.
Strategy: group into sets of 4 bits each. Convert each set
of 4 bits into hex equivalent.
Adding binary values
Binary additions are very similar to the way we perform
decimal additions!
+1 +1 +1
1 1 0 1 = 13
+ 0 1 0 1 =+ 5
———————–
1 0 0 1 0 = 18
Adding binary values
Binary additions are very similar to the way we perform
decimal additions!
+1 +1 +1
1 1 0 1 = 13
+ 1 1 0 1 =+13
———————–
1 1 0 1 0 = 26
A “full” Adder
Takes a “carry-in” bit, two inputs bits x and y, and outputs
a sum bit and a “carry out” bit
0
1
1
0
1
0
0
1
Carry out bit K-mapSum bit K-map
A small detour: xor gates
We will show that:
Sum bit using xors
Circuit diagram of a full adder
A full adder is essentially a
single-bit adder
N-bit adder
FAFAFAFA
+1 +1 +1
1 1 0 1 = 13
+ 0 1 0 1 =+ 5
———————–
1 0 0 1 0 = 18
1
1
0
0
1
0
0
0
0 1
1
1
1
0
1
01
FA
x
y
cin
sum
cout
Generic n-bit adder
=0
Signed arithmetic
What about negative numbers?
– Sign magnitude representation
– The most-significant bit (MSB)
is zero for positive numbers and
1 for negative numbers
– The remaining bits indicate the
magnitude
Example
– Write down the numbers 2 and -7
using 6-bit SMR representation.
2 = 000010
-7 = 100111
– What is the minimum number of
bits needed to represent all
integers in range [-7,7]?
– You need 4 bits!
2s complement representation
The SMR representation is super inefficient for arithmetic
operations. Instead the 2s complement representation is very
commonly used in modern computer systems.
MSB multiplied
By negative number!
Interpreting 2s complement
The SMR representation is super inefficient for arithmetic
operations. Instead the 2s complement representation is very
commonly used in modern computer systems.
If MSB (sign bit) is zero, V(B) = M
If MSB (sign bit) is 1, V(B) = -[2^(n-1)-M]
Interpretation of signed numbers
Additions using twos complement
Add the two numbers as if they were regular unsigned values and
ignore carry-out bit from the MSB. What do you observe?
Adding two numbers in 2s complement format yields the result also
in 2s complement format (if we ignore carry-outs from MSBs)!
Dealing with Overflows
Say we want to add -8 + -7. These can be represented as 4-bit 2s
complement numbers. BUT, the result -15 cannot be represented in
4-bits. We call this an “overflow”
How can we detect that overflow has occurred?
– Overflow can only occur when adding two positive numbers or two
negative numbers.
– If the sign of the result is incorrect, then an overflow has
occurred!
Overflow Example
I added two negative numbers and got a positive result. What
happened here? OVERFLOW!
+1
1 0 0 0 = -8
+ 1 0 0 1 = -7
———————–
1 0 0 0 1 = 1 (??!)
Overflow Example
I added two positive numbers and got a negative result. What
happened here? OVERFLOW!
+1 +1
0 1 1 1 = 7
+ 0 0 1 0 = 2
———————–
1 0 0 1 = -7
Overflow Detector
What logic can you
use to detect
overflows?
+1 +1
0 1 1 1 = 7
+ 0 0 1 0 = 2
———————–
1 0 0 1 = -7
+1
1 0 0 0 = -8
+ 1 0 0 1 = -7
———————–
1 0 0 0 1 = 1
Consider the full adder truth table
Overflow
0
0
0
1
1
0
0
0
When does overflow
occur?
When the carry-in
into the MSB column
is not equal to the
carry out!
Overflow Detector
What logic can you
use to detect
overflows?
+1 +1
0 1 1 1 = 7
+ 0 0 1 0 = 2
———————–
1 0 0 1 = -7
+1
1 0 0 0 = -8
+ 1 0 0 1 = -7
———————–
1 0 0 0 1 = 1