Monthly Archives: February 2014

IEEE-754 pt 3 – Increased granularity

In part 2 we showed that the position of the implicit bit i was also the width of the biased exponent. That makes the bias i-1 bits wide. Since all bits of the bias are 1, the value of the bias is 2i-1-1. With one bit for the sign, that leaves n-i-1 bits for the width of the significand. By specifying i as a function of n the storage format becomes fully defined. This works not only for eight-bit boundaries but for the six-bit boundaries of Color My Data eight-bit compressed binary format (CBF8). CBF8 is designed for loss-less data exchange using binary formats. One base-64 digit could represent plus or minus sixteenths between 0 and 0.9375; eighths between 1 and 1.875; fourths between 2 and 3.75, infinity, quiet NaN or NaN with up to two signals. That represents a potential compression of 87.5% over double precision WITH NO LOSS OF DATA.
The graph below shows how i varies with n in comparison to the current standard.ieee-754 graph

The graph was generated from the following tables. Here are the column definitions.
Bytes (Digits):

Data storage size in bytes or base-64 digits
Bits:
Data storage size in bits (8 bits per byte; 6 bits per base-64 digit)
Sign:
The sign is a one-bit value
BiasExp:
The width, i of the biased exponent in bits
Significand:
The width of the significand in bits
Precision:
The number of decimal digits of precision (Ada digits)
DynRange:
Twice the bias converted to decimal digits
bytes bits sign biasExp significand precision bias dynRange
1 8 1 3 4 1.20 3 1.81
2 16 1 5 10 3.01 15 9.03
3 24 1 7 16 4.82 63 37.93
4 32 1 8 23 6.92 127 76.46
5 40 1 9 30 9.03 255 153.53
6 48 1 10 37 11.14 511 307.65
7 56 1 10 45 13.55 511 307.65
8 64 1 11 52 15.65 1023 615.91
9 72 1 11 60 18.06 1023 615.91
10 80 1 12 67 20.17 2047 1232.42
11 88 1 12 75 22.58 2047 1232.42
12 96 1 13 82 24.68 4095 2465.44
13 104 1 13 90 27.09 4095 2465.44
14 112 1 14 97 29.20 8191 4931.47
15 120 1 14 105 31.61 8191 4931.47
16 128 1 15 112 33.72 16383 9863.55
digits bits sign biasExp significand precision bias dynRange
1 6 1 2 3 0.90 1 0.60
2 12 1 4 7 2.11 7 4.21
3 18 1 5 12 3.61 15 9.03
4 24 1 7 16 4.82 63 37.93
5 30 1 8 21 6.32 127 76.46
6 36 1 8 27 8.13 127 76.46
7 42 1 9 32 9.63 255 153.53
8 48 1 10 37 11.14 511 07.65
9 54 1 10 43 12.94 511 307.65
10 60 1 11 48 14.45 1023 615.91
11 66 1 11 54 16.26 1023 615.91
12 72 1 11 60 18.06 1023 615.91
13 78 1 12 65 19.57 2047 1232.42
14 84 1 12 71 21.37 2047 1232.42
15 90 1 13 76 22.88 4095 2465.44
16 96 1 13 82 24.68 4095 2465.44
17 102 1 13 88 26.49 4095 2465.44
18 108 1 14 93 28.00 8191 4931.47
19 114 1 14 99 29.80 8191 4931.47
20 120 1 14 105 31.61 8191 4931.47
21 126 1 15 110 33.11 16383 9863.55
22 132 1 15 116 34.92 16383 9863.55

IEEE-754 pt 2 – Composition

There are five important components to an IEEE-754 floating point number

  1. sign – a one-bit value indicating whether the value is negative
  2. biased exponent – determines the magnitude of the floating-point value
  3. significand – the precision of the floating point value derives from its width
  4. bias – the dynamic range of the floating point value derives from its width
  5. implicit bit – has an implied weight of 1.

In the following illustrations let us break down the composition of a floating point value n bits wide. Constants are shown as 0 and 1. The variable x represents any 0 or 1; the variable y represents at least one 1 and the variable z represents at least one 0.  Note that the position i of the implicit bit (blue) is also the width of the biased exponent (orange) and is the least significant bit (LSB) of both the bias (green) and the biased exponent. The sign (red) is always the most significant bit (MSB) and the significand (yellow) is always aligned on the implicit bit.  The weight of each bit of the significand is one half the weight of the predecessor bit. Thus, bit i+1 is one half the weight of the implicit bit or one half. This means the significand represents a value between 1.0 up to but not including 2.0. The product of this value and 2biasedExponent-bias is the magnitude. Applying the sign to the magnitude yields what is called the normalized value.

ieee-754 comp

The minimum value for a biased exponent is zero. The IEEE-754 standard reserves this value for zero and subnormal values.  The maximum value for the biased exponent is the sum of twice the bias and one (i.e. the exponent with bias removed is greater than the bias). The IEEE-754 standard reserves this value for infinity and Not-a-Number (NaN) When the significand is zero, the value is an infinity; but, when the significand has at least one 1 the result is a NaN. When the 1 is the most significant bit of the significand and the remaining bits are zero, the NaN is called a quiet NaN. When any other bit of the significand is set, the NaN is called a signaling NaN and the set bit is the signal.

ieee-754-cases

Angle Pt 5 – A Novel GPS Location Code

Color My Data Eight-bit Compressed Binary Format (CBF-8) encodes data on six-bit boundaries using base-64 digits.  Base-64 digits include the digits 0 to 9, the upper case letters A to Z , the lower case letters a to z and the special characters $ and &. Using three digits each (18-bits) GPS positions are accurate to within 500 feet (best case) to 1000 feet (worst case). At four digits each (24-bits) position accuracy increases to 7.8 to 15.6 feet. In the United States the five digit  zip code gets you the nearest post office. Zip plus four narrows it much further. By contrast, using the angle primitive, base-64 digits, a four-digit latitude and four-digit longitude together with GPS means locating any place on the surface of the earth to an accuracy of better than 16 feet.

Angle pt 4 – Quantization Errors

Fixed point types have quantization errors.  Quantization errors can be as high as the weight of the least significant bit. For an n-bit angle primitive, the weight of the least significant bit is 22-n. For values near zero the angle and its arctangent are approximately the same. Thus, the best case quantization error is the weight of the least signficant bit.
The tangent function is non-linear. Quantization error increases as the square of the secant. For values near +/-1 this means the quantization error is nearly twice the weight of the least significant bit.

To translate quantization errors into distances along the surface of the earth we will use pi radians equals 10800 nautical miles or 20,000 kilometers. (A nautical mile is about 6076 feet). As seen in the following table, it takes very few bytes to get high accuracy. For example, a four-byte angle primitive has a quantization error of between 0.366 inches (best case) and 0.733 inches (worst case = 2x best case). Using a four-byte angle type in lieu of an eight-byte double precision value in radians yields a 50% savings in memory and bandwidth.
prev continue

bytes radians distance units meters
1 0.024543693 84.375 nm 156250
2 9.58738E-05 0.329589844 nm 610.3515625
3 3.74507E-07 7.822608948 ft 2.384185791
4 1.46292E-09 0.366684794 in 0.009313226
5 5.71452E-12 0.001432362 in 3.63798E-05

Angle pt 3 – Sine and Cosine Terms

Navigation and astronomy are based on spherical trigonometry. Spherical trigonometry uses the sine and cosine of an angle extensively.  The beauty of using the tangent of the half angle is that the sine and cosine can be calculated with double precision accuracy without the need for transcendental functions as seen from the following equations.
prev continue

equations-2

Angle pt 2 – Side Opposite; Side Adjacent

When you have two sides of a right triangle, calculating the tangent of the half angle is straightforward. Calculate the square root of the sum of the squares of the side opposite, y, and the side adjacent, x (r in the equation below). When x is negative, use the ratio of -y to r-x and set the pi bit; otherwise, use the ratio of y to r+x and clear the pi bit. Note that the ratio is always between -1.0 and 1.0.
prev continue
equations-1

Angle pt 1 – A New Primitive Data Type

Since GPS, navigation and astronomy all perform calculations on angles, why not have a dedicated angle data type that would compress location data and simplify trigonometric calculations?  Allow me to introduce you to the angle type.

I think of a primitive as a value that can be placed in a machine register. Values like char, int, long, float, double and boolean come to mind. The angle primitive has two fields: a boolean pi-bit and a fixed-point field designed to hold a value between -1.0 up to but not including 1.0. Let the fixed point value be the tangent of the half angle. The arctangent is a value between -pi/4 and +pi/4. Twice the arctangent ranges between -pi/2 and pi/2. The pi bit adds or subtracts pi yielding an angle between -pi and pi; a full circle.  In the following illustration the pi bit is in orange and the fixed point value is in green.
continue
angle bits

IEEE-754 pt 1 Floating Point Standard

Floating point arithmetic allows one to deal with numbers that are very large or very small by combining a number with an exponent. In the early 80s there were many approaches to doing floating-point arithmetic. It was like the software equivalent of the  tower of Babel. In 1983 the military’s Ada programming language took the approach of specifying the number of digits of precision and sweeping the implementation details under the rug. Binary interoperability became possible when the IEEE released the IEEE-754 floating point standard. Floating point units (FPUs) that implemented the standard quickly emerged. For binary formats the standard specifies four sizes: 16, 32, 64 and 128 bits. In Ada these would be precisions of 3, 6, 15 or 33 digits.  Half-precision is a storage only format (i.e. it is not used for computation).  That begs the question, if the precision requirement is for an in-between value (e.g. 9 or 11 digits), can we conserve memory with storage formats that meet the requirements for precision but also take less storage? The answer is absolutely yes, but in order to do that we need to add storage-only binary formats to the IEEE-754 standard and understand the implications of widening a storage format to a computational format and narrowing a computational format to fit within a storage only format.