discrete fourrier maar geen FFT

Gewoon de standaard DFT gebruiken. Zie
http://en.wikipedia.org/wiki/Discrete_Fourier_transform

Calvin

Calvin, met een linkje naar wikipedia help je hem echt niet hoor

@TS:
Goed, ik zie dat je excel wil gebruiken. Excel kent (bij mijn weten) enkel de FFT, en inderdaad, het aantal samples moet een macht van 2 zijn. En ook maximaal 4096 samples dacht ik, maar dit terzijde.
Wat je moet doen is voor of achter de reeks met samples een aantal nullen toevoegen zodat het aantal samples een macht van 2 vormt. Deze techniek noemt 'padding' en wordt zeeeer vaak gebruikt. Het toevoegen van deze nullen aan de reeks samples beinvloed je transformatie hoegenaamd niet, er is absoluut geen vermindering van nauwkeurigheid.
Om te begrijpen waarom zul je toch goed moeten begrijpen hoe fourier transformaties werken, als je geinteresseerd bent in een begrijpbare en diepgaande uitleg, hier vind je een legaal boek op in pdf formaat, hoofdstuk 8 gaat over de DFT, hoofdstuk 12 over de FFT. Aanrader!
Korte uitleg: In het tijdsdomein kan je voor of na de reeks samples nullen toevoegen zoveel je wil, want die nullen zijn in het frequentiedomein ook gewoon nul! Maw ze stellen geen frequentie voor. (Nouja, nul)

BTW: vergeet niet dat de FFT een extra sample toevoegd, en dat je de waarden nadien nog moet normaliseren

Voor mijn gevoel moet je niet aanvullen met nullen maar resampelen... eens kijken, er zijn ook java simulatoren op internet te vinden.

http://www.falstad.com/fourier/

Hiermee kun je zelf spelen met de golfvorm en het effect op de fourier analyse bekijken

@joop Wat Wartos zegt over de padding klopt wel. Je kunt gewoon aanvullen met nul, dat heeft geen invloed op de nauwkeurigheid van de uitkomst. De makkelijkste oplossing is dus aanvullen of inkorten tot een macht van 2.
Resamplen geeft meer verlies in nauwkeurigheid...

Ik heb even zitten spelen met dat java applet hierboven maar de spectrale output (FFT) van een sinus met een vlak stukje erachter is heel wat anders dan de FFT van een sinus zonder een vlak stuk er achter.

Je zou kunnen kijken of je de volgende C# code in Excel kan droppen met VB achtige koppeling ofzo;

http://code.google.com/p/aforge/source/browse/trunk/Sources/Math/Fouri…

Helaas ben ik niet heel bekend met scripting in Excel, maar de code laat in ieder geval een voorbeeld zien hoe je snel een DFT berekening op kan zetten.

Er komt een Complex in (object met Im en Re waarde) en direction. Direction is gewoon of je naar frequentiedomein wilt (forward) of naar tijddomein (backward)

[Bericht gewijzigd door hans1990 op vrijdag 16 juli 2010 00:21:34 (52%)]

@Joop heb je er daar ook voor gezorgd dat de voledig vullende sinus dezelfde golflengte heeft als de sinus met een 0-padding?

FFT is een gemiddelden algoritme en 0-en hebben daar geen invloed op.
Enige wat je kunt krijgen is dat je door het toevoegen van de 0-en een resultaat krijgt die bestaat uit meerdere waarden..
Stel je had 32 samples en in je resultaat krijg je op [0] een result van 1 en op [1] een result van 0.5 en de rest is 0.
Nu vul je e 32 samples aan tot 128 samples (eerste volgende macht van 2)
Dan kan het best zo zijn dat je een result krijgt van:
[0] = 1
[1] = 0.9
[2] = 0.7
[3] = 0.5

immers is de resolutie van je resultaat ook met de factor (128/32) omhoog gegaan..
De uitkomst is hetzelfde als je het resultaat dus weer zou middelen naar de factor.

Op 16 juli 2010 09:56:42 schreef BernardV:
@Joop heb je er daar ook voor gezorgd dat de voledig vullende sinus dezelfde golflengte heeft als de sinus met een 0-padding?

Je doet toch een FFT over de hele periode, dus een sinus met de 0 padding er bij?

Bijvoorbeeld een sinus van 1 ms periodetijd met b.v. 0,5ms stilte er achteraan. Totale periodetijd 1,5ms. Over die cycle die je dan een FFT.
Als je dat dan vergelijkt met de een sinus van 1,5ms oftwel een schone sinustoon van 666 Hz dan zit er zowel auditief als qua FFT spectrum analyse een gigantisch verschil in.

Hier gaan we scheef, tenminste jij doet iets anders dan wat ik bedoel.

Stel je hebt een sinus van 1ms (1000Hz) en je bekijkt de analyse...
Dan pak je dezelfde sinus van 1ms en zet je er 0.5ms space achter, dan krijg je dus een opvulling.
Het is logisch dat als je een 1ms sinus die je aanvult tot 1.5ms met 0 een ander spectrum geeft dan een sinus van 1.5ms, immers verander je dan de golflengte dat doe je niet als je dezelfde golflengte gebruikt, maar alleen aanvult..

Door in excel bv 32 samples aan te vullen met 96 lege samples verander je de golflengte niet.. wat jij nu doet is de 32 samples extrapoleren over 128 samples en dan vergelijken.. dan kom je inderdaad tot de conclusie dat de analyse compleet anders is.

0 padding in je timedomain kan geen kwaad voor het resultaat, enige is dus dat je resultaatresolutie ook veranderd.

Laat me de vraag anders formuleren.
Stel je hebt een staaf diagram met een maandelijkse meting over 2 jaar. Dit geeft me de 24 meetpunten.
Kan ik nu met FFT één of meedere ritmes terugvinden in dit staafdiagram.

Met andere woorden ik wil weten welke sinussen ik moet optellen om terug tot het oorspronklijk staafdiagram te komen.

Indien ik nu voor en achter in de grafiek "nullen" toevoeg dan verandert mijn periode van de sinus toch. Hiermee zou ik kunnen leven want ik ben alleen geinteresseerd in de verhouding van de hogere harmonische ten opzichte van de grondtoon.

Maar door het toevoegen van de nullen verandert mijn signaal (grafiek) toch ook. Gaat de FFT er dan niet voor zorgen dat als ik al de hogere harmonische terug optel ik ook het vlakke stuk (het aantal toegevoegde nullen) in het begin en op het einde terug krijg?
De FFT in excel gaat er immers van uit dat het signaal periodiek is na 32 punten in plaats van na 24 punten. (32 is de dichts bijzijnde macht van twee)

Ja, als jij 0-en toevoegd en je krijgt bijvoorbeeld je magnitude en phase en je rekent deze terug met een inv. FFT dan heb je je 0-en ook terug.
De vraag is alleen: "Is dat erg?" Want neem aan dat geen 1 meetpunt van je een 0 is, dus zou je die ook gewoon weer kunnen verwijderen.

//EDIT:
Heb een jaartje geleden ofzo eens een FFT implementatie gemaakt in flash om zo een equalizer te maken.
http://blog.debit.nl/eq_mp3/
De source van de FFT: http://blog.debit.nl/eq_mp3/fft.c (misschien heb je er iets aan)

Ik heb gisteren volgende test gedaan in Excel.
Ik heb de functie y = sin x + sin 3x geprogrameerd.

In de eerste kolom heb ik 36 hoeken gezet gaande van 0 , 10 , 20 tot 350 graden
In de tweede kolom heb ik voor iedere hoek (sinx + sin 3x) uitgerekend.

Dan heb ik hiervan de eerste 32 punten geselecteerd en hierop de FFT toegepast.
Ik verwachte de grondgolf en de derde harmonische terug te vinden.
Ik kreeg echter een compleet spectrum met talrijke hogere harmonisen.

Als ik in de eerste kolom nu 32 hoeken zet, gaande van 0 - 11.25 - 22.5 - 33.75 - ... - 348.75
en ik reken terug (sin x + sin 3x) uit en neem hiervan de FFT, dan krijg ik mooi mijn grondtoon en mijn derde harmonische.
(er was ook nog een 29 en een 32 harmonische, maar dit laat ik even achterwege owv nyquist aantal sampels)

Het toevoegen van nullen ga ik straks ook even proberen.

Op 16 juli 2010 14:27:32 schreef pamwikkeling:
Ik heb gisteren volgende test gedaan in Excel.
Ik heb de functie y = sin x + sin 3x geprogrameerd.

In de eerste kolom heb ik 36 hoeken gezet gaande van 0 , 10 , 20 tot 350 graden
In de tweede kolom heb ik voor iedere hoek (sinx + sin 3x) uitgerekend.

Dan heb ik hiervan de eerste 32 punten geselecteerd en hierop de FFT toegepast.
Ik verwachte de grondgolf en de derde harmonische terug te vinden.
Ik kreeg echter een compleet spectrum met talrijke hogere harmonisen.

Dat was te verwachten - door waardes gewoon weg te snijden heb je een discontinuiteit (vervorming) gecreeerd.

Het toevoegen van nullen ga ik straks ook even proberen.

Door extra samples te verzinnen creeer je ook een vervorming. Ook al zijn ze "0".

Door extra samples te verzinnen creeer je ook een vervorming. Ook al zijn ze "0".

Sorry dat ik het moet zeggen joopv, maar je hebt echt ongelijk en als je er niks van kent moet je de mensen niet verwarren met geblaat alsof je er wel iets van kent. Om fourier transformaties te echt te snappen heb je toch behoorlijk wat wiskunde kennis nodig en het lijkt me dat je die mist.

Ik raad je echt aan om het boek dat ik eerder aanhaalde eens te studeren en dan ga je hopelijk begrijpen waarom je jezelf hier zo hopeloos belachelijk maakt. Met "je gevoel" zonder de theoretische basis ga je fourier, laplace en Z- transformaties niet begrijpen vrees ik.

Omdat ik stiekem al weet dat je dat boek toch niet gaat lezen, heb ik in Excel vlug even wat grafiekjes zitten maken om jou en de TS te overtuigen. Excel-bestand

Ik heb een sinus gemaakt van 3Hz en een van 10 Hz en die opgeteld. Telkens een fourier analyse gemaakt. Dit heb ik 2 maal gedaan: 1 keer met 500 samples + 12 nullen, 1 keer met 512 samples.
Het resultaat is hetzelfde. Er wordt geen vervorming gecreëerd, bij beide kan je duidelijk de grondtonen op 3Hz en 10Hz onderscheiden. Je kan gaan klagen dat de spectra niet 100% overeenkomen, maar dat is de schuld van Excel. (Excel maakt afrondingsfouten)

Aan de TS:
Als je geen moeite wil doen om de theorie achter fourier te leren snappen (niks mis mee hoor, ik zou het ook niet geleerd hebben indien het niet van moeten was) dan volg je gewoon mijn raad op en voeg je achteraan nullen toe. Let wel: voeg de nullen toe in het tijdsdomein.
Nadat je de FFT genomen hebt moet je nog wel even de absolute waarde nemen van je waarden. Slechts de eerste helft van het spectrum dat je dan krijgt heeft dan betekenis voor jou. De tweede helft is het spiegelbeeld van de eerste helft die door de absolute waarde te nemen achter het eerste deel "geplakt" werd. (Het spectrum spiegelt zich namelijk rond de samplefrequentie)

Praktijkvoorbeeld:
Signaal -> 10-bit ADC aan 400ksps -> DSP
In de DSP wordt bv iedere honderdste van een seconde een FFT uitgevoerd. Dan worden de laatste 4000 samples aangevuld met 96 nullen tot de dichtstbijzijnde macht van 2, nl 4096. Daarop wordt dan de FFT uitgevoerd.

Ik hoop dat je hiermee wel geholpen bent, en spiek gerust eens mijn excel voorbeeldje

Dat excel bestand is niet te downloaden. Ik krijg een partypoker advertentie als ik op download click. Bovendien resized die m'n browser, en dan heb ik vervolgens een uitermate slecht humeur.

@rew Heb hem even op een andere plek gezet voor je: http://blog.debit.nl/co/fourier_met_padding.xlsx

Hmm, ik snap het ook niet helemaal denk ik, maar ik dacht altijd dat als je b.v. maar 3000 samples hebt en deze wilt padden tot aan 4096 samples en je gaat padden met nullen en de laatste sample (nr. 2999) is ongelijk aan 0, je een sprong in je signaal introduceert en dus je freq. spectrum veranderd. Wat wel kan is de 3000 samples eerst door b.v. een hanning window te halen en dan te padden.

Wartos, ik heb nog eens zitten denken....

Fourier gaat er van uit dat het signaal buiten de sample-periode repeteert.

Dus als ik een sinus over 2048 samples verdeel (precies 1 periode) en dan een FFT doe, dan hoor ik toch precies die ene frequentie te krijgen?

Als ik dit pad met 2048 nullen en dan weer een FFT doe, dan zitten er toch frequenties in die niet in het origineel zaten? Het wordt nog erger als we met een cosinus beginnen. Dan komen er twee discontinuiteiten in. Die leveren nogal wat hoogfrequente troep op.

Het effect zal natuurlijk beperkt zijn als je van 4000 naar 4096 samples gaat. Maar de TS wil/moet subtiele signalen in 36 samples zien te vinden. Als dat naar FFT gepad moet worden, moeten 64-36 = 28 samples worden toegevoegd. Dat wordt toch wel significant.

Volgens mij moet TS gewoon naar DFT of DCT kijken en de "fast" van FFT laten vallen. Dat boeit niet zo in een niet-realtime niet-veel-data probleem...

Ik geef toe dat fourier op het HBO al weer een hele tijd (25jr) geleden is, en dat in mijn dagelijks werk als netwerkbeheerder ik het niet meer nodig gehad heb sindsdien.

Alhoewel het handig zou kunnen zijn om patronen in netwerkverkeer te kunnen herkennen. Ik ga toch die kennis wat verversen. Om te beginnen krijg ik een lastig te begrijpen cijferbrij uit de excel fourier functie....

Maar het verschil in die spectra die je in je xls file hebt gegraphd (kudo's voor het uitgebreide excel sheet wat je gemaakt hebt) is m.i. niet aan afrondingsfouten toe te kennen, maar aan de padding die je gedaan hebt. Je zult ook zien dat naarmate je meer padding gaat doen, het verschil tussen de 2 spectra met en zonder padding groter gaat worden. Dat kun je toch niet aan afrondingsfouten toekennen.

Daarnaast kan je met een beetje inzicht toch wel inzien dat een serie van aaneensluitende sinussen toch een heel ander spectrum gaat opleveren dan dezelfde serie sinussen die onderling gescheiden zijn door een "stilte". Daar hoef ik geen diepgaande kennis van fourieranalyse voor te hebben. Je zou kunnen stellen dat in het laatste geval je te maken hebt met een carrier die 100% AM gemoduleerd is met een blokgolf.

Ik heb gisteren avond mijn zakrekenmachientje en wikipedia er nog eens bijgehaald.
Het eerste (groot ???) probleem is dat fourrier gaat over continue functies, terwijl bij gesampelde waarde je de discrete fourrier analyse moet hebben.
Het tweede probleem is dat als je meer samples neemt, je een betere benadering krijgt. Als je de fourrier neemt van een continue wiskundige functie en je sampelt diezelfde functie met aan groot aantal samples zal het spectrum verschillen, hoe minder samples, hoe groter het verschil. (wat te verwachten was)
Tot slot heb ik me ledig gehouden met het berekenen van een DFT (discrete fourrier transform) van een test functie y = cos x + cox 2x.
Ik heb deze genomen omdat dat gemakkelijker te berekenen was met mijn 6 samples om de 60 graden.

Na veel en veel gecosinus en het rondlopen over de goniometrische cirkel en nadat ik Euler zijn formule nog eens boven gehaald heb, bleek de uitkomst te kloppen. En inderdaad, enkel het eerste deel van het spectrum heeft zin, terwijl het tweede deel gewoon het spiegelbeeld is.

Bon, in de komende dagen wil ik wel eens proberen in excel zelf mijn discrete fourrier te programmeren, maar ik had stiekem gehoopt dat een van jullie dit reeds voor mij gedaan zou hebben.

groetjes alvast en bedankt voor het meedenken.

@ Lexy:
Je hebt uiteraard gelijk, wat jij beschrijft noemt men spectral leakage. Spectral leakage treedt op als er geen geheel aantal periodes passen in het venster waarover we de FFT berekenen. Het FFT algoritme gaat ervan uit dat het signaal zich buiten dit venster zich periodiek verder zet; aan het eind van het venster wordt maw het begin van het venster geplakt. Wanneer het einde van het venster dus niet precies overeenkomt met het einde van een periode van het signaal, is er een abrupte sprong. Dit veroorzaakt de extra frequenties in het spectrum; de energie is uitgelekt van de scherpe piek naar de naburige frequenties. Daarom zal men in de praktijk altijd het eerste en het laatste sample op nul zetten. Wat men ook vaak doet is windowing. Deze techniek gaat de uiteinden van het venster geleidelijk op nul brengen en aldus spectral leakage voorkomen. Uiteraard verdiend dit de voorkeur, maar ik heb geen idee hoe je dit eenvoudig in excel wilt uitvoeren...
Er zijn trouwens vele window technieken, (gauss, hanning, blackmann, hamming of als je echt los wilt gaan: kaiser) maar "When in doubt, use Hamming".
Uiteraard kun je gaan berekenen welk window jou best uitkomt als je weet welke verzwakking, frequenties, etc je precies nodig hebt, en dat is niet eens zo moeilijk, maar hamming is vaak voldoende.
Maar nu kom je toch in een ander vakgebied dan wat de TS oorspronkelijk vroeg

@rew

Dus als ik een sinus over 2048 samples verdeel (precies 1 periode) en dan een FFT doe, dan hoor ik toch precies die ene frequentie te krijgen?

Dan zul je op de grafiek indd die ene ferquentie kunnen aflezen, maar let op: de FFT schuift je spectrum met 1 op! (maar dit had ik al aangehaald)

Als ik dit pad met 2048 nullen en dan weer een FFT doe, dan zitten er toch frequenties in die niet in het origineel zaten?

Zie mijn antwoord van hierboven aan Lexy, maar er is nog een valkuil: je moet normaliseren. Een frequentie van 10Hz zal nu op punt 21 liggen. Dit vanwege je verdubbeling in resolutie. Je moet dus effectief door 2 gaan delen (en -1 doen).

Het wordt nog erger als we met een cosinus beginnen. Dan komen er twee discontinuiteiten in. Die leveren nogal wat hoogfrequente troep op.

Dacht het niet, de FFT werkt voor iedere periodieke signaal vorm... Maar ik vermoed dat je geen rekening hield met (daar is het opnieuw) spectral leakage. Probeer eens te padden met 1-en bij je cosinus

Volgens mij moet TS gewoon naar DFT of DCT kijken en de "fast" van FFT laten vallen. Dat boeit niet zo in een niet-realtime niet-veel-data probleem...

Je hebt volledig gelijk, maar de TS wil Excel gebruiken, en dan heb je geen keus denk ik...

@joopv

Daarnaast kan je met een beetje inzicht toch wel inzien dat een serie van aaneensluitende sinussen toch een heel ander spectrum gaat opleveren dan dezelfde serie sinussen die onderling gescheiden zijn door een "stilte". Daar hoef ik geen diepgaande kennis van fourieranalyse voor te hebben. Je zou kunnen stellen dat in het laatste geval je te maken hebt met een carrier die 100% AM gemoduleerd is met een blokgolf.

Zucht...
Je bekijkt het verkeerd, je moet denken in windows, in gehele periodes van een periodiek signaal.
Met de padding verander je niks aan het signaal zelf, maar je moet weten wat je doet. Indien je je opnieuw gaat verdiepen in de materie zal je het vanzelf wel begrijpen

_{Hmm deze post is opnieuw iets langer geworden dan ik wou en ik vrees dat de discussie iets te ver voert voor de TS...}

oeps, oeps, het is inderdaad ingewikkeld aan het worden.
Maar goed, heb me nog eens verdiept in excel en de originele meetwaarden aangevuld met nullen voor het signaal, met nullen achter het signaal, met nullen symmetrisch links en rechts van het signaal.... allemaal boter aan de galg zoals ze hier zeggen.
Excel wil en zal een macht van 2 punten hebben, anders loopt het fout, althans bij mij toch. (kan natuurlijk ook met de TS te maken hebben )

Heb dan van misserie maar MATLAB geinstalleerd op mijn pcke.
en ja hoor, die werkt onafhankelijk van het aantal meetpunten.
Netjes opnieuw de testfunctie y = sin (x) + cos (3x) berekend in excel en dan de gegevens gecopieerd naar Matlab.
Met 12 punten, met 16 punten het werkt en geeft het juiste resultaat.
Dezelfde proef gedaan voor Y = sin(x) + cos (x)
en voor y = sin (x) + cos(x) + 2sin (3x)
allemaal met juiste resultaten.

Dus ik ga proberen verder te werken met Matlab.

Bedankt in ieder geval voor al de steun en toeverlaat.

Goeie keuze, matlab. Nu ga je ergens geraken.

Btw:

abs(ifft(fft(ones(3,1), 8)))

voer dit eens in op de commandline, dan zie je hoe matlab het uitbreiden van een reeks samples oplost

Wastos, als jij zegt dat ik de cosinus met 1-en meot gaan padden, dan zit je naar het resultaat toe te werken. Ja, dan heb je de meest-gunstige padding gekozen.

Als je een sinus met 0-en pad, dan is de afgeleide discontinue. Dat geeft minder harmonischen dan wanneer de functie zelf discontinue is, maar ze zijn er toch. En dat is wat je in een kloppende oplossing itt een benadering niet wilt hebben.

Dat de boel verschuift wist ik niet. Maar is in dit verhaal dus niet relevant. Waar het om gaat is dat het spektrum verandert. Vergelijk het met een deling. Als ik 24 door 3 deel, wil ik 8.00000 krijgen en niet 8.001. Als ik een zo perfect mogelijke sinus door een FFT haal, wil ik een spektrum zien wat uitsluitend die ene frequentie laat zien.

P.S. Leestip: http://en.wikipedia.org/wiki/Discrete_cosine_transform