Need Help with Booth Algorithm

[Digit0001]

Hi
Ok, Can someone tell me when creating the booth multiplier would you create two processes, one for testing of lower bits and the other for the state transitions?
Description of lab below:

The objective of this part of the lab is to design and simulate a multiplier for signed numbers binary using Booth’s algorithm. Negative numbers should be represented using by their twos complement. Booths algorithm works as follows assuming each number is n bits : Use an (n + 1) –bit register for the accumulator (A) so the sign bit will not be lost is an overflow occurs. Also, use an (n + 1)-bit register to hold the multiplier and an n-bit register (C) to hold the multiplicand.
1. Clear A ( the accumulator), load into the upper n bits of B, clear B0, and load the multiplicand into C.
2. Test the lower two bits of B (B1 B0).
a. If B1 B0 = 01 , then add C to A ( C should be the sign-extended to n + 1 bits and added to A using an (n + 1)– bit adder).
b. If B1 B0 = 10 , then add the twos complement of C to A
c. If B1 B0 = 11 or 00 skip this step
3 Shift A and B right one place with sign extended
4. Repeat steps 2 and 3 , n-1 more times
5. Product will be in A and B , ignore B0

This is what i had in mind.

generic(n : integer := 7);\mathrm{d} 
signal A : std_logic_vector(n+1 downto 0);
signal B : std_logic_vector(n+1 downto 0);
signal C : std_logic_vector(n downto 0); 
	Condition:process(A,B)
	begin
	B(1 downto 0) <= lower_B;
		for i in 1 to n-1 loop
			if(lower_B = "01") then
				A <= A + C(n+1 downto 0) & '0';
			elsif(lower_B = "10") then
				A <= ((not C) + '1');
			else
				A <= A;
			end if;
		end loop;
	end process Condition;

For the state transition how many would you have if i was doing a 8 x 8? would it be 17 states like a normal 2's complement multiplier or less?

P.S

 

[TrickyDicky]

First problem is you have no registers in your code, you need a clock for that.

 

[Digit0001]

yes i was going to give a clock in the state transition process, but my problem is how many states should be required for this multiplier

 

[permute]

This is a common college project for a class. The easiest method is the shift-and-add with fixed latency.
eg. start - conditional_add - shift - conditional_add - shift -conditional_add - shift ... - end
clearly you will not need more than N stages, for two N bit values.

you can also do the conditional add and the shift in the same cycle, which would give start - M0 - M1 - M2 - M3 ... MN - end.

you can also add more states if you want -- start - reset accumulator - check bit 0 - (add0 or wait0) - shift operand - check bit 1 - (add1 or wait1) - shift ... - end

all of these are easy to design, and have a fixed latency. You could do an algorithm where the check bit 0 would go to shift operand, instead of wait0. This is a bit more complex.

 

[ali_umair21]

you can find booths algorithm based divisions at opencore.org

 

[Digit0001]

.................................

 

[Digit0001]

ok i have tried this, however i get the wrong value when simulating. Can someone tell me what is wrong with my logic in this code?

 

[TrickyDicky]

You only need M, B and K in your state machine process sensitivity list (but thats not the problem)

in your clocked process, if SH = '1', it has priority over load = '1' and AD = '1' because it is on an "if" rather than an elseif. Could this be the problem?

I cant tell you whats wrong with the code unless you tell us what the problem is. I dont know what a wrong value is. Why dont you post the testbench code and say what the value should be?

 

[Digit0001]

ok well suppose i got the value 10100110 x 01100110 = 0100011110111000 however i get 00XXXXXXXXXXX001
From what i know there is a conflict occurring but i don't know where.
I don't think the testbench code has anything to do with the error, i have only declared the Mplier and Mcand the given value.

 

[TrickyDicky]

It might do - have you loaded a value into C?
With the testbench, I can run the code.

 

[Digit0001]

It might do - have you loaded a value into C?
With the testbench, I can run the code.

no, i made the value C <= Mcand

View attachment test_booth.txt

 

[TrickyDicky]

heres your problem:

if(Ad ='1') then
  A <= addout;
else
  A <= not_addout;
end if;

Because of this, A is never loaded with "00000000", because this assignments happens after the load assignemnt. In VHDL signals always take the last assignment give to them. Because you have said "if ad = '1' then else" rather than "elsif ad = '1', A always assigned either addout or not_addout (unless sh is '1', which overrides even this).

You should only really assign signals inside one if/elsif/else branch. You have assigned A (and other signals) in more.

 

[Digit0001]

what would be the best way to resolve this problem? by creating another signal like: if(Cadd = '1') then A <= not_addout; ?

 

[TrickyDicky]

no

combine all the separate ifs into a single if/elsif tree

---------- Post added at 12:21 ---------- Previous post was at 12:16 ----------

like this :

process(Clk)
	begin
		if Clk'event and Clk = '1' then 
			if(Load = '1') then --when the counter is cleared the multiplier is loaded
				A <= "000000000"; --clear A 
				Count <= "000"; -- clear counter;
				B(8 downto 1) <= Mplier; --Load upper bits to Mplier
				B(0) <= '0'; --Clear B(0)
				C <= Mcand; --Load Multiplicand
			elsif(Ad ='1') then
				A <= addout;
			
			elsif(Sh = '1') then -- counter is incremeneted when A-B registers are shifted
				A <= '0' & A(8 downto 1);
				B <= A(0) & B(8 downto 1); -- right shift A and B
				count <= count + 1; --increment counter
				
		  else
				A <= not_addout;
			end if;
		State <= nextState;
		end if;
	end process;

 

[Digit0001]

I simulated the code and i still cannot get correct answer. I have looked through my code and i cannot see what is wrong.
The value i simulated is 10100110 x 01100110 however i get 0011101101100100 instead of 0100011110111000.

 

[TrickyDicky]

Welcome to the world of debugging. I guess theres a problem with your design.