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,
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
1 | library IEEE; |
2 | use ieee.std_logic_1164.all; |
3 | use ieee.numeric_std.all; |
4 | |
5 | entity eight_bit_multiplier is |
6 | generic
|
7 | (
|
8 | size : integer := 8 |
9 | );
|
10 | port
|
11 | (
|
12 | clock : in std_logic; |
13 | a : in std_logic_vector(0 to size-1); |
14 | b : in std_logic_vector(0 to size-1); |
15 | c : out std_logic_vector(0 to size*size-1) |
16 | );
|
17 | end eight_bit_multiplier; |
18 | |
19 | -- c = a ^ b
|
20 | architecture eight_bit_multiplier_rtl of eight_bit_multiplier is |
21 | subtype long is integer range 0 to (2 ** (size*size))-1; |
22 | |
23 | signal exp : long; |
24 | signal erg : long; |
25 | begin
|
26 | generate_key : process (clock) |
27 | begin
|
28 | if rising_edge(clock) |
29 | then
|
30 | erg <= 1; |
31 | exp <= to_integer(unsigned(a)); |
32 | for i in b'range loop |
33 | if b(i) = '1' |
34 | then
|
35 | erg <= erg * exp; |
36 | end if; |
37 | exp <= exp * exp; |
38 | end loop; |
39 | c <= std_logic_vector(to_unsigned(erg,size*size)); |
40 | end if; |
41 | end process; |
42 | end architecture eight_bit_multiplier_rtl; |
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.
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)
@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,
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.