Optimierte Multiplikationsverfahren mit >= 32 Bit Inputs

[Nico B. (Firma: Hochschule Bonn-Rhein-Sieg) (jacetms)]

Hallo Zusammen,

vorab möchte ich sagen, dass ich im Bereich VHDL ein Neuling bin, daher 
möchte ich auch meine Frage etwas detaillierter vorstellen.

Ich möchte gerne eine bestimmte Form der Montgomery Multiplikation in 
VHDL umsetzten. Dabei werden die Faktoren (a und b jeweils 32 Bit 
std_logic_vector) für die Multipliaton in 5 Teile zerlegt.
Dies geschieht durch Na = (a'length / 5) + (a'length mod 5). Nb ist 
identisch aufgebaut. D.h. bei einem 32 Bit Input erhalte ich 5 Outputs a 
8 Bit, was auch ohne Probleme funktioniert.

Im nächsten Schritt soll die Montgomery Multiplikation mit diesen 5 
Inputs durchgeführt werden. Da dieses Verfahren sehr groß ist, werde ich 
nur einen kleinen Teil präsentieren.

Die beiden Faktoren (a4,a3,a2,a1,a0),(b4,b3,b2,b1,b0) jeweils 8 Bit 
lang, werden beispielsweise folgendermaßen miteinander multipliziert:

(a0 + a1 + a2 + a3 + a4) * (b0 + b1 + b2 + b3 + b4) * (X^5 - X^4 + X^3)

Im hinteren Teil werden die Ergebnisse wieder um gewisse Stellen 
geshiftet.
Daher wird auch das Na,Nb benötigt, um zu wissen, um wie viele Stellen 
geshiftet werden muss.

Im Folgenden Beispiel werden die Faktoren a und identisch b 
folgendermaßen behandelt:
a4 = tempf1upper
a3 = tempf1middle1
a2 = tempf1middle2
a1 = tempf1middle3
a0 = tempf1lower

b4 = tempf2upper
b3 = tempf2middle1
b2 = tempf2middle2
b1 = tempf2middle3
b0 = tempf2lower

Ich habe das ganze jetzt mit unsigned realisiert. Bei der Simulation 
stelle ich jedoch fest, dass er mir bei den Variablen tempResult und 
shiftResult die Werte in die Mitte des Vektors schreibt. Woran liegt 
dies?

Gäbe es eine Möglichkeit, die Berechnung in std_logic_vectoren 
durchzuführen? Am liebsten wäre es, wenn ich weiterhin  mit integer, 
unsigned, signed arbeiten könnte, da so das shiften sehr einfach 
durchgeführt werden kann. Im weiteren Verlauf soll das ganze aber mit 
256 Bit werden funktionieren. Daher komme ich leider mit Integern und 
der gleichen nicht weiter.

Ich hoffe mir kann weiter geholfen werden und bedanke mich schon mal für 
die Antworten.

VG

JaceTMS

Beispiel-Quellcode (Soll erstmal nur Simulierbar sein):

library ieee;
use ieee.std_logic_1164.ALL;
use IEEE.numeric_std.all;

entity mont_mult_ma_nb is
  port(
      --Eingehnde Ports
      f1upper: in std_logic_vector (7 downto 0);
      f1middle1: in std_logic_vector (7 downto 0);
      f1middle2: in std_logic_vector (7 downto 0);
      f1middle3: in std_logic_vector (7 downto 0);
      f1lower: in std_logic_vector (7 downto 0);
      f2upper: in std_logic_vector (7 downto 0);
      f2middle1: in std_logic_vector (7 downto 0);
      f2middle2: in std_logic_vector (7 downto 0);
      f2middle3: in std_logic_vector (7 downto 0);
      f2lower: in std_logic_vector (7 downto 0);
      randomGen: in std_logic_vector (1 downto 0);
      N : in integer;
      clk : in std_logic;
      --Ausgehende Ports
      result : out std_logic_vector
    );
end mont_mult_ma_nb;

architecture Behavioral of mont_mult_ma_nb is
begin
  montgomery : process (f1upper, f1middle1, f1middle2, f1middle3, f1lower, f2upper, f2middle1, f2middle2, f2middle3, f2lower, randomGen, N, clk)
    
    --Temporäre Variablen für die Berechnung
    variable tempf1upper : unsigned (7 downto 0) := (others=>'0');
    variable tempf1middle1 : unsigned (7 downto 0) := (others=>'0');
    variable tempf1middle2 : unsigned (7 downto 0) := (others=>'0');
    variable tempf1middle3 : unsigned (7 downto 0) := (others=>'0');
    variable tempf1lower : unsigned (7 downto 0) := (others=>'0');
    variable tempf2upper : unsigned (7 downto 0) := (others=>'0');
    variable tempf2middle1 : unsigned (7 downto 0) := (others=>'0');
    variable tempf2middle2 : unsigned (7 downto 0) := (others=>'0');
    variable tempf2middle3 : unsigned (7 downto 0) := (others=>'0');
    variable tempf2lower : unsigned (7 downto 0) := (others=>'0');
    
    --Temporäre Variablen für die vorberechneten Ergebniswerten
    variable tempResult1 : unsigned (21 downto 0) := (others=>'0');

    
    --Temporäre Variablen für shift_left Funktion
    variable shiftResult1 : unsigned (63 downto 0) := (others=>'0');

      
  begin
  
    if (rising_edge(clk)) then
      if (randomGen = "11") then
        
        --Typenumwandlung von std_logic_vector -> signed
        tempf1upper := unsigned(f1upper(7 downto 0));
        tempf1middle1 := unsigned(f1middle1(7 downto 0));
        tempf1middle2 := unsigned(f1middle2(7 downto 0));
        tempf1middle3 := unsigned(f1middle3(7 downto 0));
        tempf1lower := unsigned(f1lower(7 downto 0));
        tempf2upper := unsigned(f2upper(7 downto 0));
        tempf2middle1 := unsigned(f2middle1(7 downto 0));
        tempf2middle2 := unsigned(f2middle2(7 downto 0));
        tempf2middle3 := unsigned(f2middle3(7 downto 0));
        tempf2lower := unsigned(f2lower(7 downto 0));
        
        --Berechnung der Multiplikationen
        tempResult1 := (tempf1upper + tempf1middle1 + tempf1middle2 + tempf1middle3 + tempf1lower) * (tempf2upper + tempf2middle1 + tempf2middle2 + tempf2middle3 + tempf2lower);

        
        --Berechnung der shift_left Funktionen
        shiftResult1 := shiftResult1 + shift_left(tempResult1, 5*N) - shift_left(tempResult1, 4*N) + shift_left(tempResult1, 3*N);
        
        
        --Ergebnis Addition
        result <= std_logic_vector(shiftResult1);
    
      end if;
    end if;  
  end process montgomery;
end Behavioral;

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Kleiner Tipp, probiers mal aus:

[vhdl]
VHDL-Code
[/vhdl]

[tspotz (Gast)]

Du willst doch eigentlich das ihr rechnen :

        --Berechnung der shift_left Funktionen
        shiftResult1 := shift_left(tempResult1, 5*N) - 
shift_left(tempResult1, 4*N) + shift_left(tempResult1, 3*N);

        Ergebnis := TempResult1 * ShiftResult1;

[Nico B. (Firma: Hochschule Bonn-Rhein-Sieg) (jacetms)]

Hallo,

hab gemerkt, dass das so nicht weiter aufgeht, was ich vor habe.
Versuche das ganze jetzt auf einem anderen Weg und schaue, in wie weit 
ich dort komme.