Minimum aus einem Fenster auslesen

[Patrick B. (p51d)]

Hallo Allerseits

Ich sitze gerade wieder einmal an einer Schulaufgabe:
Es werden kontinuierlich Daten von einem Modul eingelesen. Dabei soll 
jeweils das Minimum von z.B. 3 Werten (könnte auch variabel sein, aber 
erst einmal fix) ausgelesen werden. Wobei sich diese 3 Werte mit jedem 
Takt natürlich ändern können.

Mein bisheriger Ansatz war, dass ich aus dem Stream ein paralleler 
Datenfluss mache und diesen dann durch ein Sortiernetzwerk schicke. 
Funktioniert eigentlich sehr gut (so kriege ich gleichzeitig Minimum, 
Median und Maximum), aber wenn ich mir die Ressourcen so ansehe... Ich 
ich brauche aktuell Maximum und Median nicht, von dem her ist es schon 
ein wenig verschwenderisch.

Gibt es eine einfachere / ressourcenärmere Methode, an die ich noch 
nicht gedacht habe?

Gruss
Patrick

[Uwe N. (nasenase)]

Ganz einfach,
eine Speicherstelle reservieren, und dann Vergleich:
Wenn Istwert kleiner als Speicherwert, dann ab damit in den Speicher.
Wenn nicht, dann nächsten Wert holen.
Nun steht im Speicher immer der kleinste Wert. Fertig!

[Kai S. (kai1986)]

Hallo,

ich würde die Werte in einen Ringpuffer schreiben und dann ne klassische 
Minimumsfunktion drüber laufen lassen.
Ringpuffer:
3 Speicherzellen (oder wieviel auch immer du gerne hättest bei variabel) 
und einen Zeiger auf die erste Zelle. Ankommenden Wert an die 
Zeigerposition schreiben und Zeiger eine Zelle weiter schieben. Wenn der 
Zeiger an der letzten Zelle steht und weitergeschoben werden soll, 
springt er wieder auf die erste Zelle. Damit hast du immer die drei 
letzten Werte und überschreibst die vorhergehenden.
Minimumsfunktion:
Wert der ersten Zelle in eine Variable übernehmen. Abgleich des 
nächstens Werts mit der Variable. Ist der nächste Wert kleiner, wird er 
in die Variable übernommen, ist er größer bleibt der Wert der Variable. 
Wenn du durch alle Zellen durch bist steht dann in der Variable der 
kleinste Wert.

Gruß Kai

[Patrick B. (p51d)]

Uwe N. schrieb:
> Wenn Istwert kleiner als Speicherwert, dann ab damit in den Speicher.

Generiert aber das Minimum über einen kompletten Stream (globales 
Minimum)

Das mit dem Ring-Buffer klingt interessant

Kai S. schrieb:
> Wert der ersten Zelle in eine Variable übernehmen. Abgleich des
> nächstens Werts mit der Variable. Ist der nächste Wert kleiner, wird er
> in die Variable übernommen, ist er größer bleibt der Wert der Variable.
> Wenn du durch alle Zellen durch bist steht dann in der Variable der
> kleinste Wert.

Müssen dazu die Werte im Ringbuffer nicht konstant sein, währendem das 
Minimum gebildet wird?

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Patrick B. schrieb:
> Wobei sich diese 3 Werte mit jedem Takt natürlich ändern können.
Kommen die 3 Werte parallel/gleichzeitig neu an?

> Gibt es eine einfachere / ressourcenärmere Methode, an die ich noch
> nicht gedacht habe?
Ein paar Vergleicher und 1 MUX reichen aus...
Etwa so:
erg := obergrenze
if a<erg then erg:=a
if b<erg then erg:=b
if c<erg then erg:=c
if erg<untergrenze then erg:=untergrenze

[Oli P (Gast)]

Lothar M. schrieb:
> Etwa so:
> erg := obergrenze
> if a<erg then erg:=a
> if b<erg then erg:=b
> if c<erg then erg:=c

wird das wirklich parallel so aufgebaut, daß in einem Takt zwei 
Entscheidungen ergehen können und b das eben erst geschriebene a 
überschreiben kann? Ich denke NICHT!

[Patrick B. (p51d)]

Lothar M. schrieb:
>> Wobei sich diese 3 Werte mit jedem Takt natürlich ändern können.
> Kommen die 3 Werte parallel/gleichzeitig neu an?

Als Beispiel die Folge:
6 | 5 | 4 | 3 | 2 | 1

Dann befinden sich im Fenster nach 2 Taktzyklen
3 | 2 | 1

Im nächsten Takt wird das zu
4 | 3 | 2
und so weiter.

Lothar M. schrieb:
> Ein paar Vergleicher und 1 MUX reichen aus...
> Etwa so:
> erg := obergrenze
> if a<erg then erg:=a
> if b<erg then erg:=b
> if c<erg then erg:=c
> if erg<untergrenze then erg:=untergrenze

Resultiert das nicht in einem Sortiernetzwerk?

Mein optimierender Ansatz war, dass ich über 2 Stufen gehe:

signal temp1, temp2 : std_logic_vector(7 downto 0);
if A < B then
  temp1 <= A;
else
  temp1 <= B;
end if;
temp2 <= C;
if temp2 < temp1 then  
  min <= temp2;
else
  min <= temp1;
end if;

[Oli P (Gast)]

Wie ist denn nun eigentlich die Aufgabe`?

Wenn z.B. das Minimum aus 4 gesucht wird, wie erfolgt das Datenupdate?

Ist es A) das Minumum aus den Daten 1,2,3,4 und dann 5,6,7,8

oder ist es  B) 1,2,3,4   2,3,4,5  3,4,5,6 ...


Dann brauchst du einfach einen Vorrangmultiplexer.

if (wert 2 > wert1) then winner1 = wert 2, else wert 1

if (wert 3 > winner1) then winner2 = wert2, else winner2

if (wert 4 > winner2) then winner3 = wert3, else winner3

usw

Dann kann man in jedem Takt ein Datum einwerfen und bekommt das Minium 
aus der Gruppe.

Nur, wenn es so läuft, wie bei A kann man das sequentialisieren und mit 
einem Enscheider arbeiten.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Oli P schrieb:
> Ich denke NICHT!
Du denkst falsch. Probiers aus...
Nur braucht ein voll kombinatorischer mehrfacher Vergleich eben auch 
mehr Logikebenen und wird deshalb auch langsamer (im Sinne von: kann 
nicht mehr so schnell getaktet werden)...

Hier z.B. ein komplett kombinatorischer BubbleSort und der Vergleich mit 
einem getakteten Algorithmus:
http://www.lothar-miller.de/s9y/archives/78-Bubblesort.html

[Mh. M. (mhm)]

Ich habe aus Interesse mal zwei Varianten implementiert (siehe Anhang) 
und die (Quartus-)Synthese drüber laufen lassen.

Variante 0: beschrieben per If-Else, ohne Hilfsvariable. Geht bei einer 
Fenstergröße von drei noch, wird bei mehr aber ziemlich aufwändig zu 
beschreiben.

 Logic utilization (in ALMs)  22

Ergebnis sind drei Vergleicher und drei Muxe (siehe variant0.png).

Variante 1: beschrieben per Schleife und Hilfsvariable. Sehr einfach, 
auch für beliebig große Fenster.

 Logic utilization (in ALMs)  19

Ergebnis sind zwei Vergleicher und zwei Muxe (siehe variant1.png).

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Mh. M. schrieb:
> habe aus Interesse mal zwei Varianten implementiert
Genau DAS ist der eigentliche Trick an der Sache: nicht "glauben" oder 
"meinen", sondern einfach mal "ausprobieren".
Und auf diese Art "seinen" Synthesizer besser kennenlernen.

[Michael B. (laberkopp)]

Uwe N. schrieb:
> eine Speicherstelle reservieren, und dann Vergleich:
> Wenn Istwert kleiner als Speicherwert, dann ab damit in den Speicher.
> Wenn nicht, dann nächsten Wert holen.
> Nun steht im Speicher immer der kleinste Wert. Fertig!

Bloss der falsche.

Er will nicht den kleinsten von allen, sondern den kleinsten der letzten 
3.

Wenn von 1 2 3 4 5 6 zuerst 1 2 3 betrachtet wurden und 1 gewählt war, 
kann man beim weiterschalten auf 2 3 4 nicht den bisherigen Minimalwert 
1 löschen, weil man nicht weiss, daß die 1 rausfällt, und selbst wenn 
man es wüsste, kann man nicht auf 2 zurückstellen, weil man die 2 nicht 
mehr kennt.

Man muss also alle 3 Werte speichern und vergleichen, oder bei 256 
Werten eben alle 256.

[Häh? (Gast)]

Nee, auch bei 256 nur immer den der letzten drei!