Flanke in langer Variable suchen

Ja, das aufteilen ist wohl eine gute Idee.
Im Moment nutze ich eine for Schleife mit Abbruchbedingung, so wie du 
sie in deinen Beispielen auch angibst.

Es war mal ein Signal, ist nun aber tatsächlich eine Variable, also im 
Speicher so abgelegt.
Direkt einlesen geht leider nicht.
Das Ganze ist Teil einer hochauflösenden Zeitmesseinrichtung. Das Signal 
läuft durch eine Verzögerungskette und wird mit dem Taktsignal 
eingefroren.
Wollte man es direkt abtasten, um die selbe Auflösung zu erhalten, 
bräuchte man einen Takt mit 80 GHz.

Wenn das Teil mal ordentlich funktionieren sollte, kann ich das gerne 
detaillierter vorstellen. Im Moment sind noch zu viele Unbekannte 
enthalten.

Grüße
Beni

Ich würde die Suche in zwei bzw. drei Stufen aufteilen.
1. Suche in der maximalen, natürlichen Datenbreite (8, 16 oder 32 Bit).
   Ist bei der 8-Bit-Suche eine minimale Pulsbreite von 10 Bit zu
   aufzufinden, so braucht nur jedes zweite Byte durchsucht werden.
2. Wurde die erste Änderung gefunden, so kann, falls Mehrschrittsuche
   angewandt, die Suche, ab dieser Stelle im 1-er Raster rückwärts
   und/oder vorwärts gestartet werden.
3. Ab dieser Stelle muss dann Bitweise gesucht werden.

Der Puls ist 200 bit lang, bei einer Variablenlänge von 300 bit. 
Entspricht ca. 5 ns.
Insofern habe ich in meinem ersten Beitrag Mist geschrieben. Es kann 
auch nur eine Flanke zu sehen sein. Wenn man aber die Position der 
Flanke kennt, kann man leicht prüfen, ob es sich um eine steigende oder 
fallende Flanke handelt.  Demenstprechend ist die Zeitberechnung wieder 
korrekt, da die Pulsbreite nahezu konstant ist.

Wenn ich dich richtig verstehe, interessiert dich nur die Position der 
steigenden Flanke des Pulses.
Und da der Puls 200 Bits breit ist und dein Betrachtungsfenster nur 300 
Bit, kann es also in dem Fenster immer nur EINE steigende Flanke geben.

Vielleicht reduziert das schonmal die Summe der Möglichkeiten.

Über ein XOR zweier Bits kannst du erkennen, ob dazwischen eine Flanke 
ist.
Durch Plausinilisierung mit einem der beiden Bits kann man erkennen, ob 
die Flanke steigend war.
Diese Logik sollte sehr klein und schnell abbildbar sein.

Die Positionen der beiden zu vergleichenden Bits sind einstellbar.

Zuerst prüfst du, ob zwischen Pos 0 und 150 die steigende Flanke ist.
Wenn ja, dann lädst du den Vergleicher mit neuen Positionen (75 und 
150), wenn nein, dann lädst du ihn mit (150 und 225) und vergleichst 
wieder.
So kannst du das Btrachtungsfenster immer halbieren und solltest nach 8 
Takten am Ziel sein.
Da die Logik eigentlich recht schlank ausfallen sollte, gehe ich davon 
aus, dass man diesen Algorithmus auch schnell takten kann.
Ob du damit deine Anforderungen erfüllen kannst, weiss ich allerdings 
nicht

Ach ja, setzt natürlich voraus, dass die Pause zwischen den Pulsen nicht 
zuu winzig ist ;-)

@Lothar
Deine Frage habe ich, glaube ich nicht ganz verstanden. Es ist so, dass 
der Puls immer gleiches Aussehen und gleiche Länge hat.
Mitteln zwischen mehreren Pulsen geht nicht. Ich brauche die 
Zeitinformation für jeden Puls.



So ein Puls kommt mit 20 MHz rein. Es kommen 1-20 Pulse hintereinander, 
dann ist für einige Zeit Pause.
Aber: Es gibt mehrere Kanäle und ich würde die Messschaltung gerne im 
Zeitmultiplexing betreiben. Das wiederrum mindert die Pause zwischen den 
Pulspaketen.
Genaue Zeiten kenne ich noch nicht. Grob kann man aber sagen, dass die 
Wandlung innerhalb von 10, besser 5-6 Taktzyklen abgeschlossen sein 
sollte, wenn es denn geht.

Es wäre gut, beide Flanken zu ermitteln. Diese können zur Kalibrierung 
der Verzögerungsleitung verwendet werden, da ja die Pulsbreite bekannt 
ist. Die Verzögerungsleitung ist etwas Temperaturempfindlich.

20 MHz entspricht 50ns
Der Puls ist nur 5ns lang. Also ist die Pause zwischen zwei Pulsen 45ns 
lang.
Damit kann man schonmal sicherstellen, dass es im Betrachtungsfester 
immer nur EINE steigende Flanke geben kann.

Dein Betrachtungsfenster ist 300 Bit lang. Das entpricht 7,5ns.
Das heißt aber auch, dass du niemals sicherstellen kannst, dass du auch 
immer die negative Flanke des Pulses noch erfassen kannst. Daher würde 
ich da keinen Wert drauf legen, einen Mechanismus dafür einzubauen.

Wenn du es aber sicherstellen kannst, dass du die fallende Flanke noch 
siehst, dann setzt das voraus, dass die steigende Flanke innerhalb der 
ersten 100 Bits zu finden sein muss. Was die Suche nach der steigenden 
Flanke natürlich deutlich vereinfacht.
Die Fallende muss dann zwangsläufig in einem eingeschränkten Fenster am 
Ende zu finden sein. Daher musst du dann gar nicht das ganze Feld 
durchsuchen.

Entweder habe ich etwas übersehen, nicht verstanden, oder deine 
Anforderungen sind nicht ganz klar...

Das macht man bereits beim Einlesen

Fredo schrieb:
> Das macht man bereits beim Einlesen

Bitte einfach alles lesen, bevor man was dazu schreibt..
Einlesen geht in diesem Fall offensichtlich nicht.

Lothar Miller schrieb:
> Wie auch immer: du könntest das 0. und das 49. Bit miteinander
> vergleichen. Sind die unterschiedlich, dann ist irgendwo dazwischen eine
> Flanke. Das wären dann in der ersten Stufe der Pipeline 6 zu
> vergleichende Bitpärchen, dann vergleichst du das 0. und das 9., das 10.
> und das 19., usw...

Das wäre eine Mischung aus der von mir vorgeschlagener Methode und einer 
darauffolgenden sequenziellen Suche in fortschreitendenden, gleichgroßen 
Fenstern.
Interessante Frage, was da am Ende den "schlankeste" Ergebnis in der 
Synthese liefert. Die Wahl der Methode, oder eine Kombination aus 
Methoden wird wohl von der Größe des Betrachtungsfensters abhängen.

Allerdings muss man die Betrachtungsfenster um 1 überlappen lassen, 
sonst würde man nicht erkennen, wenn genau an den Grenzen der 
Flankenwechsel wäre.

Angenommen, man müsste tatsächlich alle 300 Werte "scannen", könnte man 
sich auch überlegen, dies in 3 Pipeline-Stufen à 7 parallele Vergleicher 
zu machen. (300 ^1/3)

man zerlegt das Suchfeld in Siebtel

Erste Stufe vergleicht:
(0/42), (42/84), (84/126), (126/168), (168/210), (210/252), (252/294)

Trifft z.B. der erste Vergleicher, dann lädt man in die zweite Stufe die 
sieben Vergleicher folgendermaßen:

(0/6), (6/12), (12/18), (18/24), (24/30), (30/36), (36/42)

Trifft hier der fünfte Vergleicher, so folgt noch eine letzte Stufe mit 
den Werten:

(24/25), (25/26), (26/27), (27/28), (28/29), (29/30)

Man wäre also mit einer dreistufigen Pipeline "durch"..

Die Methode wäre:
Überlege, wieviele Pipelinestufen (n) man maximal zulassen will und die 
Breite der Stufen ergibt sich dann (zumindest ungefähr) aus

Datenfeldgröße ^ 1/n

Oder hab ich da nen schwerwiegenden Denkfehler?

Nachtrag:

Problem bei meiner o.g. Methode könnte allerings sein, dass der Mux, der 
dann die Bits aus dem großen Datenfeld anhand des Ergebnisses aus der 
vorherigen Stufe in die nachfolgende Stufe routet, ziemlich mächtig 
werden könnte.
Aber das muss man einfach mal ausprobieren.. eventuell könnte man sich 
auch mit einer Konstruktion weiterhelfen, die anhand des Ergebnisses der 
ersten Stufe eine Kopie des betreffenden Feldes in einen Hilfs-Vektor 
zieht, aus dem sich dann die dritte Stufe "bedient"..

Lothar Miller schrieb:
> Wenn man zighundert Bits in 5ns einliest, dann braucht man ein schnelles
> FPGA...

Wenn man dem ollen Shannon nicht auf die Füße treten will, dann sollte 
das mit mindestens 80GHz geschehen.. ein wirklich flottes FPGA gg

Schlumpf schrieb:
> Problem bei meiner o.g. Methode könnte allerings sein, dass der Mux, der
> dann die Bits aus dem großen Datenfeld anhand des Ergebnisses aus der
> vorherigen Stufe in die nachfolgende Stufe routet, ziemlich mächtig
> werden könnte.

koennte man damit umgehen, dass man die vielen hundert bits, die ja in 
FFs liegen muessen um parallel auf alles zugreifen zu koennen, parallel 
ja auch in BRAMs speichern koennte. Die koennten am Read-Port dann z.B. 
nur 16bit breit sein. Wenn man aus den hunderten FFs dann erkannt hat, 
wo in etwa der Flankenwechsel war, dann kann man leicht daraus eine BRAM 
Read-Adresse generieren. Vorteil: Der dicke Mux verschwindet im RAM. 
Dann muss man nur noch aus 16bit den Phasenwechsel erkennen.

Nur mal so als 'my humble opinion'...

Beni schrieb:
> Gegeben sei eine lange Variable (> 100 bit). Diese enthält die
> Aufzeichnung eines Pulses. Beispielsweise kann das so aussehen:
>
> 000000000111111000000000000000000
>
> Es ist immer nur ein Puls, d.h. zwei Flanken vorhanden.

uebrigens: Liest du wirklich >100bit ueber >100 Chip-I/Os gleichzeitig 
in einem Takt ein? Oder wie kommen diese Daten eigenlich ins FPGA?

Hallo,

erstmal vielen Dank für die Antworten.

Das Problem mit dem stufenweisen Vergleichen ist wahrscheinlich, dass 
das ein sequentieller Vorgang ist und damit für einen FPGA nicht ideal 
ist. Das Vergleichen an sich geht schnell und braucht nicht viel Logik. 
Das Bereitstellen neuer Daten für die Vergleicher ist aber langsam und 
benötigt einen riesigen MUX. Aufgrund der hohen Singallaufzeiten im FPGA 
wird das mit deutlich unter 100 MHz takten. Die Bereitstellung der Daten 
könnte man durch ein RAM beschleunigen, allerdings müssen die Daten da 
auch erstmal reingetaktet werden.

Im Moment überlege ich, ob man nicht die Bits überlappend an LUT4 
Eingänge legen kann. Durch die Programmierung der LUTs könnte man so 
gezielt nach steigender und fallender Flanke suchen. Als Ergebnis würde 
man zwei lange Vektoren mit nur je einer 1 und vielen 0 erhalten. Dann 
müsste man nur noch die Position der 1 herausfinden.
Und da ist wieder das Problem.


Ich versuche nochmal, den Aufbau an sich zu erklären, da es hier noch 
Unklarheiten gibt:

Das Signal geht über einen einzigen Pin in den FPGA und läuft dort in 
eine lange Leitung mit vielen FF Abgriffen. Die Takteingänge der FF sind 
mit einem Takt verbunden. Da die Ausbreitung des Signals im FPGA eine 
endliche Geschwindigkeit hat, ist die Position des Signals zeitabhängig. 
Mit dem Taktzyklus kann die Position des Signals quasi eingefroren und 
die Ankunftszeit des Signals berechnet werden. Das Ganze ist eigentlich 
eine zeitkontinuierliche Analogschaltung. Um eine hohe zeitliche 
Auflösung zu erhalten muss daher nicht mit einer hohen Frequenz 
abgetastet werden.

Gruß
Beni

Trundle Trollkönig schrieb:
> wie sollen die daten dann
> überhaupt ins fpga

parallel?

Trundle Trollkönig schrieb:
> was kann überhaupt daten oder irgendwas mit 80
> ghz produzieren??

Die Daten kommen anscheinend mit 40 GHz an (müssten nur daher mit 80GHz 
gesampelt werden)
Das könnte eine externe Delayline sein, die pro Stage um 25ps 
verzögert...

Beni schrieb:
> Das Signal geht über einen einzigen Pin in den FPGA und läuft dort in
> eine lange Leitung mit vielen FF Abgriffen. Die Takteingänge der FF sind
> mit einem Takt verbunden. Da die Ausbreitung des Signals im FPGA eine
> endliche Geschwindigkeit hat, ist die Position des Signals zeitabhängig.
> Mit dem Taktzyklus kann die Position des Signals quasi eingefroren und
> die Ankunftszeit des Signals berechnet werden. Das Ganze ist eigentlich
> eine zeitkontinuierliche Analogschaltung. Um eine hohe zeitliche
> Auflösung zu erhalten muss daher nicht mit einer hohen Frequenz
> abgetastet werden.

Schonmal ausprobiert?
Du kannst nicht einfach ein "Stück Draht" in ein FPGA synthetisieren und 
von dort beliebig viele Abriffe an Register machen.
Außerdem wird die Genauigkeit nicht erreichbar sein.
25ps reproduzierbarer Delay ist sehr sehr wenig. Und alleine die Stubs 
zum Abreifen machen ja auch nochmal nen Delay.
Ich behaupte mal, dass du diese Anforderungen nicht in einer Delayline 
im FPGA umsetzen kannst (zumindest nich in einem bezahlbaren FPGA)

Beni schrieb:
> Mit dem Taktzyklus kann die Position des Signals quasi eingefroren und
>
> die Ankunftszeit des Signals berechnet werden.

Deine Methode nennst sich time to digital conversion und wird so in 
ASICs praktiziert. Allerdings bezweifle ich, ob du mit den routing 
resourcen in einem FPGA dahin kommen kannst. Wie willst du das 
kontrollieren?

Ich glaube, dass Du Dir da was theoretisches ausgedacht hast, was 
praktisch so nicht wird funktionieren können.

Die eigentliche Aufgabe, nämlich:
" Flanke in langer Variable suchen"
ist dagegen ja förmlich trivial.

high tec ing schrieb:
> Die eigentliche Aufgabe, nämlich:
> " Flanke in langer Variable suchen"
> ist dagegen ja förmlich trivial.

Das sehe ich auch so...

high tec ing schrieb:

> Deine Methode nennst sich time to digital conversion und wird so in
> ASICs praktiziert. Allerdings bezweifle ich, ob du mit den routing
> resourcen in einem FPGA dahin kommen kannst. Wie willst du das
> kontrollieren?
>

Wo hat er geschrieben dass er die eigentliche Conversion im FPGA machen 
will?

Kleine Zwischenfrage, wie ist denn das zu verstehen:

> 500 kHz continuous rate per channel
Heisst das, dass man mit 500kHz Rate jeweils einen Wert bekommt, der 
dann ein TDC-Wert darstellt?

Ich meine, wie wird der eingesetzt?

>Schonmal ausprobiert?
>Du kannst nicht einfach ein "Stück Draht" in ein FPGA synthetisieren und
>von dort beliebig viele Abriffe an Register machen.
>Außerdem wird die Genauigkeit nicht erreichbar sein.
>25ps reproduzierbarer Delay ist sehr sehr wenig. Und alleine die Stubs
>zum Abreifen machen ja auch nochmal nen Delay.
>Ich behaupte mal, dass du diese Anforderungen nicht in einer Delayline
>im FPGA umsetzen kannst (zumindest nich in einem bezahlbaren FPGA)
Probiert hats schon mal jemand mit einer "carry chain delay line":
http://cds.cern.ch/record/1158663/files/p383.pdf

bko schrieb:
> Probiert hats schon mal jemand mit einer "carry chain delay line":

Probiert habe ich das selber auch schon und das funktioniert auch 
problemlos, wenn man keinen Wert auf Genauigkeit legt und es nur auf dem 
Schreibtisch zuverlässig funktionieren muss.

Damit kann man in komplett asynchronen Designs z.B. eine Flanke 
erkennen.
Aber um verwertbare Messungen im 20ps Bereich durchzuführen taugt es 
nicht. Jedenfalls nicht in bezahlbarer FPGA-Technik, da die 
Temperaturabhängigkeit nicht zu verachten ist.

>nicht. Jedenfalls nicht in bezahlbarer FPGA-Technik, da die
>Temperaturabhängigkeit nicht zu verachten ist.
Die könnte man evtl. mit einem Referenztakt ausgleichen,
So wirds im ASIC ja auch gemacht; ok, ASIC delay-inverter kann man viel
besser matchen:
http://sus.ziti.uni-heidelberg.de/Lehre/VLSIVorlesungHS09/VLSI_06_BauteileUndLayout.pdf

Schlumpf schrieb:
> Aber um verwertbare Messungen im 20ps Bereich durchzuführen taugt es
> nicht. Jedenfalls nicht in bezahlbarer FPGA-Technik, da die
> Temperaturabhängigkeit nicht zu verachten ist.
Das kann man rauskalibrieren.
Siehe hier, Seite 16:
http://lnr.irb.hr/pd/daqws/images/E.Bayer.pdf

Duke