Hallo zusammen! Ich hab folgende Formel zu realisieren: 1/wurzel(1+index) index .. integer Mein Problem dabei ist das ausrechnen der Wurzel. Kennt jmd vielleicht eine standard Funktion alias sqrt()?? Liebe Grüße
Im package math_real gibt es eine Wurzelfunktion. USE ieee.math_real.all; function sqrt(x:in real) return real;
math_real lässt sich aber nur simulieren und nicht synthetisieren. willst du logik generieren, oder nur eine Testbench erstellen?
logik, also ich gebrauchs in einem process das nächste wär ja, das mein input integer und nicht real ist
Kannst du mal deine benötigten Formeln hier hinschreiben? Oft kann die die Benutzung einer Wurzelfunktion durch Umformen der Formel ungehen.
> Mein Problem dabei ist das ausrechnen der Wurzel.
Dein vorrangiges Problem ist das Ausrechnen der Wurzel.
Auch das 1/(...) ist für die Synthese nicht ohne.
Wie wäre es, eine Tabelle mit der Funktion abzulegen und zwischen den
Stützpunkten zu interpolieren?
Mir fällt dazu nur wieder der Quake 3 Source Code ein:
1 | float InvSqrt (float x) {
|
2 | float xhalf = 0.5f*x; |
3 | int i = *(int*)&x; |
4 | i = 0x5f3759df - (i>>1); |
5 | x = *(float*)&i; |
6 | x = x*(1.5f - xhalf*x*x); |
7 | return x; |
8 | } |
Altera und Xilinx bieten beide ziemlich gute Funktionen dafür an die Platzsparend und schnell synthetisier werden. Bei Xilinx etwa als vereinfachter Cordic-Core. Einfach mal in den Megawizard oder coregenerator reinschauen. Da du ohnehin scheinbar nicht interessiert bist die Funktion an sich selbst zu beschrieben wäre das immer die erste Anlaufstelle. Allerdings muss man sich fragen ob du tatsächlich diese Funktion berechnen willst und insbesondere wieviel Zeit du dafür hast. Wenn das eventuell sogar in einem Takt passieren soll...
schau dir mal das dsp-ch3.pdf auf der Xilinx homepage an. auf seite 59 beschreiben sie eine möglichkeit wie du das mit dem DSP48 slice lösen könntest. welche hardware möchtest du den verwenden?
Ein Altera Cyclone II packt eine 18 Bit-Wurzel bei 50MHz mit 6 Takten Latenz. "ALT SQRT"
Vl. reicht auch schon der Wurzelalgorithmus von Heron, Dieser löst das Problem durch einfache Addition und Division. x= 0,5 * (x+a/x) Wobei x die Näherungslösung ist und a die Zahl aus der die Wurzel errechnet werden sol. Das ganze lässt man dann in einer Schleife solange ablaufen bis (x*x-a) <= ERROR_MAX ist. Sollte nun auch in Logik eifnach zu realisieren sein. Aber die allerschnellste wäre es wahrscheinlich eine Interpolationsfunktion zu erstellen und anhand dieser die Werte zu errechnen.
Also die FPGA-internen Funktionen nutzen das schriftliche Wurzelziehen, wie es früher, in der guten alten Zeit, noch an der Schule gelehrt wurde.
Ich habe auch schriftlich Wurzelziehen inner schule gelernt, und bin erst 1997 eingeschult worden. lernte man also nicht nur "Früher" ;)
>> Also die FPGA-internen Funktionen nutzen das schriftliche Wurzelziehen FPGA-interne Funktionen ? Welches FPGA hat denn bitte dedizierte Wurzel-Blöcke ?
Ich denke auch, der Ansatz mit einer Lookup-Tabelle wäre hier am Effizientesten...
Ich würde mal sagen, dass die Funktionen sowieso in LUTs realisiert sind. Beim "schriftlichen Wurzelziehen" wird nur nicht soviel Platz verschwendet. Wenn man eine Wurzel auf 8 Bit genau ziehen will, braucht man einen 16 Bit-Wert. Das ist ein komplettes 64k-RAM. Mehr Verschwendung geht eigentlich kaum.
Hallo, ich hatte mal diesen Code-Schnippsel nach VHDL portiert und es hat sehr gut funktioniert:
1 | public static int sqrt(int num) { |
2 | int op = num; |
3 | int res = 0; |
4 | int one = 1 << 14; // The second-to-top bit is set: 1L<<30 for long |
5 | |
6 | // "one" starts at the highest power of four <= the argument.
|
7 | while (one > op) |
8 | one >>= 2; |
9 | |
10 | while (one != 0) { |
11 | if (op >= res + one) { |
12 | op -= res + one; |
13 | res += 2 * one; |
14 | }
|
15 | res >>= 1; |
16 | one >>= 2; |
17 | }
|
18 | return res; |
19 | }
|
Wie du siehst, braucht man keine Multiplikation für die Wurzelberechnung. Grüße, Gast
Hallo Gast ja, funktioniert gut, hab es mal in matlab ausprobiert. aber leider ohne nachkommastellen. hat das für deine VHDL anwendung so gereicht? gruss Stefan
@Stefan: Ja, bei mir war es gut genug. Handelte sich um eine RMS-Berechnung über einige Audiosamples (so glaub 256 oder so). Mit dem RMS-Wert sollte dann ein Verstärkungsfaktor berechnet werden. Quasi eine Art Dynamikkompressor. Aber noch nciht fertig ... Grüße, Gast
Wie wäre es mit modified Dijkstra's square root? Ich habe auch keine Erfahrung damit. http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf
Wofür braucht man bei einem Dynamikkompressor noch den RMS?
Angehängte Dateien:
-
dbyd.jpg
910 KB -
dbyd001.jpg
870 KB -
dbyd002.jpg
1,4 MB
About squareroot operation according to CORDIC: http://baykov.de/CORDIC1972.htm http://baykov.de/Cordic1975.htm
Da haben wir doch den richtigen in der Runde >>Vladimir Baykov Ich habe mich mit Cordic auch schon intensiv beschäftigt, allerdings zur Sinussignalerzeugung. http://www.dossmatik.de/vhdl.html Die Wurzel lässt sich im hyperbolischen Modi berechnen. Wenn ich mich richtig erinnere, müssen bestimmte Interationsschritte doppelt durchgeführt werden.
Gibt es das in kyrillisch verfasste Paper auch in westeuropäisch? Vielleicht als link im Bronstein? ....................... Weisst Du noch Vladimir, früher auf der Universität? Als wir Mathe hatten, hast Du uns immer Aufgaben gemacht mit viele Formeln und Zeichen ... war grauenhaft ...
Frager schrieb: > Gibt es das in kyrillisch verfasste Paper auch in westeuropäisch? > > Vielleicht als link im Bronstein? > > ....................... > > Weisst Du noch Vladimir, früher auf der Universität? > Als wir Mathe hatten, hast Du uns immer Aufgaben gemacht > mit viele Formeln und Zeichen ... > war grauenhaft ... <3 switch
> Wofür braucht man bei einem Dynamikkompressor noch den RMS?
Weil es ohne RMS kein RMS-Dynamik-Kompressor ist ...
Hmm ... die letzten Postings werte ich so, dass es wohl mit Cordic auch
gehen würde, auch wenn ich kein kyrillisch verstehe.
Mit Cordic kenn ich mich leider garnicht aus, obwohl ich viel darüber
gelesen habe ...
Grüße,
Gast
Die Formel-Sprache der Mathematiker ist international. Leider fehlen ein paar Diagramme oder ein Strukturgramm für den Algorithmus, um einen Einstieg zu haben. Das ist das eigentliche Problem Vladimir's. Es handelt sich bei allen Problemen um Kegelschnitte. Auf diesen Schnittebenen gibt es mit jedem Schritt eine Bewegung, die sich dem Ergebnis nähert. Die Schrittweite wird mit jedem Schritt auch kleiner. Diese Schritte muss man sich mal in ein Diagramm eintragen, dann versteht man es. Ander blöde Frage was ist RMS? RMS ist bei mir root mean square, der Quadratische Mittelwert
> der Quadratische Mittelwert
Richtig, nachdem man die Quadrate gebildet und bearbeitet hat, sollte
man die Wurzel ziehen...
Das mit den Kegelschnitten ist gut erklärt, finde ich. Aber die Theorie dahint kann man auch im Wiki nachlesen. True RMS braucht man bei der Leistungsbetrachtung über einen gewissen Freqenzbereich. Man muss mindestens über die Periode der geringsten Frequenz integrieren.
Ich habe mich mit Cordic nochmal beschäftigt. Es lässt sich die Wurzel nur indirekt berechnen. Mit der hyperbolische Variante lässt sich folgende Funktion annähern.
Nimmt man für
und
So berechnet man:
So die Theorie. Es könnte sein, dass es noch eine einfachere Cordic Variante gibt. Das ist meine eigene Herleitung.
>>Jürgen ich habe leider in deinem Link nicht gefunden, wie man eine Wurzel berechnet. >> Melanie >>die formel ist: >>1/sqrt(1+2^(-2*i)) Wenn mich nicht alles täucht, ist das der der reziproke Cordic gain? Bei Cordic ist das eine Konstante! Also wenn du Cordic vor hast, dann ist dieser Wert nicht ständig zu berechnen.
Crest schrieb: > Mir fällt dazu nur wieder der Quake 3 Source Code ein: >
1 | > float InvSqrt (float x) { |
2 | > float xhalf = 0.5f*x; |
3 | > int i = *(int*)&x; |
4 | > i = 0x5f3759df - (i>>1); |
5 | > x = *(float*)&i; |
6 | > x = x*(1.5f - xhalf*x*x); |
7 | > return x; |
8 | > } |
9 | >
|
Kann mir das bitte mal jemand entschlüsseln?
"df" , "f"?
Ist das rekursiv?
>Quake 3
?
:
Bearbeitet durch Admin
ralf schrieb: > "df" , "f"? df = Hex-Zahl (beginnt in C mit 0x) 0.5f = Null Komma Fünf als float Das ist jetzt aber eigentlich keine Frage wert, weil Urschleim^3 ... :-/ >>Quake 3 > ? Das ist/war ein Computer-Spiel. BTW: warum mußt du hier so alte Threads wieder ausgraben?
Weil mich das interessiert. Warum fragst Du? Danke für die Erklärungen, aber die Frage ist mehr nach der Funktion des Algo. (?) Und was hat der mit dem Spiel zu tun?
Ralf schrieb: > Danke für die Erklärungen, aber die Frage ist mehr nach der Funktion des > Algo. Google doch einfach mal danach. An den paar Zeilen haben sich schon viele Leute den Kopf zerbrochen. Ralf schrieb: > Und was hat der mit dem Spiel zu tun? Der Code stammt aus dem Quake Sourcecode.
ralf schrieb: >> Mir fällt dazu nur wieder der Quake 3 Source Code ein:
1 | float InvSqrt (float x) { |
2 | float xhalf = 0.5f*x; |
3 | int i = *(int*)&x; |
4 | i = 0x5f3759df - (i>>1); // hier muß man sich mal den Aufbau einer IEEE float-Zahl genauer anschauen |
5 | x = *(float*)&i; |
6 | x = x*(1.5f - xhalf*x*x); |
7 | return x; |
8 | }
|
> Kann mir das bitte mal jemand entschlüsseln? Spiel doch mal selber Prozessor und sieh dir dazu vorab den Aufbau von IEEE 754 float-Zahlen mal sehr genau an. Da wird nämlich auf Bit-Ebene in einer solchen Zahl herumgemantscht... Als Tipp: es kommt (mit hinreichender Genauigkeit) der Kehrwert der Wurzel raus InvSqrt(36.000000) = 0.166477 --> 6.006850 InvSqrt(49.000000) = 0.142762 --> 7.004646 InvSqrt(64.000000) = 0.124788 --> 8.013566 InvSqrt(81.000000) = 0.111086 --> 9.002046 > Ist das rekursiv? Nein, weil InvSqrt() nicht innerhalb von InvSqrt() aufgerufen wird.
>Weil es ohne RMS kein RMS-Dynamik-Kompressor ist ...
Bei Dynamikkompressoren muss man immer ein wenig aufpassen, was man über
welche Zeiträume komprimiert. Bei kurz eingestellten Integrationszeiten
und Bezug auf die Anplitudenwerte kommt es zu starken
Signaldeformationen.
Das ist das Newton'schen Näherungsverfahren, bei der einfach die erste Division des 1/k-Wertes weggelassen wurde, wodurch man folglich 1/sqrt() erhält. Keine Hexerei. Der wirklich kluge Kunstgriff dieses Ansatzes besteht im trickreichen Ermitteln des Startwertes, damit die Folge schon nach der ersten Korrektur gut konvergiert. Im Grunde wäre es auch für FPGAs gut nutzbar, allerdings liegen im FPGA die Werte so selten im float vor :-) Um zu einem guten Startwert zu gelangen, muss man anders vorgehen. Ich habe da selber schon einiges probiert, allerdings kosten die meisten Überlegungen zuviel Zeit, um noch effizient zu sein. Ein VHDL-Wurzel Core auf binärer Basis braucht mitunter deutlich weniger Takte, als die Eingangsbitbreite.
René D. schrieb: > Wie wäre es mit modified Dijkstra's square root? > Ich habe auch keine Erfahrung damit. > > http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf Halla, ich habe das Thema auf der Suche nach Dijkstra gefunden und einen Frage: Ist bekannt, worum hier das "INT I=1" sein soll? Das wird weder fortgeschrieben, noch verwendet. Ist das überhaupt von Nöten?
Ich möchte kurz generell anmerken, dass es für Wurzel ziehen/wurzelziehen, wie es hier oft verwendet wurde, auch einen richtiges Verb gibt: radizieren. Das erleichtert oft den Satzbau. https://www.duden.de/rechtschreibung/radizieren
Racotti schrieb: > https://www.duden.de/rechtschreibung/radizieren Viele Dank, ich lerne noch Deutsch :-) Welche Möglichkeit gibt es für die Lösung des Problems?
Morten schrieb: > Ist bekannt, worum hier das "INT I=1" sein soll? Das wird weder > fortgeschrieben, noch verwendet. Ist das überhaupt von Nöten? Offenbar nicht. Könnte sein, dass es ein Überbleibsel des original Algos von Dijkstra ist, wobei ich nicht genau weiß, wie der aussieht. Ich sehe auch nicht, was daran jetzt so Schlaues sein soll, bzw. worin wiederum die Modifikation der Autoren besteht. Die vorgestellte Methodik ist ein iteratives Näherungsverfahren, welches weitgehend dem schriftlichen Wurzelziehen aus der Schule entspricht, das seinerseits wiederum auf selbiges von Heron zurückgeht, wie ich weiter oben schon angemerkt hatte. Morten schrieb: > Welche Möglichkeit gibt es für die Lösung des Problems? Welches Problem besteht? Der Algo als solcher funktioniert ja. Ich denke, "I" ist ein Zähler, der die Anzahl der Iterationen und damit Rechentiefe mitprotokolliert. Diese ist allerdings durch die Wahl der Breite des Eingangsvektors bereits implizit determiniert. Redundante Info.
Racotti schrieb: > auch einen > richtiges Verb gibt: radizieren. Das ist aber genau so wenig deutsch wie dein Pronomen "einen":-)
Jürgen S. schrieb: > Morten schrieb: >> Ist bekannt, worum hier das "INT I=1" sein soll? Das wird weder >> fortgeschrieben, noch verwendet. Ist das überhaupt von Nöten? > Offenbar nicht Irgendeine Bedeutung muss es haben denke ich. Immerhin ist es ja ein wissenschaftlicher Artikel auf IEEE. Vielleicht fehlt etwas vom Code? > Die vorgestellte Methodik ist ein iteratives Näherungsverfahren, welches > weitgehend dem schriftlichen Wurzelziehen aus der Schule entspricht, das > seinerseits wiederum auf selbiges von Heron zurückgeht Mir ging es hauptsächlich um den Weg wie es gemacht wurde um besonders schnell zu sein mit der Wurzelbildung. Es muss einen Vorteil bei der Methode geben bei FPGA.
Morten schrieb: > Es muss einen Vorteil bei der > Methode geben bei FPGA. Wenn es den gäbe, müsste man nicht einen Core dafür entwickeln: http://www.xilinx.com/support/documentation/ip_documentation/cordic_ds249.pdf
Entwickler schrieb: > Wenn es den gäbe, müsste man nicht einen Core dafür entwickeln: Das ist auch wieder wahr. Vielleicht ist die Methode überholt. Ich habe es in VHDL gemacht, mit einer Statusmaschine und sehe eine langsame Realisation.
Entwickler schrieb: > Wenn es den gäbe, müsste man nicht einen Core dafür entwickeln: Ob man pauschal von der Existenz eines Cores in der Bib eines Herstellers darauf schließen kann, dass dieser das nun plus ultra ist und es nicht Besseres gibt, sei mal dahin gestellt. Ich verweise an dieser Stelle auf die anderweitig gepostete Gegenüberstellung meiner DDS und der von Xilinx :-) Nochmals zu dem Dokument hier: Mir ist beim nochmaligen Überfliegen nicht so ganz klar, worin jetzt genau die Errungenschaft besteht. Irgendwie liest es sich, als hatten die Autoren nur Probleme, die in C formulierte "Rotation" des Zwischenvektors in VHDL abzubilden, weil es keinen Befehl dafür gab und das irgendwie klug gelöst. Ich nehme an, dass das (nicht publizierte) VHDL den links in der Box dargestellten Algorithmus tatsächlich sequenziell abbildet und dort wirklich Zwischenwerte rotiert werden. Dass man aber in VHDL eine Rotation durch ein Verschieben bzw Umgreifen realisiert, muss hier eigentlich nicht erwähnt werden und sicher auch nicht, dass man nicht nur auf das Hineinpassen des Probevektors mit Faktor 2 auf Ja und Nein testen kann, um zu entscheiden, ob man eine 1 oder 0 in den Ergebnisvektor setzt. Ich habe das z.B. in "meiner" VHDL-Wurzel mit 4 Fragezweigen realisiert und kann folglich in einem Takt 2 Ergebnisbits bilden. Damit kriegt man aus den 32 Eingangsbits die 16 Ausgangsbits in 8 Takten raus. Daraus mache ich jetzt aber kein paper :-) ... sondern verweise auf den einfachen Algo hier: Beitrag "Re: Wurzel ziehen - VHDL"
Jürgen S. schrieb: > Ich habe das z.B. in "meiner" VHDL-Wurzel mit 4 Fragezweigen realisiert > und kann folglich in einem Takt 2 Ergebnisbits bilden. Damit kriegt man > aus den 32 Eingangsbits die 16 Ausgangsbits in 8 Takten raus. Darf man das irgendwo bestaunen?
Edi M. schrieb: > Darf man das irgendwo bestaunen? Ist in einigen designs verbaut, z.B. wo es um Abstandsberechnungen mit X und Y geht, um Radien zu ermitteln, oder komplexe Zahlen zu berechnen. Als Core erhältlich :-)
Thread beobachten
Seitenaufteilung abschaltenBitte 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.