mikrocontroller.net

Forum: FPGA, VHDL & Co. Wurzel ziehen - VHDL


Autor: Melanie (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: René D. (Firma: www.dossmatik.de) (dose)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Im package math_real gibt es eine Wurzelfunktion.

USE ieee.math_real.all;

function sqrt(x:in real) return real;

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
math_real lässt sich aber nur simulieren und nicht synthetisieren. 
willst du logik generieren, oder nur eine Testbench erstellen?

Autor: Melanie Schranz (melanie)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
logik, also ich gebrauchs in einem process

das nächste wär ja, das mein input integer und nicht real ist

Autor: Claudio H. (bastelfinger)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kannst du mal deine benötigten Formeln hier hinschreiben? Oft kann die 
die Benutzung einer Wurzelfunktion durch Umformen der Formel ungehen.

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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?

Autor: Crest (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mir fällt dazu nur wieder der Quake 3 Source Code ein:
float InvSqrt (float x) {
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i>>1);
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    return x;
}

Autor: Melanie Schranz (melanie)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
die formel ist:

1/sqrt(1+2^(-2*i))

Autor: Iulius (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Andreas Fischer (chefdesigner)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ein Altera Cyclone II packt eine 18 Bit-Wurzel bei 50MHz mit 6 Takten 
Latenz. "ALT SQRT"

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Andreas Fischer (chefdesigner)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also die FPGA-internen Funktionen nutzen das schriftliche Wurzelziehen, 
wie es früher, in der guten alten Zeit, noch an der Schule gelehrt 
wurde.

Autor: Gustav K. (hanibal)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe auch schriftlich Wurzelziehen inner schule gelernt, und bin 
erst 1997 eingeschult worden. lernte man also nicht nur "Früher" ;)

Autor: Iulius (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> Also die FPGA-internen Funktionen nutzen das schriftliche Wurzelziehen

FPGA-interne Funktionen ?

Welches FPGA hat denn bitte dedizierte Wurzel-Blöcke ?

Autor: dito (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich denke auch, der Ansatz mit einer Lookup-Tabelle wäre hier am 
Effizientesten...

Autor: Harry Hirsch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich hatte mal diesen Code-Schnippsel nach VHDL portiert und es hat sehr 
gut funktioniert:
public static int sqrt(int num) {
        int op = num;
        int res = 0;
        int one = 1 << 14; // The second-to-top bit is set: 1L<<30 for long
 
        // "one" starts at the highest power of four <= the argument.
        while (one > op)
            one >>= 2;
       
        while (one != 0) {
            if (op >= res + one) {
                op -= res + one;
                res += 2 * one;
            }
            res >>= 1;
            one >>= 2;
        }
        return res;
    } 

Wie du siehst, braucht man keine Multiplikation für die 
Wurzelberechnung.

Grüße,
Gast

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: René D. (Firma: www.dossmatik.de) (dose)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Jürgen Schuhmacher (engineer) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wofür braucht man bei einem Dynamikkompressor noch den RMS?

Autor: Vladimir Baykov (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
About squareroot operation according to CORDIC:

http://baykov.de/CORDIC1972.htm
http://baykov.de/Cordic1975.htm

Autor: René D. (Firma: www.dossmatik.de) (dose)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Frager (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ...

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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

Autor: René D. (Firma: www.dossmatik.de) (dose)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> der Quadratische Mittelwert
Richtig, nachdem man die Quadrate gebildet und bearbeitet hat, sollte 
man die Wurzel ziehen...

Autor: Kriticker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: René D. (Firma: www.dossmatik.de) (dose)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: J. S. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: René D. (Firma: www.dossmatik.de) (dose)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>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.

Autor: ralf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Crest schrieb:
> Mir fällt dazu nur wieder der Quake 3 Source Code ein:float InvSqrt (float x) {
>     float xhalf = 0.5f*x;
>     int i = *(int*)&x;
>     i = 0x5f3759df - (i>>1);
>     x = *(float*)&i;
>     x = x*(1.5f - xhalf*x*x);
>     return x;
> }

Kann mir das bitte mal jemand entschlüsseln?

"df" , "f"?

Ist das rekursiv?

>Quake 3
?

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Ralf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: dito (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ralf schrieb:
>> Mir fällt dazu nur wieder der Quake 3 Source Code ein:
 float InvSqrt (float x) {
     float xhalf = 0.5f*x;
     int i = *(int*)&x;
     i = 0x5f3759df - (i>>1);  // hier muß man sich mal den Aufbau einer IEEE float-Zahl genauer anschauen
     x = *(float*)&i;
     x = x*(1.5f - xhalf*x*x);
     return x;
 }
> 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.

Autor: Edi M. (elektromeister)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: Jürgen Schuhmacher (engineer) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.