Conversion into the Q31 Format

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 :-)

• sample=((byte1<<24)|(byte2<<16)|(byte3<<8))>>8; why are you shifting the whole thing to the right by 8 bits? why aren't you leaving the sample words left justified? and if you want it right justified why not leave out 8 bits of unnecessary shifting: sample=(byte1<<16)|(byte2<<8)|byte3; are you doing that for the purpose of sign extension? – robert bristow-johnson May 29 '16 at 1:02
• @robertbristow-johnson: Hey! The 8bit shift is in order to maintain the sign. The 24bit are signed. The bitshift maintains the sign. It seemed the fastest possebility to do so. – Chuchaki May 29 '16 at 9:10

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.

• Hey!Amazing Answer. Thanks for your effort!Unfortunatley this is (in a more precise way) more or less what I understood to be the purpose of this data format. My confusion lies more in the application. There is this "DSP" unit,that expects the incoming data to be Q1.31 and the Output is Q9.23. Now I have an 24bit signed adc result, transform that into an 32bit signed int. Now I ask myself what I am expected to do. I don't know if I'm supposed to input the integer and that the Q31 format is just an internal detail of the algorithm. And how to treat the output. Conversion, Shift Greetings :-) – Chuchaki May 28 '16 at 19:10
• I'd be happy to give more details. I'm not that confident with my english and sometimes tend to confuse stuff :-) – Chuchaki May 28 '16 at 19:11
• Left shift your data by 7 or 8 bit so the MSB starts wiggling. The output will be in Q9.23. Whether that needs to change or not, depends on what you are planning to do with it. – Hilmar May 28 '16 at 20:36
• Could it be that the specification "Number of bits to upscale: 8" means, that I have to left shift the output by 8 bit to reverse the scaling that has be done while computing the fft? That would mean if I place the 24bit data just to the MSB's, the output would have the right scaling. – Chuchaki May 29 '16 at 9:15

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.

• This is really a very nice method to avoid floating point arithmetic. So basically, in this case, I would just ignore the fact, that the algorithm uses the Q format and input my integers and then scale the output and walk away with integers again? Probably the "Number of bits to upscale: 8" refers to the scaling of the output... – Chuchaki May 29 '16 at 9:18
• it "avoids floating-point arithmetic" at some risk or peril. most coders would prefer not to avoid floating-point, because sometimes it covers their ass. and you may need to use long long or some type that is 64 bits. with this Q1.31, make sure your result $z$ is never meant to exceed 1 in magnitude. not only in division, but also in addition. if you can spare a bit on the right, maybe go with Q2.30 but maintaining the $-1 \le x, y, z \le +1$ and you'll have 6 dB of headroom, that you can use to at least inform you that you've exceeded limits. – robert bristow-johnson May 29 '16 at 17:27
• The avoiding is more because of a processor without hardware floating point support. Apart of that I just want to use a library from the manufacturer that is not that well documented. Or at least not enough for me to get it right away. I can't change anything about the Formats: Q31 in, Q9.23 out. I just wanted to ask how to get from my 24 signed bit to Q31 and then how to transform the output to get an int without scaling. Currently I think I could just input an int32 and treating the output like an int and doing a bitshift of 8 should do the Trick. – Chuchaki May 30 '16 at 4:19
• i think you might wanna take your 24-bit signed int from the ADC and shift it left 8 bits to get Q1.31 . you might wanna leave it as a Q9.23 number, i dunno. to convert from Q1.31 to Q9.23, you simply arithmetic shift (replicating the sign bit, C does this with signed int) your Q1.31 number to the right 8 bits. if you want to round, shift right 7 bits, add 1, and shift right one more bit to convert Q1.31 to Q9.23 . – robert bristow-johnson May 30 '16 at 4:24
• Here now :-) : I'll try that out and come back to you. Unfortunately today I won't be able to do anything. I'll write something as soon as possible. thanks! – Chuchaki May 30 '16 at 4:34