Transcript Numbering systems

Data Representation and Numbering Systems
ACOE161
1
The Decimal Numbering System
• In the Decimal system a digit can take one out of ten different values (0..9)
• A number in the decimal system is expressed by the following expression:
(dndn-1…d1d0)10 = (dnX10n )+ (dn-1X10n-1) + …+ (d1X101) +( d0X100)
Where d = {0,1,2,3,4,5,6,7,8,9} = {0..9}
• Notes:
N
– A decimal system with N digits can represent the numbers from 0 to 10 -1.
N
– In a decimal system with N digits there are 10 different combinations.
– The digit to the right of a number is called the Least Significant Digit (LSD).
– The digit to the left of a number is called the Most Significant Digit (MSD).
ACOE161
2
The Binary Numbering System
• Digital systems and computers use the Binary system because it has only two
states (0 and 1)
• A number in the Binary system is expressed by the following expression:
(dndn-1…d1d0)2 = (dnX2n )+ (dn-1X2n-1) + …+ (d1X21) +( d0X20)
Where d = {0,1}
Examples:
• (1011)2 = (1X23 )+(0X22)+(1X21) +(1X20) = 8+0+2+1= (11)10
• (10110)2 = (1X24 )+(0X23)+(1X22) +(1X21) +(0X20) = 16+0+4+2+0= (22)10
• (101100)2=(1X25 )+(0X24)+(1X23)+(1X22)+(0X21)+(0X20)=32+0+8+4+0+0=(44)10
ACOE161
3
The Binary Numbering System (Cont.)
•
•
•
•
•
•
•
•
A binary digit is called the BIT (BInary digiT).
A group of eight bits is called the BYTE.
The leftmost bit of a number is called the Most Significant Bit (MSB).
The rightmost bit of a number is called the Least Significant Bit (LSB).
N
A binary system with N bits can represent the numbers from 0 to 2 -1.
N
In a binary system with N digits there are 2 different combinations.
A binary number is multiplied by two, if we append a zero at the LSB.
Prefixes in the binary system:
10
2 = 1,024 = 1K (Kilo)
20
2 = 1,024 X 1,024 = 1,048,576 = 1M (Mega)
0
2 =1
1
2 =2
2
2 =4
3
2 =8
4
2 = 16
5
2 = 32
6
2 = 64
7
2 = 128
8
2 = 256
9
30
2 = 512
40
2 =1024=1K
2 = 1G (Giga)
2 = 1T (Tera)
ACOE161
Powers of 2:
10
16
2 = 65536
4
A General Numbering System With Base R
• A numbering system with base R can have digits in the range from 0 to R-1
• A number in a system with base R is expressed by the following expression:
(dndn-1…d1d0)R = (dnXRn )+ (dn-1XRn-1) + …+ (d1XR1) +( d0XR0)
Where d = {0.. R-1}
Examples:
• A computer that uses light (color) to represent information will use a numbering
system with a base of 3, since there are three basic colors.
• Usually in computers we group the bit of a number for simplicity. A group of 4
bits yields a system with 16 combinations. Such a system is called the
Hexadecimal system
ACOE161
5
Conversion from a system with base R to Decimal
• To convert a number from a system with base R to decimal we replace R with the
base of the system in the following expression:
(dndn-1…d1d0)R = (dnXRn )+ (dn-1XRn-1) + …+ (d1XR1) +( d0XR0)
Examples:
• (214)5 = (2X52 )+(1X51) +(4X50) = (2X25)+(1X5)+(4X1)=50+5+4= (59)10
• (2021)3 = (2X33)+(0X32)+(2X31)+(1X30)=(2X27)+(2X3)+(1X1)=54+6+1= (61)10
• (13A)12 = (1X122)+(3X121)+(10X120)=144+36+10=(190)10
• (4C)18 = (4X181)+(12X180)=72+12=(84)10
• (135)4 = Invalid. Digit 5 is greater than 4 which is the base of the system.
ACOE161
6
Examples
Do the following conversions:
• (234)6 = (?)10
• (2012)3 = (?)10
• (A1C)14 = (?)10
• (5H)20 = (?)10
• (122)4 = (?)10
• (1220)4 = (?)10
• (12200)4 = (?)10
• (122003)4 = (?)10
ACOE161
7
Conversion from Decimal to a system with base R
A decimal number can be converted into its equivalent in base R using the following
procedure:
Step 1: Perform the integer division of the decimal number by R and record the
remainder.
e.g. if the number is 70 and the base is 4 then 70/4 = 17 + 2/4
Step 2: Replace the decimal number with the result of the division in step 1. Repeat step
1, until a zero result is found.
e.g.
17/4 = 4 + 1/4
4/4 = 1 + 0/4
1/4 = 0 + 1/4
Step 3: The number is formed by reading the remainders in reversed order.
e.g.
(70)10 = (1012)4
ACOE161
8
Examples
Do the following conversions:
• (53)10 = (?)2
• (47)10 = (?)3
• (124)10 = (?)14
• (253)10 = (?)20
• (97)10 = (?)7
• (25)10 = (?)4
• (250)10 = (?)4
• (100)10 = (?)4
ACOE161
9
Homework: Do the necessary
Decimal
67
Binary
conversions to fill up the table below:
Base 3 Base 9 Base 14 Base 18
100111
2102
135
6C
6C
ACOE161
10
Homework
Do the following conversions:
• (244)5 = (?)10
• (2132)4 = (?)10
• (A4F)18 = (?)10
• (6H)22 = (?)10
• (1202)3 = (?)10
• (12020)3 = (?)10
• (120200)3 = (?)10
• (1202003)4 = (?)10
ACOE161
11
The Octal and Hexadecimal Numbering Systems
• Computers use the binary system to represent data. In most cases a number is
represented with 16, 32 or more bits, which is difficult to be handled by humans.
• To make binary numbers easier to manipulate, we can group the bits of the
number in groups of 2, 3 or 4 bits.
• If we take a group of 2 bits, then we can have 4 combinations or different digits
in each group. Thus the new system is a system with the base of 4.
(11)2 = 3
(00)2 = 0
e.g. (10110100)2= (10 11 01 00)2= (2310)4
• The system with the base 4 is not widely used because many digits are still
required to represent typical numbers.
ACOE161
12
The Octal and Hexadecimal Numbering Systems (Cont.)
• If we take a group of 3 bits, then we can have 8 combinations or different digits
in each group. Thus the new system is a system with the base of 8 and is called
the Octal system.
(110)2 = 6
e.g. (10110100)2= (10 110 100)2= (264)8
• If we take a group of 4 bits, then we can have 16 combinations or different digits
in each group. Thus the new system is a system with the base of 16and is called
the hexadecimal or hex system. Letters A to F are used to represent digits from 10
to 15.
e.g. (10110100)2= (1011 0100)2= (B4)16
ACOE161
13
Decimal, Binary, Octal and Hexadecimal Conversion Table
Decimal
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ACOE161
Binary
Base 4
Octal
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
10
11
12
13
20
21
22
23
30
31
32
33
0
1
2
3
4
5
6
7
10
11
12
13
14
15
16
17
Hex
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
14
Examples
Decimal
Binary
Base 4
Octal
Hex
51
10101011
1320
154
5F
ACOE161
15
Homework
Do the following conversions:
• (53)10 = (?)2 = (?)4 = (?)8 = (?)16
• (1000111)2 = (?)10 = (?)4 = (?)8 = (?)16
• (1203)4 = (?)10 = (?)2 = (?)8 = (?)16
• (253)8 = (?)10 = (?)2 = (?)4 = (?)16
• (9C)16 = (?)2 = (?)4 = (?)8 = (?)10
ACOE161
16
Fractional number representation
• Let us assume a radix point (.) with the decimal
part on the left and the fractional part on the
right
(d n 1d n2 ...d 0 .d 1d 2 ...d k ) r
• Then
N
n 1
d
i  k
i
r
i
• Example: (72.51)10  7 101  2 100  5 10 1  110 2
ACOE161
17
Examples
(1001.0101) 2  (?)10
(0.213) 4  (?)10  (?) 2
(2B.1A)
ACOE161
16
 (?) 2  (?)10
18
Converting fractional numbers from
decimal number system to radix r
• To convert a decimal fraction to a radix r number,
repeatedly multiply the fraction part by r and
retain the integer digit in sequence until the
fraction is zero, or the number of digits required
are obtained (the number of digits may be
infinite).
• Then the digits following the radix point from left
to right with the integer digits, the earliest
obtained first.
ACOE161
19
Example
(0.5625)10  (?) 2
•
•
•
•
0.5625  2 = 1.1250 Most significant
0.1250  2 = 0.2500
0.2500  2 = 0.5000
0.5000  2 = 1.0000 Least significant
(0.5625)10  (0.1001) 2
ACOE161
20
Converting fractional numbers from from binary
to hex and from hex to binary
• The same principle with integer numbers applies: Group four bits together,
padding with zeros if necessary, but this time from left to right, and convert
its 4-bit group to its corresponding Hexadecimal number and vice versa
• Examples:
(0.5A4C)16  (0.0101101001001100) 2
(0.01001) 2  (0.01001000) 2  (0.48)16
(3B.25)16  (00111011.00100101) 2
(110.011) 2  (0110.0110) 2  (6.6)16
ACOE161
21
Homework
Decimal
Binary
Base 4
Octal
Hex
12.25
101011.01
132.1
13.5
4A.21
ACOE161
22
The Binary Coded Decimal (BCD) System
• In many applications it is required to encode each decimal digit to the equivalent
4-bit binary number. This binary code is called the BCD code.
4 =(0100)2
e.g. (2 4 9)10= (0010 0100 1001)BCD
Examples:
• (173)10 = (?)2 = (?)BCD
• (1000 0111)BCD = (?)10
• (0100 0010)2 = (?)BCD
• (53)16 = (?)BCD
• (1011 0101)BCD = (?)10
ACOE161
23
Addition in any numbering system
• Addition in any numbering system can be performed by following the same rules
used for decimal addition, where 10 is replaced by the base of the system (R).
• Decimal Addition:
3 + 6 = 9  9/10 = 0 + 9/10  write 9 and carry 0
7 4 3
1 8 6+
9 2 9
8 + 4 = 12  12/10 = 1 + 2/10  write 2 and carry 1
1+ 7 + 1 = 9  9/10 = 0 + 9/10  write 9 and carry 0
• Rules for addition in the decimal system:
– Begin the addition by adding the 2 least significant digits first.
– Perform the integer division of the sum with 10. Write down the remainder of the
division and carry out the result to the next column.
– Repeat the addition for the next columns by adding the two digits and the carry from
the previous column.
ACOE161
24
Addition in any numbering system
• Rules for addition in a system with base R:
– Begin the addition by adding the 2 least significant digits first.
– Perform the integer division of the sum with R. Write down the remainder of the
division and carry out the result to the next column.
– Repeat the addition for the next columns by adding the two digits and the carry from
the previous column.
Examples:
Perform the following additions
• (173)8+ (265)8 = (?)8
• (01101011)2+ (00111010)2 = (?)2
• (1243)5+ (234)5 = (?)5
• (1A79)16+ (C827)16 = (?)16
• (1A79)18+ (C827)18 = (?)18
ACOE161
25
Subtraction in any numbering system
• Subtraction in any numbering system can be performed by following the same rules
used for decimal addition, where 10 is replaced by the base of the system (R).
• Decimal Subtraction:
7 4 9
1 8 65 6 3
(96)  9 - 6 = 3  write 3 and borrow 0 from next column
(4<8)  borrow 1  10+4-8=6  write 6 and borrow 1 from next column
(7-11)  7 - 1 - 1 = 5 write 5 and borrow 0 from next column
• Rules for subtraction in the decimal system:
– Begin the subtraction from 2 least significant digits first.
– If the minuend is greater than the subtrahend then perform the subtraction.
– If the minuend is less than the subtrahend then borrow 1 from the next column. Write
down the result of (minuend + 10 - subtrahend). The one borrowed must be subtracted
from the minuend of the next column.
– Repeat the subtraction for the next columns.
ACOE161
26
Subtraction in any numbering system
• Rules for subtraction in a system with base R:
The rules for subtraction in a system with base R are the same as in decimal,
except that a borrow into a given column adds R units to the minuend digit.
Examples:
Perform the following subtractions:
• (476)10 - (285)10 = (?)10
• (285)10 - (476)10 = (?)10
• (173)8 - (265)8 = (?)8
• (01101001)2- (00111010)2 = (?)2
• (423)5 - (234)5 = (?)5
• (61A9)16- (C827)16 = (?)16
• (61A9)18- (C827)18 = (?)18
ACOE161
27
Subtraction using the complement’s method
• In the previous examples, the subtraction {(285)10 - (476)10 } give a result equal
to 809. The correct result is -191. If we examine carefully the subtraction we can
observe that the subtraction of the last digit was carried out using a borrow, i.e.
the result 809 is obtained after we borrow 1000. If we add 809 and 191 then we
get 1000, which is what is borrowed in order to complete the subtraction. The
number 809 is said to be the 10’s complement of the number 191. This shows
that:
– Negative numbers can be represented in the complement’s form.
– Subtraction in the decimal system, can be carried out by adding to the minuend the
10’ s complement of the subtrahend.
i.e.
(285)10 - (476)10 = (285)10 + (-476)10 = (285)10 + [ (523)9’s ++ 1]
= (285)10’s + (524)10’s = (809)10’s
– Subtraction in a system with base R, can be carried out by adding to the minuend the
R’ s complement of the subtrahend.
ACOE161
28
Examples on subtraction using the complement’s method
Perform the following subtractions using the R’s complement method:
• (476)10 - (285)10 = (?)10
• (285)10 - (476)10 = (?)10
• (173)8 - (265)8 = (?)8
• (01101001)2- (00111010)2 = (?)2
• (423)5 - (234)5 = (?)5
• (61A9)16- (C827)16 = (?)16
• (61A9)18- (C827)18 = (?)18
ACOE161
29
Homework: Do the necessary
Binary
Base 7
Base 9
10101100
11011101
2564
3462
5721
5646
10101100
11011101
ACOE161
+
-
2564
3462
+
-
5721
5646
operations to fill up the table below:
Base 14 Base 18
+
-
3A49
596C
3A49
596C
+
-
3A49
596C
3A49
596C
Base 6
+
2435
2342
1234
3443
30
+
Negative Number Representation: Signed Magnitude
• In the Signed Magnitude representation the most significant bit is used as the sign
of the number. The sign bit is zero for positive numbers and one for negative
numbers.
+ve => Sign bit = 0
(+38)10 = +(100110)2 = (00100110)SM:8
-ve => Sign bit = 1
(-38)10 = -(100110)2 = (10100110)SM:8
Magnitude
Sign bit = 0 => +ve
(00101011)SM:8 = +(0101011)2 = (+43)10
Magnitude
Magnitude
Sign bit = 1 => -ve
(10101011)SM:8 = -(0101011)2 = (-43)10
Magnitude
• SM:8 means Signed Magnitude with 8 bits (1 for the sign and 7 for the magnitude.
• The problem with the SM is that there are two values for zero: (0000000 = +0, and
10000000 = -0).
ACOE161
31
Negative Number Representation: One’s Complement
• The Ones Complement representation can be derived from the Signed Magnitude
representation. If the number is positive then the one’s complement is the same as
the SM. If the number is negative then the one’s complement is obtained by
inverting all magnitude bits of the SM. The sign bit is unchanged.
Sign bit
(+38)10 = (00100110)SM:8 = (00100110)1's C:8
Sign bit
(-38)10 = (10100110)SM:8 = (11011001)1's C:8
Magnitude
Sign bit
(00101011)1's C:8 = (00101011)SM:8 = (+43)10
Magnitude
Magnitude
Sign bit
(11010100)1's C:8 = (10101011)SM:8 = (-43)10
Magnitude
• The problem with the One’s Complement is that there are two values for zero:
(0000000 = +0, and 11111111 = -0).
ACOE161
32
Negative Number Representation: Two’s Complement
• If the number is positive then the two’s complement is the same as the SM. If the
number is negative then the two’s complement is obtained by adding 1to the
magnitude bits of the one’s complement. The sign bit is unchanged.
Sign bit
(+38)10 = (00100110)SM:8 = (00100110)2's C:8
Sign bit
(-38)10 = (11011001)1's C:8 = (11011010)2's C:8
Magnitude
Sign bit
(00101011)2's C:8 = (00101011)SM:8 = (+43)10
Magnitude
Magnitude
+1
Sign bit
(11010101)2's C:8 = (10101011)SM:8 = (-43)10
Magnitude
+1
• The two’s complement is widely used in computers to represent signed integers. In
most languages such as Pascal and C an integer variable is represented in a 16-bit
two’s complement representation.
ACOE161
33
Negative Number Representation: Excess 2N-1
• The Excess 2N-1 of a number is obtained by adding 2N-1 to the number and then
convert it to binary. Where N is the number of bits used to represent the number.
For example if 8 bits are used then 2N-1 is 27 = 128 and the system is called the
Excess 128 system.
• Examples:
(+38)10 = 128 + 38 = 166 = (10100110)ex-128
(-38)10 = 128 - 38 = 90 = (01011010)ex-128
(10101011) ex-128 = 171 = 128 + 43 = (+43)10
(01010101) ex-128 = 85 = 128 -43 = (-43)10
• Note that the 2N-1 can also be obtained by inverting the sign bit of the two’s
complement of the number.
ACOE161
34
Negative Number Representation: Excess (2N-1-1)
• The Excess (2N-1 -1)of a number is obtained by adding (2N-1 -1)to the number and
then convert it to binary. Where N is the number of bits used to represent the
number. For example if 8 bits are used then (2N-1 -1) is (27 -1)= 127 and the system
is called the Excess 127 system.
• Examples:
(+38)10 = 127 + 38 = 165 = (10100101)ex-127
(-38)10 = 127 - 38 = 89 = (01011001)ex-127
(10101011) ex-128 = 171 = 128 + 43 = (+43)10
(01010101) ex-128 = 85 = 128 -43 = (-43)10
• Note that the (2N-1 -1) can be obtained by inverting the sign bit of the one’s
complement of the number, ONLY if the number is positive.
• The (2N-1 -1) representation is used in computers to represent the exponent of
floating point numbers.
ACOE161
35
Negative Number Representation: 16’s Complement
• Examples:
(+38)10 = 127 + 38 = 165 = (10100101)ex-127
(-38)10 = 127 - 38 = 89 = (01011001)ex-127
(10101011) ex-128 = 171 = 128 + 43 = (+43)10
(01010101) ex-128 = 85 = 128 -43 = (-43)10
• The (2N-1 -1) representation is used in computers to represent the exponent of
floating point numbers.
ACOE161
36
Examples
• Fill up the table shown below:
Dec.
Binary
SM:8
1's C:8
2's C:8
Ex-127
Ex-128
Hex
15's C
16's C
+57
-57
-74
+128
-128
10000000
10000000
11001100
00110000
58
C5
ACOE161
37
Homework
• Fill up the table shown below:
Dec.
Binary
SM:8
1's C:8
2's C:8
Ex-127
Ex-128
Hex
15's C 16's C
10010011
10010011
10010011
10010011
10010011
9A
C5
ACOE161
38