Transcript CA_3_Encoding - KTU

COMPUTER
ARCHITECTURE
(T120B125)
Assoc.Prof. Stasys Maciulevičius
Computer Dept.
[email protected]
Information in computers

n bit binary word in computer can represent
the following types of information:

data (numbers, binary vectors, or symbols)
 instructions
 addresses of memory cells or input/output
devices.

Modern computers use and other types of
information:



2009-2013
tags - bit groups indicating type of information;
descriptors of information units;
identifiers (names) of information units
©S.Maciulevičius
2
Number encoding
Numbers can be:

integer,
 floating point,
 decimal,
 binary, hexadecimal, octal.
2009-2013
©S.Maciulevičius
3
Binary, octal, …numbers
We use positional numeral systems in which
each digit has a certain weight.
Therefore for integer A we can write:
A = am-1am-2…a2a1a0 = am-1.pm-1+am-2.pm-2
+… +a2.p2+a1.p1+a0.p0;
Here p is – base of numeral system
So, 1847 = 1.103+8.102+4.101+7.100
2009-2013
©S.Maciulevičius
4
Binary, octal, …numbers
Let us see once more:
A = am-1.pm-1+am-2.pm-2 +…+a2.p2+a1.p1+a0.p0;
If we divide this expression by p, we get integer
part am-1.pm-2+am-2.pm-3 +…+a2.p1+a1.p0 and
remainder a0.
If we divide integer part by p again, we get a new
integer part am-1.pm-3+am-2.pm-4 +…+a2.p0 and a
new remainder a1.
So, to find the representation of given number in a
specific numeral system, we have to divide it
consistent by base of that numeral system and
fix remnants received at each step
2009-2013
©S.Maciulevičius
5
Binary, octal, …digits
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
2009-2013
=
=
=
=
=
=
=
=
=
=
0
1
2
3
4
5
6
7
8
9
000
001
010
011
100
101
110
111
©S.Maciulevičius
=
=
=
=
=
=
=
=
0
1
2
3
4
5
6
7
6
Binary, octal, …integers
10810 = ?2 = ?8 = ?16
108
54 0
27 0
13 1
6 1
3 0
1 1
108 8
4 13
5
1001 = 9
8
1010 = A
1
1011 = B
1100 = C
10810 = 1548
1101 = D
1110 = E
10810 = 1 101 1002 1111 = F
1 5 4
10810 = 11011002
10810=110 11002=6C16
6 C
2009-2013
©S.Maciulevičius
7
Binary, octal, …integers
11011002 = ?10
A = an-1pn-1 + an-2pn-2 + … + a3p3 + a2p2 + a1p1 +
a 0p 0
1 1 0 1 1 0 02
n =6 5 4 3 2 1 0
11011002 = 26 + 25 + 23 + 22 = 64+32+8+4 = 108
11011002 = 1548 = 182 + 581 + 480 =
64+40+4 = 108
2009-2013
©S.Maciulevičius
8
Binary, octal, …integers
11011002 = ?10
A = an-1dn-1 + an-2dn-2 + … + a3d3 + a2d2 + a1d1 + a0d0
A = d(an-1dn-2 + an-2dn-3 + … + a3d2 + a2d1 + a1) + a0 =
= d(d(an-1dn-3 + an-2dn-4 + … + a3d1 + a2) + a1) + a0 = … =
= d(d(d(…d(an-1d + an-2) + … + a3) + a2) + a1) + a0 =
= (((…((an-1d + an-2)d + an-3)d + … + a3)d + a2)d + a1)d +
a0
11011002 = (((((12+1) 2+0) 2+1) 2+1) 2+0) 2+0
3
=108
6
13
27
54
2009-2013
©S.Maciulevičius
9
Binary, octal, …fractions
And now, extend the expression for fractions:
A = a-1.p-1+a-2.p-2 +a-3.p-3 + … (pvz., A = 0,1011…2).
If we multiply this expression by p, we get integer part a-1 and
fraction a-2.p-1+a-3.p-2 +… (e.g.,2 0,1011…2 = 1,011…2;
integer part is 1 and fraction 0,011…).
Multiplying the by p, we get a new integer part a-2 and fraction
a-3.p-1+a-4.p-2 +… (e.g., 20,011… = 0,11…2; integer part
is 0 and fraction 0,11…).
So, to find the representation of given fraction in a
specific numeral system, we have to multiply it
consistent by base of that numeral system and fix
integer parts received at each step
2009-2013
©S.Maciulevičius
10
Binary fractions
Let us transform the fraction 0,3125 to binary
system. We can it to by doubling the fractional
part:
0, 3125
0, 625
1, 25
0, 5
1, 0 – fractional part becomes equal to 0, so
multiplication is finished. The answer is:
0,312510 = 0,01012.
2009-2013
©S.Maciulevičius
11
Octal fractions
Let us transform the fraction 0,3125 to octal
system. We can do it by multiplying the
fractional part by 8:
0, 3125  8 =
2, 5  8 =
4, 0 – fractional part becomes equal to 0, so
multiplication is finished. The answer is:
0,312510 = 0,248.
We can transform from binary system to octal in
such a way:
0,312510 = 0,01012 = 0,010 1002 = 0,248.
2
2009-2013
©S.Maciulevičius
4
12
Integers
Integers can be:

i
i
i
i
i
i
i
i
7
6
5
4
3
2
1
0
unsigned:

signed :
s i6 i5 i4 i3 i2 i1 i0
Range:
unsigned
n
8
16
32
2009-2013
min
0
0
0
signed
max
min
max
255
65536
232-1
-128
-32768
-231
127
32767
231-1
©S.Maciulevičius
13
Representing of negative integers
Negative integers can be represented using
different ways (codes):



sign-and-magnitude,
ones' complement,
two's complement.
Representation
sign-and-magnitude
ones' complement
two's complement
2009-2013
A≥0
0.A
0.A
0.A
©S.Maciulevičius
A<0
1.A
1.A
1.A+1
14
Representing of negative integers
Let we use one byte (8 bits) for representing of integer.
The integers +108 and -108 (10810=11011002) can be
represented as follows:
Representation
sign-and-magnitude
ones' complement
two's complement
+108
0.1101100
0.1101100
0.1101100
-108
1.1101100
1.0010011
1.0010100
In two's complement representation bit weigths can be
interpreted as: 1.0010100
-128
64
32
16
8
Indeed: -128 + 16 +4 = -108
2009-2013
©S.Maciulevičius
4
2
1
15
Longer word
Let we have 8-bit integer 108. If word length is 16 bit, free
positions will be filled by 0 or 1 depending on sign and
representation:
Integer
Representation
+108
-108
-108
-108
2009-2013
sign-andmagnitude
ones'
complement
two's
complement
n=8
n=16
0.1101100
0.000000001101100
1.1101100
1.000000001101100
1.0010011
1.111111110010011
1.0010100
1.111111110010100
©S.Maciulevičius
16
Integer addition and subtraction
Both operations (addition and subtraction) are
executed by the same device, so integer
subtraction is replaced by addition after
changing sign of subtrahend by the opposite :
Operation needed
to execute
A+B
A-B
-A + B
-A - B
2009-2013
©S.Maciulevičius
Addition to be
executed
A+B
A + (-B)
(-A) + B
(-A) + (-B)
17
Integer addition using adder
Addition of two bits, taking
into account carry, is
carried out as follows :
(here ai, bi – operands,
ci – carry to this
position,
si – sum,
ci+1 – carry to next
position)
si
ci+1
Σ
ci
ai
0
0
0
0
1
1
1
1
bi
0
0
1
1
0
0
1
1
ci
0
1
0
1
0
1
0
1
ci+1
0
0
0
1
0
1
1
1
si
0
1
1
1
0
0
0
1
ai bi
2009-2013
©S.Maciulevičius
18
Integer addition
In a computer algebraic addition ir realized
using two's complement representation. All
the bits (including sign bit) are interpreted
similar.
Let us see, how two integers +77 and -108
(+7710=0.1001101, -10810=1.00101002)
will be added using two's complement
representation:
2009-2013
©S.Maciulevičius
19
Integer addition
+77
-108
- 31
0.1001101
+ 1.0010100
1.1100001
1.1100001 (two's compl. ) =
1.0011111 (sign-and-magn.) = -31
Now let us change signes of operands by
opposites; in two's complement representation
-7710= 1.0110011, o 10810=0.11011002:
1.0110011
+0.1101100
10.0011111
2009-2013
Ignoring most left “1”, we
get 0.0011111= + 31
©S.Maciulevičius
20
Integer addition
Let both operands are positiv: +7710= 0. 1001101,
+10810= 0.11011002.
Add them:
77
+108
185
0.1001101
+0.1101100
1.0111001
The sum (result) is negative. Of course, this is
impossible while both operands are positive
Please note that the sum should be equal to 185, while
the maximum positive number that can be written in
this format is +127. Thus, we have a situation called
overflow
2009-2013
©S.Maciulevičius
21
Integer addition
The same picture we have, if you add a negative integer 7710 = 1. 1001101 (sign-and-magn.) = 1.0110011 (two's compl.)
and -10810= 1.1101100 (sign-and-magn.) = 1.0010100 (two's
compl.):
- 77 1.0110011
-108 +1.0010100
-185 0.1000111
The sum (result) is positive. Of course, this is impossible
while both operands are negative
Please note that the sum should be equal to -185, while
the maximum (in absolute value) negative number that
can be written in this format is -128. Thus, we have
again a situation called overflow
2009-2013
©S.Maciulevičius
22
Floating point numbers
Floating point describes a system for numerical
representation in which a string of digits (or
bits) represents a rational number
Floating point number consists of:


A signed digit string of a given length in a given base.
This is known as the significand, or sometimes the
mantissa. The length of the significand determines
the precision to which numbers can be represented.
A signed integer exponent, also referred to as the
characteristic, which modifies the magnitude of the
number
2009-2013
©S.Maciulevičius
23
Floating point numbers
E.g., the 137,15 can be written as follows:
137,15 = 13,715×101 =
= 1,3715×102 =
= 0,13715×103 =
= 0,013715×104 = ±M×10e .
Here M is mantissa, e – exponent.
The bolded expression is called normalized. In
this case a decimal mantissa M must satisfy
the condition
0,1 ≤ M < 1
2009-2013
©S.Maciulevičius
24
IEEE 754 encoding
Now computers are using the IEEE 754 encoding.
The value A of normalized floating point numbers
can be calculated using the formula:
s
A = (-1) × 1,M × 2E-bias
Here are:
s – sign bit (1 – for negative, 0 – for positive numbers),
M – mantissa,
E – biased exponent: E = bias + e
2009-2013
©S.Maciulevičius
25
IEEE 754 encoding
According to this standard of encoding following
main formats for representing of floating point
numbers are in use:
a) 32 bit, single precision format:
s
E
M
b) 64 bit, double precision format:
...
s
2009-2013
E
M
©S.Maciulevičius
26
IEEE 754 encoding
Sign bit allways is in 1st position; for positive
numbers s = 0, for negative numbers s = 1
(while (-1)0 = +1, (-1)1 = -1)
Length of E and M fields, value of bias depend
from n:
n
E bits
M bits
bias
Maximal number
32
8
23
127
1038
64
11
52
1023
10308
2009-2013
©S.Maciulevičius
27
IEEE 754 encoding
Consider as example number 17,25 which in
binary form is:
17,25 = +10001,01 =
= +1,000101×24.
Comparing it with formula A = (-1)s × 1,M × 2E-bias,
we determine: s = 0, M = 000101, E – bias =
E – 127=4; i.e., E=127+4=131 (=128+3).
So:
0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 ...
2009-2013
©S.Maciulevičius
000
28
IEEE 754 encoding
Consider as example now the number 0,375 which
in binary form is:
0,375 = +0,011 = +1,1×2-2.
Comparing it with formula A = (-1)s × 1,M × 2E-bias
again we determine : s = 0, М = 1, E – bias = E
– 127 = -2; i.e., E=127 – 2=125.
So:
001111101100000
2009-2013
©S.Maciulevičius
...
00000
29
IEEE 754 encoding
According to rules of this standard the value
of subnormal floating point numbers can
be calculated using the formula:
A = (-1)s × 0,M × 2-bias
Exponent in this case is equal 0, mantissa subnormal
2009-2013
©S.Maciulevičius
30
IEEE 754 encoding
Particular values are reserved to represent some
floating point numbers:
Part. value
Sign bit Exponent Mantissa
+0
0
0
0
-0
1
0
0
+
0
FF
0
-
1
FF
0
NaN
0/1
FF
0
Subnormal numbers
0/1
0
0
NaN is a value or symbol that is usually produced as the result of an
operation on invalid input operands (e.g., in operations 0/0 and -1)
2009-2013
©S.Maciulevičius
31
Decimal numbers
In binary-coded decimals (BCD), a digit is usually represented by four
bits which, in general, represent the values/digits/characters 0–9.
Other bit combinations are usually used for a sign (in most cases
1100 represents +, and 1101 represents −)
BCD usualy are represented in "packed“ or compressed form where 1
byte encode two decimal digits. In such case +127 uses two
bytes and looks so:
,
00010010 01111100
−127 – so:
00010010 01111101
IBM/360 used uncompressed form, where 1 byte encodes one
decimal digit: 4 bits for digit and 4 bits for “zone”. Most right
byte encodes sign and digit. “Zone” is encoded by 1111
2009-2013
©S.Maciulevičius
32
Character encoding
Most modern character-encoding schemes
are based on ASCII (American Standard
Code for Information Interchange).
There are two variants of encoding:
 basic, which uses 7 bits for a symbol (the
8th bit - for control);
 extended, which uses 8 bits for a symbol,
the additional combinations are used for
encoding of national and pseudographic
characters
2009-2013
©S.Maciulevičius
33
Character encoding
Part of ASCII encoding table is presented below:
0
1
2
3
4
5
6
0 1 2 3
0
! 1
“ 2
# 3
$ 4
% 5
& 6
2009-2013
4
@
A
B
C
D
E
F
5
P
Q
R
S
T
U
V
6
‘
a
b
c
d
e
f
7
p
q
r
s
t
u
v
8
А
Б
В
Г
Д
Е
Ж
©S.Maciulevičius
9
Р
С
Т
Ы
Ф
Х
Ц
A B C D E F
а
└
р
б
┴
с
в
┬
т
г
├
ы
д
ф
е
х
ж
ц
34