8 Bit potenzieren in VHDL ?

[Hans-Werner (Gast)]

Bin auf ein "kitzekleines" Problem gestossen.
Ich möchte einen 8Bit Wert mit einem anderen 8Bit Wert in VHDL 
potenzieren.
ISE Webpack sagt mir bei der Synthese berechtigterweise:

Operator <EXP> must have constant operands or first operand must be 
power of 2

Beides trifft in meinem Fall nicht zu.
Das Ergebnis soll wieder auf einen 8Bit Wert abgebildet werden, also 
Modulo-Operation durchführen.
Was tun ? Eine Tabelle mit 256*256 Elementen für das Ergebnis wäre 
möglich, aber nicht unbedingt empfehlenswert.

Dank euch

[Ralf S. (spacedog)]

Vielleicht musst du die Potenzierung selber zusammenbasteln. Du könntest 
ja den Algorithmus welcher in O(log n) Zeit die Potenz berechnet:

  * http://www.osix.net/modules/article/?id=696

auch in einen Zustandsautomaten würgen.

[Jan M. (mueschel)]

Wenn es bis zu 256 Multiplikationen brauchen darf: m^n = m  m  ... * 
m.
Schneller geht es, wenn du den Exponenten zerlegst:

m^n = (m2 m1 m0) ^ (n2 n1 n0)   (a2..a0 sind die einzelnen Stellen 
zweier 3bit-Zahlen, Ergebnis auch 3 bit, zur Vereinfachung)

= (m ^ (n2*4)) * (m ^ (n1*2)) * (m ^ n0)  mod 8

folgender Pseudocode löst es demnach mit 16 Multiplikationen (für 8 bit)
erg = 1
exp = m
for i in 0 to 7 do
  if ni = 1 then
    erg = erg * exp;
  exp = exp * exp

Bei Benutzung von zwei Multiplizierern braucht das also 9 Takte


Edit: Ich schreibs auf, und Ralf findet den passenden Link ;-)

[Hans-Werner (Gast)]

Mmmmmhhh,

auf der Website von OSIX seh ich nur die rekursive Lösung.
Und das stimmt mit exp = exp * exp in deiner Lösung ?
Kann das auf dem Papier so nicht nachvollziehen,

[Hans-Werner (Gast)]

Bekomme noch 10 Warnings bei der Synthese.
Testbench ncoh nicht verfügbar.
Stimmt die Bitbreite ?
c = a ^ b
a 8 Bit, b 8 Bit ---------> c 8*8 Bit

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

entity eight_bit_multiplier is
  generic
  (
    size : integer := 8
  );
  port
  (
    clock              : in   std_logic;
    a                : in   std_logic_vector(0 to size-1);
    b                       : in   std_logic_vector(0 to size-1);
    c                       : out std_logic_vector(0 to size*size-1)
  );  
end eight_bit_multiplier;

-- c = a ^ b
architecture eight_bit_multiplier_rtl of eight_bit_multiplier is
  subtype long is integer range 0 to (2 ** (size*size))-1;

  signal exp : long;
  signal erg : long;
begin
   generate_key : process (clock)
  begin
    if rising_edge(clock)
    then
      erg <= 1;
      exp <=  to_integer(unsigned(a));    
      for i in b'range loop
        if b(i) = '1'
        then
          erg <= erg * exp;
        end if;
        exp <= exp * exp;
      end loop;
      c <= std_logic_vector(to_unsigned(erg,size*size));
    end if;
  end process;
end architecture eight_bit_multiplier_rtl;

[Andreas S. (andreas) (Admin)]

So könntest du das schreiben wenn exp und erg Variablen wären, aber dann 
käme ein monströses Schaltnetz heraus, was sicher nicht erwünscht ist. 
Um den Algorithmus getaktet umzusetzen musst du dir schon ein paar mehr 
Gedanken darüber machen wie sich Signale in einem VHDL-Prozess 
verhalten.

[Hans-Werner (Gast)]

Das man das nicht machen kann ist ja wohl klar: exp <= exp * exp;
Das ergibt natürlich einen Schleife vom Ausgang zum Eingang.
Das Ergebnis der Multiplikation muss zwischengespeichert werden und darf 
erst beim nächsten Takt wieder exp zugewiesen werden.
Fragt sich noch wie.
Aber das kriege ich irgendwie hin.

[gast (Gast)]

Square and Multiply wäre hier eine mögliche Lösung, wird in der 
Kryptographie verwendet um seeehr grosse Potenzen zu berechnen.

http://de.wikipedia.org/wiki/Schnelles_Potenzieren#Square_.26_Multiply

Aufwand in Multiplikationen = 3/2*log2(Exponent)

[Jan M. (mueschel)]

@gast:
Ah, "square & multiply" nennt sich das Verfahren - irgendwie 
einleuchtend.

@Hans-Werner:
>Das Ergebnis der Multiplikation muss zwischengespeichert werden und darf
>erst beim nächsten Takt wieder exp zugewiesen werden.
Das passiert in deinem Code doch schon, der ist ja synchron.

Warum ist der Ausgang c denn size*size breit? Du wolltest doch die 
gleiche Breite wie a und b?

[gast (Gast)]

@Jan M. Na Na, nicht ohne zu recherchieren unnötige äussern.

Square and Multiply ist ein Algorithmus, welcher in der Kryptographie 
viel eingesetzt wird und genau für die Aufgabe: a^b mod n ausgelegt ist. 
Wie man am Aufwand für eine Berechnung erkennen kann ist dieses 
Verfahren sehr gut. Im RSA werden Potenzen mit Zahlen von bis zu 700Bit 
berechnet.

[Jan M. (mueschel)]

@Andreas:
>So könntest du das schreiben wenn exp und erg Variablen wären, aber dann
>käme ein monströses Schaltnetz heraus, was sicher nicht erwünscht ist.

Für 8bit^8bit = 8bit sind es tatsächlich nur 187 LUTs, wenn man keine 
Hardware-Multiplizierer benutzt. Erstaunlich wenig, aber verständlich, 
schließlich werden bei den höheren Exponenten nur wenige Bits wirklich 
benötigt.

@gast:
>Na Na, nicht ohne zu recherchieren unnötige äussern.
Wie darf ich das verstehen?

[Hans-Werner (Gast)]

Hallo Jan,

es geht mir erst mal um die Potenzierung a hoch b.
Da sollte dann eine Bitbreite von Bitbreite a * Bitbreite b 
herauskommen.
Die Modulo Operation oder Subtraktion falls grösser als 2 hoch 8 wollte 
ich später einbauen.
Habe leider noch keine Lösung bzg. exp = exp*exp und erg=erg*exp 
gefunden.
Habe es mit zusätzlichen zwei Prozessen versucht.
Der Sqaure&Multiply Algorithmus hat die Modulo Operation ja bereits 
eingebaut.

[Jan M. (mueschel)]

Wie Andreas schrieb, dein Code oben ist korrekt, wenn du statt Signalen 
Variablen verwendest. Allerdings wird er in parallele Logik umgesetzt, 
was bei 8^8=8 noch gerade funktioniert, fuer 8^8=64 aber garantiert viel 
zu gross wird.

Du wirst das ganze sequentiell implementieren muessen. Dazu brauchst du 
eine state machine, die nacheinander die einzelnen Schritte der 
for-Schleife abarbeitet.

[Hans-Werner (Gast)]

Ich versteh immer nur Bahnhof.
Wieso brauche ich für eine For-Schleife einen Zustandsautomaten ?
Was soll den in den einzelnen Zuständen passieren ?
Zustandsautomaten kenne ich jetzt nur aus der BNF-Notation, Erkennung 
von Symbolen. Parsern usw.
Zustandautomaten für arithmetische Berechnungen ?
Hat jemand ein Beispiel in der Tasche ?

[Jan M. (mueschel)]

In C wird eine for-Schleife Schritt fuer Schritt abgearbeitet. Ein 
Durchlauf nach dem anderen, eine Multiplikation nach der anderen.

In VHDL dient eine for-Schleife nur zur bequemeren Beschreibung 
paralleler Logik, ein zeitlicher Ablauf ist nicht enthalten.

Um nicht alle Multiplikationen parallel auszufuehren, was sehr viele 
Resourcen brauchen wuerde, gilt es deshalb, das sequentielle Verhalten 
von C auch in der Logik nachzubilden. Das funktioniert aber nur, wenn 
man die komplette Berechnung auf mehrere Takte aufteilt und explizit 
Schritt fuer Schritt aufschreibt. Zur Steuerung dieses Ablaufs bietet 
sich daher ein Zustandsautomat an.

[Klaus (Gast)]

Hallo,
Die Beiträge sind zwar schon etwas älter, ich habe dazu aber dennoch 
eine Frage : Kann man das ganze über einen Xilinx Core (aus dem Xilinx 
core generator) lösen und falls ja, wie heißt der ? Ich habe schon 
danach geschaut aber nichts direkt gefunden.
Alternativ : davon ausgehend, das ich einen multiplikationscore habe und 
das ganze mit diesem Core rekursiv aufbaue, wie in dem Link beschrieben, 
wird das dann ebenfalls soviele Ressourcen benötigen ?

[Ralf (Gast)]

Geht EXP nicht über den Cordic?

[Manfred Menfield (Gast)]

> Kann man das ganze über einen Xilinx Core (aus dem Xilinx
> core generator) lösen und falls ja, wie heißt der ? Ich habe schon
> danach geschaut aber nichts direkt gefunden.

Viele wege führen nach Rom. Du kannst einen uc core nehmen und ein 
kleines Progrämmchen schreiben oder du nimmst einen ROM Core 128kByte 
groß und benutzt diesen als LUT. Oder einen CORDIc-Core.
Oder der eine Mischung aus PROM und LUT-Kombinatorik.
Willst du das ganze über einen externen Speicher als LUT lösen, brauchst 
du einen Memorycontroller-core.

MfG,