Transcript Topic 1 – Number Systems and Codes

Topic 1 –
Number Systems
What is a Number System?



A number system consists of an ordered set
of symbols (digits) with relations defined for
addition, subtract, multiplication, and division.
The radix of a number system is the total
number of digits allowed in the system.
Any number in a system can have both an
integer (whole) part and a fractional part,
separated with a radix point.
Positional Notation



As an example, consider a fictional paycheck
of $956.81.
This number is expressed in positional
notation. This means that the position of
each digit indicates its relative weight (or
significance).
Here, this paycheck can be cashed for 9
hundred dollar bills, 5 ten dollars bills, 6 one
dollar bills, 8 dimes, and 1 penny.
Positional Notation



A positive number, N, can be written in
positional notation as:
N = (an-1an-2…a1a0a-1..a-2…a-m)r
Here, n represents the number of digits to
the left of the radix point, m represents the
number of digits to the right of the radix
point, and r represents the radix.
Using this notation, our paycheck can be
expressed as (956.81)10. In general, we can
emit the ()r if the radix is known by context.
Polynomial Notation



We can also express this amount in
polynomial notation.
For example, we can express our value of
956.81 as
9 x 102 + 5 x 101 + 6 x 100 +
8 x 10-1 + 1 x 10-2
Note that each digit resides in a weighted
position and that weight is a power of the
radix (10 in this case).
Important Number Systems

In the study of digital systems we have
a number of important number
systems…




Binary
Octal
Decimal
Hexadecimal-
Radix
Radix
Radix
Radix
2
8
10
16
Important Number Systems
Decimal
Binary
Octal
Hexadecimal
0
0
0
0
1
1
1
1
2
10
2
2
3
11
3
3
4
100
4
4
5
101
5
5
6
110
6
6
7
111
7
7
8
1000
10
8
9
1001
11
9
10
1010
12
A
11
1011
13
B
12
1100
14
C
13
1101
15
D
14
1110
16
E
15
1111
17
F
16
10000
20
10
Binary in Digital Systems



Digital systems are usually constructed in a
two state device (it’s either on or off). This
makes the binary number system ideally
suited for representing numbers in digital
systems.
Only two digits, 0 and 1 (called bits) are
needed. A bit can be stored in a two stage
storage device known as a latch.
A binary number of length n can be stored in
an n-bit long device known as a register,
which is built with n latches.
Binary Addition


Binary addition is very simple.
This is best shown in an example of
adding two binary numbers…
1 1 1 1
1 1 1 0 1
+
1 0 1 1 1
--------------------1 0 1 0 1 0 0
1
1
1
carries
Binary Addition

We can add four binary numbers:
(101101)2, (110101)2, (001101)2, and
(010001)2…
10 10 10 10 1 10
1 0 1 1 0 1
1 1 0 1 0 1
0 0 1 1 0 1
+
0 1 0 0 0 1
---------------------1 0 0 0 0 0 0 0
carries
Binary Subtraction


We can also perform subtraction (with
borrows in place of carries).
Let’s subtract (10110)2 from (1001101)2…
1
0 10 10
1
0
10
0 0 10
0 1 1 0 1
1 0 1 1 1
-----------------------1 1 0 1 1 0
borrows
Binary Multiplication

Binary multiplication is much the same
as decimal multiplication, except that
the multiplication operations are much
simpler…
1 0 1 1 1
X
1 0 1 0
----------------------0 0 0 0 0
1 0 1 1 1
0 0 0 0 0
1 0 1 1 1
----------------------1 1 1 0 0 1 1 0
Binary Division

Binary division is the same trial and
error procedure as decimal division…
1
0
remainder
0
1 1 0 1
------------------------1 / 1 1 1 0 1 1 1
1 0 0 1
---------quotient
1 0 1 1
1 0 0 1
---------1 0 1 1
1 0 0 1
---------1 0
Hexadecimal Arithmetic

Arithmetic in hexadecimal follows the same
procedures…
Adding (2A58)16 + (71D0)16
1
2 A 5 8
+
7 1 D 0
--------------9 C 2 8
carries
Hexadecimal Arithmetic
Subtracting (9F1B)16 - (4A36)16
E 11
9 F 1 B
4 A 3 6
--------------5 4 E 5
borrows
Hexadecimal Arithmetic
Multiplying (5C2A)16 X (71D0)16
5 C 2 A
X
7 1 D 0
---------------------4 A E 2 2 0
5 C 2 A
2 8 5 2 6
---------------------2 8 F 9 6 C 2 0
Hexadecimal Arithmetic
Dividing (27FCA)16 / (3E)16
quotient
3
E
A 5 1
------------------------/ 2 7 F C A
2 6 C
------1 3 C
1 3 6
------6 A
remainder
3 E
---2 C
Base Conversions



Often, you will need to convert numbers from
one base into another.
The easiest and most direct way to do this is
series substitution.
To convert a number from base A to base B,
first form the series representation of the
number in base A and the evaluate the series
using base B arithmetic.
Series Substitutions

For example, to convert (10100)2 to base
10…
N = 1(24)+0(23)+1(22)+0(21)+0(20)
N = (16)10 + 0 + (4)10 + 0 + 0
N = (20)10

And, to convert (1101.011)2 to base 8…
N = 1(23)+1(22)+0(21)+1(20)+0(2-1)+1(2-2)+1(2-3)
N = (10)8 + (4)8 + 0 + (1)8 + 0 + (.2)8 + (.1)8
N = (5.3)8
Series Substitution

To convert (AF3.15)16 to base 10…
N=A(162) + F(161) + 3(160)
+ 1(16-1) + 5(16-2)
N=1010(25610) + 1510(1610) + 310(110)
+ 110(0.062510) + 510(0.0039062510)
N=256010 + 24010 + 310 + 0.062510
+ 0.0195312510
N = (2803.08203125)10
Radix Divide Method

An alternate method of converting from base
A to base B is the radix divide method.




(1) Divide (N)A by the desired base B, producing
quotient Q1 and remainder R0. R0 is the least
significant digit (d0) of the result.
(2) Compute each remaining digit by dividing the
quotient Qi by (B)A, producing Qi+1 and remainder
Ri, which represents di.
(3) Stop when the quotient Qi+1 = 0.
This is best seen with some examples…
Radix Divide Method

Converting (234)10 to base 8…
2 9
------8 / 2 3 4
1 6
----7 4
7 2
--2
b0
3
----8 / 2 9
2 4
--5
b1
0
--8 / 3
0
3
b2
Therefore,
(234)10 = (352)8
Radix Divide Method

Converting (234)10 to base 16…
1 4
------16 / 2 3 4
1 6
----7 4
6 4
--1 0
(10)10 = (A)16 = b0
0
----16 / 1 4
0
--1 4
(14)10 = (E)16 = b1
Therefore,
(234)10 = (EA)16
Radix Multiplication Method

In order to convert fractional numbers from
base A to base B, we can use the radix
multiplication method.




(1) Let F-1 = (N)A.
(2) Compute digits (b-i)A by multiplying Fi by (B)A,
producing integer I-i which represents digit (b-i)A
and fraction F-(i+1).
(3) Convert each digit (b-i)A to base B.
Again, this is best seen with some examples…
Radix Multiplication Method

Converting Therefore,
(0.828125)10 to base 2…
(0.828125)10 = (0.110101)2
0.828125
0.656250
0.312500
X
2
X
2
X
2
---------------------1.656250
1.312500
0.625000
b-1
b-2
b-3
0.625000
X
2
-------1.250000
b-4
0.250000
X
2
-------0.500000
b-5
0.500000
X
2
-------1.000000
b-6
Radix Multiplication Method

Therefore, 10 to base 8…
Converting (0.1285)
0.1285
X
8
-----1.0280
b-1
0.3360
X
8
-----2.6880
b-5
(0.1285)10 = (0.10162540…)8
0.0280
0.2240
0.7920
X
8
X
8
X
8
---------------0.2240
1.7920
6.3360
b-2
b-3
b-4
0.6880
0.5040
0.0320
X
8
X
8
X
8
---------------5.5040
4.0320
0.2560
b-6
b-7
b-8
General Conversion Algorithms
There are two general conversion
algorithms.
Algorithm 1:

To convert N from base A to base B, use:
(a) the series substitution method with base
B arithmetic, or
(b) the radix divide and/or multiply methods
with base A arithmetic.
General Conversion Algorithms
Algorithm 2:
To convert N from base A to base B, use:
(a) the series substitution method with base
10 arithmetic to convert N from base A to
base 10, and then
(b) the radix divide and/or multiply methods
with base 10 arithmetic to convert N from
base 10 to base B.
General Conversion Algorithms




Algorithm 1 is more direct, as we simply go
from base A to base B.
Algorithm 2 goes from base A to base 10 to
base B.
So, algorithm 2 requires more steps than
algorithm 1. However, it is often easier,
faster, and less error prone, as all arithmetic
is performed in decimal (base 10).
Bottom line … do what is easier for you.
Signed Number
Representation


The easiest and most straightforward method
of representing signed numbers is the sign
magnitude code.
A signed number may be written as…
N = (san-1an-2…a1a0a-1…a-m)rsm
where s = 0 if the number N is positive and s
= (r-1) if the number N is negative (where r
is the radix of the number system used to
represent the number N).
Sign Magnitude
Representation



Therefore, the sign magnitude code of
N=(-13)10 in decimal is…
N = (9, 13)10sm
And the sign magnitude code of
N = (-13)10 in binary is…
N
= -(13)10
= -(1101)2
= (1, 1101)2sm
The comma is used to delimit sign digits for
the sake of clarity.
Sign Magnitude and
Digital Systems



Sign magnitude code is typically not used in
digital systems.
This method requires circuitry and algorithms
that require the system to understand and
process the sign magnitude coded
numbers…a process which is both time
consuming and requires complex circuitry.
A much more powerful code number systems
can be used in digital systems.
Complementary Number
Systems


Complementary numbers form the basis of
complementary arithmetic which is a powerful
method used by digital systems to handle
signed number manipulation.
In these systems, positive numbers are
represented the same as in sign-magnitude
representation; negative numbers are
represented as the complement of the
corresponding positive number.
Radix Complements


The radix complement [N]r of a number
(N)r is defined as:
[N]r = rn – (N)r
where n is the number of digits in (N)r.
The largest positive number (positive
full scale) that can be represented in
such a scale of rn-1-1 while the most
negative number (negative full scale) is
–rn-1.
Two’s Complement Numbers


The two’s complement number system
is the most commonly used system for
digital systems.
The two’s complement of a number (N)2
is defined as
[N]2 = 2n – (N)2
Calculating the 2’s
Complement of a Number

To calculate the two’s complement of
(N)2 = (01100101)2…
[N]2
=
=
=
=
[01100101]2
28 – (01100101)2
(100000000)2 – (01100101)2
(10011011)2
2’s Complement &
Negative Numbers
Therefore, (10011011)2 is the 2’s complement
of (01100101)2. We can show that this can
be used to represent –(N)2 by showing that
(N)2+[N]2 = 0…
1 0 0 1 1 0 1 1
+
0 1 1 0 0 1 0 1
------------------1
0 0 0 0 0 0 0 0
 If we discard the carry, we can see that the
2’s complement of a binary number can be
used to represent its negative counterpart.

Complement of the
Complement

We can also take the 2’s complement of the
2’s complement of a number and get the
original number back…
[[N]2]2 = [00101100]2
= 28 – (00101100)2
= (100000000)2 – (00101100)2
= (11010100)2.
Since this is the original (N)2, we can see that
[[N]2]2 = (N)2.
Complement Shortcuts


There also are shortcuts to computing the 2’s
complement of a binary number…
Algorithm 1 – Starting with the least
significant bit, copy all of the bits up to and
including the first 1 bit and then
complementing the remaining bits.

N
=01100101
[N] = 1 0 0 1 1 0 1 1
Complement Shortcuts


N
[N]
=11010100
=00101100
For N = (10110)2 for n = 8 (each number
represented in 8 bits)…
N
=00010110
[N]
=11101010
Complement Shortcuts

Algorithm 2 – Simply complement
each bit and then add 1 to the result.

Finding the 2’s complement of (01100101)2
and of its 2’s complement…
N= 01100101
10011010
+
1
--------------10011011
N=
10011011
01100100
+
1
--------------01100101
2’s Complement Numbers

To summarize 2’s complement numbers:
 The two’s complement is computed using
the expression [N]2 = 2n – (N)2.
 The two’s complement of a binary number
is equivalent to the inverse of that
number...-(N)2 = [N]2.
 There are multiple ways of calculating [N]2,
with the simplest being to complement
each bit of (N)2 and then add one to the
result.
Complementary Arithmetic


As subtracting two numbers is equivalent to
adding the complement of one number to the
other number, digital systems need only
adder circuitry to perform both addition and
subtraction.
As any digital system has a limited number of
resources (and the circuits must be a fixed
size), machines have fundamental limits as to
the range of numbers they can represent.
Finite Number Representation

Machines that use 2’s complement
arithmetic can represent integers in the
range
-2n-1 <= N <= 2n-1-1
where n is the number of bits available
for representing N. Note that 2n-1-1 =
(011..11)2cns and –2n-1 = (100..00)2cns.
Adders



Circuitry that performs addition (usually using
2’s complement numbers) is known as an
adder.
Adders have a set number of bits of precision.
For instance, an adder that handles n bit
numbers is referred to as a n-bit adder.
Adders will produce a carry bit when their
computed sum is greater than what the adder
can represent in n bits. An n-bit adder will
produce a carry bit for any sum A >= 2n.
Overflows



When an operation (such as addition)
produces a result that falls outside this range,
an overflow condition is said to occur.
In such a case, the n-bit number produced by
the operation will not be a valid
representation of the result.
Generally, digital systems monitor the
operations they perform and generate a
warning signal when overflow occurs, so
invalid numbers are not mistaken for correct
and valid results.
Complementary Arithmetic

In order to see how arithmetic in the 2’s
complement system works, let’s look at
three cases. In each of these cases, we
will assume that B >= 0 and C >= 0.



A=B+C
A=B–C
A=–B–C
Case 1: A = B + C




In the first case, A = B + C, we know that
since B and C are nonnegative, A must also
be nonnegative.
The difficulty that arises here is when A>2n-11, as this is when an overflow occurs.
This is easily detected as the sign bit of A will
be incorrect.
To see this, let’s consider the sum of the two
largest possible n-bit positive numbers…
Case 1: A = B + C




The largest possible n-bit number is 2n-1-1.
If we add this number to itself,
(2n-1-1) + (2n-1-1) = 2n - 2
As this is greater than 2n-1-1, an overflow
condition occurs for any sum, A, in the range
A >= 2n-1.
The nth bit of any number in this range will
be set to 1. Therefore, any such result will
appear to be negative, thus indicating the
overflow condition.
Case 1 Summary

To summarize A = B + C…


When A > 2n-1-1, an overflow is indicated
by the sign bit of A being incorrect. If two
positive numbers are added and the result
is negative, overflow has occurred.
Since the maximum possible A = 2n-2,
there will never be a carry bit out of the
nth bit of the binary adder.
Case 1 Example #1

For case 1, let’s compute (9)10 + (5)10
using 5-bit 2’s complement arithmetic.
0 1 0 0 1
+
0 0 1 0 1
-------------0 1 1 1 0

(2cns code for (9)10)
(2cns code for (5)10)
Since the result has a zero sign bit, it
correctly represents the desired sum.
Indeed, (01110)2cns = +(1110)2 =
+(14)10.
Case 1 Example #2

Now, let’s compute (12)10 + (7)10 using 5-bit
2’s complement arithmetic.
0 1 1 0 0
+
0 0 1 1 1
-------------1 0 0 1 1

(2cns code for (12)10)
(2cns code for (7)10)
This result has a 1 sign bit, indicating a
negative number! Thus, overflow has
occurred and the result is invalid. Indeed,
the correct result, (19)10 is outside the 5-bit
2’s complement range.
Case 2: A = B – C

In this case, the computation is treated
as A = B + (-C). As we’re using 2’s
complement coding, we can write (-C)
as [C]…
A
= (B)2 + [C]2
= (B)2 + 2n – (C)2
= 2n + (B)2 – (C)2
Case 2: A = B – C



So, we can see that A = 2n+(B)2–(C)2.
This seems right, except for the extra 2n
term. To understand this, let’s consider when
B >= C. In this case, B-C >- 0. Therefore A
>= 2n. Since A >= 2n, this is a carry bit
(recall that an adder generates a carry bit for
any sum >= 2n).
This carry bit can be ignored and we arrive at
the result A = B – C, which is what we want.
Case 2: A = B – C



To be complete, let’s also consider when B <
C. In this case, B-C < 0 and A = 2n – (C –
B)2 = [C – B]2. This gives A = -(C-B)2, which
is the correct answer.
Note that here there is no carry bit generated
by the adder (as there is no 2n term).
When B and C are both positive numbers, B-C
will always be less than either of the two
numbers, meaning no overflow cannot be
generated in this condition.
Case 2 Example #1

Let’s compute (12)10 – (5)10.



carry

(12)10 = +(1100)2
(-5)10 = -(0101)2
= (01100)2cns
= (11011)2cns
Adding these two 5-bit codes…
0 1 1 0 0
+
1 1 0 1 1
-------------1 0 0 1 1 1
Discarding the carry bit, the sign bit is seen
to be zero, indicating a correct result.
Indeed, (00111)2cns = +(0111)2 = +(7)10.
Case 2 Example #2

Let’s compute (5)10 – (12)10.



(-12)10 = -(1100)2 = (10100)2cns
(5)10
= +(0101)2 = (00101)2cns
Adding these two 5-bit codes…
0 0 1 0 1
+
1 0 1 0 0
-------------1 1 0 0 1

Here, there is no carry bit and the sign bit is
1. This indicates a negative result, which is
what we expect. (11001)2cns = -(7)10.
Case 3: A = –B – C

Here, we will take the complements of B and
C and add them together to compute A.
Therefore…
A

=
=
=
=
[B]2
2n –
2n +
2n +
+ [C]2
(B)2 + 2n – (C)2
2n – (B+C)2
[B + C]2
If the carry bit is discarded, the computation
produces the correct result, the 2’s
complement representation of –(B+C)2.
Case 3 Example #1

Let’s compute –(9)10 – (5)10…



carry

-(9)10
-(5)10
= -(1001)2
= -(0101)2
= (10111)2cns
= (11011)2cns
Adding these codes…
1 0 1 1 1
+
1 1 0 1 1
-------------1
1 0 0 1 0
If we ignore the carry bit, we can see the
sign bit is 1. Therefore, the result is correct.
Indeed, (10010)2cns = -(1110)2 = -(14)10.
Negative Number Overflow


Just as too large of a positive number
can produce an overflow, so can too
small of a negative number. Any result
in the range A < -2n-1 will cause an
overflow, indicated by an incorrect sign
bit (it appears to be positive).
This can be illustrated…
Case 3 Example #2

Let’s compute –(12)10 – (5)10…



carry

-(9)10
-(5)10
= -(1100)2
= -(0101)2
= (10100)2cns
= (11011)2cns
Adding these codes…
1 0 1 0 0
+
1 1 0 1 1
-------------1
0 1 1 1 1
If we ignore the carry bit, we can see the
sign bit is 0. This indicates an overflow and
the result is invalid.
2’s Complement Summary
Case
B+C
B–C
-B–C
Carry Sign
Bit
0
0
Condition
B+C <= 2n-1-1
Over
flow?
no
0
1
B+C > 2n-1-1
yes
1
0
B <= C
no
0
1
B>C
no
1
1
-(B+C) >= -2n-1
no
1
0
-(B+C) < -2n-1
yes
Diminished Radix Complement
Number Systems


In addition to the radix complement
number systems (such as 2’s
complement), there is a class of
number systems known as the
diminished radix complement systems.
This is defined as…
[N]r-1 = rn - (N)r -1
1’s Complement


For binary numbers, the 1’s
complement system is used. To find
the 1’s complement of a n-bit binary
number…
[N]2-1 = 2n – (N)2 – 1
As a shortcut algorithm, simply
complement each bit of (N)2.
1’s Complement Arithmetic


Using 1’s complement numbers,
subtracting a number is not the same
as adding its inverse (or subtracting it).
For example, suppose we wish to add
+(1001)2 and –(0100)2. We compute
the 1’s complement of (0100)2 and
obtain 11011. We add 01001 and
11011 and obtain 100100. This is not
the correct result.
End-Around Carry



The correct result, in this system, is obtained
by adding the carry out of the most
significant bit to the result.
In this case, we take the result 00100 and
add the carry out bit of 1 and obtain the
result of 00101. This is the correct result.
This procedure is referred to as an endaround carry and is a necessary step in
diminished complement arithmetic.
Diminished Radix Complement
Number Systems


Diminished radix complement number
systems (especially the 1’s complement) are
not used very often. There are significant
advantages to the complementary number
systems.
However, the 1’s complement system comes
up sometimes in the study of digital systems,
so it is a good idea to understand how this
system of number representation works.
Summary

You should now know:




Decimal, binary, octal, and hexadecimal
number systems
Conversion between these bases
Arithmetic operations in these bases
How negative numbers can be represented
in computers, which method is most
commonly used, and why