Conversion into the Q31 Format

Question

I have a Setup, where I receive 24-bit ADC samples in the two's complement in 8-bit chunks. Usually I just "converted" them into a signed 32-bit integer like this:

sample=((byte1<<24)|(byte2<<16)|(byte3<<8))>>8;

Now, for educational purposes I moved the project to an Arduino Due and want to use the CMSIS-DSP Library of the Cortex-M3.

The DSP Methods Support the Q1.31 Format. I've read a lot of different sources but don't quite understand what this means for me.

As I understood, the Q1.31 format can have values between -1 and 1. Am I supposed to scale my samples somehow? Or is it kind of implicit scaling by just using it with my samples?

Furthermore the documentation provides the following information:

• RFFT Size: 512
• Input Format: Q1.31
• Output Format: Q9.23
• Number of bits to upscale: 8

I don't understand what this means for the output I would get.

Can anyone point out to me what this means?
I'm quite new at this :-)

Answer 1

This is actually pretty complicated (if you haven't done it before) and there isn't enough space here to do go through it thoroughly. Start here https://en.wikipedia.org/wiki/Q_(number_format)

Quick (simplified) overview: We use 8 bit unsigned numbers as an example. Signed makes it more complicated.

When you multiply two integers you basically get twice the number of bits. The result of an 8 bit number multiplied with another 8 bit number requires 16 bit for accurate representation. So after a few multiples you end up with hundreds of bits which simply doesn't work. So you need to decide which bits to keep and which ones to throw away.

The Q notation is a bookkeeping process to help with this. You assume that somewhere there is a decimal point. "Q" denotes where the decimal point is. Q=0 means all the way to the right, Q=8 means all the way to left. To convert from integer to floating point you simply multiply by $2^{-Q}$.

The largest number you can represent this way is 255 for Q0, $\frac{255}{256} = 0.966$ for Q8, and $\frac{255}{16} = 15.9375$ for Q4. The smallest non zero number you can represent is 1 for Q0, $\frac{1}{256} = 0.004$ for Q8 and $\frac{1}{16} = 0.0625$ for Q4. So you basically trading the absolute range against resolution.

Let's say you want to represent the number 2.5. You can't do this in Q0 (you could chose 2 or 3 but there is nothing in between) and you can't do it in Q8 either since it's larger than 1. Q1, however would work. 0b00000101 in Q1 = 2.5 Q1. Q3 would work as well: 0b00010100 in Q3 = 2.5. So any floating point number can be represented as different bit pattern, depending on what Q you chose.

If you want the same floating point number in a different Q you need to shift. shifting. Shifting to the left increases Q, shifting to the right decreases Q.

In Q8 the largest number you can represent is smaller than 1. That means it's impossible that any multiplication would give a result that's larger than any of its inputs and hence it can never overflow. To produce an 8 bit result you keep the MSBs of the 16 bit result and throw away the LSBs.

For a Q0 multiply you keep the LSB and throw away the MSBs. This can and will overflow. 2*2 is 4 but 16*200 will overflow since the result cannot be represented in 8 bits.

If you multiply two numbers, both the number of bits and the Qs will add. So if you multiply an 8-bit Q6 with an 8-bit Q5, you get a 16-bit Q11. To convert 16 bit back to 8 bit you have to throw some bits away. Throwing away LSBs (least significant bits) reduces the number of bits and the Q by the same amount. In our example, removing the lower 8 bits and keeping the upper 8 bits would result in an 8-bit Q3.

So what does this all mean in practice? It basically determines how you implement multiplies and which bits you keep. In general a multiply looks like this

1. Multiply 2 N bit numbers into a 2N wide accumulator or register
2. Shift the result depending on the desired output $Q_C$. $S = Q_C - (Q_A + Q_B - N)$.
3. Keep the upper N bits and transfer to result variable

The tricky part here is to figure which Q to chose for each variable. If the Q is too low, you can overflow and if it's too high you can get very bad signal to noise ratio. Often this requires careful analysis of the specific algorithm and the properties of the input signals.

Answer 2

Randy Yates has a nice pdf that's an intro to fixed-point arithmetic.

my spin on fixed-point is that since languages like C don't support Q1.31 fixed-point as a primitive type, the fixed-point numbers are just integers with an "implicit scaling" of $2^{31}$. that means

$$ I_x \triangleq 2^{31} \cdot x \quad \quad \text{where } \ -1 \le x < +1 $$

and the integer representation has $ -2^{31} \le I_x < +2^{31} $.

the scaling factor comes along for the ride when you add or subtract two like-scaled fixed-point numbers, so nothing extra is needed for addition or subtraction. that is, if

$$ I_x \triangleq 2^{31} \cdot x $$ $$ I_y \triangleq 2^{31} \cdot y $$ $$ I_z \triangleq 2^{31} \cdot z $$ and $$ z = x + y $$ then the Q1.31 fixed-point representations add just the same. $$ I_z = I_x + I_y $$

but for multiplication, there is an extra scaling factor that must be removed. that is, if $$ z = x \cdot y $$ then $$ I_z = \lfloor 2^{-31} (I_x \cdot I_y) \rfloor $$

where $\lfloor \cdot \rfloor$ is the floor() operator (the most positive integer no greater than the argument).

if you're rounding, it's

$$ I_z = \lfloor 2^{-31} (I_x \cdot I_y \ + \ 2^{30}) \rfloor $$

and for division

$$ z = \frac{x}{y} \quad \quad \text{where } |x| \le |y|$$ then $$ I_z = \left\lfloor \frac{2^{31}I_x}{I_y}\right\rfloor $$

and if you're rounding, it's

$$ I_z = \left\lfloor 2^{-1} \left( \frac{2^{32}I_x}{I_y} + 1 \right) \right\rfloor $$

that's how you would code it, in an integer machine, to do Q1.31 arithmetic.