Multiplication of two binary numbers in fixed point arithmetic

Question

I'm performing some operations with fractional numbers in a 16-bit FIXED-POINT processor.

I have to multiply the numbers \$ x=-6.35 \$, represented in \$ Q_{11} \$, and \$ y=-0.1 \$, represented in \$ Q_{14}\$.

First I represent the numbers in the respective notation in binary. The MSB is the sign bit.

So \$ x=11001.10100110011 \$ and \$ y=11.11100110011001 \$. I know the binary point is just in our mind and the processor treats this numbers as integers.

Ok then we multiply the numbers and get \$ x*y=11001000000100010011111001111011 \$. We eliminate the repeated sign bit and save the 16 MSB and represent the result in the appropriate format \$ Q_{10}\$: \$ x*y=100100.0000100010\$. This number corresponds to \$ - 27.966796875\$. But this doesn't make any sense, the result should be \$ 0.635\$.

What is going on here? Why is the result different? Am I missing something?

EDIT: So I realized that it was pointed out that I was performing unsigned multiplication. Taking what was said now I'm doing signed multiplication:

$$1100110100110011$$ $$1111100110011001$$ $$----------------$$ $$\color{blue}{1111111111111111}1100110100110011$$ $$\color{blue}{000000000000000}0000000000000000\text{_}$$ $$\color{blue}{00000000000000}0000000000000000\text{__}$$ $$\color{blue}{1111111111111}1100110100110011\text{___}$$ $$\color{blue}{111111111111}1100110100110011\text{____}$$ $$\color{blue}{00000000000}0000000000000000\text{_____}$$ $$\color{blue}{0000000000}0000000000000000\text{______}$$ $$\color{blue}{111111111}1100110100110011\text{_______}$$ $$\color{blue}{11111111}1100110100110011\text{________}$$ $$\color{blue}{0000000}0000000000000000\text{_________}$$ $$\color{blue}{000000}0000000000000000\text{__________}$$ $$\color{blue}{11111}1100110100110011\text{___________}$$ $$\color{blue}{1111}1100110100110011\text{____________}$$ $$\color{blue}{111}1100110100110011\text{_____________}$$ $$\color{blue}{11}1100110100110011\text{______________}$$ $$\color{blue}{0}0011001011001101\text{_______________}$$ $$----------------$$ $$\color{red}{1}\color{green}{0}{0010001000111111010101001111011}$$

The last carry (red) is eliminated. Then the repeated sign bit (green) is also shifted to the left, adding an extra 0 bit at the end. Finally we save the 16 most significant bit and represent the result in \$ Q_{10}\$:

$${0010001000111111}$$

But this is \$ 8.5615234375 \$, not \$ 0.635 \$... So we are getting closer but the result is still off. Any ideas?

Answer 1

I have to multiply the numbers \$ x=-6.35 \$, represented in \$ Q_{11} \$, and \$ y=-0.1 \$, represented in \$ Q_{14}\$. So \$ x=11001.10100110011 \$ and \$ y=11.11100110011001 \$

I have just calculated the corresponding values for \$x\$ and \$y\$ using scaling values \$2^{11} \$ and \$2^{14}\$ respectively, and found them to be correct in 2's complement signed notation. So there is nothing wrong in your starting point.

I know the binary point is just in our mind and the processor treats this numbers as integers. Ok then we multiply the numbers and get \$ x*y=11001000000100010011111001111011 \$

This is where things went wrong. You would have been absolutely correct if you were multiplying two unsigned numbers (unsigned arithmetic). It is straight forward. But if one of the numbers is signed, then you have to do signed arithmetic, which is a little different.

There are two points I would like to highlight:

• When you multiply two signed numbers \$x\$ and \$y\$, each partial product has to be treated as signed and you have to properly sign-extend each partial product.
• If the multiplier(\$y\$) is a negative number, the last partial product has to be computed differently. It should be computed as the 2's complement of the sign-extended multiplicant (\$x\$).

Based on the two above points I will illustrate a simple example \$x* y\$ for \$x=-3\$ and \$y = -2\$, in 3-bit 2's complement notation (pardon my naive formatting):

$$x=-3=101_2$$ $$y=-2=110_2$$ So \$x * y\$ in signed arithmetic will go like: $$101$$ $$110$$ $$---$$ $$\color{blue}{000}000$$ $$\color{blue}{11}101\text{_}$$ $$\color{blue}{0011}\text{__}$$ $$-------$$ $$\color{red}{1}{000110}$$

Notice how partial products are sign-extended (blue color).

Notice that since \$y\$ is negative, the last partial product was calculated as 2's complement of sign-extended \$x\$ which is \$ = 0011_2\$.

The 7th bit can be disregarded (red color), because the answer is only 6 bits when two 3-bit numbers are multiplied. The rest 6 bits hence form the signed result (product). Therefore, the answer is \$x*y = 000110_2=\color{green}{+6_{10}}\$.

For the same \$ x\$ and \$y\$, if you do unsigned arithmetic, you will get \$x*y= 011110_2=\color{red}{+30_{10}}\$ !!

Conclusion

In your example, while multiplying two signed binary numbers, you probably did (if hand-derived/calculator) unsigned arithmetic, not signed arithmetic, hence the wrong results.

Answer 2

What you have done is taken two signed numbers, and multiplied them together using unsigned arithmetic. Signed 2's compliment multiply is different.

In a higher-level language like C, C++ or Rust, make sure that your fractional numbers are sign extended into 32-bit signed integers and multiply them, then convert the result.

In assembly language, use the signed multiply instruction -- and if you're using a 32-bit processor and 32-bit data, make sure to sign-extend the numbers when you put them into the argument registers, or the result will be as if you did unsigned arithmetic.

Answer 3

I believe the core problem you are having has to do with multiplying signed (and perhaps unsigned) integers in twos-complement notation.

Let me illustrate by taking a page out of the instruction set for the ADSP-21xx Family DSPs from Analog Devices:

........

Please note that they include signed-signed multiplication, signed-unsigned multiplication, and so on. Pretty much every combination is there. There's a good reason why.

To provide a concrete example about why, let's assume that the word size is 16 bits. (I know, convenient.) Keeping in mind that a twos-complement negative number is just \$1+\left(\text{0xFFFF} - N\right)\$, then you find that multiplying two signed values results in the following table of possible permutations. (I'm using + for a positive value and - for a negative value.):

 N x M
(- x -)     [ 1 + (0xFFFF - N) ] * [ 1 + (0xFFFF - M) ]     +(M x N - [(N+M) << 16])
(- x +)     [ 1 + (0xFFFF - N) ] * M                        -(N x M - [M << 16])
(+ x -)     N * [ 1 + (0xFFFF - M) ]                        -(N x M - [N << 16])
(+ x +)     N x M                                           +(N x M)

In your case, you are performing (- x -), so you can directly multiply both your 16-bit values using an unsigned multiplication that produces a 32-bit result. Here, you'd multiply 0xCD33 by 0xF999 and get 0xC8113E7B as the result of this unsigned multiplication. Let's follow through:

    0x C811 3E7B
  - 0x CD33
  - 0x F999
  ------------
    0x 0145 3E7B

Which is the correct result (if you keep in mind that this is a \$Q_{25}\$ format, now.)

So, your answer, in binary, is: +0.1010001010011111001111011

You can round or truncate that as you see fit. But you will need to keep track of its format when doing that.

For example, if you wanted to round that into another 16-bit word while retaining maximum precision, you'd have 0.101000101010000 (the upper bit being '0' to retain the sign, of course) and that would now be in a \$Q_{15}\$ format. You have to "normalize" the value, first, counting the shifts required (6 of them) and the number of bits you are truncating/rounding off (16) in order to know that \$Q_{25} + 6 - 16 = Q_{15}\$.

This last bit is one of the reasons why a fully combinatorial barrel-shifter is very handy! If your MCU lacks one, I'd recommend finding another. The barrel-shifter is super-useful when you are screwing around like this. Analog Device's ADSP-21xx family was a marvel for its time (still is, I think.) You can read the chapters for the ADSP-21xx Family Manual at your leisure.

Answer 4

I think the main problem is that you didn't do the two's complement multiplication correctly.

To convert -6.35 to binary with 11 fractional bits, do as follows.

1. Multiply 6.35 * 2¹¹ = 13005.
2. Optionally, convert to hex: 13005 -> 0x32CD.
3. Convert to binary: 0011 0010 1100 1101
4. Negate it by inverting every bit and adding 1: 0011 0010 1100 1101 -> 1100 1101 0011 1110

The binary point would be here: 1100 1.101 0011 1110.

To convert -0.1 to binary with 14 fractional bits, do as follows.

1. Multiply 0.1 * 2¹⁴ = 1638.
2. Optionally convert to hex: 1638 -> 0x0666.
3. Convert to binary: 0000 0110 0110 0110
4. Negate it by inverting every bit, then adding 1: -> 1111 1001 1001 1010

The binary point would be here: 11.11 1001 1001 1010.

If you are having trouble with the two's compliment multiplication, convert the numbers to unsigned first then do the unsigned multiplication. The sign of the result is positive if both numbers have the same sign, and negative if both numbers have different signs. After multiplying using unsigned arithmetic, you can negate the result if needed (based on sign of two inputs).

It is easier to do the multiplication in decimal, but of course it doesn't matter what base is used the result will be the same number.

1. Multiply: 1638 * 13005 = 21302190.
2. Optionally convert to hex: 21302190 -> 0x1450BAE
3. Convert to binary: 0001 0100 0101 0000 1011 1010 1110

In this case, we know that the result is positive because the two sign bits of the inputs were both negative. So this is the final result. If only one of the inputs had been negative, then we would negate the final result using the same procedure, invert every bit, then add one.

Since fractional bits accumulate, there are now a total of 25 fractional bits in the result. So the binary point will be located as follows:

000.1 0100 0101 0000 1011 1010 1110

If you convert that back to decimal it is pretty close to 0.635. The way I do it is as follows:

13005 * 1638 / (2²⁵) = 0.6349

But you can painstakingly add up the bits, too. 1/2 + 1/8 + 1/128 + 1/512 + 1/16384 + 1/64k + 1/128k + 1/256k + 1/1024k.... etc