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*