Quelltext der Seite Benutzer:Haseneder/Q-Format

Das '''Q-Format''' ist ein [[Festkommazahl]]enformat, das die Anzahl der [[Fraction (mathematics)|Nachkommastellen]][[bit]]s (und optional die Anzahl der Vorkommastellenbits) beschreibt.
Zum Beispiel: Eine Q15-Zahl hat 15 Nachkommastellen; eine Q1.14-Zahl hat 1 Vorkommastellenbit and 14 Nachkommastellenbits.
Das Q-Format wird oft in Rechenwerken benutzt, die keine Gleitkommazahlen-Recheneinheit besitzen und in Anwendungen,
die eine [[Fixed-point arithmetic|konstante Genauigkeit]] erfordern.

== Characteristics ==
Q format numbers are notionally fixed point numbers, that is, they are stored and operated upon as regular binary signed integers, thus allowing standard integer hardware/[[Arithmetic logic unit|ALU]] to perform [[rational number]] calculations. The number of integer bits, fractional bits and the underlying word size are to be chosen by the programmer on an application-specific basis — the programmer's choices of the foregoing will depend on the range and resolution needed for the numbers.

Some DSP architectures offer native support for common formats, such as Q1.15. In this case, the processor can support arithmetic in one step, offering saturation (for addition and subtraction) and renormalization (for multiplication) in a single instruction. Most standard CPUs do not. If the architecture does not directly support the particular fixed point format chosen, the programmer will need to handle saturation and renormalization explicitly with bounds checking and bit shifting.

There are two conflicting notations for fixed point. Both notations are written as Q''m''.''n'', where:
* Q designates that the number is in the Q format notation — the [[Texas Instruments]] representation for signed fixed-point numbers (the "Q" being reminiscent of the standard symbol for the set of [[rational number]]s).
* ''m.'' (optional, assumed to be zero or one) is the number of bits set aside to designate the two's complement integer portion of the number, exclusive or inclusive of the sign bit (therefore if m is not specified it is taken as zero or one).
* ''n'' is the number of bits used to designate the fractional portion of the number, i.e. the number of bits to the right of the binary point. (If n = 0, the Q numbers are integers — the degenerate case).

One convention includes the sign bit in the value of ''m'',<ref name=arm>[http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0066d/CHDFAAEI.html ARM® Developer Suite AXD and armsd Debuggers Guide	Version 1.2 . Home > AXD > AXD Facilities > Data formatting > Q-format . 4.7.9. Q-format]</ref> and the other convention does not. The choice of convention can be determined by summing ''m+n''. If the value is equal to the register size, then the sign bit is included in the value of ''m''. If it is one less than the register size, the sign bit is not included in the value of ''m''.

In addition, the letter U can be prefixed to the Q to indicate an unsigned value, such as UQ1.15, indicating values from 0.0 to +1.99997.

Signed Q values are stored in [[two's complement]] format, just like signed integer values on most processors. In two's complement, the sign bit is extended to the register size.

For a given Q''m''.''n'' format, using an ''m''+''n''+1 bit signed integer container with ''n'' fractional bits:
* its range is <math>[ - (2^m) , 2^m -2^{-n}]</math>
* its resolution is <math>2^{-n}</math>

For a given UQ''m''.''n'' format, using an ''m''+''n'' bit unsigned integer container with ''n'' fractional bits:
* its range is <math>[ 0 , 2^m -2^{-n}]</math>
* its resolution is <math>2^{-n}</math>

For example, a Q14.1 format number:
* requires 14+1+1 = 16 bits
* its range is [-2<sup>14</sup>, 2<sup>14</sup> - 2<sup>−1</sup>] = [-16384.0, +16383.5] = [0x8000, 0x8001 … 0xFFFF, 0x0000, 0x0001 … 0x7FFE, 0x7FFF]
* its resolution is 2<sup>−1</sup> = 0.5

Unlike [[floating point]] numbers, the resolution of Q numbers will remain constant over the entire range.

== Conversion ==

=== Float to Q ===
To convert a number from [[IEEE 754|floating point]] to Q''m''.''n'' format:
# Multiply the floating point number by 2<sup>''n''</sup>
# Round to the nearest integer

=== Q to float ===
To convert a number from Q''m''.''n'' format to floating point:
# Convert the number to floating point as if it were an integer, in other words remove the binary point
# Multiply by 2<sup>−''n''</sup>

== Math operations ==
Q numbers are a ratio of two integers: the numerator is kept in storage, the denominator is equal to 2<sup>''n''</sup>.

Consider the following example:

* The Q8 denominator equals 2<sup>8</sup> = 256
* 1.5 equals 384/256
* 384 is stored, 256 is inferred because it is a Q8 number.

If the Q number's base is to be maintained (''n'' remains constant) the Q number math operations must keep the denominator constant. The following formulas show math operations on the general Q numbers <math>N_1</math> and <math>N_2</math>.

<math>\begin{align}
\frac{N_1}{d} + \frac{N_2}{d} &= \frac{N_1+N_2}{d}\\
\frac{N_1}{d} - \frac{N_2}{d} &= \frac{N_1-N_2}{d}\\
\left(\frac{N_1}{d} \times \frac{N_2}{d}\right) \times d &= \frac{N_1\times N_2}{d}\\
\left(\frac{N_1}{d} / \frac{N_2}{d}\right)/d &= \frac{N_1/N_2}{d}
\end{align}</math>

Because the denominator is a power of two the multiplication can be implemented as an [[arithmetic shift]] to the left and the division as an arithmetic shift to the right; on many processors shifts are faster than multiplication and division.

To maintain accuracy the intermediate multiplication and division results must be double precision and care must be taken in [[rounding]] the intermediate result before converting back to the desired Q number.

Using [[C (programming language)|C]] the operations are (note that here, Q refers to the fractional part's number of bits) :

=== Addition ===
<syntaxhighlight lang="c">
int16_t q_add(int16_t a, int16_t b)
{
    int16_t result;

    result = a + b;

    return result;
}
</syntaxhighlight>
With saturation
<syntaxhighlight lang="c">
int16_t q_add_sat(int16_t a, int16_t b)
{
    int16_t result;
    int32_t tmp;

    tmp = (int32_t)a + (int32_t)b;
    if (tmp > 0x7FFF)
        tmp = 0x7FFF;
    if (tmp < -1 * 0x8000)
        tmp = -1 * 0x8000;
    result = (int16_t)tmp;

    return result;
}
</syntaxhighlight>

=== Subtraction ===
<syntaxhighlight lang="c">
int16_t q_sub(int16_t a, int16_t b)
{
    int16_t result;

    result = a - b;

    return result;
}
</syntaxhighlight>

=== Multiplication ===
<syntaxhighlight lang="c">
// precomputed value:
#define K   (1 << (Q - 1))
 
// saturate to range of int16_t
int16_t sat16(int32_t x)
{
	if (x > 0x7FFF) return 0x7FFF;
	else if (x < -0x8000) return -0x8000;
	else return (int16_t)x;
}

int16_t q_mul(int16_t a, int16_t b)
{
    int16_t result;
    int32_t temp;

    temp = (int32_t)a * (int32_t)b; // result type is operand's type
    // Rounding; mid values are rounded up
    temp += K;
    // Correct by dividing by base and saturate result
    result = sat16(temp >> Q);

    return result;
}
</syntaxhighlight>

=== Division ===
<syntaxhighlight lang="c">
int16_t q_div(int16_t a, int16_t b)
{
    int16_t result;
    int32_t temp;

    // pre-multiply by the base (Upscale to Q16 so that the result will be in Q8 format)
    temp = (int32_t)a << Q;
    // Rounding: mid values are rounded up (down for negative values).
    if ((temp >= 0 && b >= 0) || (temp < 0 && b < 0))
        temp += b / 2;
    else
        temp -= b / 2;
    result = (int16_t)(temp / b);

    return result;
}
</syntaxhighlight>

== See also ==
{{Portal|Computer Science}}
* [[Binary scaling]]
* [[Fixed-point arithmetic]]
* [[Floating-point arithmetic]]

== References ==
{{Reflist}}

== External links ==
* [http://www.superkits.net/whitepapers/Fixed%20Point%20Representation%20&%20Fractional%20Math.pdf Fixed Point Representation And Fractional Math] (Note: the accuracy of the article is in dispute; see discussion.)
* [https://github.com/mgarcia01752/Q-Number-Format Q-Number-Format Java Implementation]

[[:Category:Computer arithmetic]]