Transcript Chapter 2

Chapter 2
Number Systems + Codes
Overview
Objective:
•To use positional number systems
•To convert decimals to binary integers
•To convert binary integers to decimals
•To represent binary integers in 3 forms:
–Sign magnitude
–1’s complement
–2’s complement
•To reprensent number in octal (base 8) and hexadecimal
numbers and convert them to decimal and binary numbers
•To understand various computer codes
Overview
Two types of representations of information:
• Numeric information
-Positional number system
-Conversion between number systems
-Operation on number systems (add, substract …)
•Non numeric information
-Codes
- Properties of codes
Overview
Real life Data
•Numeric data
(125.5 : a price
•Nonnumeric data
(John : a name )
Representation of data in
Computer or digital circuits
000111000000 : string of 0’s and 1’s
Correspondance or Representation
I. Representation of numerical information
Positional Number Systems (PNS)
• PNS – a number is represented by a string of digits.
Each digit position is weighted by a power of the base
or radix.
• Example: Decimal PNS, in base 10 digit position i is
weighted by 10i
937.5210=9100 + 310 + 71 + 5.1 + 2.01 +
2.001 + 0.0001
• General Form: Base or Radix = 10
D : dp-1dp-2 dp-3… d2 d1d0. d-1 d-2…d-n
D = dp-1.10p-1 + dp-2.10p-2 +…+ d1.101 + d0.100 +
d-1.10-1 + d-2.10-2 + … + d-n.10-n
p-1
di is a decimal digit
D =  di.10i
i=-n
I. Representation of numerical information
Positional Number Systems (PNS)
• General Form: Base or Radix = 2
D : bp-1bp-2 bp-3… b2 b1b0. b-1 b-2…b-n
D = bp-1.2p-1 + bp-2.2p-2 +…+ b1.21 + b0.20 +
b-1.2-1 + b-2.2-2 + … + b-n.2-n
p-1
D = bi.2i
i=-n
bi is a binary digit
I. Representation of numerical information
Summary of PNS
• Decimal is natural (we count in base 10)
- (Radix or Base 10 ) digits  {0,1,…,8,9}
• Binary is used in digital system
- (Radix or Base 2 ) digits  {0,1}
• Octal is used for representing multibits (group of 3
bits) numbers in digital systems.
- (Radix or Base 8=23) digits  {0,1,…,6,7}
• Hexadecimal is used for representing multibits (group
of 4 bits) numbers in digital systems
- (Radix or Base 16=24) digits  {0,1,…9,A,B,…,F}
I. Representation of numerical information
Summary of PNS (…)
Dec
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Binary
0
01
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111
10000
Oct
0 (000)
1 (001)
2 (010)
3 (011)
4 (100)
5 ( 101)
6 (110)
7 (111)
10 (001 000)
11 (001 001)
12 (001 010)
13 (001 011)
14 (001 100)
15 (001 101)
16 (001 110)
17 (001 111)
20 (010 000)
Hex
0 (0000)
1 (0001)
2 (0010)
3 (0011)
4 (0100)
5 (0101)
6 (0110)
7 (0111)
8 (1000)
9 (1001)
A (1010)
B (1011)
C (1100)
D (1101)
E (1110)
F (1111)
10 (0001 0000)
I. Representation of numerical information
Conversions
From any base r ---> Decimal
Use base 10 arythmetic to expand :
p-1
D = di.ri
(r is the base and di are the digits)
i=0
Two solutions can be used to do this :
• Polynomial expansion
D = dp-1.rp-1 + dp-2.rp-2 +…+ d1.r1 + d0.r0
Examples : 31016 = 3.162 + 1.161 + 0.160
= 3.256 + 16 + 0 = 78410
1CE816 = 1.163 + 12 .162 + 14. 161+ 8.160 = 740010
436.58 = 4.82 + 3. 81 + 6 .80 + 5. 8-1 = 286.62510
I. Representation of numerical information
Conversions
From any base r ---> Decimal
• Iterative multiplication (Expansion of D)
D can be written as :
((….((dp-1).r + dp-2).r +…+d2).r + d1).r + d0
Examples : 31016 = ((3).16+ 1).16 + 0)
= (49).16 + 0 = 78410
Good for programming
I. Representation of numerical information
Conversions
From Decimal ---> Any base r
Successive divisions of D by r yield the digits from
the least to the most significant bit.
Remember that D can be written in base r as :
D = dp-1.rp-1 + dp-2.rp-2 +…+ d1.r + d0.
= ((….((dp-1).r + dp-2).r +…+d2).r + d1).r + d0
D/r -----> quotient D1 = (….((dp-1).r + dp-2).r +…+d2).r + d1
remainder d0
D1/r -----> quotient
D2 = (….((dp-1).r + dp-2).r +… d3).r+d2)
remainder d1
D2/r -----> quotient
D3 = (….((dp-1).r + dp-2).r +…+d3)
remainder d2
And so on …..
I. Representation of numerical information
Conversions
From Decimal ---> Any base r
• Example : conversion of 179 from Base 10 -> Base 2
17910
1
2
4
8
16
32
64
128
weight
179
89 1
LSB
44 1
22 0
11 0
5 1
2 1
1 0
0 1
MSB
Successive divisions by 2
17910 = 101100112
I. Representation of numerical information
Conversions
From Decimal ---> Any base r
• Example : conversion of 467 from Base 10 ->
Base 8
467
3
1
58 3
LSB
16
8
7 2
448
64
0 7
MSB
467
weight successive divisions
46710 = 7238
I. Representation of numerical information
Other Conversions
From Binary ---> Octal/Hex
• Conversion by substitution
– Binary to Oct : Starting from rightmost bit, make
groups of 3 bits and convert each group to base8
1000110011102 = 100/011/001/110 = 43168
4 / 3 / 1 / 6
– Binary to Hex : Starting from rightmost bit, make
groups of 4 bits and convert each group to base 16
1000110011102 = 1000/1100/1110 = 8CE16
8 / C / E
I. Representation of numerical information
Other Conversions
From Octal/hex ---> Binary
• Conversion by substitution
– Octal to Binary : Convert each digit to a 3 bits binary
number
5768= 101 111 1102
5
7
6
– Hex to Binary : Convert each digit to a 4 bits binary
number
57616 = 0101 0111 01102
5
7
6
I. Representation of numerical information
Addition of binary numbers
• Example 1 (Addition)
Carry
1 01111000
X 190
10111110
+ Y 141
10001101
331 1 01001011
Result has more bits than binary addends
Carry equals 1 in the last bit position
• Example 2 (Addition)
Carry
0 01011000
X 173
10101101
+ Y 44 00101100
217 11011001
Carry equal to 0 in the last bit position
I. Representation of numerical information
Addition of binary numbers
• In general, given two binary number
X = ( xn-1 … xi … x1 x0 )2 and Y = ( yn-1 … yi … y1 y0)2
the sum (X+Y) bit by bit at position i is given by
(ci is the ith position’s carry)
ci-1
+ xi
+ yi
ci si
Addition table
ci-1 xi yi si ci
0 0 0 0 0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
1
0
1
0
1
0
1
1
1
0
1
0
0
1
0
0
1
0
1
1
1
I. Representation of numerical information
Substraction of binary numbers
• Substraction
B
X 12129
- Y
46
183
B
X
- Y
1 1 1 10
0 10 1 0 1 0 0
1110 0101
0010 1110
1011 0111
0
2110
1 09
1 01
1
0 1
0
1
1 0 10
0
10
1101 0010
0110 1101
110 0101
I. Representation of numerical information
Addition of hexadecimal numbers
Addition of two hexadecimal numbers
C
X
+Y
1
1
1 9 B 9 16
C 7 E 6 16
E 1 9 F 16
I. Representation of numerical information
Representation of negative numbers
Signed-magnitude systems
• +99, -57, -13.3
Binary uses a (sign bit, the most significant bit (MSB))
MSB = 0 (Positive) MSB = 1 (Negative)
0 10101012 = + 8510
0 11111112 = + 12710
0 00000002 = + 010
1 10101012 = -8510
1 11111112 = -12710
1 00000002 = - 010
• Problem:
Too much logic needed to
- detect and compare sign bit
- add or abstract magnitudes
- determine the sign of the result
I. Representation of numerical information
Representation of negative numbers
Complement number system
• Difficult to change to complement
• But adding or substracting two numbers are
easier once they are represented in complement
number systems
I. Representation of numerical information
Representation of negative numbers
Radix – Complement representation
• n digit number is substracted from rn
• Example:
if r = 10 and n = 4,
rn = 104 =10,000
The 10’s complement of D=184910 is:
(rn – D) = 8151
• Computing 10’s complement: rn – D = (rn - 1 – D) +1
(rn - 1) – D => complement of each digit with rspect to
base (r-1)
In base 10 complement each digit with respect to 9 and 1
to the result
Example: The 10’s complement of 184910 is
(104 - 1849)= (9999 – 1849) + 1 = 8 1 5 0 + 1 = 8151
I. Representation of numerical information
Representation of negative numbers
Radix – Complement representation
• Complement of each digit :
r –1 – di
In base 10 : 10 –1 – di = 9 – di
Example : The complement of each digit of 345 is :
For 5 : (10 – 1) – 5 = 9 – 5 = 4
For 4 :
=9–4=5
For 3 :
=9–3=6
• In base 3 the radix complement of 121 is 101
• In base 2 the radix complement of 1110111 is 0001000
I. Representation of numerical information
Representation of negative numbers
Two’s Complement
• The MSB is the sign bit
n-1
Note: The weight of the MSB is –2
• Example:
1710 = 000100012
11101110
-12710 = 100000012
01111110
+1
+1
111011112 = -1710
01111111 =12710
• The range is -(2n-1) -> (2n-1-1), For n=8
010 = 000000002
-12810 = 100000002
The range of positive numbers is 0 to 127
The range of negative numbers is –1 to -128
I. Representation of numerical information
Representation of negative numbers
Two’s Complement
• Two’s complement of 010 and -12810
010 = 000000002
-12810 = 100000002
11111111
01111111
+1
+1
1000000002 = 010
10000000 = -12810
Note: Ignore carry out of the MSB position
Note: -128 does not have a positive counterpart, that is –128 is its own
Complement : this can creat problems ……
I. Representation of numerical information
2’s Complement Addition + Substraction
+3
0011
+4 +0100
+7
0111
-2 0010 -> 1101+1-> 1110
+ -6 0110 -> 1001+1-> + 1010
-8
11000
Overflow in the last position
+6 0110
0110
+ -3 0011 -> 1100+1 => 1101
+3
1 0011 = 3
Overflow in the last position
Rule : Ignore any carry beyond the MSB. The result is correct if the range of the
number system Is not exceeded.
I. Representation of numerical information
2’s Complement Addition + Substraction
Addition/Substraction rule :
Assume that the signed integers are represented in 2s complement :
To compute A – B, compute the 2’s complement B’ of B and add B’ to A
Examples :
5
+2
0101
0010
5
-2
7
0111
3
0101
+ 1110 ( = 2’)
1 0011 (ignore the leftmost carry
I. Representation of numerical information
Overflow
• Addition of 2 numbers with different signs can
never overflow
• Addition of 2 numbers with same sign
-3 1101
+5 0101
+ -6 1010
+ +6 0110
-9 1 0111 = +7
+11 1011 = -5
wrong
wrong
If signs of (addends) are same and sign of sum is
different
I. Representation of numerical information
Substraction rules (2’s complement)
+4 0100 0100
- +3 -0011 1101
1
1 0001
-3
- -4
1
1101
1100
1101
0011
1 0001
Same overflow rules apply
I. Representation of numerical information
Binary multiplication
11
 13
33
11
143
1011
1101
1011
10000
11011
11011
10001111
uses a shift register and adder, and logic control
• Signed multiplication
++=+
+-=-
--=+
II. Representation of non numerical information
Binary codes for decimal numbers
Goal:
Use binary strings (sequence of 0’s and 1’s) to
represent decimal information
Definition:
• A code is a set of n-bit strings. Each n-bit
string represrnts a different number.
• A code word is a particular member of a code
II. Representation of non numerical information
Binary codes for decimal numbers
• A code is a set of n-bit strings. Each n-bit string
represrnts a different number.
• A code word is a particular member of a code
• If n bit is used to represent each code words, the total
number of possible code words is 2n
Examples:
To encode a set consisting of 3 elements {A,B,C}
• we need 2 bits to represent each code word.
• The possible code words are {00, 01, 10, 11}
II. Representation of non numerical information
Binary codes for decimal numbers
• We need to assign a code word to each element of the
original set.
Assignment 1 :
00 -----> A
01 -----> B
10 -----> C Code 11 is unused
Another assignment :
10 -----> A
01 -----> B
11 -----> C Code 00 is unused
II. Representation of non numerical information
Binary codes for decimal numbers
•
0
1
2
3
4
To encode the 10 decimal digits {0,1,….,8,9} We need 4 bit binary
code words. There are 16=24 possible code words. So 6 codes are
unused.
Assignment 1 :
-----> 0000
-----> 0001
-----> 0010
-----> 0011
-----> 0100
5
6
7
8
9
-----> 0101
-----> 0110
-----> 0111
-----> 1000
-----> 1001
The following codes are unused: 1010, 1011, 1100, 1101, 1110, 1111