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
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.
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 ;-)
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,
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.
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:
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?
@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.
@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?
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.
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.
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 ?
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.
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 ?
> 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,
