delucagiovanni forum

Ciao,
Dovrei realizzare la descrizione VHDL di un moltiplicatore digitale che realizzi
l’algoritmo di Booth (con codifica a 2 bit) per due moltiplicandi rappresentati su N ed M bit rispettivamente e con risultato su N+M bit.
Qualcuno potrebbe dirmi se sono corretti?
Vi posto i codici sorgente del moltiplicatore(A) e del test bench(B) che ho provato a scrivere.
Grazie in anticipo

A) library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
entity booths is
GENERIC(k : POSITIVE := 7); --input number word length less one
Port ( a,b : in STD_LOGIC_VECTOR (k downto 0);
mul : out STD_LOGIC_VECTOR (2*k+1 downto 0));
end booths;

architecture Behavioral of booths is

begin

process(a,b)

variable m: std_logic_vector (2*k+1 downto 0);
variable s: std_logic;

begin
m:="00000000"&b;
s:='0';
for i in 0 to k loop
if(m(0)='0' and s='1') then
m(k downto k-3):= m(k downto k-3)+a;
s:=m(0);
m(k-1 downto 0):=m(k downto 1);
elsif(m(0)='1' and s='0') then
m(k downto k-3):= m(k downto k-3)-a;
s:=m(0);
m(k-1 downto 0):=m(k downto 1);
else
s:=m(0);
m(k-1 downto 0):=m(k downto 1);
end if;
end loop;
mul<=m;
end process;
end Behavioral;


B)library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
entity Testbench_di_Booth is
end Testbench_di_Booth;
architecture behavior of Testbench_di_Booth is

component booths
GENERIC(k : POSITIVE := 7); --input number word length less one
Port( a,b : in STD_LOGIC_VECTOR (k downto 0);
mul : out STD_LOGIC_VECTOR (2*k+1 downto 0));
end component;

--Inputs
signal A : STD_LOGIC_VECTOR (7 downto 0):= "00000011";
signal B : STD_LOGIC_VECTOR (7 downto 0):= "00000100";
--Outputs
signal MUL : STD_LOGIC_VECTOR(15 downto 0);

begin
--Instantiate the UnitUnder Test (UUT)
uut: booths PORT MAP
(a => A,
b => B,
mul => MUL);

--Stimulus process
stim_proc: process
begin

--insert stimulus here
A<="00000011"; B<="00000100"; wait for 500 fs;
A<="00000110"; B<="00000111"; wait for 500 fs;
A<="00001011"; B<="00000100"; wait for 500 fs;
wait;
end process;
end;

caro mike,
qualcuno mi ha insegnato alcune buone regole di comportamento quando ci si registra in un forum serio e professionale quale io reputo questo.

1) presentarsi e salutare
2) partecipare al forum attivamente (se possibile)
3) ricevere credibilità da parte dei moderatori
4) quando si postano quesiti fare in modo da non far perdere tempo alle persone potenzialmente disponibili e quindi:
5) formattare o allegare i sorgenti e le fonti in modo adeguato

Di sicuro, adoperandoti in tal senso, qui troverai anche in futuro persone molto disponibili e con la voglia di aiutarti

ciao e scusami per la segnalazione.

Ciao cyclone,

Scusate ma non volevo sembrare troppo "invadente"; in ogni caso, caro cyclone, mi dispiace averti dato questa brutta impressione.
Cerco di riportare nuovamente i codici formattati.

BOOTH:

Code: Select all

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
entity booths is
   GENERIC(k : POSITIVE := 7); --input number word length less one
   Port ( a,b : in STD_LOGIC_VECTOR (k downto 0);
          mul : out STD_LOGIC_VECTOR (2*k+1 downto 0));
end booths;

architecture Behavioral of booths is

begin 
   
process(a,b)

variable m: std_logic_vector (2*k+1 downto 0);
variable s: std_logic;

begin
m:="00000000"&b;
s:='0';
for i in 0 to k loop
if(m(0)='0' and s='1') then
   m(k downto k-3):= m(k downto k-3)+a;
   s:=m(0);
   m(k-1 downto 0):=m(k downto 1);
elsif(m(0)='1' and s='0') then
      m(k downto k-3):= m(k downto k-3)-a;
      s:=m(0);
      m(k-1 downto 0):=m(k downto 1);
else
      s:=m(0);
      m(k-1 downto 0):=m(k downto 1);
end if;
end loop;
      mul<=m;
end process;
end Behavioral;

TEST BENCH:

Code: Select all

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
entity Testbench_di_Booth is
 end Testbench_di_Booth;
 architecture behavior of Testbench_di_Booth is
 
 component booths
    GENERIC(k : POSITIVE := 7); --input number word length less one
 Port( a,b : in STD_LOGIC_VECTOR (k downto 0);
       mul : out STD_LOGIC_VECTOR (2*k+1 downto 0));
 end component;
 
 --Inputs
 signal A : STD_LOGIC_VECTOR (7 downto 0):= "00000011";
 signal B : STD_LOGIC_VECTOR (7 downto 0):= "00000100";
 --Outputs
 signal MUL : STD_LOGIC_VECTOR(15 downto 0);
 
 begin
    --Instantiate the UnitUnder Test (UUT)
 uut: booths PORT MAP
 (a => A,
  b => B,
  mul => MUL);   
 
  --Stimulus process
 stim_proc: process
 begin
   
 --insert stimulus here
 A<="00000011"; B<="00000100"; wait for 500 fs;
 A<="00000110"; B<="00000111"; wait for 500 fs;
 A<="00001011"; B<="00000100"; wait for 500 fs;
 wait;
 end process;
 end;

in qualità di amm. approvo pienamente quanto postato da cyclone.

ma assolutamente voglio sindacare sul modo di intervenire di mike.
capisco che si tratta di uno studente che ha trovato difficoltà nell'applicare un algoritmo per moltiplicare due numeri.

ti posso aiutare spiegandoti in poche parole l'algo.

Algoritmo per moltiplicare X=xxxxxxxx e Y=yyyyyyyy:
1) inizializzare P a 0
2) aggiungere uno 0 a destra di Y (Y diventa: yyyyyyyy0)
3) esaminare la coppia C di bit piu' a destra di Y
3a) se C=01 sommare X a P (P=P+X)
3b) se C=10 sottrarre X da P (P=P-X)
4) traslare X a sinistra di una posizione
5) traslare Y a destra di una posizione
6) tornare al punto 3 se non si sono esauriti i bit di Y

ti faccio un esempio:
Moltiplicatore a codifica di Booth.... proviamo a moltiplicare due numeri es: 79 x 83

Code: Select all


  X= 01001111 (79) Y=010100110 P=0000000000000000 (0)
  C=10: P=P-X=(0)-(79)=-79 ; Lshift X ; Rshift Y
  X= 010011110 (158) Y= 01010011 P=1111111110110001 (-79)
  C=11: Lshift X ; Rshift Y
  X= 0100111100 (316) Y= 0101001 P=1111111110110001 (-79)
  C=01: P=P+X=(-79)+(316)=237 ; Lshift X ; Rshift Y
  X= 01001111000 (632) Y= 010100 P=0000000011101101 (237)
  C=00: Lshift X ; Rshift Y
  X= 010011110000 (1264) Y= 01010 P=0000000011101101 (237)
  C=10: P=P-X=(237)-(1264)=-1027 ; Lshift X ; Rshift Y
  X= 0100111100000 (2528) Y= 0101 P=1111101111111101 (-1027)
  C=01: P=P+X=(-1027)+(2528)=1501 ; Lshift X ; Rshift Y
  X= 01001111000000 (5056) Y= 010 P=0000010111011101 (1501)
  C=10: P=P-X=(1501)-(5056)=-3555 ; Lshift X ; Rshift Y
  X= 010011110000000 (10112) Y= 01 P=1111001000011101 (-3555)
  C=01: P=P+X=(-3555)+(10112)=6557 ; Lshift X ; Rshift Y

il risultato finale è = 6557


che sistema di sviluppo usi?
che simulatore stai usando per testare il tb?

Salve amministratore,

rivolgo anche a te le scuse per il modo con cui mi sono "presentato". Detto ciò ti ringrazio per avermi dedicato un pò del tuo tempo.
Il mio problema non è tanto capire l'algoritmo, bensì riuscirlo ad implementare in VHDL. Ho sempre lavorato con matlab e labview
ma è la prima volta che mi confronto con il VHDL.
Sto usando Aldec Active-HDL Student Edition (come hai ben capito sono uno studente), ho provato a scrivere questi codici ma non funziona nulla; mi spiego meglio: quando "compilo" i codici mi da 0 errori, però quando vado a simulare non appare nulla nelle WAVEFORM e da come risultato della moltiplicazione UUUU.
Questo mi ha fatto pensare che sia sbagliato il codice.

scuse accettate.

purtroppo noi utilizziamo Quartus II Altera.

spero che qlc altro ti possa aiutare qui nel forum (confido in flz che è molto presente)

se mi ritrovo un ritaglio di tempo provo a simulare il tutto con quartus e ti faccio sapere.

Grazie mille. Speriamo di riuscire a risolvere.
Ciao

ho provato per curiosità a sintetizzare il sorgente su fpga stratix con quartus.
spunta subito un errore come visibile in figura.

Error (10504): VHDL error at booths.vhd(32): slice that is assigned to target slice has 8 elements, but must have same number of elements as target slice (4)

fai un search su google e trova il rimedio....
postalo appena lo trovi.

Se vuoi puoi rivedere questo x 4 bit:

Code: Select all


library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
   
    entity Booth4 is
        port(A, B: in std_logic_vector(3 downto 0);
             O: out std_logic_vector(7 downto 0));
    end Booth4;
   
    architecture boothMult4Arch of Booth4 is
        begin
           
            process(A, B)
             variable num: std_logic_vector(8 downto 0);
             variable Y, Z: unsigned(3 downto 0);
             variable i:integer;

                begin
                    num := "000000000";
                    Y := unsigned(B);
                    num(4 downto 1) := A;
                   
                    for i in 0 to 3 loop
                       if(num(1) = '1' and num(0) = '0') then
                          Z := unsigned(num(8 downto 5));
                          num(8 downto 5) := std_logic_vector(Z - Y);
                         
                       elsif(num(1) = '0' and num(0) = '1') then
                          Z := unsigned(num(8 downto 5));
                          num(8 downto 5) := std_logic_vector(Z + Y);
                         
                       end if;                       
                       num(7 downto 0) := num(8 downto 1);
                       
                    end loop;
                   
                    O(7 downto 0) <= num(8 downto 1);                   
                end process;               
            end boothMult4Arch;


Il problema riscontrato è che m ed a hanno un numero di elementi diverso!?
Però se così fosse dovrebbe dare errore anche alla riga 27........mmmmmm

Ho trovato questo:
http://quartushelp.altera.com/11.1/mergedProjects/msgs/msgs/evrfx_vhdl_target_slice_is_a_elements_value_is_b_elements.htm

il sintetizzatore fa cose strane (ma esatte!!)
se commenti la riga 32 l'errore si sposta alla riga 27

prova a vedere l'esempio che ho scritto per un moltiplic a 4 bit che ho appena appeso al post

Code: Select all

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
   
    entity Booth4 is
        port(A, B: in std_logic_vector(3 downto 0);
             O: out std_logic_vector(7 downto 0));
    end Booth4;
   
    architecture boothMult4Arch of Booth4 is
        begin
           
            process(A, B)
             variable num: std_logic_vector(8 downto 0);
             variable Y, Z: unsigned(3 downto 0);
             variable i:integer;

                begin
                    num := "000000000";
                    Y := unsigned(B);
                    num(4 downto 1) := A;
                   
                    for i in 0 to 3 loop
                       if(num(1) = '1' and num(0) = '0') then
                          Z := unsigned(num(8 downto 5));
                          num(8 downto 5) := std_logic_vector(Z - Y);
                         
                       elsif(num(1) = '0' and num(0) = '1') then
                          Z := unsigned(num(8 downto 5));
                          num(8 downto 5) := std_logic_vector(Z + Y);
                         
                       end if;                       
                       num(7 downto 0) := num(8 downto 1);
                       
                    end loop;
                   
                    O(7 downto 0) <= num(8 downto 1);                   
                end process;               
            end boothMult4Arch;


Ho provato a buttar giù un test bench anche per questo codice che hai postato, ma anche in questo caso fa il solito scherzetto durante la simulazione. Il mistero si infittisce!!!

Code: Select all

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
entity Testbench_di_Booth is
 end Testbench_di_Booth;
 architecture behavior of Testbench_di_Booth is
 
 component Booth4
   
 Port(A, B: in std_logic_vector(3 downto 0);
      O: out std_logic_vector(7 downto 0));
 end component;
 
 --Inputs
 signal a : STD_LOGIC_VECTOR (3 downto 0):= "0011";
 signal b : STD_LOGIC_VECTOR (3 downto 0):= "0100";
 --Outputs
 signal o : STD_LOGIC_VECTOR(7 downto 0);
 
 begin
    --Instantiate the UnitUnder Test (UUT)
 uut: Booth4 PORT MAP
 (A => a,
  B => b,
  O => o);   
 
  --Stimulus process
 stim_proc: process
 begin
    --hold reset state for100ms.
 wait for 1 ps;
 --insert stimulus here
 a<="0011"; b<="0100"; wait for 500 fs;
 a<="0110"; b<="0111"; wait for 500 fs;
 a<="1011"; b<="0100"; wait for 500 fs;
 wait;
 end process;
 end;
 

visto che la cosa incuriosisce anche il sottoscritto
ho provato a simulare il mio codice con modelsim ed ecco il risultato!
il mio codice è esatto e la simulazione ne mostra il risultato.

non so che esperienza hai, ma c'è qualcosa che ti sfugge nell'adoperare i tb e soprattutto il tools.

Buongiorno amministratore,

ok quindi sicuramente c'è qualcosa che mi sfugge per quanto riguarda la simulazione.
Vorrà dire che oggi cercherò di capire bene come va fatta la simulazione e dopo cercherò di generalizzare il codice per stringhe di lunghezza arbitraria.

Ps: Prof. ho visitato la sua pagina web.... wow molto interessante!!!
Soprattutto considerando che tutto ciò è ambientato nella nostra magica terra.

Forse ci siamo.... Cosa ne dite?

Code: Select all

 -------------------------------------
-- Define data width
--
-------------------------------------
package mypackage is
   constant NBITS :natural := 7;
   constant MBITS :natural := 9;
end mypackage;
---------------------------------------------------------
-- Booth-1 multiplier
--
----------------------------------------------------------      
library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;
use IEEE.std_logic_unsigned.all;
use work.mypackage.all;

entity booth_1 is
    port (
        X: in STD_LOGIC_VECTOR (NBITS-1 downto 0);
        Y: in STD_LOGIC_VECTOR (MBITS-1 downto 0);
         P: out STD_LOGIC_VECTOR (NBITS+MBITS-1 downto 0)
     );
end booth_1;

architecture simple_arch of booth_1 is

component booth_1_cell
    Port ( P : in std_logic_vector(MBITS-1 downto 0);
           Y : in std_logic_vector(MBITS-1 downto 0);
           x_i : in std_logic_vector(1 downto 0);
           S : out std_logic_vector(MBITS  downto 0)
          );
end component;

type conections is array (0 to NBITS) of STD_LOGIC_VECTOR (MBITS downto 0);
Signal wires: conections;
Signal eX: STD_LOGIC_VECTOR (NBITS downto 0);

begin
  eX(NBITS downto 1) <= X;     eX(0) <= '0';
  wires(0) <= (others => '0');
  iterac: for I in 0 to NBITS-1 generate
  mult: booth_1_cell port map (P => wires(i)(MBITS downto 1),
                                   Y => Y, x_i => eX(i+1 downto i), S => wires(i+1) );
        p(i) <= wires(i+1)(0);
 end generate;

 p(MBITS+NBITS-1 downto NBITS) <= wires(NBITS)(MBITS downto 1);

end simple_arch;

Code: Select all

--
-- booth-1 cell: basic cell for booth 1 multiplier
--
----------------------------------------------------------
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
use work.mypackage.all;

entity booth_1_cell is
    Port ( P : in std_logic_vector(MBITS-1 downto 0);
           Y : in std_logic_vector(MBITS-1 downto 0);
           x_i : in std_logic_vector(1 downto 0);
           S : out std_logic_vector(MBITS  downto 0)
          );
end booth_1_cell;


architecture Behavioral of booth_1_cell is
signal sS : std_logic_vector(MBITS-1 downto 0);
begin
the_mux: process(x_i,P, Y)
         begin
            case x_i is
               when "00" => S <= (P(MBITS-1) & P);
               when "01" => S <= (P(MBITS-1) & P) + (Y(MBITS-1) & Y);
               when "10" => S <= (P(MBITS-1) & P) - (Y(MBITS-1) & Y);
               when "11" => S <= (P(MBITS-1) & P);
               when others => NULL;
            end case;
end process;

end Behavioral;

Code: Select all

-- VHDL Test Bench for booth-1 multiplier
--
-- Notes:
----------------------------------------------------------------------
LIBRARY  IEEE;
USE IEEE.std_logic_1164.all;
USE IEEE.std_logic_arith.all;
USE IEEE.std_logic_signed.all;
USE work.mypackage.all;


ENTITY test_exhaustive IS
END test_exhaustive;

ARCHITECTURE behavioural OF test_exhaustive IS

   COMPONENT booth_1
   PORT(
      X : IN std_logic_vector(NBITS-1 downto 0);
      Y : IN std_logic_vector(MBITS-1 downto 0);
      P : OUT std_logic_vector(MBITS+NBITS-1 downto 0)
      );
   END COMPONENT;
   --Inputs
   SIGNAL x :  std_logic_vector(NBITS-1 downto 0);
   SIGNAL y :  std_logic_vector(MBITS-1 downto 0);
    --Outputs
   SIGNAL p :  std_logic_vector(MBITS+NBITS-1 downto 0);

BEGIN
    --Instantiate the UnitUnder Test (UUT)
   uut: booth_1 PORT MAP(X => x, Y => y, P => p);

    --Stimulus process
 stim_proc: process
 begin
    --hold reset state for100ms.
 wait for 1 ns;
 --insert stimulus here
 x<="0000011"; y<="000000100"; wait for 50 ns;
 x<="0000110"; y<="000000111"; wait for 50 ns;
 x<="0001011"; y<="000000100"; wait for 50 ns;
 wait;
 end process;
 

END;



ok, esatto.

PS. Però attenzione al tuo prof. che potrebbe

Dice davvero? perchè dovrebbe?

Non è necessario che te lo spieghi,
ci potresti arrivare da solo.

che Dio me la mandi buona!!!

...nonostante mi avete "evocato" sono arrivato troppo tardi, vedo che il problema è stato risolto
Ne approfitto comunque per dare il benvenuto a Mike

Ciao!
PS: Non sapevo di questo algoritmo di Booth, ma velocizza effettivamente le operazioni su FPGA rispetto ad algoritmi più classici o l'utilizzo di celle native moltiplicatrici?

Ciao flz,

grazie del benvenuto.

Booth ha ideato questo algoritmo osservando che la fattorizzazione in somme e differenze
di potenze di 2 del moltiplicatore si può automatizzare valutando la sequenza dei
bit del moltiplicatore stesso.

Nella maggior parte dei casi, questo approccio consente la riduzione del numero
di operazioni di somma necessarie al calcolo del prodotto.
La riduzione del numero di somme necessarie dipende però dalla disposizione dei bit.


Il numero di somme necessarie è notevolmente ridotta in caso di sequenze ripetute di 1 (es:“1011110”).
Non c’è riduzione delle somme quando il moltiplicatore presenti alternanze di 0 e 1 (es:“1010101”).

In media, la velocità di calcolo di una moltiplicazione eseguita con l’algoritmo di
Booth è uguale a quella che si raggiunge con gli algoritmi standard.


Ciao