01.3 Fractional Binary

fds

In binary there are two ways to represent fractional numbers :

• Fixed point notation (where there are a fixed known amount of bits that are after the point)
• Floating point notation (where the point is not fixed and can move, using an exponential)

Fixed point representation

We have an entire part $x_{\text{int}}$ and a fractional part $x_{\text{fr}}$ :

$$x=x_{\text{int}}+x_{\text{fr}}$$

Let’s give it a true mathematical definition :

$$x=\sum _{i=-f}^{m-1}{X}_i{2}^i$$

The point is fixed after the $0^{th}$ bit → Hence “fixed point”

If the point is not shown, we assume it is to the right of the least significant digit

This principle applies to binary just as well as for decimal.

Precision

The precision is the maximum amount of bits that can be used It is given by

$$\text{Precision}(x)=m+f$$

Resolution

The resolution is the smallest possible distance between two consecutive numbers It is given by

$$\text{Resolution}(x)=2^{-f}$$

Range

The range is the maximum distance between the most positive and the most negative number that is representable It is given by

$$\text{Range}(x)=x_{max}-x_{min}$$

Accuracy

The accuracy is the magnitude between the value we’re trying to represent The worst case scenario is given by

$$\text{Accuracy}(x)=\frac{\text{Resolution}(x)}{2}$$

Dynamic range

The dynamic range is the ratio of the maximum absolute value that is representable, and the minimum positive absolute value that is representable It is given by

$$\text{Dynamic Range}(x)=\frac{2^{m-1}}{2^{-f}}=2^{m-1+f}$$

Floating Point Representation

Floating point representation consits of two components

• The mantissa $M^{\ast }$
• The signed exponent $E$

$$x=M^{\ast }\times b^E$$

It is similar to the scientific notation $a\cdot 10^b$

Significand

It is written in Sign and Magnitude.

However this system is redundant !!! → To avoid redundancy, we normalize the mantissa between $1$ (included )and $2$ (excluded)

Therefore there is a bit that is always on, and we hide it

The corresponding significand value becomes

$$(-1{)}^S\times \left(1+\sum _{i=1}^n{M}_{n-i}{2}^{-i}\right)$$

Exponent

The exponent is signed using “Biased Representation”

Biased Representation

It is basically unsigned, and just has its lowest (negative) value be $000\dots 0$ This allows for simple comparisons for checking what number is bigger than another. We shift the value by removing the bias $B$, which is given by

$$B=2^{n-1}-1$$

Rounding

The result of floating point operation is a real number that might require an infinite amount of digits

We have to round the number to be able to represent it

Rounding Modes

• Nearest (even when tie)
• Towards $0$ (Floor-ish)
• Towards the closest infinity (Roof-ish)

IEEE Standard 754

• $(n+1)$-bit significand
  • Sign and magnitude
  • Normalized, and one hidden bit
• $m$-bit exponent
  • Biased by $B=2^{m-1}-1$

f32	f64
Single precision	Double precision
Sign : $1$ bit	Sign : $1$ bit
Exponent : $8$ bits	Exponent : $11$ bits
Fraction : $23$ bits	Fraction : $52$ bits

Special values

Floating point zero:

• $E=0$
• $F=0$

Infinity (p/neg):

• $E$ is all ones
• $F=0$

NaN (not a number):

• Sign is $0$ or $1$
• $E$ is all ones
• $F\ne 0$

Exceptions

• The value can overflow (set the result to infinity)
• The value can underflow
• Division by 0
• Inexact result
• Invalid result

Example -- Conversion

$S=1$ $E=01111100=4+8+16+32+64-B=124-127=-3$ $M=010\cdots =.25+1\text{(hidden bit)}$ $-1.25\ast 2^{-3}=-1.25/8=-0.15625$

Arithmetic

We are interested in how to manipulate fractional numbers in binary

Fixed-Point Arithmetic

Addition and subtraction and multiplication are done the same way as for integers

Multiplication of fixed point numbers can be wrong, since we have to format the result into what the fixed point format requires

Floating-Point Arithmetic

Because we don’t want numbers to be redundant, we have to normalize the significands.

Addition/Subtraction

We format the number $x$ and $y$ as $(S_x,M_x,E_x)$ and $(S_y,M_y,E_y)$

The result is $z$ and formatted as $(S_z,M_z,E_z)$ The result is also normalized

Algorithm

Four main steps to compute and produce the result

1. We add/subtract the significands (mantissas), set the exponent

• The mantissa of the number with the smaller exponent has to be multiplied by two to the power of the difference between exponents (we call this alignement) (it can be simplified to a simple bit shift).

• We then add/remove this value to the mantissa of the other number

2. We normalize the result, and adjust the exponent (if required)
3. Round the result and normalize and adjust the exponent (if required)
4. We set the value to the Special values if required

Alignement

Definition

Alignement Three approaches :

• Align the operands to a common exponent
• Align to the common exponent minus the minimum of the two
• Align to the common exponent minus the maximum of the two

We prefer the third approach, as it is more optimized, and produces less error (as we end up removing less significant bits, so we differ by a tiny amount)

Normalization

When we normalize a number, various situations may occur

1. The result is already normalized, so we do nothing
2. The significand might overflow
   • We shift the result by one position
   • We increment the exponent by one
3. When subtracting, the result might have leading 0s
   • We shift the result to the left until there are no more leading 0s
   • Each time we shift, we decrement the exponent

Rounding

The result might not be representable, as it can be situated in between two values. We perform rounding towards the nearest value, and to the even number when there is a tie

We prefer to tie to the nearest even number, as it leads to smaller errors when the result is divided by two

Max Round-off Error

If a number is really big, we can have a huge error, in fact, the max rounding error happens when the exponent is at its max value, and the exact value in a tie