Multiplication by power series summation with nega

问题:

How can I calculate a floating point multiplicand in Verilog? So far, I usually use shift << 1024 , then floating point number become to integer. Then I do some operations, then >> 1024 to obtain a fraction again.

For example 0.3545 = 2^-2 + 2^-4 + ...

I have question about another way, like this. I don't know where does the minus (-) comes from:

0.46194 = 2^-1 - 2^-5 - 2^-7 + 2^-10.

I have just look this from someone. but as you way, that is represented like this

0.46194 = 2^-2 + 2^-3 + 2^-4 + 2^-6 + 2^-7 + 2^-10 + .... .

I don't understand how does it know the minus is used it?

How do we know when the minus needed to it? Also how can I apply to verilog RTL?

UPDATE : I understand the concept the using minus in operation. But Is there any other way to equation or methodologies what to make reduce expression what multiplying with power of 2?

UPDATE : how can we use this method in verilog? for example, I have leaned 0.46194 = 2^-1 - 2^-5 - 2^-7 + 2^-10. then this code was written like this in verilog. 0.011101101 ='hED = 'd237. So the point of the question is how can we apply it to application in verilog?

---

UPDATE : Sir Would you please check this one? there are a little difference result.

0.46194 = 0.011101101. I just tried like this

0.011101101

0.100T10T01

= 2^-1 - 2^-4 + 2^-5 - 2^-7 + 2^-9. = 0.462890625

Something different. What do I wrong?

回答1:

In a 4 bit base 2 number can have these values:

Base 2: Unsigned 4 bit integer, 
2^3  2^2  2^1  2^0  
  8    4    2    1 

If we have a 0111 it represents 7. If we were to multiply by this number using a shift add architecture it would take 3 clockcycles (3 shift and adds).

An optimisation to this is called CSD (Canonical Signed Digit. It allows minus one to be present in the 'binary numbers'. We shall represent -1 as one bar, or T as that looks like a one with a bar over the top.

100T represents 8 - 1 which is the same as 0111. It can be observed that long runs of 1's can be replaced with a the 0 that ends the run becoming 1 and the first 1 of the run becoming a -1, (T).

An example of conversion:

00111101111
01000T1000T

But if passed in two section we would get :

00111101111
0011111000T
010000T000T

We have taken a number that would take 8 clock cycles or 8 blocks of logic to compute and turned it into 3.

Related questions to fixed point values in Verilog x precision binary fixed point representation? and verilog-floating-points-multiplication.

To cover the follow up question:

To answer the follow up section about your question on CSD conversion. I will look at them as pure integers to simplify the numbers, this is the same as multiplying the values by 2^9 (9 fractional bits).

256  128 64 32 16 8 4 2 1
  0    1  1  1  0 1 1 0 1

128 + 64 +32 + 8 +4 +1 => 237

Now with your CSD conversion:

256  128 64 32 16 8 4 2 1
  1    0  0  T  1 0 T 0 1

256  -32 + 16 - 4 + 1 => 237

You can see your conversion was correct. I get 237* 2^-9 as 0.462890625, which matches your answer when converted back to fractional. The 0.46194 that you started with must have been a rounded version, or when quantised to 9 fractional bits gets truncated. This error is known as quantisation error. The most important thing here though is that you got the CSD conversion correct.

回答2:

Multiplication of a variable by a constant is often implemented by adding the variable to shifted versions of itself. This is much cheaper to put on an FPGA than a multiplier circuit accepting two variables.

You can get further savings when there's a sequence of 1-bits in the constant, by using subtraction as well. (A subtraction circuit is only equally expensive as addition.)

Consider the number 30 = 11110. It's equal to 16 + 8 + 4 + 2, but it's also equal to 32 - 2.

In general, a sequence of multiplicand 1-bits, or the sum of several successive powers of two, can be formed by adding the first power of two after the most significant bit, and subtracting the least significant bit. Hence, instead of 16x + ... + 2x, use 32x - 2x.

It doesn't matter if the sequence of 1-bits is part of a fraction or an integer. You're just applying the identity 2^a = 1 + ∑2^0 ... 2^(a-1), in other worsd ∑2^0 ... 2^a = 2^(a+1) - 1.