Ich möchte eine FFT durchführen, die aber sehr lange ist. Ich verwende das streaming Modell und erhalte bei z.B. 2048 Daten erst nach 2048 (Einschreiben )+ ca 500 Latenz + 1024 (Auslese) = 3500 Taktzyklen einen ersten Wert. Das FPGA ist schnell genug, aber die Daten kommen nicht scheller rein (120MHz). Ich würde gerne die FFT in der Geschwindigkeit verdoppeln, also ein Core berechnet die eine Hälfte und der andere die andere Hälfte. Damit hätte ich nur 1024 Takte zum Einschreiben, weniger Latenz und auch nur 512 zum Auslesen. Der erste Block könnte quasi schon nach 1024 Daten losrechnen und das Ergebnis wäre nach dem zweiten fertig, also 2048 + 512 + kleinere Latenz. Geschätzt: 2600 Wie könnte man das machen? Bez kann man einen FFT Core halb nutzen (halb mit Daten füttern)?
Jan schrieb: > also ein Core berechnet die eine Hälfte und der andere die andere Hälfte. Von was? > Wie könnte man das machen? Was ist dein eigentliches Problem? > Ich verwende das streaming Modell Mach es doch einfach anders... :-/
Versteh ich es richtig, statt einer 2048 Punkte FFT möchtest du eine 1024 Punkte FFT machen?
Wozu benutzt Du das Ergebnis der FFT? Kommt eventuell auch ein digitaler Filter in Frage?
Gab doch jetzt vor ein paar Tagen einen Bericht, nachdem MIT an der schnelleren-schnellen-Fourier-Transformation arbeitet. Die haben das wohl mit vorgeschalteten Filterbänken gemacht oder so ... Kann man nicht per Filter das Frequenzband in der Mitte in 2 Gleiche trennen und dann jeweils eine 1024pt FFT drauf ansetzen?
Also ich meine, Halbbandfilter, Polyphase-Dezimierer mit Saplerate-Halbierung und dann 2*FFT
Fetz schrieb: > Kann man nicht per Filter das Frequenzband in der Mitte in 2 Gleiche > trennen und dann jeweils eine 1024pt FFT drauf ansetzen? Hört sich hinreichend verwegen an. Das könnte klappen... ;-) Jan schrieb: > Ich würde gerne die FFT in der Geschwindigkeit verdoppeln Man kann (in gewissen Grenzen) immer Geschwindigkeit gegen Ressourcen aufwiegen. Nur gibt es für eine Abschätzung bisher zu wenige Zahlen...
klar, ich kann das Signal runtermischen und zwei grobe FFTs machen. Ich möchte das Problem aber nicht analog sondern digital lösen. Der FFT-Core - so wie ich ihn instanziere - geht ja davon aus, dass er "n" werte bekommt. Dann rechnet und sortiert er. Darauf aufbauend müsste es möglich sein: 1) Die Rechnung dahingehend zu vereinfachen, dass die eine Hälfte der Werte Null ist, was zu weniger Code führt, weil Berechnungen wegfallen und die Ergebnisse früher stabil sind, bzw nicht so stark gepipelined werden muss, um die speed zu schaffen, also mehr der Berechnungen (butterfly) in einem Takt erfolgen können. 2) Wenn weniger zu berechnen ist, muss auch weniger ausgeben werden. Somit liesse sich die Berechung aufteilen, dass ein Core etwas berechnet und die eine Hälfte ausgibt, der andere quasi dasselbe berechnen könnte, sich aber auf die ungeraden Frequenzen konzentriert und nur diese ausgibt.
Jan schrieb: > klar, ich kann das Signal runtermischen und zwei grobe FFTs machen. Ich > möchte das Problem aber nicht analog sondern digital lösen. Ööh ... und wieso nicht digital runtermischen und zwei FFTs machen?
Mit "analog" meinte ich solche Mischereien und Frequenzverschiebespielchen. Das müsste doch mit der FFT selber gehen. Meine ich halt ..
Klar kannst du Teile der FFT parallelisieren, bzw. eine grosse aus mehreren kleinen zusammensetzen. z.B. kann man eine 32768 Punkt FFT aus 3*1024 Läufen von getrennten 32Punkt FFTs machen. Dass das wirklich aufgeht, sieht man zB. an der Gesamtzahl der Butterflies (15*16384 = 3*1024*80). Wenn du eine 2048er FFT kleinbekommen willst, geht das über 2 1024er, deren Ergebnisse dann über einen Radix2-Kernel zusammengefügt werden (in beiden Fällen 11264 Butterflies). Das braucht aber durchaus 1024 (unterschiedliche) Koeffizienten. Also mindestens ein BRAM mit denen. Fertig gibts da AFAIK nix, musst du schon selber machen. Fang am besten mal an zu verstehen, wie die FFT überhaupt abläuft, zB. mit einer übersichtlichen 16er. Es sollte dann relativ offensichtlich sein, dass man jede der 4 Runden mit je 8 Butterflies parallelisieren kann, bzw. wie der letzte Durchlauf die Ergebnisse von vorher zusammenfügt.
Macht es doch nicht so kompliziert. Du must eine Pipline verwenden. Du berechnest die 1 FFT. Während der Berechnung schreibst die nächsten Daten in den 2 FFT-Kern der dann wieder 3500 Takte benötigt. Du kannst z.B. 4 FFTs immer versetzt berechnen. Dem nach dem welchen FPGA Du verwendest kannst Du auch 20 FFTs gelichzeitig berechnen. Ich hoffe das hat Dir weiter geholfen. Ach eins habe ich noch vergessen. Du bekommst aus 2048 Datenpunkte 1024 komplexe Zahlen (also 1024 Realteile und 1024 Imaginärteile) Wie hast Du denn deb Betrag gebildet?
Jan schrieb: > Ich möchte eine FFT durchführen, die aber sehr lange ist 2048 ist aber noch nicht Soooo lange, speziell in einem FPGA nicht. Deine Überlegung Nummer 1 kannst Du umformulieren zu, Wie man FFTs interlacet. Dazu benutzt Du die halbe FFT-Auflösung und den Core mit 2 Kanälen oder 2 parallelnl FFTs. Um das Runter-, bzw Hochmischen kommst Du dann aber nicht rum oder Du musst Deine FFT selber programmieren und eigene Frequenzen festlegen. Damit landest du funktionstechnisch bei einer DFT. Inwieweit man die nun noch so zusammenfassen kann, das sie schneller wird, musst du schauen. Deine Überlegung Nummer 2 kannst Du umformulieren zu, wie man beschleunigt ausgibt. Da um das Abwarten des letzten Wertes nicht herum kommst (du kannst NICHT schon nach der Hälfte der Daten beginnen, weil dann die Auflösung sinkt), bleibt die eigentlich nur ein paralleles Auslesen. Auch ohne die Nummer 1 wird irgendwann mal das Ergebnis-Set stabil und ist bekannt. Dieses Auslesen muss freilich nicht sequenziell erfolgen. Wenn Du die FFT händisch programmierst, kannst Du die Registerwerte ja rausflashen, wann und wohin Du möchtest. Z.B. interessieren Dich gfs nur bestimmte Frequenzen oder Bänder. Dann kannst Du Dich darauf konzentrieren und früher beginnen, auszuwerten. Andererseits läuft das dann schon wieder auf den Görtzel hinaus, wenn du nur wenige Frequenzen brauchst. Wenn du aber doch alle Frequenzen brauchst, muss Du auch die Berechung aller Ergebnisse abwarten. Dann greift nur der Vorschlag der parallelen Ausgabe, sofern das bei einem FPGA am Anschlag überhaupt Sinn macht, da ja alle Folgeoperationen dann ebenfalls parallel laufen müssten. Du willst mit den Daten ja auch was tun und die FFT Cores in den FPGAs sind nicht ohne Grund auf pipelining und damit optimalen Datendurchsatz getrimmt. Am Ende investierst du mit anderen Lösungen viel Struktur, um nur wenig Tempo zu gewinnen. Wenn, müsstest Du auch das Einschreiben in die Register parallelisieren. Was Du gfs noch nicht ausgeschöpft haben wirst: 1) FiFo vor die FFTs und mit maximaler Geschwindigkeit prozessieren. 2) Auf die Ausgabe der natürlichen Reihenfolge verzichten und selber umsortieren. Dann muss nicht gewartet werden, bis der FFT-Wert 1 fertig ist. Sebastian schrieb: > Du berechnest die 1 FFT. Während der Berechnung schreibst die nächsten > Daten in den 2 FFT-Kern der dann wieder 3500 Takte benötigt. Du kannst > z.B. 4 FFTs immer versetzt berechnen Das ist was anderes. Man bekommt eine feinere Auflösung der Frequenzinformation über die Daten, das Extrem wäre mit jedem Datum eine aktualisierte FFT. Die Latenz ist dieselbe. Was der TO aber will, ist Latenzverkürzung.
Jan schrieb: > Mit "analog" meinte ich solche Mischereien und > Frequenzverschiebespielchen. Das müsste doch mit der FFT selber gehen. > Meine ich halt .. Es ist keine Mischerei. Ein Halbband-Polyphase-Filter macht ja schon alles alleine. Per Matlab-DSP Toolbox kann man sich die Koeffizienten für so einen Filter (bereits inklusive Sample-Rate-Halbierung) berechnen lassen. Der Filter ist dann ein simpler FIR. Am Ausgang lässt man jedes 2te sample weg (Halbierung der Sample-Rate) und das wars ... Ganz easy
Ah, Link wieder gefunden: http://www.mathworks.de/products/dsp-system/demos.html?file=/products/demos/shipping/dsp/pr2chfilterbankdemo.html
Ich erkenne noch nicht, wie (alleine!) das Halbbandfilter mir
weiterhilft. Das HBF trennt mir doch nur die Frequenzen auf und ich habe
zwei parallele Datenkanäle, der eine hat die Tiefen und der andere die
Höhen.
Nehme ich nun zwei FFT-cores unveränderter Bauart gegenüber der
eindimensionalen Variante, bekomme ich doch in der einen auch einfach
nur die Bässe und in der anderen die Höhen. Der Rest ist jeweils mehr
oder weniger 0.
Da sehe ich noch nicht den Gewinn! Der Core liefert die Daten
sequenziell und ich kann bei dem einen früher aufhören, mitzuhören, weil
die Tiefen von 0% bis 25% der Auslese kommen. Aber andere bringt mir die
Höhen erst zwischen 25% und 50% der Auslesezeit. Oder kann man das
umdrehen?
Meines Erachtens muss ich die hohen Frequenzen doch auch nach unten
schieben, um schneller zu werden, also doch mischen? Aus der NT weiss
ich, dass man bei einer Multiplikation der Frequenz A mit B die
Frequenzen A-B und A+B erhält. Muss ich dann vor der zweiten FFT die
Höhen mit der halben Samplefrequenz runtermischen?
Und dann, wie bringe ich nun die halbe FFT ins Spiel? War das so gemeint
eine halb so lange FFT zu nehmen?
>Wenn du eine 2048er FFT kleinbekommen willst, geht das über 2 1024er,
Jan schrieb: > der eine hat die Tiefen und der andere die > Höhen. Nein, das ist nicht richtig ... Nach der Sample-Rate-Dezimierung hast du "2 mal tief". Das kann man machen, weil es kein Aliasing mehr mit dem anderen halben Band gibt, weil es nicht mehr vorhanden ist.
Vlt noch zusätzlich ... Normalerweise hast du den Nyquist, der dir sagt, dass du 40kHz Sample-Rate brauchst für 20kHz Signal. Wenn du das in zwei Bänder teilst mit 0-10kHz und 10kHz-20kHz, dann kannst du das obere Band einfach runtersampelt auf 20kHz. Das Sprektrum sieht dann so aus, als wäre es 0-10kHz. Das geht aber nur dann, wenn die 0-10kHz nicht mehr da sind, mit denen die Frequenzen Aliasen könnten. Wenn du den Polyphase-Filter mit 40kHz takten lässt, kriegst du quasi 2 Kanäle mit Frequenzen von 0-20kHz, wobei der eine Kanal eigentlich 0-20 ist und der andere 20-40.
Fetz schrieb: > Nein, das ist nicht richtig ... Nach der Sample-Rate-Dezimierung hast du > "2 mal tief". ok, nach der Ratendezimierung! Wobei ich das nur für die niedrigen Frequenzen direkt einsehe. Für die Tiefen entfällt durch den Filter das Aliasproblem. Aber für die Höhen fällt doch Information weg, wenn man jedes 2. sample weglässt. Mir fehlt da wohl ein wenig NT-Knowhow. Die Signalkette wäre also: Input -> Halbbandfilter -> 0% - 50% Frequenz -> FFT1 -> 50% - 100% Frequenz -> FFT2 Die Frequenzen der FFT binde ich dann einfach zusammen. Nach demselben Muster liessen sich auf 4 Bänder definieren, meine ich. Allerdings: Habe ich zwei Probleme; 1) So ganz hunderprozentig kann das nicht sein, weil doch die Filter nicht-ideal sind. An den Bereichsgrenzen dürften sich Artefakte zeigen. Müsste man gfs durch Überlappung lösen (wie?) 2) Die Filterei kostet mich wahrscheinlich rodentlich Zeit, weil der Filter sicher nicht gerade mit 5 Taps auskommen wird. Die Latenz kommt ja dann nochmals in meine Signalkette hinein. Momentan sehe ich eher, dass ich später fertig sein werde, als früher.
Schau mal hier. ;) http://www.elektor.de/elektronik-news/schneller-als-die-fft-erlaubt.2061779.lynkx Es geht also noch schneller als FFT.
Nur jetzt so aus der Zusammenfassung beurteilt ist das Verfahren nur in Sonderfällen nutzbar... zB. bei fast allen Modulationsstandards, die eine FFT brauchen, sind so gut wie alle FFT-Punkte auch notwendig. WLAN nutzt 52 aus 64, DVB-T 6144 aus 8192, DAB 1536 aus 2048. Da bringt Filterung (ausser Phasenproblemen) nicht mehr viel... Algorithmisch ist das auch kein neues Verfahren, so wie es einst die FFT selbst war...
Jan schrieb: > Aber für die Höhen fällt doch Information weg, wenn man > jedes 2. sample weglässt. Mir fehlt da wohl ein wenig NT-Knowhow. Nein, eben nicht ... Theoretisch gehen keine Informationen verloren. Praktisch durch Rechenungenauigkeiten. Such dir mal Tutorial zu Polyphase-Filter, da wirds dann klarer, wieso das so ist.
Achja, und natürlich das Matlab-Beispiel ... Es heißt ja auch "2 channel perfekt reconstruction filterbank" ... Da darf nichts verloren gehen :)
Ich bin an einer ähnlichen Fragestellung dran und auch beim HBF geladnet. Bleibt die Frage, wie das Halbbandfilter gebildet wird. Ein "Idealer Tiefpass" nach den üblichen Verfahren nehme ich an. Aber: Fenstern oder nicht? Die Fensterung verkrümmt doch die Frequenzspektren, wie kann das dann noch stimmen? Siehe auch meine Überlegung zu hier: Beitrag "Fenstern oder nicht Fenstern"
Ich habe einen solchen Filter nun gebaut und einfach die halbe Nyquist angesetzt. Ich hoffe, ich bon da nicht daneben. Leider klappt es aus anderen Gründen nicht so, wie gedacht: Beitrag "Mappen versagt, weil Summationen nicht getaktet sind (?)"
Nein :-) @Fetz: wie wiet kann man das Spiel mit der FFT-Unterteilung treiben? Hat das Verkürzen der FFT nicht Auswirkungen auf die erfasste Frequenz nach unten? Ich meine, man muss doch sicher eine gewisse Mindestmenge an Daten in die FFT einleiten, damit die Frequenzen erfasst werden können. Also wenigstens mal die Grundwelle. Wenn man aber mit z.B. 100kHz erfassen will, brauche ich mindestens 10us sample time, bei 100MHz also 1000 Werte. ???
Jan schrieb: > @Fetz: wie wiet kann man das Spiel mit der FFT-Unterteilung treiben? > Hat das Verkürzen der FFT nicht Auswirkungen auf die erfasste Frequenz > nach unten? Hmm ... ich schätze, dass die Faltungseffekte durch die FFT immer größer werden, je kleiner das Fenster ist. Da war erst ein ähnlicher Thread über das Fenstern bei FFT.
Fetz schrieb: > Jan schrieb: >> @Fetz: wie wiet kann man das Spiel mit der FFT-Unterteilung treiben? >> Hat das Verkürzen der FFT nicht Auswirkungen auf die erfasste Frequenz >> nach unten? > > Hmm ... ich schätze, dass die Faltungseffekte durch die FFT immer größer > werden, je kleiner das Fenster ist. > > Da war erst ein ähnlicher Thread über das Fenstern bei FFT. Müsste es logisch betrachtet nicht bis auf 2 Frequenzen hinunter so funktionieren ? Man hätte dann eine Filterbank und hinter jeder eine 2-Punkt FFT, also letzendlich das Gleiche als ohne diesen Trick mit einer kompletten großen FFT ? Der einschänkende Effekt sind dann wirklich nur die unerwünschten Faltungseffekte der FFT selber, aber diese müssen ja auch bei den Filterbänken eintreten, oder ? Gruß Hagen
Ich bin kein Experte für FFTs, aber es ist irgendwie einleuchtend, was passiert, wenn man das Fenster verkürzt: Es gibt weniger Werte, die dazu beitragen, dass sich die jeweils untersuchte Frequenz von den Nachbarn abheben kann. Meines Erachtens wird bei der Verkürzung des Fensters die Abdeckung der FFT-Linien immer grösser, d.h. sie werden weniger selektiv. Eine gute FFT zeichnet sich aber dadurch ab, dass sie möglichst schmalbandig ist, wenigstens so, dass die Überlappung sinnvoll passt, dass also keine Frequenz "durchfällt", weil sie nicht gut erfasst wird. Ich habe beim meinen Messungen immer den Eindruck, dass die Frequenzen in den Amplituden etwas variieren, wenn man sie durchsweept - je nachdem, wie gut die Frequenz zur FFT-Frequenz passt. Es bilden sich quasi kleine Höcker, die im Ausmass geringer werden, wenn die Auflösung steigt. Zum Zweiten habe ich die FFT, die ,im Gegensatz zur DFT, immer genau so viele Frequenzen auswirft, wie sie an Daten reingestopft bekommt, immer so aufgefasst, dass sie damit genau ausbalanciert ist - die Überlappung der Frequenzen also sozusagen optimiert ist. Aber egal, ob das so ist, oder nicht - Ich bin eigentlich sicher, dass man durch eine DFT, die mit z.B. 128 Frequenzen arbeitet, sich aber über 512 Werte erstreckt, schmalbandiger ist, als mit einer, die sich nur über 128 Werte ersteckt. (Mal davon abgesehen, dass sich das zu messenende Signal in seiner Struktur ändern könnte, wenn die Zeit wächst). Wenn man also herginge und das Fenster verkleinern würde, wird die FFT sehr unselektiv werden - egal, mit welcher Windowfunktion man da die Daten noch glättet. Eine Filterbank auf letztlich zwei Punkte herunter zu brechen, kann sicher keinen Vorteil bringen, denke ich. Die eigentliche Frage war aber wohl eine andere, nämlich , wie man die existente FFT beschleunigt. Ich würde sagen, paralleles einlesen, paralleles rechnen und paralleles auslesen.
FFT-Neuling schrieb: > Die eigentliche Frage war aber wohl eine andere, nämlich , wie man die > existente FFT beschleunigt. Ich würde sagen, paralleles einlesen, > paralleles rechnen und paralleles auslesen. das wäre das Maximum was rauszuholen ist durch die geänderte Verarbeitung der Daten durch das FPGA. Aber eben keine Lösung die den Gesamt-Algorithmus optimiert, also die Frage ob man mathematisch was an der FFT drehen kann um es zu beschleunigen. Gruß hagen
"Paralleles Einlesen": Dazu muss ich mir wohl einen eigenen Core schreiben, nehme ich an. Oder gibt es eine FFT, die das kann? Die open cores FFT macht das offenbar nicht.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.