Multiplication using shift-add technique

[ashfaq2419]

Dear friends,

i have to design a structure in which i have to implement some multiplications and additions/subtractions. for multiplications, i am simply using the shift-add tecchnique. e.g. if i have to multiply 51 (which is constant) with an incoming number e.g. 'a' then i am doing like, (a<<5)+(a<<4)+(a<<1)+a. it is OK for a positive number. but i want to know that if the incoming number is negative e.g. in my case it is -32 and i am using 10 bits to represent it, what should i do in order to maintain the rules of multiplications that a +*+=+, +*-=- etc. i myself tried to do a little technique but it is not efficient. e.g. i am saving the MSB of the incoming number in a temporary std_logic. then after shifts and adds, i am concatenating the inverted sign_bit with the result. but here i have a problem of the incoming number is zero. in this case the result must be 0 but after concatenating a '1' with it, makes it something else.

please guide me in this regard. i need a little detail because i have worked on it for the last 2 days but to now avail.

regards

 

[jeppe]

Hi

Try this site - could be useful for you.
http://users-tima.imag.fr/cis/guyot/Cours/Oparithm/english/Multip.htm

Your welcome

 

[flymolo]

Hi
Can you please provide some code? What is the width of a signal for the result.
I dont think you will get better result by coding it by hand. Synthesizers nowadays will infer constant coefficient multiplier efficiently. I would try this:

library ieee;
use ieee.numeric_std.all;
...
  constant c : signed(6 downto 0) := to_signed(51, 7);
  signal a : signed(9 downto 0);
  signal y : signed(16 downto 0);
begin
  y <= a*c;
...

there's always a little confusion with signed/unsigned Never mix both in one expression. It's pretty popular topic here on forum, youll find out why tu use numeric_std package instead std_logic for arithmetic.
If you want to stick with your initial description im not sure for now. But maybe extending the constant with leading 0 will help. You would have 10bit and 7bit operands, result will be 17 bit wide.
PS. I checked implementation on Spartan3 FPGA, you will get 47 LUT's (4-input) with description above. Its pretty cheap

 

[ashfaq2419]

dear friends,

the problem has been solved. because what i am doing now is, that e,g. i have to multiply some variable 'x' with 51. it means it can be written as x*(51) or x*(32+16+2+1) or (x<<5 + x<<4 + x<<1 + x). now let us suppose that x is 10 bits wide. it means that i should sign extend all the shifts up to 10+y where y is the maximum shift in this whole calculation. in this way i will preserve the sign of x. after doing this multiplication, i can normalize the result by taking some useful upper bits.

anyhow i am really very thankful to all the friends. but if somebody have some better idea he/she is welcome and i thanks in advance.

regards