Fixed Point Division of Two Q15 Numbers

Fixed point division is quite a bit more complicated than fixed point multiplication, and usually takes a lot more cycles than performing a multiplication. When dividing by a known value (a constant), it is usually better to multiply by the reciprocal than to do a division. And when dividing a fixed point number by an integer that is a power of two, a right shift can be used to implement a division. For example, to divide by 16, just shift your dividend right by 4 bits.

But there are cases where it is necessary to do a division by a calculated value. The easiest way to picture how the division should proceed is to think of the inverse of multiplying two Q15 numbers. The multiplication of two Q15 numbers produces a Q30 product. It then makes sense that a Q30 number divided by a Q15 number produces a Q15 result.

Let a = \hat{a}/{2}^{30}, b = \hat{b}/{2}^{15}

then a/b = \frac{\hat{a}/{2}^{30}}{\hat{b}/{2}^{15}}=\left(\hat{a}/\hat{b} \right)/{2}^{15}

So one procedure for finding a/b has the following steps:
1.convert the dividend a from Q15 to Q30 by shifting left by 15
2.divide the Q30 format number a by the Q15 format number b to get result in Q15

Let’s try an example. Let a = 0.03125 and b = 0.25, then c = a/b = 0.125. The Q15 numbers as hexadecimal integers will be a = 0x0400 and b = 0x2000. In step 1, a becomes 0x02000000 in Q30. In step 2, divide 0x02000000 by 0x2000 to get c = 0x1000 which is 4096 in decimal. As a check, find 4096/32768 = 0.125, the expected result.

In C language code, fixed point Q15 division can be coded as follows:

int16 a;
int16 b;
int16 c;

if ( abs(b) > abs(a) ) {
    c = (int16)(((int32)a << 15) / ((int32)b));
}

The casting is very ugly, but this works. Note that I have restricted the result of the division to be less than one. Removing the restriction that the magnitude of the divisor is larger than that of the dividend has an effect on the number of bits required for the result. To see this, try dividing the largest positive Q15 number by the smallest positive Q15 number, which results in a large number with 15 digits in front of the fractional point:

(0x7FFF/0x8000) / (1/0x8000) = (0x7FFF * 0x8000 ) / 0x8000 = 0x3FFF8000 / 0x8000

The result (0x3FFF8000) requires 30 bits, and it will have 15 bits to the left of the fractional point and 15 bits to the right. That is, the most significant bit has a weighting of {2}^{14} and the least significant bit has a weight of {2}^{-15} . In my work, I have almost always used Q15 division where the magnitude of the divisor is smaller than that of the dividend.

Along with looking ugly, the C code above for division is often inefficient. The C compiler will likely implement this as a division between two 32 bit numbers. When implementing division on a fixed point DSP chip, I have usually used assembly language coding and made use of a special purpose division instruction.

For example, the Texas Instruments TMS320C55x processor has the “subc” instruction or “conditional subtract.” To perform the type of division I have just described do the following:

1.make the dividend and divisor both positive and note original sign of each
2.load the dividend shifted left by 15 into an accumulator register
3.execute the conditional subtract of the divisor 16 times
4.store the result (in the lower 16 bits of the accumulator )
5.determine the correct sign for the result, and negate it if necessary

Note that a short cut is to load the dividend shifted left by 16 in the first step, and then execute the subc instruction 15 times. This works because it is known that the result will be positive.

Fixed point division is not difficult, but it can take a lot of cycles, and one needs to recognize the need to consider the range of the resulting output.

The C code and output below shows a couple of examples from this tutorial.

Example code:

#include <stdio.h>

typedef short int16;
typedef int int32;

int main( void )
{
    int16 a;
    int16 b;
    int16 c;
    int32 d;

    // example 1: magnitude of divisor is greater than magnitude of dividend
    printf("example 1: magnitude of divisor is greater than magnitude of dividend\n");

    a = 0x0400;
    b = 0x2000;

    if ( abs(b) > abs(a) ) {
        c = (int16)(((int32)a << 15) / ((int32)b));
    } else {
        printf("division error\n");
    }

    printf("a = %d, b = %d, c = %d\n",a,b,c);
    printf("a = 0x%x, b = 0x%x, c = 0x%x\n",a,b,c);

    // example 2: no restrictions on divisor other than not 0
    printf("\nexample 2: no restrictions on divisor other than not 0\n");

    a = 0x7fff;
    b = 0x0001;

    if ( b != 0 ) {
        d = ((int32)a << 15) / ((int32)b);
    } else {
        printf("division by zero error\n");
    }

    printf("a = %d, b = %d, d = %d\n",a,b,d);
    printf("a = 0x%x, b = 0x%x, d = 0x%x\n",a,b,d);

   return 0;
}

Code output:

example 1: magnitude of divisor is greater than magnitude of dividend
a = 1024, b = 8192, c = 4096
a = 0x400, b = 0x2000, c = 0x1000

example 2: no restrictions on divisor other than not 0
a = 32767, b = 1, d = 1073709056
a = 0x7fff, b = 0x1, d = 0x3fff8000

Advertisements

7 Comments on “Fixed Point Division of Two Q15 Numbers”

  1. reproducingkernel Says:

    How will be the division by zero?:

    Division by Zero z/0 = 0 in Euclidean Spaces
    Hiroshi Michiwaki, Hiroshi Okumura and Saburou Saitoh
    International Journal of Mathematics and Computation Vol. 28(2017); Issue 1, 2017), 1
    -16. 
    http://www.scirp.org/journal/alamt   http://dx.doi.org/10.4236/alamt.2016.62007
    http://www.ijapm.org/show-63-504-1.html
    http://www.diogenes.bg/ijam/contents/2014-27-2/9/9.pdf
    http://okmr.yamatoblog.net/division%20by%20zero/announcement%20326-%20the%20divi
    http://okmr.yamatoblog.net/

    Relations of 0 and infinity
    Hiroshi Okumura, Saburou Saitoh and Tsutomu Matsuura:
    http://www.e-jikei.org/…/Camera%20ready%20manuscript_JTSS_A…
    https://sites.google.com/site/sandrapinelas/icddea-2017

  2. Shawn Says:

    Hi Mr. Saitoh,

    Thanks for taking a look at my blog. I didn’t discuss division by zero in my post, but the example code does do a check for it. Whenever I have done fixed point division in my own work, I’ve usually had a check that the magnitude of the divisor is larger than the dividend, which automatically excludes division by zero.

    I don’t see any problem with defining division by zero as having a particular value, as in your work. I think in any case, computer code written in a high level language would need to explicitly check the divisor, since the arithmetic logic unit will not handle division by zero in a well defined way. Values close to zero for the divisor are also problematic, but can be handled for fixed point division if there are enough bits in the result. I show an example in my post above.

    Cheers,
    Shawn

  3. Ted Says:

    This article is useful for me, studying fixed-point computation. Thank you!
    I am struggling to get the division in case of [dividened>divisor], whose result is greater than one.
    Would you have any ideas to solve this?
    Also, in the beginning of this blog, you mentioned it should be better to multiply by the reciprocal than to do a division.
    I wonder how your solution would be to get the reciprocal. might do it by Newton-method?

    • Shawn Says:

      Hi Ted,

      I’m glad the article is useful for you. When the dividend is greater than the divisor, you need to know how much bigger it will be, or use a lot more bits in your result. For example, if you know that the magnitude of the dividend is no larger than one, and the magnitude of the divisor can be as small as 0.5, then the largest magnitude of the result would be 2. You could shift your result such that a value this large could be represented. If you had no restrictions, then you might need to keep a lot of bits in the result to represent the entire range of possible results. In my last example, the division of two Q15 numbers would require a Q30 number to hold the range of results possible.

      The multiplication by reciprocal that I mentioned was to do with constant values. I think most C/C++ compilers these days would automatically change a division by constant to a multiplication automatically when optimization is done. I was probably thinking back to when I used to write things in assembly code. I wouldn’t recommend doing a reciprocal normally, unless the result is going to be multiplied by more than one different value afterwards.

      I hope that helps.
      Shawn

  4. Dharmendrasinh rathod Says:

    Q15 numbers as hexadecimal integers will be a = 0x0400 and b = 0x2000. In step 1, a becomes 0x02000000 in Q30.

    0x400 << 15 = 80000000 not 0x02000000. How did you get the anwer then?

    • Shawn Says:

      Thanks for checking out my tutorials. I will show you a couple of ways to get the answer.

      Using decimal numbers, 0x400 is 1024, and 1024 times 2^15 is, 1024 * 32768 = 33554432. If you convert this back to hexadecimal, then you get 0x2000000.

      Using shifts, 0x400 << 12 is 0x400 with another 3 zeros on the right (12/4 is 3), or 0x400000. This has to be shifted left another three places (15-12 is 3). One shift results in 0x800000, two shifts 0x1000000 and finally the third shift is 0x2000000.

      How are you doing the calculations?

      Cheers,
      Shawn

      • Dharmendrasinh rathod Says:

        Thanks for the answer. Actually, In windows calculator, this was confusing in hex mode. 0x400 must be shifted 0xc times left not 0x12 times.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: