4
$\begingroup$

I am new to DSP and I am trying to understand how to work with fixed point operations and in particular the Q31 format.

In floating point (full range) I am doing some multiplications, it could be for example 6.0 * 10.0 = 60.0. Converting this to Q31 would require first scaling it down to [-1,1) and then converting that to an int32_t (q31).

However when doing the same multiplication in Q31 we get a new Q31 result (after bit shifting properly), that can be taken back to float in the range [-1,1). But if I then scale that back up by reversing the original downscaling I do not end up with 60.

In summary:

  • Downscale full range float to float in the range [-1,1) to be able to be represented in Q31
  • Convert float in the proper range to Q31
  • Perform fixed point multiplication (and possibly other unknown operations)
  • Convert Q31 back to float
  • Scale this float back up to the original range?

Is it possible to scale back to the original range somehow as in my last point - or is it a one-way conversion?

An example:

  • Downscale: Input floats in an original range [0-5000] are scaled down to [-1,1). I tried with scaling function sign(val) * (abs(val) - min)/(max-min) where min is 0 and max 5000. This takes the values 6 and 10 to 0.0012 and 0.002.
  • FloatToQ31: 0.0012 -> 2576980, 0.002 -> 4294967
  • Multiply in Q31: 2576980*4294967 >> 31 = 5152
  • Q31ToFloat: 5152 -> 2.39909e-06
  • Upscale: Reversed downscale function val * (max - min) + min (again min=0, max=5000). This takes the value back to 0.0119954 which is not close to 60.
$\endgroup$
8
  • $\begingroup$ "I do not end up with 60" -- what do you end up with? if you end up with $60 \pm \epsilon$, and $\epsilon$ is significantly smaller than the errors caused by noise in your input data, then you're close enough. If you end up with 2 or 200, then you have problems. $\endgroup$
    – TimWescott
    Dec 17, 2022 at 15:42
  • $\begingroup$ It would be helpful if you would edit your question with this information. $\endgroup$
    – TimWescott
    Dec 17, 2022 at 16:56
  • $\begingroup$ @TimWescott I updated with all the steps and the final result which is far from 60. Either my Downscale or Upscale functions are wrong or it's not possible in general to take it back to the original range and expect matching results? $\endgroup$
    – Zitrax
    Dec 17, 2022 at 18:51
  • 2
    $\begingroup$ "Q31" (which I would call "Q1.31") is not the only way to do 32-bit fixed point. If you have a range up to ±64.0 (or -64.0 to +63.999999999), then the fixed-point format that you want is Q7.25. 25 bits to the right of the binary point. This means that, in a language like C, your integer representation is $2^{25}$ times larger than the value it represents. $\endgroup$ Dec 17, 2022 at 19:22
  • $\begingroup$ Multiply in Q31: 2576980*4294967 >> 31 = 5152 ...... Why are you shifting right 31 bits? And you know that right-shifting loses precision, right? There is truncation. Are you rounding in that truncation? Also, have you considered that your intermediate value from multiplication might be too big for a 32-bit word? You might need to do that in int64_t. $\endgroup$ Dec 17, 2022 at 22:57

4 Answers 4

9
$\begingroup$

Fixed point processing is very difficult (unless it's a very simple algorithm and well behaved data).

Here is roughly how this can be done. For simplicity I will assume that the fixed point data type is a 32-bit signed integer.

  1. Prototype your entire algorithm in floating point. Make sure it's fully unit tested, corner case tested, meets all requirement and has stakeholder approval before writing any fixed point code.
  2. Go through your algorithm and determine the maximum range that each individual variable can take. This may take a fair bit of simulation effort including figuring out what the worst case signals for each variable are, what's the likelihood of occurrence and how many guard bits you can afford as "insurance" against clipping. This may involve a trade off between occasional clipping and continuous SNR.
  3. Pick a Q for each variable based on it's range. For example, a variable that's in the range of [6,-6) can be represented in Q28. If you want to add an extra guard bit, make it Q27.[10,-10) can be represented in Q27
  4. Then implement your algorithm one instruction at a time, keeping carefully track of all Qs.

Rules for working with "mixed Q" representation.

  1. Multiplication: The Qs just add. In your example 6(Q28)*10(Q27) the result would be a 64-bit number with a Q of Q55. Typically you only keep the top 32 bits. To determine the Q of the resulting 32 bit number, subtract 31. Final Q will be Q24 which accommodates a range of [128,-128], so 60 fits easily in there. Many compilers have support for a so-called "fractional multiply" which just calculates the top 32-bit and you don't have to deal with a 64-bit intermediate result.
  2. Changing Q: Right shift to decrease Q, Left shift to increase Q. Increasing Q can result in clipping, so some care is advised
  3. Addition/Subtraction: You can only add numbers with the same Q. If you have different Qs, you need to right shift the one with the higher Q to match the smaller Q. The final result will be in the smaller Q. Note that an addition or subtraction can clip by 1 bit, so to be safe you can add one more guard bit

Please note that this is mostly a bookkeeping exercise on paper, spreadsheet, or comments in the code. The actual code still has just multiplies, adds and bit shifts. The Q simply determines how a fixed point pattern is related to the underlying floating point quantity, it doesn't change the bit pattern itself.

Once that's all done, you can start running noise & clipping analysis, etc.

EDIT: based on the example in the question:

Let's do the example of doing $6*10$ in the range of [5000,-5000].

  1. Both numbers are in the same range and for simplicity we'll pick the same Q of 18. 6 becomes $x = 6*2^{18} = 1572864$ (0x00180000) and 10 becomes $y = 10*2^{18} = 2621440$ (0x00280000)
  2. We multiply keeping the 32 MSBs. We get $z = 1572864*2621440/2^{31} = 1920$ or $z = (0x00180000 * 0x00280000) >> 31 = 0x00000780$
  3. Per the rules stated above the Q of the result is $18+18-31 = 5$
  4. Converting this back to floating point we get $z*2^{-5} = 60$ exactly

Note: the reason why this works with no error here is just coincidental. Lucky choice of numbers to multiply.

$\endgroup$
13
  • $\begingroup$ Thanks, so if I understand it correctly if I want to be able to keep the original full float range I can't scale down to a Q31 and scale back up again. I have to keep the full range in the fixed point Q number, but using fewer fractional bits? $\endgroup$
    – Zitrax
    Dec 17, 2022 at 15:10
  • $\begingroup$ "Go through your algorithm and determine ... a fair bit of simulation effort". My preference, where I can, is to start by figuring out the limits by analysis. Then I back that up with simulation to make sure I had my head screwed on straight when I did the analysis. Analysis, done properly, covers all possible inputs -- simulation, done properly, catches at least some of the times when you failed to do your analysis properly. $\endgroup$
    – TimWescott
    Dec 17, 2022 at 15:45
  • $\begingroup$ "Pick a Q for each variable based on it's range." Quite a few processors (as opposed to FPGA or custom logic circuits) won't do fractional arithmetic quickly unless the fractions are scaled in the range $[-1, 1)$. So you can't (for instance) choose Q28 (on a 32-bit machine) to represent a variable -- you have to scale it into the range $[-1,\ 1)$, use Q31 (or Q15, or Q63), and upon going back to floating point scale it correctly on the output. $\endgroup$
    – TimWescott
    Dec 17, 2022 at 15:50
  • 2
    $\begingroup$ @TimWescott: Sorry for not being clear enough. Picking the Q for each variable DOES NOT CHANGE the code in any way. I just assume support for a standard Q31xQ31=Q31 multiply instruction aka "keep the MSB" or what Analog Devices calls a "fractional multiply". If you apply this instruction to, say, Q20xQ30 the result will be in Q19. It doesn't change the bit patterns or the code, it's just an efficient way to do bookkeeping of the scale factors and makes it really easy to compare the floating point reference. It's overkill for something simple like an FIR but useful for more complicated stuff. $\endgroup$
    – Hilmar
    Dec 17, 2022 at 16:17
  • 1
    $\begingroup$ @DanBoschen. Oops. Thanks for the catch. I added the hex versions as well $\endgroup$
    – Hilmar
    Dec 19, 2022 at 17:58
7
$\begingroup$

OK -- I see your problem. You're multiplying $a$ and $b$, by first bringing them into Q31 then bringing them out. $a$ and $b$ happen to be 6 and 10, but let's not worry about that at the moment.

Algebraically, let $a_{Q31} = \frac 1 {5000} a$ and $b_{Q31} = \frac 1 {5000} b$ (keeping in mind that the weight for the MSB is 2, and the weight for the LSB is $2^{-31}$).

Now you compute a result: $c_{Q31} = a_{Q31} b_{Q31}$. But work this out: $$c_{Q31} = a_{Q31} b_{Q31} = a b \left(\frac{1}{5000}\right)^2 \tag 1$$

Your scaling has changed. This is one of the "fun" things about using fractional arithmetic -- you need to dot a lot more 'i's and cross a lot more 't's for it all to work out. This changed scaling means that when you go to extract the "real world" $c$ from $c_{Q31}$, you need to multiply not by $5000$, but by $5000^2$.

Note that scaling changes for multiplicative operations, but not for addition or subtractions. Note too that if you add two numbers, it's up to you to make sure the scalings are the same. Finally, if you're using a Q31 or Q15 trigonometry library, there's a good chance that angles are represented not in radians, but in inits where a full circle is in the range $[-1, 1)$ (i.e., the LSB is weighted as $2 \pi 2^{-31}$ or $2 \pi 2^{-15}$ radians).

So your example $c_{Q31} = \left(2^{-31}\right)\left(5152\right)$. To get that back, you need to calculate $$c = \left(5000^2\right)c_{Q31} = \left(5000^2\right)\left(2^{-31}\right)\left(5152\right) \simeq 59.977 \tag 2$$

Which is pretty close to 60. Given that your $a$ and $b$ were right down at the bottom of their range, this is pretty close.

$\endgroup$
3
  • $\begingroup$ Note that for some reason when I do the calculation I get $(2576980)(4294967)(2^{-31}) \simeq 5153.95$, and using 5154 in my (2) gives me 60.0005, which is much closer. $\endgroup$
    – TimWescott
    Dec 17, 2022 at 19:31
  • $\begingroup$ Right I see, so to be able to go back I need to keep track of exactly which and how many operations I do in the fixed point world to know how to scale it back again. $\endgroup$
    – Zitrax
    Dec 17, 2022 at 19:36
  • $\begingroup$ Yes. I expanded my answer a bit about when you need to do that. $\endgroup$
    – TimWescott
    Dec 17, 2022 at 19:41
3
$\begingroup$

Here is a higher level summary of Q notation that will help demystify the other good answers:

The post mentions "Q31" as a signed binary number, in this case with 32 total bits, and scaled to [-1, +1).

More generally with Q notation for fixed point hardware design (not limited to processor implementations with fixed precisions such as 8, 16, 32 etc but for any arbitrary scaling) the Q notation is given as follows:

$Qm.n$: signed representations

$UQm.n$: unsigned representations

In the above forms, m represents the integer bits and n represents the fractional bits. To add to the confusion, for signed numbers there are two primary conventions that either include or don't include the sign bit in m. That said,in this case ”Q31” would either be Q1.31 or Q0.31 depending on if we include the sign bit or not since we know the range is [-1,1).

I will use the convention of not including the sign bit for the remainder of this posting.

The total bit width not including the sign bit when used is $m+n$. $Qm.n$ is a $m+n+1$ bit word represented in fractional form as a ratio of two integers: The numerator is the integer value of the $m+n+1$ binary number, and the denominator is $2^n$.

As a simple example, $Q5.2$ represents an 8 bit signed word that has 2 fractional bits, and therefore has a step size of 0.25. To represent 6.25 for example, this would be $000110.01$ where I have shown an "implied" decimal place for clarity, which is really given by the denominator which is also implied in implementation--we are simply storing 8 bits. So here in this example, the numerator of the fraction of integers is $00011001$ binary which is $25$ decimal and the implied denominator is $4$ decimal resulting in $6.25$ as planned. The denominator is implied and not stored, but if we do change to a different Q format, the number stored must change to still represent $6.25$ accurately. For example if we wanted it to be $Q4.3$ this would still be 8 total bits but result in a bit shift to the left as $00110.010$ which still represents 6.25 here as 50/8.

In general, the range for represented numbers using Q notation is as follows:

Signed: $-2^m$ to $+2^m-2^{-n}$

Unsigned: $0$ to $2^m-2^{-n}$

And for either case the step size is given as $2^{-n}$.

This means the 32 bit signed number that is scaled to [-1, 1) is represented as $Q0.31$, and an unsigned 32 bit number would be $Q0.32$. The maximum value shown as 1) is specifically $1-2^{-31}$.

All that said, we can easily take the pain out of processing mathematical operations properly by remembering that each number represented is an integer divided by $2^n$. An arbitrary $Qm.n$ format number would be some integer $x$ within the range allowed by the $m+n$ bits divided by the denominator $2^n$ as:

$$\frac{X}{2^n}$$

Thus a product with different Q formats such as $Qm1.n1$ and $Qm2.n2$ would be as follows (prior to final scaling of the output if desired):

$$\frac{X_1}{2^{n1}}\frac{X_2}{2^{n2}} = \frac{X_1X_2}{2^{n1+n2}}$$

The Q format of this result would be $Qm3.n3$ where $m3=m1+m2$ and $n3=n1+n2$ with a total bit width required of $m3+n3+1$ (adding the sign bit).

We also see more easily how addition of different Q formats can be properly done (which is the rescaling often mentioned):

$$\frac{X_1}{2^{n1}} + \frac{X_2}{2^{n2}} = \frac{X_12^{n2}+X_22^{n1}}{2^{n1+n2}}$$

Which is simply aligning the implied decimal points prior to doing the addition.

Note that the integer $X_1$ multiplied by $2^k$ is a "shift left" of $k$ bits for positive $k$. If we multiply both numerator and denominator by $2^k$, meaning add $k$ to both $m$ and $n$ as $Q(m+k).(n+k)$, we have not changed the implied fractional representation, but we will have shifted the stored number $k$ bits (as we demonstrated with the simple 8 bit example representing 6.25).

Once a given mathematical operation is completed (with no rounding thus far as presented above), the output can be rounded as desired based on the maximum value represented and tolerable error either as truncation on the right or clipping on the left (when simply shifting) or rounding (when adding 0.5 first and then shifting).

I have demonstrated the more universal $Qm.n$ and $UQm.n$ formats which can include negative values for $m$ and $n$ and provides for arbitrary scaling and bit width changes from either MSB or LSB sides of the digital word, and provided a simple notation for properly keeping track of the radix and mathematical operations.

As a more detailed reference on fixed point arithmetic, see this nice write-up by Randy Yates: http://www.digitalsignallabs.com/fp.pdf

$\endgroup$
7
  • 1
    $\begingroup$ I tried to tell them that, Dan. Qm.n . Fell on deaf ears. $\endgroup$ Dec 19, 2022 at 0:56
  • 1
    $\begingroup$ Also shown how to properly do fixed-point multiplication and division in C. As if anyone thinks that's useful. $\endgroup$ Dec 19, 2022 at 0:58
  • $\begingroup$ Also, I think I disagree that the total bit width not including the sign bit is $n+m$. The entire word width is that. "Q31" normally means Q1.31 . and the 1 and 31 add to 32. $\endgroup$ Dec 19, 2022 at 1:06
  • $\begingroup$ TI agrees with your convention, but ARM agrees with mine. $\endgroup$ Dec 19, 2022 at 1:11
  • 2
    $\begingroup$ Randy and I had several discussions about it. I have a much simpler perspective on fixed-point than Randy had and maybe simpler than yours. I did a lotta fixed-point DSP on the 56K but also coding it on the 68K. As well in C for the Renesas SH-3. $\endgroup$ Dec 19, 2022 at 4:59
1
$\begingroup$

32 bits is a lotta bits. Usually more than you need, but not always. The result of unsigned multiply of an $N$-bit number against an $M$-bit number is an $(N+M)$-bit number. When both are signed, the result of multiplying an $N$-bit number against an $M$-bit number is an $(N+M-1)$-bit number (with the exception of $-2^{N-1} \times -2^{M-1}$ which is an extreme corner case that, to be exact, requires $N+M$ bits).

But if you're doing this in C or C++, you need a register for the result of multiplication that is wide enough to accommodate all of the bits before you cast it back to the destination word size. And you should normally round-to-nearest by adding $\frac12$LSB before truncating.

I'm more interested in elegance and not tearing my hair out. So when I do fixed-point math in C/C++, I examine the general range of the quantities I'll be working with and pick a Q format that will accommodate the range to within 6 dB and use that format throughout. I almost never (in fact, I never) mix Q formats in the same environment.

Sometimes it doesn't matter. Audio samples can be whatever Q format you like as long as you're consistent. The scaling is just in your imagination. It's the scaling coefficients (like filter coefficients) that have non-ambiguous quantitative value. For an audio sample, if you want to scale it by the number $2$, the result, whatever the Q format of the audio, must be twice as large as what went into the scaling operation. So the number $2$, as a scaler, must have non-ambiguous quantitative value.

int32_t a, b, c, d;     // let's say it's Q6.26, 
                        // so that these numbers can get as large as +/- 32

// here is how you do  d = a*b + c;

d = (int32_t)( ( (int64_t)a * (int64_t)b + 0x0000000002000000LL )>>26 ) + c;

// here is how you do  c = a/b;

c = (int32_t)( ( ((int64_t)a<<27) / (int64_t)b + 0x0000000000000001LL )>>1 );

// another way to division with rounding  c = a/b;

c = (int32_t)( ( (int64_t)a<<26) + ((int64_t)b>>1) ) / (int64_t)b );

If you're careful, fixed-point processing is that simple in C/C++. You can make a C++ class outa this and overload the * and / operators. You won't need to overload the + or - operators. Doing higher-level math, like transcendentals is doable, but you just have to be careful about the ranges of both inputs and outputs and saturate if necessary.

$\endgroup$
10
  • $\begingroup$ When you say a "signed N bit number", are you including the sign bit? So for example, a signed 16 bit number can represent integers from -2^15 to +2^15-1... $\endgroup$ Dec 18, 2022 at 15:31
  • 1
    $\begingroup$ yes. i always include the sign bit and "$N$ bits" means the entire word width. $\endgroup$ Dec 18, 2022 at 15:33
  • $\begingroup$ Then I think your corner case would still be M+N-1 bits for multiplying signed values, wouldn't it? Your case given would result in an exponent of N+M-2, but worst case would be (-2^(N-1) x (2^M-1)) with an exponent close to N+M-1...am I missing something? $\endgroup$ Dec 18, 2022 at 15:43
  • 1
    $\begingroup$ In all cases, except that single corner case, the two most significant bits of the $N+M$ bit resulting word are identical. For a negative number they are both 11 and for a non-negative number they are both 00. So, except for the corner case, a word size of $N+M-1$ suffices. The one and only exception (let's assume Q31) is $-1.0 \times -1.0 = +1.0$ which doesn't quite fit. in the $N+M$ bit result, the two MSBs are 01. $\endgroup$ Dec 18, 2022 at 15:50
  • 1
    $\begingroup$ $$-2^{N-1} \times -2^{M-1} = +2^{N+M-2}$$ for an $(N+M)$-bit word, the bits will be 01000000000000000000000000000000, There is no redundancy on the left. in order for this to fit in an $(N+M-1)$-bit word the positive result must be less than $2^{N+M-2}$. But it's not. $\endgroup$ Dec 18, 2022 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.