Effizienter Weg gesucht um zu prüfen, ob Variable im Bereich liegt

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...

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).

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...

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...

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

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

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.