www.mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP DSPic FFT mit 48khz 16bit Audio Codec


Autor: Tobias Rüggeberg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)

Autor: Gerhard (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Unit* (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Unit* (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Gerhard (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ 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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ 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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ 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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
"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.

Autor: Gerhard (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo

hier habe ich einen Artikel gefunden, der dir evtl weiterhilft:

http://www.uni-koblenz.de/~kubias/FFTGPU.pdf

Gerhard

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Gerhard (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
habe gehört das jemand seine diplom oder master-arbeit darüber 
geschrieben hat...

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Marius (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Unit* (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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*

Autor: dc4mg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: joep (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: T. H. (pumpkin) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ).

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: joep (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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).

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: joep (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)

Autor: joep (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: T. H. (pumpkin) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: joep (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Gerhard (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Tobias Rüggeberg (morph)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.