Fixed-point arithmetic

From Wikipedia, the free encyclopedia

 It has been suggested that binary scaling be merged into this article or section. (Discuss)
It has been suggested that Q (number format) be merged into this article or section. (Discuss)
This article is about a form of limited-precision arithmetic in computing. For the fixed points of a mathematical function, see fixed point (mathematics).

In computing, a fixed-point number representation is a real data type for a number that has a fixed number of digits after (and sometimes also before) the radix point (e.g., after the decimal point '.' in English decimal notation). Fixed-point number representation can be compared to the more complicated (and more computationally demanding) floating point number representation.

Fixed-point numbers are useful for representing fractional values, usually in base 2 or base 10, when the executing processor has no floating point unit (FPU) or if fixed-point provides improved performance or accuracy for the application at hand. Most low-cost embedded microprocessors and microcontrollers do not have an FPU.

Contents

[edit] Introduction and basic features

[edit] Mathematical definition, number range

Based on the verbal definition above, a fixed-point number may be written as M.F, where M represents the magnitude, i.e., the integer part, '.' is the radix point, and F represents the fractional part.

In binary fixed-point numbers, each magnitude bit represents a power of two, while each fractional bit represents an inverse power of two. Thus the first fractional bit is ½, the second is ¼, the third is ⅛ and so on. For signed fixed point numbers in two's complement format, the upper bound is given by 2m − 1 − 2 − f, and the lower bound is given by − 2m − 1, where m and f are the number of bits in M and F respectively. For unsigned values, the range is 0 to 2m − 2 − f.

In decimal fixed-point numbers, each magnitude digit represents a multiple of a power of ten, while each fractional digit represents a multiple of an inverse power of ten. Thus the first fractional digit multiplies 0.1, the second multiplies 0.01, and so on.

[edit] Comparison with floating point and BCD

Binary fixed-point numbers can represent fractional powers of two exactly, but, like floating point numbers, cannot exactly represent fractional powers of ten. If exact fractional powers of ten are desired, then a decimal format should be used. For example, one-tenth (0.1) and one-hundredth (0.01) can be represented only approximately by binary fixed-point or floating-point representations, while they can be represented exactly in decimal fixed-point or floating-point representations. These representations may be encoded in many ways, including BCD.

A fixed-point number can exactly represent any integer within the range determined by the magnitude bits. A floating-point number can have a wider range of values (a range greater than ±21023 in IEEE 754 machines). However, the range in which a floating-point number can exactly represent any integer is often smaller than a fixed-point number of the same size (±253 in IEEE 754 machines).

[edit] Programming language implementations

A common use of fixed-point BCD numbers is for storing monetary values, where the inexact values of binary floating-point numbers are often a liability. Historically, fixed-point representations were the norm for decimal data types; for example, in PL/I or COBOL. The Ada programming language includes built-in support for both fixed-point (in two variants: ordinary and decimal) and floating-point. JOVIAL and Coral 66 also provide both floating- and fixed-point types.

Very few computer languages include built-in support for fixed point values, because for most applications, binary or decimal floating-point representations are usually simpler to use and accurate enough. Floating-point representations are easier to use than fixed-point representations, because they can handle a wider dynamic range and do not require programmers to specify the number of digits after the radix point. However, if they are needed, fixed-point numbers can be implemented even in programming languages like C and C++, which do not commonly include such support.

With the publication of ISO/IEC TR 18037:2004, fixed-point data types are specified for the C programming language; vendors are expected to implement the language extensions for fixed point arithmetic in coming years.

[edit] Nomenclature

There are various notations used to represent word length and radix point in a fixed-point number. (Unfortunately there is no standard support in common programming languages either.)

  • One common notion is the "Q" prefix, where the number following the Q specifies the fractional bits to the right of the radix point. For example, Q15 represents a number with 15 fractional bits. This notation is ambiguous since it does not specify the word length, however it is usually assumed that the word length is either 16 or 32 bits depending on the target processor in use. The unambiguous form of the "Q" notation is a Q followed by a dotted pair of numbers that represent the number of integer bits to the left of the decimal point followed by the number of fractional bits. Since the entire word is a 2's complement integer, a sign bit is implied. For example, Q1.30 describes a number with 1 integer bit and 30 fractional bits stored as a 32-bit 2's complement integer. Q format notation references from Texas Instruments[1]Appendix A.2 and from The MathWorks [2].
  • Another notation, the "fx" prefix, is similar but uses the word length as the second item in the dotted pair. For example, fx1.16 describes a number with 1 magnitude bit and 15 fractional bits in a 16 bit word.
  • Yet other notations include a sign bit (such as one used in the PS2 GS User's Guide, Chapter 7.1 "Explanatory Notes". In addition, it also differs from convention usage by using a colon ":" instead of a period "." as the separator.) Its format is:
number of sign bits : number of integer bits : number of fractional bits
i.e.
0:8:0 // unsigned 8-bit integer[citation needed]

[edit] Precision loss and overflow

Because fixed point operations can produce results that have more bits than the operands, there is opportunity for information loss. For instance, the result of fixed point multiplication could potentially have as many bits as the sum of the number of bits in the two operands. In order to fit the result into the same number of bits as the operands, the answer must be rounded or truncated. If this is the case, the choice of which bits to keep is very important. When multiplying two fixed point numbers with the same format, for instance with I  integer bits, and Q fractional bits, the answer could have up to 2×I  integer bits, and 2×Q  fractional bits.

For simplicity, many coders of fixed-point multiply procedures use the same result format as the operands. This has the effect of keeping the middle bits; the I-number of least significant integer bits, and the Q-number of most significant fractional bits. Fractional bits lost below this value represent a precision loss which is common in fractional multiplication. If any integer bits are lost, however, the value will be radically inaccurate. This is considered to be an overflow, and needs to be avoided in embedded calculations. It is recommended that a model based operator simulation tool like VisSim be used to detect and avoid such overflows by use of appropriate result word size and radix point, proper scaling gains, and magnitude limiting of intermediate results.

Some operations, like divide, often have built-in result limiting so that any positive overflow results in the largest possible number that can be represented by the current format. Likewise, negative overflow results in the largest negative number represented by the current format. This built in limiting is often referred to as saturation.

Some processors support a hardware overflow flag that can generate an interrupt on the occurrence of an overflow, but it is usually too late to salvage the proper result at this point.

[edit] Current common uses of fixed-point arithmetic

  • BC - An Arbitrary Precision Desk-Calculator Language [3], written in C for Unix by Lorinda L.Cherry and Robert Morris. Source code is freely available. 99 digits out of the box but can be recompiled for any scale up to hardware imposed (virtual memory) limits and your patience. The original BC was a compiler for DC [4], a postfix (RPN) calculator. The current GNU BC [5] is a standalone program.
  • The Ada programming language supports both binary and decimal fixed-point arithmetic and data types
  • Almost all relational databases support fixed-point arithmetic and storage of numbers
  • SQL and other widely used languages such as COBOL include fixed-point arithmetic
  • VisSim A visually programmed block diagram language that supports a fixed-point block set to allow simulation and automatic code generation of fixed-point operations. Both word size and radix point can be specified on an operator basis.
  • GnuCash is an application for tracking money. It is written in C and switched from a floating-point representation of money to a fixed-point implementation as of version 1.6. This change was made to trade the less predictable rounding errors of floating-point representations for more control over rounding (for example, to the nearest cent).
  • Tremor and Toast are software libraries that decode the Ogg Vorbis and GSM Full Rate audio formats respectively. These codecs use fixed-point arithmetic because many audio decoding hardware devices do not have an FPU (partly to save money, but primarily to save power - integer units are much smaller in silicon area than an FPU) and audio decoding requires enough performance that a software implementation of floating-point on low-speed devices would not produce output in real time.
  • All 3D graphics engines on Sony's original PlayStation, Sega's Saturn, Nintendo's Game Boy Advance (only 2D) and Nintendo DS (2D and 3D) video game systems use fixed-point arithmetic for the same reason as Tremor and Toast: to gain throughput on an architecture without an FPU.
  • Fractint represents numbers as Q3.29 fixed-point numbers,[6] again to speed up drawing on old PCs with 386 or 486SX processors, which lacked an FPU.
  • TeX font metric files use 32-bit signed fixed-point numbers, with 12 bits to the left of the decimal, extensively.
  • PostgreSQL has a special numeric type for exact storage of numbers with up to 1000 digits.

[edit] See also

[edit] External links

Wikibooks
Wikibooks' [[wikibooks:|]] has more about this subject: