Transcript PPT - the GMU ECE Department

ECE 645: Lecture 5
Number Representation
Part 2
Little-Endian vs. Big-Endian Representations
Floating Point Representations
Rounding
Representation of the Galois Field elements
Required Reading
Endianness,
from Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Endianness
Behrooz Parhami,
Computer Arithmetic: Algorithms and Hardware Design
Chapter 17, Floating-Point Representations
Little-Endian vs. Big-Endian
Representation of
Integers
Little-Endian vs. Big-Endian Representation
A0 B1 C2 D3 E4 F5 67 8916
MSB
LSB
Little-Endian
Big-Endian
0
MSB = A0
B1
C2
D3
E4
F5
67
LSB = 89
address
MAX
LSB = 89
67
F5
E4
D3
C2
B1
MSB = A0
Little-Endian vs. Big-Endian Camps
0
MSB
LSB
...
...
address
MSB
LSB
MAX
Big-Endian
Motorola 68xx, 680x0
Bi-Endian
IBM
Hewlett-Packard
Sun SuperSPARC
Internet TCP/IP
Motorola Power PC
Silicon Graphics MIPS
Little-Endian
Intel
AMD
DEC VAX
RS 232
Little-Endian vs. Big-Endian
Origin of the terms
Jonathan Swift, Gulliver’s Travels
• A law requiring all citizens of Lilliput to break their soft-eggs
at the little ends only
• A civil war breaking between the Little Endians and
the Big-Endians, resulting in the Big Endians taking refuge on
a nearby island, the kingdom of Blefuscu
• Satire over holy wars between Protestant Church of England
and the Catholic Church of France
Little-Endian vs. Big-Endian
Advantages and Disadvantages
Big-Endian
• easier to determine a sign of
the number
• easier to compare two numbers
• easier to divide two numbers
• easier to print
Little-Endian
• easier addition and multiplication
of multiprecision numbers
Pointers (1)
Big-Endian
0
address
MAX
Little-Endian
int * iptr;
89
67
F5
E4
D3
C2
B1
A0
(* iptr) = 8967;
iptr+1
(* iptr) = 6789;
Pointers (2)
Big-Endian
0
address
MAX
Little-Endian
long int * lptr;
89
67
F5
E4
D3
C2
B1
A0
(* lptr) = 8967F5E4;
lptr + 1
(* lptr) = E4F56789;
Floating Point Representations
The ANSI/IEEE standard floatingpoint number representation formats
Originally IEEE 754-1985.
Superseded by IEEE 7542008 Standard.
Short (32-bit) format
8 bits,
bias = 127,
–126 to 127
Sign Exponent
11 bits,
bias = 1023,
–1022 to 1023
23 bits for fractional part
(plus hidden 1 in integer part)
Significand
52 bits for fractional part
(plus hidden 1 in integer part)
Long (64-bit) format
Table 17.1 Some features of the ANSI/IEEE standard
floatingpoint number representation formats
Exponent Encoding
Exponent encoding in 8 bits for the single/short (32-bit)
ANSI/IEEE format
Decimal code
Hex code
Exponent value
0
00
1
01
–126
126 127 128
7E 7F 80
–1
0
+1
254 255
FE FF
+127
1.f  2e
f = 0: Representation of 0
f  0: Representation of denormals,
0.f  2–126
f = 0: Representation of 
f  0: Representation of NaNs
Fig. 17.4 Denormals in the IEEE single-precision format.
New IEEE 754-2008 Standard
Basic Formats
New IEEE 754-2008 Standard
Binary Interchange Formats
Requirements for Arithmetic
Results of the 4 basic arithmetic operations (+, -, , ) as well as squarerooting must match those obtained
if all intermediate computations were infinitely precise
That is, a floating-point arithmetic operation should introduce
no more imprecision than the error attributable to the final
rounding of a result that has no exact representation (this is
the best possible)
Example:
(1 + 2-1)
Exact result
Rounded result

(1 + 2-23 )
1 + 2-1 + 2-23 + 2-24
1 + 2-1 + 2-22
Error = ½ ulp
Rounding 101
Rounding Modes
The IEEE 754-2008 standard includes five
rounding modes:
Default:
Round to nearest, ties to even (rtne)
Optional:
Round to nearest, ties away from 0 (rtna)
Round toward zero (inward)
Round toward + (upward)
Round toward – (downward)
Required Reading
Parhami,
Chapter 17.5, Rounding schemes
Rounding Algorithms 101
http://www.diycalculator.com/popup-m-round.shtml
30
Rounding
• Rounding occurs when we want to approximate a more
precise number (i.e. more fractional bits L) with a less
precise number (i.e. fewer fractional bits L')
• Example 1:
• old: 000110.11010001 (K=6, L=8)
• new: 000110.11 (K'=6, L'=2)
• Example 2:
• old: 000110.11010001 (K=6, L=8)
• new: 000111. (K'=6, L'=0)
• The following pages show rounding from L>0 fractional bits
to L'=0 bits, but the mathematics hold true for any L' < L
• Usually, keep the number of integral bits the same K'=K
31
Rounding Equation
Whole part
Fractional part
xk–1xk–2 . . . x1x0 . x–1x–2 . . . x–l
Round
yk–1yk–2 . . . y1y0
• y = round(x)
32
Rounding Techniques
• There are different rounding techniques:
• 1) truncation
• results in round towards zero in signed magnitude
• results in round towards -∞ in two's complement
• 2) round to nearest number
• 3) round to nearest even number (or odd number)
• 4) round towards +∞
• Other rounding techniques
• 5) jamming or von Neumann
• 6) ROM rounding
• Each of these techniques will differ in their error depending
on representation of numbers i.e. signed magnitude versus
two's complement
• Error = round(x) – x
33
1) Truncation
The simplest possible rounding scheme: chopping or truncation
xk–1xk–2 . . . x1x0 . x–1x–2 . . . x–l
trunc
xk–1xk–2 . . . x1x0
ulp
•
Truncation in signed-magnitude results in a number chop(x) that is always of smaller
magnitude than x. This is called round towards zero or inward rounding
• 011.10 (3.5)10  011 (3)10
• Error = -0.5
• 111.10 (-3.5)10  111 (-3)10
• Error = +0.5
•
Truncation in two's complement results in a number chop(x) that is always smaller
than x. This is called round towards -∞ or downward-directed rounding
• 011.10 (3.5)10  011 (3)10
• Error = -0.5
• 100.01 (-3.5)10  100 (-4)10
• Error = -0.5
34
Truncation Function Graph: chop(x)
chop( x)
chop(x)
4
4
3
3
2
2
1
1
x
–4
–3
–2
–1
1
2
3
4
x
–4
–3
–2
–1
1
–1
–1
–2
–2
–3
–3
–4
–4
Fig. 17.5 Truncation or chopping
of a signed-magnitude number
(same as round toward 0).
2
3
4
Fig. 17.6 Truncation or chopping
of a 2’s-complement number
(same as round to -∞).
35
Bias in two's complement truncation
•
•
X
(binary)
X
(decimal)
chop(x)
(binary)
chop(x)
(decimal)
Error
(decimal)
011.00
3
011
3
0
011.01
3.25
011
3
-0.25
011.10
3.5
011
3
-0.5
011.11
3.75
011
3
-0.75
100.01
-3.75
100
-4
-0.25
100.10
-3.5
100
-4
-0.5
100.11
-3.25
100
-4
-0.75
101.00
-3
101
-3
0
Assuming all combinations of positive and negative values of x equally possible,
average error is -0.375
In general, average error = -(2-L'-2-L )/2, where L' = new number of fractional bits
36
Implementation truncation in hardware
• Easy, just ignore (i.e. truncate) the fractional digits
from L to L'+1
xk-1 xk-2 .. x1 x0. x-1 x-2 .. x-L
=
yk-1 yk-2 .. y1 y0. ignore (i.e. truncate the rest)
37
2) Round to nearest number
• Rounding to nearest number what we normally think of when say round
• 010.01 (2.25)10  010 (2)10
• Error = -0.25
• 010.11 (2.75)10  011 (3)10
• Error = +0.25
• 010.00 (2.00)10  010 (2)10
• Error = +0.00
• 010.10 (2.5)10  011 (3)10
• Error = +0.5 [round-half-up (arithmetic rounding)]
• 010.10 (2.5)10  010 (2)10
• Error = -0.5 [round-half-down]
38
Round-half-up: dealing with negative numbers
• Rounding to nearest number what we normally think of when say round
• 101.11 (-2.25)10  110 (-2)10
• Error = +0.25
• 101.01 (-2.75)10  101 (-3)10
• Error = -0.25
• 110.00 (-2.00)10  110 (-2)10
• Error = +0.00
• 101.10 (-2.5)10  110 (-2)10
• Error = +0.5 [asymmetric implementation]
• 101.10 (-2.5)10  101 (-3)10
• Error = -0.5 [symmetric implementation]
39
Round to Nearest Function Graph: rtn(x)
Round-half-up version
Asymmetric implementation
Symmetric implementation
rtn(x)
rtn(x)
4
4
3
3
2
2
1
1
x
–4
–3
–2
–1
1
2
3
4
x
–4
–3
–2
–1
1
–1
–1
–2
–2
–3
–3
–4
–4
2
3
4
40
Bias in two's complement round to nearest
Round-half-up asymmetric implementation
•
X
(decimal)
rtn(x)
(binary)
rtn(x)
(decimal)
Error
(decimal)
010.00
2
010
2
0
010.01
2.25
010
2
-0.25
010.10
2.5
011
3
+0.5
010.11
2.75
011
3
+0.25
101.01
-2.75
101
-3
-0.25
101.10
-2.5
110
-2
+0.5
101.11
-2.25
110
-2
+0.25
110.00
-2
110
-2
0
Assuming all combinations of positive and negative values of x equally possible, average error
is +0.125
•
•
•
X
(binary)
Smaller average error than truncation, but still not symmetric error
We have a problem with the midway value, i.e. exactly at 2.5 or -2.5 leads to positive error bias
always
Also have the problem that you can get overflow if only allocate K' = K integral bits
•
•
Example: rtn(011.10)  overflow
This overflow only occurs on positive numbers near the maximum positive value, not on negative
numbers
41
Implementing round to nearest (rtn) in hardware
Round-half-up asymmetric implementation
• Two methods
• Method 1: Add '1' in position one digit right of new LSB
(i.e. digit L'+1) and keep only L' fractional bits
=
xk-1 xk-2 .. x1 x0. x-1 x-2 .. x-L
+
1
yk-1 yk-2 .. y1 y0. y-1
ignore (i.e. truncate the rest)
• Method 2: Add the value of the digit one position to right
of new LSB (i.e. digit L'+1) into the new LSB digit (i.e.
digit L) and keep only L' fractional bits
xk-1 xk-2 .. x1 x0. x-1 x-2 .. x-L
+ x-1
yk-1 yk-2 .. y1 y0.
ignore (i.e truncate the rest)
42
Round to Nearest Even Function Graph: rtne(x)
•
To solve the problem with the midway value we implement round to nearest-even
number (or can round to nearest odd number)
rtne(x)
R*(x)
4
4
3
3
2
2
1
1
x
–4
–3
–2
–1
1
2
3
4
x
–4
–3
–2
–1
1
–1
–1
–2
–2
–3
–3
–4
–4
Fig. 17.8 Rounding to the
nearest even number.
2
3
4
Fig. 17.9 R* rounding or rounding
to the nearest odd number.
43
Bias in two's complement round to nearest even
(rtne)
X
(binary)
X
(decimal
)
rtne(x)
(binary)
rtne(x)
(decimal)
Error
(decimal)
000.10
0.5
000
0
-0.5
001.10
1.5
010
2
+0.5
010.10
2.5
010
2
-0.5
011.10
3.5
0100 (overfl)
4
+0.5
100.10
-3.5
100
-4
-0.5
101.10
-2.5
010
-2
+0.5
110.10
-1.5
010
-2
-0.5
111.10
-0.5
000
0
+0.5
• average error is now 0 (ignoring the overflow)
• cost: more hardware
44
4) Rounding towards infinity
• We may need computation errors to be in a known direction
• Example: in computing upper bounds, larger results are
acceptable, but results that are smaller than correct values
could invalidate upper bound
• Use upward-directed rounding (round toward +∞)
• up(x) always larger than or equal to x
• Similarly for lower bounds, use downward-directed rounding
(round toward -∞)
• down(x) always smaller than or equal to x
• We have already seen that round toward -∞ in two's complement
can be implemented by truncation
45
Rounding Toward Infinity Function Graph: up(x)
and down(x)
up(x)
down(x)
down(x) can be implemented by chop(x) in
two's complement
46
Two's Complement Round to Zero
• Two's complement round to zero (inward rounding)
also exists
inward(x )
4
3
2
1
x
–4
–3
–2
–1
1
2
3
4
–1
–2
–3
–4
47
Other Methods
• Note that in two's complement round to nearest (rtn)
involves an addition which may have a carry
propagation from LSB to MSB
• Rounding may take as long as an adder takes
• Can break the adder chain using the following two
techniques:
• Jamming or von Neumann
• ROM-based
48
5) Jamming or von Neumann
jam(x)
Chop and force the LSB
of the result to 1
4
3
2
1
x
–4
–3
–2
–1
1
–1
–2
2
3
Simplicity of chopping,
with the near-symmetry
or ordinary rounding
4
Max error is comparable
to chopping (double that
of rounding)
–3
–4
49
6) ROM Rounding
ROM(x)
Fig. 17.11 ROM rounding
with an 8  2 table.
4
3
Example: Rounding with a
32  4 table
2
1
x
–4
–3
–2
–1
1
2
3
4
–1
–2
–3
–4
xk–1 . . . x4x3x2x1x0 . x–1x–2 . . . x–l
ROM address
Rounding result is the same
as that of the round to nearest
scheme in 31 of the 32
possible cases, but a larger
error is introduced when
x3 = x2 = x1 = x0 = x–1 = 1
ROM
xk–1 . . . x4y3y2y1y0
ROM data
50
Representation
of the Galois Field
elements
Evariste Galois (1811-1832)
Evariste Galois (1811-1832)
Studied the problem of finding algebraic solutions for the general
equations of the degree  5, e.g.,
f(x) = a5x5+ a4x4+ a3x3+ a2x2+ a1x+ a0 = 0
Answered definitely the question which specific equations of
a given degree have algebraic solutions.
On the way, he developed group theory,
one of the most important branches of modern mathematics.
Evariste Galois (1811-1832)
1829
Galois submits his results for the first time to
the French Academy of Sciences
Reviewer 1
Augustin-Luis Cauchy forgot or lost the communication.
1830
Galois submits the revised version of his manuscript,
hoping to enter the competition for the Grand Prize
in mathematics
Reviewer 2
Joseph Fourier – died shortly after receiving the manuscript.
1831 Third submission to the French Academy of Sciences
Reviewer 3
Simeon-Denis Poisson – did not understand the manuscript
and rejected it.
Evariste Galois (1811-1832)
May 1832
Galois provoked into a duel
The night before the duel he wrote a letter to his friend
containing the summary of his discoveries.
The letter ended with a plea:
“Eventually there will be, I hope, some people who
will find it profitable to decipher this mess.”
May 30, 1832 Galois was grievously wounded in the duel and died
in the hospital the following day.
1843
Galois manuscript rediscovered by Joseph Liouville
1846
Galois manuscript published for
the first time in a mathematical journal.
Field
Set F, and two operations typically denoted by
(but not necessarily equivalent to)
+ and *
Set F, and definitions of these two operations must
fulfill special conditions.
Examples of fields
Infinite fields
{
R= set of real numbers,
+ addition of real numbers
* multiplication of real numbers
}
Finite fields
{
set Zp={0, 1, 2, … , p-1},
+ (mod p): addition modulo p,
* (mod p): multiplication modulo p
}
Finite Fields = Galois Fields
GF(pm)
GF(p)
Arithmetic
operations
present
in many libraries
p – prime
pm – number of
elements in the field
GF(2m)
Polynomial basis
representation
Most significant
special cases
Normal basis
representation
Fast in hardware
Fast squaring
Quotient and remainder
Given integers a and n, n>0
! q, r  Z
such that
a = q n + r
and
0r<n
q – quotient
a
q=
n
r – remainder
(of a divided by n)
a
r = a - q n = a –
n =
n
= a mod n
= a div n
32 mod 5 =
-32 mod 5 =
Integers coungruent modulo n
Two integers a and b are congruent modulo n
(equivalent modulo n)
written a  b
iff
a mod n = b mod n
or
a = b + kn, k  Z
or
n|a-b
Laws of modular arithmetic
Rules of addition, subtraction and multiplication
modulo n
a + b mod n = ((a mod n) + (b mod n)) mod n
a - b mod n = ((a mod n) - (b mod n)) mod n
a  b mod n = ((a mod n)  (b mod n)) mod n
9 · 13 mod 5 =
25 · 25 mod 26 =
Laws of modular arithmetic
Regular addition
a+b = a+c
iff
b=c
Regular multiplication
If a  b = a  c
and a  0
then
b=c
Modular addition
a+b  a+c (mod n)
iff
b  c (mod n)
Modular multiplication
If a  b  a  c (mod n)
and gcd (a, n) = 1
then
b  c (mod n)
Modular Multiplication: Example
18
63
 42 (mod 8)
 6  7 (mod 8)
3  7 (mod 8)
x
0
1
2
3
4
5
6
7
6  x mod 8
0
6
4
2
0
6
4
2
x
0
1
2
3
4
5
6
7
5  x mod 8
0
5
2
7
4
1
6
3
Finite Fields = Galois Fields
GF(pm)
GF(p)
Arithmetic
operations
present
in many libraries
p – prime
pm – number of
elements in the field
GF(2m)
Polynomial basis
representation
Most significant
special cases
Normal basis
representation
Fast in hardware
Fast squaring
Elements of the Galois Field GF(2m)
Binary representation
(used for storing and processing in computer systems):
A = (am-1, am-2, …, a2, a1, a0)
ai  {0, 1}
Polynomial representation
(used for the definition of basic arithmetic operations):
m-1
A(x) =  aixi = am-1xm-1 + am-2xm-2 + …+ a2x2 + a1x+a0
i=0
 multiplication
+ addition modulo 2 (XOR)
Addition and Multiplication
in the Galois Field GF(2m)
Inputs
A = (am-1, am-2, …, a2, a1, a0)
B = (bm-1, bm-2, …, b2, b1, b0)
ai , bi  {0, 1}
Output
C = (cm-1, cm-2, …, c2, c1, c0)
ci  {0, 1}
Addition in the Galois Field GF(2m)
Addition
A
B
C



A(x)
B(x)
C(x) = A(x) + B(x) =
= (am-1+bm-1)xm-1 + (am-2+bm-2)xm-2+ …+
+ (a2+b2)x2 + (a1+b1)x + (a0+b0) =
= cm-1xm-1 + cm-2xm-2 + …+ c2x2 + c1x+c0
 multiplication
+ addition modulo 2 (XOR)
ci = ai + bi = ai XOR bi
C = A XOR B
Multiplication in the Galois Field GF(2m)
Multiplication
A
B
C



A(x)
B(x)
C(x) = A(x)  B(x) mod P(X)
= cm-1xm-1 + cm-2xm-2 + …+ c2x2 + c1x+c0
P(x) - irreducible polynomial of the degree m
P(x) = pmxm + pm-1xm-1 + …+ p2x2 + p1x+p0