This blog was last modified 348 days before.

This post will discuss the addition, multiplication and division of fixed point number . Please make sure you have the basic knowledge about number encoding , for more info, check out Number Encoding Notes

ORG Encoding Multiply

When two number is represented by original encoding , the multiplication operation will be really simple.

Just like we have done with dec number, we just multiply all the significand part, and the sign of ans is acquired by the XOR of the two sign of two oprand.

Notice that we use two bits to represents sign in tmp sum and do NOT use bit to represent sign in mul.

IMG_2127

Notice that: If the bit count of oprand 2 is n, then we do n times (+, ->)

Checkout textbook 107

TWC Encoding Multiply

Therer are two method to calculate TWC mul.

Calibrate (校准法)

First do multiply like ORG encoding.

Then if oprand 2 is negative, add -X(TWC) to the result.

Notice that in this method, even if oprand 2 is negative (for example like 1.1011), we still use 1011 as mul.

Comparison

Checkout textbook P115

IMG_2128

As the img says: Everytime after SHR, we compare extra - low_bit_of_mul:

  • res < 0: tmpAns += (-X)(TWC)
  • res = 0: tmpAns += 0
  • res > 0: tmpAns += (X)(TWC)

X means oprand 1 here.

Notice we use two bits to represent sign in tmp ans, one bit to represent sign in mul in calculation.

When using this method, we need to first add an extra bit 0 to the mul part and do an add. This could be considered a preprocess.

Different from ORG, here the operation group becomes (->, +) and we do n times. (n is the bit count of the oprand 2)

Also notice that when finished calculation, we need to deprecate one more bit in the mul part. Anyway the bits count of the final result should be m+n. (m is the bit count of tmp ans and n is the bit count of oprand 2).

ORG 2-Bits Multiply

One bit a time is too time wasting, so we want to calculate 2 bits at a time. The basic thought is:

  • Using state of 2 bits to update tmp sum.
  • Perform SHR 2

State Corresponding Operation

IMG_3132

As the images implys:

Based on the number of the two bits (could be 0, 1, 2, 3) , we correspondingly add 0, X, 2X, 3X to the tmp sum.

But this is only the theoretical rules, we also need some tricks on it. Check out the passage below.

Tricks when doing operation

Divide +3X to -X+4X

Add 0, X, and 2X is easy. (we just do SHL on X to get 2X)

But how we can do ADD 3X?

The answer is we divide +3X into -X + 4X. That is in this round, we only do -X, and we set up a flag F to represent if we need to do +4X in next round.

Notice because we do a SHR 2 before into next round, so actually we only need to do +4X / 4 = +X in next round.

The final rules is like the image below:

IMG_3133

For more info, checkout Textbook P117.

Use +(-X(TWC)) to do -X

Since we use -X(TWC), so when we do SHR, we need to use the bit shift rules of Two's complement.

Notice: the mul part is still using |X|, and the final sign is still be acquired by XOR the sign of two oprand. The TWC here only be used to achieve -X.

Tricks when MUL is odd

There is two ways to solve this.

Add 0 to right most bit

For example if the mul is 0.01011, then make it to be: 0.010110. Then when retrive the result, abandon the right most bit. For example if the result is 000.10111 110100, then we only want 000.1011111010 part.

Anyway the point is the bit count of the result significand is always the significand bit count sum of two oprand. This rules always applys (we use this rules in TWC one bit multiply too)

Add 0 to the left most bit

This time The last SHR opreation only shift one bit.

Conclusion

  • Divide +3X operation to -X and +4X. Set up flag.
  • Use 3 bit to represent sign of tmp sum.
  • Use TWC bit shift rules when do SHR.

TWC Two Bit Multiply

  • Use 3 bits to represent sign in tmp sum.
  • Add 0 at the rightmost bit of mul.
  • The last SHR only shift one bit.

This time, we except the mul part is odd. (because that means it will become even after adding 0 to the right)

IMG_3134

The image above shows the rules.

When MUL is even

Add one more sign bit to mul

Then we don't do SHR at all.

For example, 1.01001 to 11.01001.

Add 0 to rightmost bit of mul

Don't change any operation. The last time we still need to do SHR 1.

We found that both in ORG and TWC two bit multiplication, when adding bit to right, then it will not affect the operation. But when adding bit to left, then we will decrease SHR by one time.

ORG One Bit Division

The basic thought is test and restore.

IMG_3147

As the image above.

Leftmost Bit In Result

Notice that this method required opr1 < opr2, so the leftmost bit of the result will be zero. And this bit will be covered by sign bit.

Result: 0010011
Sign: 1
Answer: 1.010011

ORG One Bit Division (Optimized)

Consider what we need to do in previous method:

Consider the rest is R, opr2 is Y.

  • R_i < 0: R_i += Y <- R_(i+1) - Y
  • R_i > 0: <- R_(i+1) - Y

<- means left shift

So how can we simplify it? Notice the first situation. We prefer to not do += part and directly left shift.

SHL (R_i - Y) = R_(i+1) - 2Y
R_(i+1) - 2Y + Y = R_(i+1) - Y

So we found that if R_i < 0, then we can directly shift, and replace the -Y opreation to +Y operation.

Textbook P125