mikrocontroller.net

Forum: FPGA, VHDL & Co. Effizienter Weg gesucht um zu prüfen, ob Variable im Bereich liegt


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von John (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen

Folgende Aufgabe:

Ich habe eine Laufvariable x. Diese wird hochgezählt von 0..899 (Pixel).

Der Bereich 0..899 bzw. 1-900 wird nun in 16 Teile unterteilt.
Somit 56.25 Pixel pro Bereich.

nun soll möglichst effizient geprüft werden, in welchem Abschnitt sich 
die Laufvariable befindet.

Also im Wertebereich von 0..55 soll eine 1 resultieren. im Bereich von 
55..111 eine zwei usw.

Wie könnte ein solcher Vergleich möglichst schnell durchgeführt werden, 
ohne hardkodierte Werte zu verwenden?

Der Wert 900 kann abweichen und wird dynamisch im FPGA ermittelt.

Vielen Dank schonmal.

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
John schrieb:
> Wie könnte ein solcher Vergleich möglichst schnell durchgeführt werden
Definiere den Begriff "schneller Vergleich".

> ohne hardkodierte Werte zu verwenden?
Mit ein paar Komparatoren. Aber das macht doch sowieso der Synthesizer 
für dich. Wo liegt das Problem?

Ich könnte mir aber auch vorstellen, den Wert mit einer einzigen 
geschickten Multiplikation so zurechtzurechnen, dass gleich der 
gewünschte Wert herauskommt...

: Bearbeitet durch Moderator
von John (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Danke für deine Antwort.





Lothar M. schrieb:
>> ohne hardkodierte Werte zu verwenden?
> Mit ein paar Komparatoren. Aber das macht doch sowieso der Synthesizer
> für dich. Wo liegt das Problem?

Ich habe erst wenige Erfahrungen mit FPGAs gesammelt. Ich kann daher 
noch nicht wirklich abschätzen, wie gut die Synthesizer meinen 
unoptimierten code optimieren können...

Lothar M. schrieb:
> Ich könnte mir aber auch vorstellen, den Wert mit einer einzigen
> geschickten Multiplikation so zurechtzurechnen, dass gleich der
> gewünschte Wert herauskommt...

An sowas habe ich auch gedacht. Aber irgendwie habe ich noch nicht die 
richtige Idee gehabt, wie diese Berechnung aussehen könnte.

Lässt sich über den Daumen in etwa abschätzen, wie länge Berechnungen in 
einem FPGA in etwa dauern? Ist es z.B. ähnlich wie beim uC, wo man 
möglichst wenig dividieren soll dafür addieren?

von mukel (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Kann sich der Wertebereich (900) zu jeder neuen Laufvariable x ändern?
Oder evtl nur wenn für jeden Durchgang? Einmalig bei der initaliserung?

von mukel (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Bzgl. der Multiplikationslösung:
900/16 = a
x / a = Bereich. -> Hier ganzahl division mit Rest.

Aber ob das schneller ist, als die 16 Grenzen zu berechnen, und dann zu 
vergleichen, keine Ahnung.

von Tobias B. (Firma: www.elpra.de) (ttobsen) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
John schrieb:
> Lässt sich über den Daumen in etwa abschätzen, wie länge Berechnungen in
> einem FPGA in etwa dauern? Ist es z.B. ähnlich wie beim uC, wo man
> möglichst wenig dividieren soll dafür addieren?

Das laesst sich nicht nur abschaetzen sondern exakt ermitteln per 
Simulation. Wenn mans ordentlich macht dann pro Berechnung genau ein 
Takt, wobei durch Pipelining nur entsprechende Latenzen aufgebaut werden 
und man pro Takt jeweils ein Ergebnis erhaelt (sofern pro Takt auch 
entsprechend Daten zur Verarbeitung zur Verfuegung stehen).

von John (Gast)


Bewertung
0 lesenswert
nicht lesenswert
mukel schrieb:
> Kann sich der Wertebereich (900) zu jeder neuen Laufvariable x
> ändern?
> Oder evtl nur wenn für jeden Durchgang? Einmalig bei der initaliserung?

Nur zu jedem Durchgang.

Das heisst, es wird mit einem Bereich x in die Berechnung eingestiegen.
Wie z.B. oben mit 900.

Daher liessen sich die Grenzen zuvor berechnen und dann vergleichen mit 
einem Vector.

Dann müssten jedoch einfach sehr vielene grösser kleiner vergleiche 
durchgeführt werden. Braucht dann vermutlich einige LUTs dafür.

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
John schrieb:
> An sowas habe ich auch gedacht. Aber irgendwie habe ich noch nicht die
> richtige Idee gehabt, wie diese Berechnung aussehen könnte.
Im Fall hier müsste nur der Eingangswert 0..899 mit der "Magic Number" 
18641 multipliziert und dann die Bits 23..20 des Ergebnisses für ein 
Ergebnis 0..15 verwendet werden.

Die "Magic Number" habe ich (wie schon aufgezeigt) berechnet mit
(2^24-1)/900

John schrieb:
> Also im Wertebereich von 0..55 soll eine 1 resultieren.
Den obigen 4-Bit-Vektor auf 5 aufgebohrt und eins draufaddiert und 
fertig ist der Wert 1..16. Wobei ich mir diesen Wertebereich 1..16 
angesichts des unnötigen zusätzlichen Bits noch einmal sehr durch den 
Kopf gehen lassen würde...

: Bearbeitet durch Moderator
von John (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Lothar M. schrieb:
> John schrieb:
>> An sowas habe ich auch gedacht. Aber irgendwie habe ich noch nicht die
>> richtige Idee gehabt, wie diese Berechnung aussehen könnte.
> Im Fall hier müsste nur der Eingangswert 0..899 mit der "Magic Number"
> 18641 multipliziert und dann die Bits 23..20 des Ergebnisses für ein
> Ergebnis 0..15 verwendet werden.
>
> Die "Magic Number" habe ich (wie schon aufgezeigt) berechnet mit
> (2^24-1)/900
>
> John schrieb:
>> Also im Wertebereich von 0..55 soll eine 1 resultieren.
> Den obigen 4-Bit-Vektor auf 5 aufgebohrt und eins draufaddiert und
> fertig ist der Wert 1..16. Wobei ich mir diesen Wertebereich 1..16
> angesichts des unnötigen zusätzlichen Bits noch einmal sehr durch den
> Kopf gehen lassen würde...

Cool. Vielen Dank für diesen eleganten Weg der Herleitung!
Diesen kannte ich noch nicht.

Natürlich ist 1..16 nur dezimal dargestellt. Intern kann ich natürlich 
0..15 verwenden.

von John (Gast)


Bewertung
0 lesenswert
nicht lesenswert
John schrieb:
> Lothar M. schrieb:
>> John schrieb:
>>> An sowas habe ich auch gedacht. Aber irgendwie habe ich noch nicht die
>>> richtige Idee gehabt, wie diese Berechnung aussehen könnte.
>> Im Fall hier müsste nur der Eingangswert 0..899 mit der "Magic Number"
>> 18641 multipliziert und dann die Bits 23..20 des Ergebnisses für ein
>> Ergebnis 0..15 verwendet werden.
>>
>> Die "Magic Number" habe ich (wie schon aufgezeigt) berechnet mit
>> (2^24-1)/900
>>
>> John schrieb:
>>> Also im Wertebereich von 0..55 soll eine 1 resultieren.
>> Den obigen 4-Bit-Vektor auf 5 aufgebohrt und eins draufaddiert und
>> fertig ist der Wert 1..16. Wobei ich mir diesen Wertebereich 1..16
>> angesichts des unnötigen zusätzlichen Bits noch einmal sehr durch den
>> Kopf gehen lassen würde...
>
> Cool. Vielen Dank für diesen eleganten Weg der Herleitung!
> Diesen kannte ich noch nicht.
>
> Natürlich ist 1..16 nur dezimal dargestellt. Intern kann ich natürlich
> 0..15 verwenden.

Lothar M. schrieb:
> Die "Magic Number" habe ich (wie schon aufgezeigt) berechnet mit
> (2^24-1)/900

Wie kommst du auf die 24-1?

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
John schrieb:
> Lothar M. schrieb:
>> Die "Magic Number" habe ich (wie schon aufgezeigt) berechnet mit
>> (2^24-1)/900
> Wie kommst du auf die 24-1?
Obacht: Punkt vor Strich... ;-)
Dort steht: ((2^24)-1)/900
2 hoch 24 ist eins zuviel für einen 24-Bit-Vektor, von dem die 
vordersten 4 Bits verwendet werden sollen. So wie in einen 8-Bit-Vektor 
eben nicht der Wert 2^8 (=256) rein passt, sondern nur Werte von 0..255.

Du musst dir einfach mal die Bits auf einem Blatt Papier aufzeichnen, 
einen Tag drüber grübeln und eine Nacht drüber schlafen, um auf den 
Trick zu kommen...

: Bearbeitet durch Moderator
von John (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Lothar M. schrieb:
> Du musst dir einfach mal die Bits auf einem Blatt Papier aufzeichnen,
> einen Tag drüber grübeln und eine Nacht drüber schlafen, um auf den
> Trick zu kommen...

Ok werde ich tun! Danke :)

von Theor (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Lothar M. schrieb:
> John schrieb:
>> [...]
> Die "Magic Number" habe ich (wie schon aufgezeigt) berechnet mit
> (2^24-1)/900
>
> [...]

Magst Du bitte verlinken, wo Die Berechnung der "Magic Number" 
aufgezeigt hast? Ich würde das gerne nachvollziehen.

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Theor schrieb:
> wo Die Berechnung der "Magic Number" aufgezeigt hast?
Ok, ich habe mich verguckt...

> Ich würde das gerne nachvollziehen.
Ich sage mir: die Multiplier können 18x18 => 36 Bit auf einmal 
ausrechnen. Dann muss ich eine Magic Number finden, die kleiner als 2^18 
ist. Das ist die erste Randbedingung. Die zweite ist der Wert von 900-1, 
der 10 Bits braucht. Also wäre das "genaueste", wenn ich vom Ergebnis 
die Bits 27..24 nehme.
Um von diesen Grenzen geräumig wegzubleiben, nehme ich die Bits 23..20 
und habe als Ziel, dort die Ergebnisse 0x0..0xF für den Eingangswert 
0..899 zu bekommen. Ergo teile ich den Maximalwert 0xFF_FFFF (=2^24-1) 
durch den maximalen Eingangswert (korrekterweise hier eigentlich 899).
Damit kommt dann eine (neue und bessere ;-) Wert von 16777215/899 = 
18662,0856 heraus.
Ergo ergibt ein Eingangswert von 0 ein Ergebnis von 0x0000000.
Ein Eingangswert von 100 ergibt 100*Magic Number = 1866200 = 0x1C79D8 => 
Bits 23..20 = 1. Ein Eingangswert von 450 ergibt 8397900 = 0x80244C => 
Bits 23..20 = 8. Und der Maximalwert mit 899 resultiert wie zu erwarten 
(Abschneiden der Nachkommastellen beim Berechnen der Magic Number) knapp 
vor dem "oberen Anschlag" 0xFFFFB2 => Bits 23..20 = F

von Simon (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Vielen Dank für deine Erläuterung. Ein wirklich guter Trick!

von Theor (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Lothar M. schrieb:
> Theor schrieb:
>> wo Die Berechnung der "Magic Number" aufgezeigt hast?
> Ok, ich habe mich verguckt...
>
>> Ich würde das gerne nachvollziehen.
> Ich sage mir: [...]

Danke für die Antwort, Lothar. ;-)

von VHDL hotline (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Nimm einen BRAM und fülle die Adressen 0 bis 900 mit deinen gewünschten 
Werten. Spart LUTs.

von Gustl B. (gustl_b)


Bewertung
0 lesenswert
nicht lesenswert
Könnte man machen, aber der Wert von 900 ist nicht fest.

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Simon schrieb:
> Ein wirklich guter Trick!
Letztendlich ist die allgemeine Aufgabe hier:
"Dividieren per Multiplikation mit Kehrwert"
Denn es soll ja eigentlich der Eingangswert e=0..899 durch den Divisor 
d=56,25 geteilt werden, um ein Resultat r im Bereich 0..15 zu bekommen:
Umgestellt sieht das dann so aus:
Das kann man jetzt erweitern durch eine Zweierpotenz:
Umgestellt sieht das dann so aus:
Das 1/2^n ist eine Division durch eine Zweierpotenz und damit in 
Hardware nur ein "Ignorieren" der unteren Bits, also nur ein 
Umverdrahten.

Bleibt also leztlich wieder nur die Aufgabe den mittleren Term 2^n/d zu 
optimieren. Mit ein wenig probieren oder Erfahrung kommt man da dann 
recht schnell auf eine "Magic Number", die die Eigenheiten der Hardware 
(z.B. Breite der zur Verfügung stehenden Multiplizierer) berücksichtigt. 
Und so komme ich im Fall hier mit einer Divivson durch 2^20 also dem 
Abschneiden der unteren 20 Bits auf den Wert 2^20/56.25 = 18641.
Dieser Wert war dann auch der erste, den ich intuitiv ins Rennen 
geworfen hatte.

Der zweite im 
Beitrag "Re: Effizienter Weg gesucht um zu prüfen, ob Variable im Bereich liegt" 
aufgezeigte Weg ist eigentlich mathematisch falsch, weil er nicht wie 
gewünscht durch 56,25 teilt, sondern die Bereichsendwerte 0 und 899 auf 
die Bereichsendwerte 0 und 2^24-1 zueinander skaliert. Das resultiert in 
einer geringfügig anderen Steigung der Zuordnung (im Promillebereich). 
Es entspricht quasi dem Fehler, den ich mache, wenn ich einen 
10-Bit-AD-Wandler mit 0..5V so umrechne: U = 5.0*adw/1023 oder so U = 
5.0*adw/1024.
Im ersten 1023er-Fall kommt bei einer Eingangsspannung von 5.0V eben 
auch 5.00V auf die Anzeige, im eigentlich korrekten 1024er-Fall steht 
auf der Anzeige nur 4,99V.

: Bearbeitet durch Moderator
von Barrex (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Binärer Baum, bei dem die zu überprüfenden Grenzen in die Knoten als 
Werte eingetragen werden. Hat den Vorteil, dass egal wo der aktuelle 
Wert liegt immer die selbe Anzahl von Vergleichen notwendig ist.

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.

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