hallo an alle die es interessiert, ich bin gerade dabei eine 1024 punkt FFT 48khz sampling rate @ 16bit, basierend auf einer 512 punkt complex FFT, zu implementieren und wollte nur mal in diesem super-forum rumhorchen, ob jemand bereits etwas ähnliches erfolgreich implementiert hat, oder ob jemand interesse an so einer implementierung hat, oder an selbstprogrammierten tools, die die evaluierung der MPlab simulatorausgaben (fractional conversion unit) graphisch darstellen, benötigt. das ganze implementiere ich zu zeit auf einen: dsPIC30F6014A, CS4272 audio codec und 4mbit sram. die boardlayouts sind fertig und die teile bestellt, aber bin bis jetzt bin nur am simulieren des FFT example von microchip (c30). muss feststellen, dass nach 1-3 wochen intensiven lesen und "erahnen der backgrounds" (die mathematik wird mich noch ins grab bringen) und etliche datasheets und foren später, das ganze in der implementierung doch komischerweise einfacher abläuft als ich dachte. (512 punkte FFT läuft, theoretisch, aber der rest wird auch gehen MÜSSEN, ;) ) eine für mich noch offenstehende frage ist: wie bekomme ich eine 1024 punkte real input fft in eine 512 punkte complex fft transformation unter, also wie habe ich die 1024 punkte real input auf die 512 punkte complex signal input zu kopieren/kodieren und wie habe ich den 512 points complex output wieder in ein real 1024 points umzuwandeln? ich hoffe ihr wisst was ich meine, zu sicherheit nochmal kurz: ich will nen 512 complex fft benutzen um diese mit 1024 samples real input zu füttern. wie habe ich das 512pts complex signal input mit den 1024 real samples zu initialisieren und wie ordne ich dem 512pts complex output denen daraus resultierenden 1024 real amplituden zu? argh ist alles nicht so leicht unmissverständlich in einem post zu beschreiben, aber ich hoffe gut genug, (btw: mein erster post in offiziellen foren, hehe) ich wäre für jeden tipp oder sonstige anfrage dankbar. tobias rüggeberg
so ich habe mich gerade auch hier offiziell auf diesem forum angemeldet, das sollte die kontaktaufnahme vereinfachen :) würde mich über antworten freuen, morph (tobias rüggeberg)
Hallo ich bin jetzt nicht der grosse Theoretiker, aber soweit ich die FFT verstanden habe, geht das so nicht. Du hast ja für die complexe FFT nur den Realsteil - deine Messpunkte - der imaginär-teil ist somit immer 0. Für 1024 Messpunkte brauchst du also auch eine 1024 Messpunkte-FFT. Gerhard
hallo gerhard, erstmal danke für deine antwort, so weit ich dich richtig verstanden habe, hast du recht, aber es soll laut einem post in einem englischem forum, die möglichkeit bestehen, die 1024 messpunkte (real) in eine 512 "packed complex" punkte FFT packen zu können, aber im zweifel muss ich halt ne 1024pkt real FFT implementieren, aber noch denke ich das es vielleicht auch mit ner 512 complex FFT gehen könnte tobias
Du kannst natürlich die Hälfte deiner Punkte einfach wegschmeißen (z.B. jeden zweiten)... Aber warum hast du sie dann abgetastet? Hast du den Beispielcode von Microchip heruntergeladen? Da ist alles drin, du brauchst die FFT gar nicht zu implementieren. Wie es Gerhard geschrieben hat, der Imaginärteil deiner Messpunkte sind immer 0, und eine 512 große FFT kannst du nur mit 512 reellen und 512 imaginären Abtastwerten füttern (vorausgesetzt du nutzt die komplexe FFT Funktion von Microchip - CmplxFFT oder so). Es gibt auch die RealFFT Funktion, die nur die reellen Abtastwerte braucht. Diese Funktionen von Microchip sind skalierbar, d.h. die Länge der FFT ist nur ein Input-Parameter (ich glaube, dass nicht die Länge der FFT, sondern die entsprechende Potenz von 2 angegeben werden muss).
hallo Unit*, ja die beispiele von microchip laufen bereits, bis jetzt nur bis 512 complexfft, da ich momentan zu faul bin die 1024 twiddle faktoren neu zuberechnen (die sind nicht in der microchip library enthalten). Du und Gerhard haben recht, aber nach lesen eines sehr guten DFT/FFT skripts (danke christian!), WEIß ich 100% das ich eine complexe 512pkt-FFT mit 1024realwerten füttern kann um 1024 spektralwerte (real) bekommen zu können. "Eine N-Punkt FFT transformiert N komplexe Zeitwerte in N komplexe Spektralwerte. Dank der in-place Berechnung ist im Speicher nur 1 Vektor mit N komplexen Werten erforderlich. In der Praxis sind die meisten Zeitsignale x[n] aber reellwertig, denn sie repräsentieren zum Beispiel einen Spannungsverlauf in Funktion der Zeit. Selbstverständlich ist es möglich, mit einer N-Punkt FFT aus N reellen Zeitwerten N komplexe Spektralwerte zu berechnen. Dazu muss man im Speicher einfach die Imaginärteile der N Speicherwerte mit Null initialisieren." bis jetzt entspricht die aussage eurer aussage, aber es geht weiter :) "Man kann aber vermuten, dass man effizienter arbeiten kann. Tatsächlich gibt es 2 Verbesserungsmöglichkeiten: Eine Verbesserungsmöglichkeit besteht darin, mit einer einzigen N-Punkt FFT gleichzeitig zwei N-Punkt Spektren von zwei verschiedenen, reellwertigen Zeitsignalen (z.B. linker und rechter Stereokanal) zu berechnen. Eine andere Verbesserungsmöglichkeit besteht darin, mit einer kurzen N/2-Punkt FFT ein grosses N-Punkt Spektrum eines reellwertigen Zeitsignals zu berechnen und so Rechenzeit und Speicherplatz zu sparen." an der zweiten variante bin ich interessiert. im skript selber, werden alle benötigten input werte sortierung und berechnung der output werte aus der resultierenden 512pkt complex werte beschrieben. also alle die wissen wollen, wie's geht, einfach https://home.zhaw.ch/~rur/dsv1/unterlagen/dsv1kap3dftfft.pdf durchlesen. oder das gesammte skript unter https://home.zhaw.ch/~rur/dsv1.html so also habe für mich eine lösung gefunden und wollte euch daran teilhaben lassen, falls jemand fragen zur implementierung hat, fragt gerne, bin zwar noch nicht so weit, aber wird sicher kommen :). also danke für euere mühen, auch wenn's nicht wirklich fruchtbar war, aber ich bin mir sicher, das diese informationen hier, einigen eine performance steigerung von bis zu faktor 2 ermöglichen könnte. liebe grüße, tobias rüggeberg
Der Autor meint, dass die Spektren immer symmetrisch sind, deswegen reicht es, das Spektrum bis fs/2 zu berechnen. Aber (!) dazu braucht man alle N Punkte, und die FFT Funktion macht das auch!!! Das steht auch im Tutorial drin! Die twid Faktoren kannst du auch mit Hilfe einer Microchip Funktion berechnen lassen... Mein Rat: lies noch einmal und gründlich die Hilfe zum FFT Beispiel durch...
hallo unit*, 1. das microchip beispiel läuft, habe die ergebnisse der funktionen plotten lassen 2. ich möchte die twiddle faktoren im programm memory haben, nicht im ram 3. ich möchte RAM sparen und performance optimiert arbeiten --> also finde ich die lösung über die complex FFT und den im skript beschriebenen verfahren interessant. 4. geht es mir nicht primär darum die microchip fft funktionen zum laufen zu kriegen, da dies funktioniert, vielmehr bin ich dabei zu optimieren. hast du dir ernsthaft die im skript beschriebene rangehensweise durchgelesen (seite 11)? ich habe das gefühl das wir aneinander vorbeireden. ich versuche doch nur eine "Berechnung eines N-Punkt Spektrums mit einer N/2-Punkt FFT" mit hilfe der microchip library umzusetzen. im skript selber wird beschrieben: "Zuerst bildet man aus dem reellwertigen Zeitsignal x[n] der Länge N einen Eingangsvektor für die FFT mit N/2 komplexen Werten indem man die geraden Speicherzellen im FFT-Buffer mit den geraden bzw. even-Werten xe[n], n=0,...,N/2-1, und die ungeraden Speicherzellen mit den ungeraden bzw. odd-Werten xo[n], n=0,...,N/2-1, füllt." noch verstanden? also im meinem fall N=1024 --> 512pkt complex input. "Dann berechnet man die N/2-Punkt FFT und erhält N/2 komplexe Spektralwerte" das heißt eindeutig 512pkt cplxFFT "Y[m] = Xe[m] + j·Xo[m], m=0,...,N/2-1." "Das Spektrum Y[m] setzt sich aus dem even-Spektrum Xe[m] und dem odd-Spektrum Xo[m] zusammen. Gemäss Gleichung (3.10) kann das N-Punkt Spektrum X[m] aber aus den zwei N/2-Punkt-Spektren Xe[m] und Xo[m] zusammengesetzt werden" und das mithilfe der symmetrie, irgendwie verstehe ich nicht ganz worauf du hinaus möchtest, ich berechne doch trotzdem nur ne N/2 complex FFT also 512pkt + packing operationen. im schnitt ist das doch trotzdem schneller als ne 1024pkt FFT und vor allendingen brauchs weniger RAM und ram is im DSPic ja eher mangelware. liebe grüße, tobias rüggeberg
nachtrag: ansonsten haste recht, ne 1024 pkt FFT würds auch tun :), aber ich hoffe du verstehst, dass ich eben nicht die 1024pkt FFT von microchip verwenden möchte, wenn es ne 512pkt FFT + hirnschmalz auch tut. aber es könnte durchaus passieren, dass ich doch den einfacheren weg gehen werde... wie gesagt die microchip lib und deren funktionen funktionieren ja bereits. wofür die twiddle faktoren da sind und wie diese entweder im ram oder programmmemory liegen können, weiß ich auch. was ne FFT und DFT ist weiß ich auch, et-studium bring manchmal ja doch was :). der audio codec (bin inzwischen aufn TI TLV320AIC23B "ausgewichen", da digikey den CS4272 nicht liefern "konnte") funktioniert auch. ich weiß auch das ne real 1024pkt FFT auch eine lösung ist. aber an sich versuche ich gerne den etwas komplizierteren weg, um im nachhinein nicht das nachsehen zu haben, falls die overall system perfomance doch nicht ganz ausreicht. der DSPic soll ja schließlich noch einige dinge mehr machen als nur ne FFT. trotzdem danke für deine tipps, kritik. hoffe du nimmst mir meinen ton nicht übel, ist echt nicht so gemeint, aber mit deinen hilfestellungen kann ich leider nicht viel anfangen, da ja die von dir erwähnten punkte bereits funktionieren bzw ich nicht an den anfängerkrankheiten wie "wie konvertiere ich nen fractional zu nem float zwecks darstellung/debugging" hänge. liebe grüße, tobias rüggeberg
Hallo Tobias vielleicht postest du deinen fertigen Code. Im Moment habe ich zwar keinen Bedarf, aber wer weiss .. (als alter Sammler und Jäger...) Wäre auf jeden Fall nicht schlecht. Gerhard
hallo gerhard! schön wieder was von dir zu hören, da anscheinend das eher theoretische thema nicht so viele interessiert, oder wer weiß was warum, habe ich bis auf einen anruf eines ehemaligen mit-students, nicht so sehr viele hilfreiche beiträge erhalten. anscheinend versuche ich etwas unmögliches (was ich bezweifel) oder aber es ist einfach nur so sau kompliziert, dass die meisten doch eher den konventionellen weg beschreiten. werde mich die tage daran setzten das ganze zu implementieren und sobald ich eine funktionierende "Berechnung eines N-Punkt Spektrums mit einer N/2-Punkt FFT" am laufen habe, werde ich diese posten. ob erfolgreich oder nicht, ihr werdet auf jedenfall von mir hören :). danke für dein interesse und liebe grüße, tobias rüggeberg
@ unit*, hi nochmal, ich glaube langsam zu verstehen, was du meinst, aber soweit ich das ganze thema mit "symmetrie" richtig verstanden habe, ermöglicht einem ja genau diese symmetrie des complex output vectors erst diese möglichkeit. "Der Autor meint, dass die Spektren immer symmetrisch sind, deswegen reicht es, das Spektrum bis fs/2 zu berechnen". ja ist das nicht eine allgemeine eigenschaft einer FFT, dass der output vektor ab N/2 symmetrisch zum anfang ist? also der letzte wert im N vektor = der konjugiert komplexe des "N-(N- der.punkt.der.einen.interessiert)" ist? ich verstehe ehrlichgesagt nicht wo dort das problem sein soll, da es ja symmetrisch ist, habe ich doch auch die "fehlenden werte" (die konjugiert komplexen). wäre nett wenn du mir meinen gedankenfehler nochmals genauer erklären könntest. im zweifel bin ich immer der schuldige ;) ich werde versuchen den gedankengang des skripts vorerst in matlab zu testen, dann mithilfe der microchip library verifizieren und dann endlich komplett implementieren. was mir durchaus das genick brechen könnte ist die microchip library. wenn ich feststellen werde das die realFFT von microchip bereits diese optimierung implementiert hat, dann macht es keinen sinn ne complex fft dafür zu verwenden. in dem fall hut ab vor dir, aber hättest du auch besser erklären können ;), hehe vielen dank schonmal, tobias rüggeberg
@ unit*, ansonsten fällt mir gerade auf: "Der Autor meint, dass die Spektren immer symmetrisch sind, deswegen reicht es, das Spektrum bis fs/2 zu berechnen". Kennst du ne FFT die das spektrum bis fs berechnet?!?! ih kenne ja negative frequenzen, aber das würde mich wundern. was passiert denn mit frequenzen die über fs/2 liegen?! -> aliasing bitte erkläre mir mein fehler/doofheit. ich verstehe einfach deinen post nicht, da er in sich nicht gerade logisch ist. vielen dank, tobias rüggeberg
@ all, ich hasse langsam die theorie dahinter... ist zwar genial wer sich das hat einfallen lassen, aber hätten die statt DSPs mal ASPs (analog signal processor) erfinden können?! hehe, wer nicht lacht is selber schuld :) auf jedenfall ist dies ein spannendes thema für mich und anscheinend für 2 weitere und wäre für jede hilfe dankbar. hat jemand schonmal etwas ähnliches implementiert, wenn ja: sagt mir einfach nur obs geht oder nicht. für code würde ich fast töten :). christian, hilfe!!! du bist bis jetzt der einzige von dem ich das gefühl habe, dass du mir helfen kannst, das skript war schon mehr als genial!!! liebe grüsse, tobias rüggeberg
"light is an electromagnetic wave"... so LEDs are the loudspeakers for electromagnetic currents... if FFT is an algorithm for interpretating an electromagnatic wave, why don't use it for controlling HP-LEDs currents.... hehehehhehe... sorry bin gerade leucht besoffen.
Hallo hier habe ich einen Artikel gefunden, der dir evtl weiterhilft: http://www.uni-koblenz.de/~kubias/FFTGPU.pdf Gerhard
hallo gerhard! ja dieses skript ist eine sehr sehr gute ergänzung zu dem recht kurzgehaltenem, dass mir christian hat zukommen lassen. es bestätigt meine annahme, dass die art der optimierung, die ich vorhabe, auch wirklich möglich ist. vielen dank dafür. ich muss heute leider erstmal etwas anderes erledigen, aber komme heute abend dazu, mal wieder matlab zu installieren und werde dann zumindest schonmal das "packing", also das sortieren der input-werte versuchen. vielen dank und bis später, tobias rüggeberg
Hallo Tobias ich hab mir das Skript durchgelesen, verstanden hab ich das aber nicht. Wenn ich eine komplexe FFT mit rellen Daten fülle - also den imaginären Teil mit 0 fülle, enthält die FFT relle als auch imaginäre Werte. Wo will ich denn jetzt eine "kompakte" FFT oder eine 2. FFT durchführen. Hier fehlt mir schon noch die Erklärung. Gerhard
hallo gerhard! ich glaube/weiß dass das besondere an diesem verfahren, was ich bevorzuge, ist, dass man eben nicht den imaginärteil auf 0 setzt, obwohl man die fft mit realwerten füttern möchte, sonder vielmehr die 1024 (statt normalerweise 512) realwerte in den 512 complex werte beinhaltenden complex input vektor der 512pkt complex FFT stopft anstatt eine 1024 pkt FFT verwenden zu müssen, bei der die hälfte der input werte 0 wäre (=imaginärteil). d.h. bei einer 1024 pkt complex fft benötige ich insgesamt 2048 einzele fractional (je einen für real- und einen für imaginär-teil), aber bei meiner rangehensweise brauche ich nicht eine 1024 pkt complex fft um meine 1024 spektralwerte zu bekommen, sondern nur eine 512. das verfahren was in dem skript was du mir empfohlen hast, beschrieben wird, ermöglich in diesem fall das gleichzeitige berechnen einer complex fft über zwei zeilen, statt einer. das ist im endeffekt genau das selbe wie meine vorgabe, die doppelte menge an realwert samples in einer FFT zu verarbeiten, die eigentlich nur die hälfte der ergebnisse ausspucken würde, wenn man alle imaginärteile des inputvektors auf null anstatt, wie in dem beispielen der beiden skripts, den imaginär teil mit den ungraden offsets des realwertvektors belegt... also statt realteil = der gesamplete wert und imaginärteil = 0 --> realteil = 1.gesampleter (=0. = even) wert und imaginär teil der 2. gesampleter (=1. = odd) wert. der daraus resultierende vorteil ist das ich die 512pkt complex FFT, mit 1024 pkt realwert inputs füttern kann, und den resultierenden complex 512pkt output vektor in 1024 "spektrallinien" umrechnen kann, UND DAS DANK DER SYMMETRIE. hmmmmm, bin nicht wirklich gut im erklären. vielleicht hilfste mir nochmal nen bissel nach. es ist halt echt übelste theorie, angewendet auf die realität :), ich kämpfe auch schon seit wochen damit, den knackpunkt dahinter zu verstehen/spüren und ich glaube langsam auf einen grünen zweig zu kommen. also bitte bohr mich mit fragen, ich glaube zu verstehen, was dein problemchen mit dieser theorie ist, aber bin halt echt kacke im erklären. ürbigens ich hab nochmals mit christian telefoniert und der hat mir auch bestätigt dass dein skript richtig liegt und das thema genauer beschreibt als seins. dadurch habe ich indirekt die 2. bestätigung das man in diesem gebiet der verarbeitung von realwert inputs für eine FFT noch sehr viel optimieren kann, was aber leider ziemlich viel arbeit und widerstand anderere bedeutet, meist weil das problem nicht wirklich verstanden wird, was aber eher die schuld des problems als die der beteiligten ist... ;)... liebste grüße, tobias rüggeberg
habe gehört das jemand seine diplom oder master-arbeit darüber geschrieben hat...
also um das besondere an dem verfahren nochmal kurz auf deine fragestellung zu beantworten: man braucht nur EINE 512 pkt complex fft um 1024 realwerte als input zu verarbeiten. also nicht eine zweite oder sonstwass was du vielleicht annimmst. ansonsten hab ich in erfahrung bringen können, dass das verfahren WIRKLICH mit den "normalen mitteln" implementierbar ist, aber dass das nur wenige menschen überhaupt probiert haben... das geile für mich persönlich, wenn ich es hinbekomme, ist, dass ich nur die hälfte der resourcen für ein problem benötigen werde, als normalerweise. (soll nicht so schräg arrogant klingen, wie's tut) liebe grüße, tobias rüggeberg
Hallo, ich habe mir den Thread gerade durchgelesen und will auch statt einer 512 eine 1024er FFT auf einem dsPIC30F6014A implementieren. Das Beispiel von Microchip ist schön und gut, aber ich brauche eine feinere Einteilung. Ich arbeite mich gerade in die Grundlagen ein, stumpf anwenden ist nicht mein Fall. Bist Du mit der "Speichersparversion" schon vorangekommen? Gruß Marius
Aha! Ich hab das Skript gelesen. Jetzt hab ich's verstanden! Meine Anmerkungen: 1. du weißt nicht genau wie die FFT-Funktion von Microchip das Spektrum berechnet! Optimiert ist sie irgendwie schon, da sie die twid Faktoren nur bis fs/2 (-pi) braucht. Wenn sie auch etwas trickst, dann ist es nicht sicher, dass das von dir bevorzugte Verfahren funktioniert. 2. ich bin mir nicht sicher, dass das ganze viel schneller ist wegen der post-Rechnerei. Damals habe ich die FFT-Analyse on-line mit dem DSPIC Board gemacht, und ich hatte weder Leistungs- noch Speicherprobleme. Probier's aus, ich bin gespannt, ob's funktioniert, und ob's viel effizienter ist. Unit*
Tobias Rüggeberg@ habe leider jetzt erst den Thread gelesen, ich hätte sonst vielleicht helfen können. Es ist beeindruckend, dass solche Probleme und Fragen immer wieder auftreten, obwohl sich die Zeiten und die entsprechenden Bauteile doch stark ändern. Ich selbst habe ca. 1984 mit dem damals vollkommen neuen ti TMS32010 (144 Worte Ram! ) eine 128 *2 = 256 punkte FFT nach genau diesem Schema gebaut um damit eine Sprach-Kanalvocoder zu entwickeln. Ich weiss noch, dass ich damals auch einige intensive Diskussionen mit meiner Frau hatte (Mathematikerin) bis ich das als Ingenieur zum Laufen gebracht habe (Obwohl auch damals die entsprechenden Formeln in unserem Signalverarbeitungsskrptum schon vorhanden waren.). Viel Spass und Erfolg mit deiner FFT ! hans
sooo entschuldigung das ich so lange nix von mir habe hören lassen, war recht beschäftigt mit löten der DSP mainboards und groben programmierarbeiten, wie UART-kommunikation und portzugriffen beschäftigt. das board läuft, wackelt und hat luft und heute+morgen werde ich dazu kommen die FFT mal genauer testen. bin echt gespannt. also werde es euch wissen lassen. @dc4mg: wow gut zu wissen dass diese art von algorithmus schon sehr lange bekannt und verwendet wird @unit: ja das risiko dass die complexfft von microchip schon diese optimierung verwendet oder andere optimierungen verwendet, die meine vorgeschlagene optimierung zunichte machen, sehe ich auch so, werde aber mehr dazu wissen sobald ich es getestet habe @mario: bis jetzt leider nicht, und weiß auch selber nicht 100% genau wie ich daran gehen soll/werde, aber mal sehen @all: notfalls nehme ich halt doch die 1024 pkt fft von microchip und verwende dann den 4MBit SRAM der auf meinem DSP mainboard noch unbenutzt verweilt, um darin nicht FFT spezifische variablen zu speichern. liebe grüße, tobias rüggeberg
@dc4mg hi nochmal, hmm klingt echt interessant, vielleicht musste mir doch nochn ein wenig weiterhelfen, aber momentan weiß ich die konkreten frage(n) noch nicht :) hehe, muss mir meinen thread erst nochmal intensiv durchlesen (inkl. der skripts). aber irgendetwas wird mir sicher noch das genick brechen und dann ist es gut zu wissen, dass ich jemanden ansprechen kann, der das schonmal selbst lösen musste. also danke und bis später :) liebe grüße, tobias rüggeberg
Tut mir Leid, aber ich sehe in der komplexen FFT keine Vorteile gegenüber der reellen FFT (zumindest von Geschwindigkeit und Speicher her). Grund: Der Speicher wird, egal ob als Real- oder Imaginärteil angesehen, 1024 Speicherstellen belegen, sind nunmal 1024 Werte. Das Spektrum hat im jeden Fall 1024 Werte, egal ob direkt berechnet oder später zusammengefügt, bzw. kann in beiden fällen auf 512 Werte nach der Berechnung reduziert werden, da symmetrisch. Die Geschwindigkeit wird auch nicht besser sein, da beim berechnen der Koeffizienten bei der reellen FFT die komplexen Werte ja 0 sind, heißt also die Multiplikation spare ich mir, bei der komplexen FFT sinds zwar anfangs nur 512 Koeffizienten, bei diesen müssen aber sowohl real, als auch imaginärteil berücksichtig werden, was äquivalent zur reellen FFT mit 1024 Werten ist.
joep hat Recht. Das Multiplexing der zwei N -dimensionalen Zeitvektoren sieht auf den ersten Blick interessant aus, bietet aber bei Lichte betrachtet keine Vorteile. Da du für die Berechnung eine DFT für ein quasi-komplexes N -dimensionales Signal machen musst, hast du letztendlich wieder 2N Werte (N mal Realteil + N mal Imaginärteil) die berechnet werden müssen. Abgesehen vom Aufwand des Multiplexing/Demultiplexing (der Autor nennt es "Packing" und "Splitting") hat diese Variante nur dann einen Vorteil, wenn du ausschließlich eine FFT-Funktion für komplexe Signale zur Verfügung hast und außerdem keine Lust darauf hast selber eine FFT für rein reelle Signale zu implementieren. Eine reelle FFT liefert dir aus N reellen Signalwerten wiederum N komplexe Transformationswerte (gerne auch Spektralwerte genannt). Diese Transformationswerte sind konjugiert komplex, das heißt, dass du (fast) die Hälfte der N Werte ignorieren kannst. Hier ein Beispiel eines Betragsspektrums für N = 8: o | | o o | | o o | | | | o o | | | | | | o | | | +-+-+-+-+-+-+-+ 0 1 2 3 4 5 6 7 n Du siehst, dass bei n = 4 der letzte Transformationswert ist, der 'eigenständig' ist. Ab n = 5 treten die konjugierten Werte auf. Ein komplexer Wert ist definiert mit: z = x + j y . Der konjugierte Wert zu z ist: (z)* = x - j y . Im Beispiel von oben bedeutet das also, dass du ab n = 5 die Werte ignorieren kannst. Schließlich zaubert man sich die wie folgt: X [7] = ( X [1] )* X [6] = ( X [2] )* X [5] = ( X [3] )* Dennoch spart man dabei nichts. Schließlich muss man ja eine komplexe Zahl speichern, und die besteht quasi aus zwei unabhängigen, rellen Zahlen (x und y). Wie man es also dreht und wendet, die DFT liefert aus N Werten wiederum N Werte. Es gibt jedoch eine Abhilfe, die sich MDCT (Modified Discrete Cosinus Transform) nennt. Die MDCT liefert aus N reellen Eingangswerten genau N /2 reelle Transformationswerte. Die Berechnung der Transformation braucht aber ebensoviele Operationen wie die normale FFT (wenn man keine Handstände macht): N log2( N ).
@pumpkin: > Abgesehen vom Aufwand des > Multiplexing/Demultiplexing (der Autor nennt es "Packing" und > "Splitting") hat diese Variante nur dann einen Vorteil, wenn du > ausschließlich eine FFT-Funktion für komplexe Signale zur Verfügung hast > und außerdem keine Lust darauf hast selber eine FFT für rein reelle > Signale zu implementieren. Ja, ich habe nicht vor eine FFT für rein reelle signale zu implementieren, sondern die der C30 library verwenden. Bin selber noch am testen, melde mich später nochmals. Liebe Grüße, tobias rüggeberg
> Abgesehen vom Aufwand des > Multiplexing/Demultiplexing (der Autor nennt es "Packing" und > "Splitting") hat diese Variante nur dann einen Vorteil, wenn du > ausschließlich eine FFT-Funktion für komplexe Signale zur Verfügung hast > und außerdem keine Lust darauf hast selber eine FFT für rein reelle > Signale zu implementieren. Normalerweise ist jede FFT für komplexe Signale gedacht (ein rein reelles Signal ist ja auch ein komplexes Signal, nur eben mit Imaginärteil=0). Der Algorithmus bleibt ja der gleiche, lediglich die Eingangswerte sind anders. Hat also auch da keinen Vorteil (außer natürlich die FFT ist so optimiert, dass die Terme mit den Imaginärteilen vollständig unberücksichtigt bleiben, aber da wird die Geschwindigkeitsverbesserung ebenfalls minimal sein).
also um nochmal kurz auf meine ursprünglich frage/lösungsweg einzugehen: ich habe vor eine 512pkt complex FFT mit 1024pkt real input zu füttern und das nicht indem ich jeden input-imaginär-wert auf 0 zu setzen. mich beschleicht das gefühl, das wir aneinander vorbei reden. es existiert die möglichkeit mit eine N-pkt complex FFT ein N-pkt real spectrum zu berechnen und das mit hilfe dieser symmetrie, und in sachen RAM-ersparniss: wenn ich die konjugiert komplexe zahl bilden will brauch ich doch genau 2 fractionals mehr (um die berechnung durchzuführen) und habe vor das ergebnis in den complex output vector ab N/2 aufwärts zu schreiben (der eh schon allokiert ist) --> also sieht für mich durchaus speichersparender aus. desweiteren benutze ich die inplace implementierung (d.h. input vektor wird zum output vektor der FFT). wenn ich also eine 512pkt complex FFT benutze, hat mein in/out vektor die größe 2*512 fractional (realteil und imagteil). in dieses array ist nach der FFT das spectrum von 0 bis N/2, also ergebniss 2*256 fractional, folglich ist die andere hälfte nach berechnung der FFT frei für weitere ergebnisse.. irgendwie verstehe ich nicht, warum das euerer meinung nach keine speicherersparniss sein soll. habt ihr den weg in den 2 skripten nachvollziehen können? ich selber schreibe gerade noch an debug funktionen rum, bevor ich zum testen dieser implementationsidee komme, aber da zeitdruck vorhanden ist, werde ich hoffentlich bald eine antwort, bzw mehr konkrete fragen haben... wie gesagt, die eigentliche complex FFT von microchip funktioniert bereits, habe auch noch luft im RAM, aber lieber optimieren anstatt nachher fluchen.. (rechenleistung hat man in der regel mehr, als RAM) liebe grüße, tobias rüggeberg
Wir reden nicht aneinander vorbei, ich weiß durchaus was du machen willst. Aber dass es vom Speicher her nicht sparend ist sollte dir aus folgendem Grund schon einläuchten: Egal ob du eine komplexe oder eine reelle FFT machst, das Ergebnis am Ende sollte das gleich sein (sonst wäre ja eine von beiden falsch) => beiden Ergebnisse verbrauchen am Ende gleich viel Speicher (nämlich bei einer 1024 FFT 512 Speicherblöcke, da die anderen 512 entweder wegen der komplexen FFT wegfallen oder bei der reellen FFT durch die symmetrie implizit gegeben sind) du kommst also, egal ob reell oder komplex auf ein Spektrum mit 512 Werten. => es ist völlig egal ob du eine komplexe FFT oder eine reelle FFT durchführst (auch wegen den Gründen die ich schon oben in meinen vorherigen Posts genannt habe)
>in dieses array ist nach >der FFT das spectrum von 0 bis N/2, also ergebniss 2*256 fractional, >folglich ist die andere hälfte nach berechnung der FFT frei für weitere >ergebnisse Das kannst du natürlich nach der komplexen FFT nicht mehr machen, weil das Ergebniss nicht mehr symmetrisch ist. Du brauchst alle Werte von 0 bis N um dein tatsächliches Spektrum zu berechnen. Musst also weiterhin 512 Werte speichern.
joep wrote: > Der Algorithmus bleibt ja der gleiche, lediglich die Eingangswerte sind > anders. Hat also auch da keinen Vorteil (außer natürlich die FFT ist so > optimiert, dass die Terme mit den Imaginärteilen vollständig > unberücksichtigt bleiben, aber da wird die Geschwindigkeitsverbesserung > ebenfalls minimal sein). Das wage ich zu bezweifeln. Nimmt man für ein reellwertiges Eingangssignal eine komplexe FFT verschenkt man ordentlich Rechenleistung. Eine komplexe Multiplikation umfasst 4 reelle Multiplikationen - auch wenn der Imaginärteil 0 ist wird multipliziert (es sei denn der Optimizer ist so gut und kriegt das spitz - was ich ebenfalls bezweifle). Nimmt man hingegen eine reelle FFT weiss man von Anfang an, dass der Imaginärteil 0 ist und führt die Multiplikation erst garnicht durch - also wird aus 4 Multiplikationen 2 . Back to Topic: Wenn ich mir die Gleichung (3.19) anschaue sehe ich keinen Vorteil das so zu machen. Gibts denn in der Library keine optimierte FFT für reelle Signale?
Ok, war etwas blöd ausgedrückt mit dem "wird die Geschwindigkeitsverbesserung ebenfalls minimal sein", man wird schon einen Unterschied merken. Hab das fälschlicherweise auf aktuelle PCs bezogen (schlecht wenn man in mehreren Foren gleichzeitig postet und das durcheinander bringt ;) ), und da wird man heutzutage eben keinen großen Unterschied merken. Bei nem kleinen µC merkt man das natürlich. Ansonsten ist das ja genau das was ich weiter oben geschrieben habe.
Hallo Tobias, ohne dem Thread in jeder Einzelheit gefolgt zu sein: Ja, was du willst geht. Man muss allerdings die Zeitwerte vor bzw. nach der FFT-Transformation umformatieren (je nachdem ob man Hin oder Rück-Rücktransformation berechnet). Habe hier ein altes Pascal Programm gefunden in dem ich das vor 15 Jahren mal implementiert habe. Lässt sich nach wie vor noch mit z.B. aktuellem Free-Pascal Compiler übersetzen. Habe aber leider nicht mehr die Info, aus welchen Büchern ich "abgeschaut" habe, daher möchte ich es hier nicht posten. Wenn dies für dich interessant ist kann ich es dir gerne schicken. Man kann im Programm gut sehen, welcher mathematische Zusatzaufwand notwendig ist. Auf jeden Fall ist es ein pre- oder postprocessing der reellen Zeitdaten und man benutzt als FFT eine ganz normale "Komplex-FFT" Routine. Also entweder: 1024 reelle Zeitdaten in Feld mit 512 komplexen Werten verteilen FFT Postprocess -> 512 komplexe Daten im Frequenzbereich oder 512 komplexe Daten im Frequenzbereich Preprocess inverse FFT -> 1024 reelle Zeitdaten verteilt im Array mit 512 komplex Werten Gruß Gerhard
erstmal vielen dank an alle, die sich hier echt hilfreich einbringen! so bin bis jetzt leider immer noch nicht zur FFT gekommen, da ich momentan das GLCD (128*64 ks0107/ks0108) + font + menu implementiert habe. gerade heute habe ich den CS4272 codec angeworfen (digikey hatn doch nachgeliefert und dank 5V VIO ist mir der lieber als der funktionsreichere 3.3V TI codec) und lese die ersten PCM samples aus, sieht bis jetzt super aus, mal sehen was passiert wenn ich audio einspeise.. dann wenn ich ne gescheite pegelanzeige habe, werde ich die FFT endlich mal anschmeißen.... ahhh das projekt raubt mir noch jeden nerv, aber immerhin schon mal keine layout/routing fehler.. liebe grüße, tobias rüggeberg
@gerhard ja daran wäre ich sehr interessiert, da die komplexe-FFT ja bereits funktioniert, wäre das pascal-proggi echt praktisch! morph_fdg (ät) gmx (punkt) net liebe grüße, tobias rüggeberg
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.