Digital Design:
Number Systems
Credits:
Slides adapted from:
J.F. Wakerly, Digital Design, 4/e, Prentice Hall, 2006
C.H. Roth, Fundamentals of Logic Design, 5/e, Thomson, 2004
1
Positional Number Systems
A number is represented by a string of digits, where each
digit position has an associated weight and it has the
following form:
dp-1dp-2 d1d0 . d-1d-2 d-n
The value of the number is given by:
p -1
D di r i
i - n 2
Binary Numbers
The general form of a binary number of p+n binary digits
(bits) is:
bp-1bp-2 b1b0 . b-1b-2 b-n
and its value is:
p -1
B b 2
i - n
i
i
3
Octal and Hexadecimal Numbers
The octal number system uses
radix 8, while the hexadecimal
number system uses radix 16
The octal and hex number systems
are useful for representing multibit
numbers
4
Conversion from Binary to Decimal
p -1
Method: summation B i
b
i - n
2 i
Example:
101110110012 = 1 210 + 0 29 + 1 28 + 1 27 + 1 26 + 0 25 +
1 24 + 1 23 + 0 22 + 0 21 + 1 20 = 149710
5
Conversion from Decimal to Binary
Method: successive divisions
Example:
6
EXAMPLE: convert 5310 to binary
7
EXAMPLE: convert .625ten to binary
8
EXAMPLE: convert 0.710 to binary.
9
EXAMPLE: convert 231.34 to base 7.
10
Addition of Binary Numbers
EXAMPLE: Add 1310 and 1110 in binary.
11
Subtraction of Binary Numbers
EXAMPLES:
12
Representation of Negative Numbers
Signed-Magnitude Representation
+10ten -10ten
001010two 101010two
The number zero has two representations (+0 and -0)
An n-bit signed-magnitude number lies within the range
-(2n-1 - 1) through +(2n-1 - 1)
To add signed-magnitude numbers we must examine the signs of
the addends to determine what to do …
Radix Complement Representation
13
Diminished Radix Complement Representation
Representing Numbers ????
Key observation:
Numbers are just strings of symbols. The meaning (value) we
assign to each string instance (pattern) is up to us. If the string is n
symbols (digits) long and each symbol can take up to different r
instances (radix) then we can form rn different patterns.
“Common sense” characteristics of a system number:
Assign a different value to each different pattern
Split the patterns equally between positive numbers and
negative numbers
The mechanic of doing arithmetic operations should be as
“simple’ as possible 14
Complement Number Systems
While the signed-magnitude system negate a number by
changing its sign, a complement number system negates a
number by taking its complement.
Radix-complement Representation
The complement of an n-digit number D is obtained by
subtracting it from rn
rn – D = ((rn-1)-D) + 1
Diminished Radix-complement Representation
In a diminished radix-complement system the complement
of an n-digit number D is obtained by subtracting it from rn-1
15
Complement Number Systems
16
Complement Number Systems
17
Complement Number Systems
Once we know how to compute the diminished-radix
complement of a number, computing the radix-complement
is very simple:
radix complement = diminished-radix complement + 1
0
9 1
8 2
7 3
6 4 18
5
C2 Number System
For binary numbers, the radix complement is called two’s
complement (C2).
The MSB of a number in this system serves as the sign bit.
Negative numbers have MSB equal to 1
Positive numbers have MSB equal to 0
The range of representable numbers is:
–(2n-1) through +(2n-1-1)
Zero has only one representation
19
Two’s Complement Number System
-8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7
0
-1 1
0000
1111 0001 2
-2
1110 0010
-3 3
1101 0011
-4 4
1100 0100
5
1011 0101
-5
1010 0110
-6 1001 6
1000 0111 20
-7 -8 7
C1 Number System
For binary numbers, the diminished-radix complement is
called one’s complement (C1).
The MSB of a number in this system serves as the sign bit.
Negative numbers have MSB equal to 1
Positive numbers have MSB equal to 0
The range of representable numbers is:
–(2n-1-1) through +(2n-1-1)
Zero has two representations: positive zero (00 00) and
negative zero (11 11)
21
Summary of Signed Number Systems
22
C1 Number System
In the C1 number system to negate an n-bit number all we
have do is to flip (invert) all the bits
23
C2 Number System
In the C2 number system to negate an n-bit number
requires two steps:
invert all bits of the number (i.e. take
the C1 of the number) and then
add 1
24
“Playing” with the C2 notation
The sum of a number and its inverted representation must be
111….111two, which in C2 represent –1
X + X -1 X + 1 -X X + X + 1 0
25
C2 EXAMPLES
26
C2 sign extension
As far as m > n, it is possible to convert n-bit numbers into m-
bit numbers, but some care is needed :
copy the most significant bit (the sign bit) into the other bits
0010 0000 0010
1010 1111 1010
This procedure is referred as "sign extension"
27
C2 Addition and Subtraction
1. Addition of 2 positive numbers, sum < 2n –1.
2. Addition of 2 positive numbers, sum ≥ 2n –1
28
C2 Addition and Subtraction
3. Addition of positive and negative numbers
(negative number has greater magnitude).
4. Addition of positive and negative numbers
(positive number has greater magnitude).
29
C2 Addition and Subtraction
5. Addition of two negative numbers, |sum| ≤ 2n –1.
6. Addition of two negative numbers, | sum | > 2n –1.
30
Detecting overflow
Overflow occurs when the value affects the sign bit:
adding two positives yields a negative
adding two negatives gives a positive
subtract a negative from a positive and get a negative
subtract a positive from a negative and get a positive
No overflow when adding a positive and a negative number
No overflow when subtracting two numbers of same sign
Consider the operations A + B, and A – B
Can overflow occur if B is 0 ? cannot occur !
Can overflow occur if A is 0 ? can occur !
(for A-B if B=-2n-1) 31
Binary Codes for Decimal Numbers
32
Gray Code
33
Character Codes
34
N-cubes and Hamming distance
35
Traversing a 3-cube in Gray code order
36