Fourier transformaties...

[Verwijderd]

Eerst een klein verhaaltje:
Toen ze laatst op de radio iemand belden lieten ze gewoon de DTMF tonen horen. Ik dacht, iemand met een beetje training kan die toch gewoon herkennen? en toen kwam ik op het idee er een programmaatje voor te schrijven.

Wat ik wil doen is dus:
- De sinus van de soundblaster ontvangen
- Er een Fourier transformatie op los laten met het Fast Fourier Transform algoritme.
- Dan kijken welke frequenties de top vormen en dan dus vergelijken met frequenties van de nummers van de telefoon (frequenties ken ik)

Mijn probleempjes:

Op zich geen probleempjes, zolang ik de source van iemand anders gebruik om die fft te doen...
En dat wil ik dus niet, ik wil die FFT zelf bouwen.
Op zich is ie niet zo moeilijk, ik heb diverse sources en kan hem zo nabouwen, maar wat ik wil is weten hoe hij psies werkt, wat de achtergrond ervan is, en hem dan uit mezelf bouwen. Probleempje is dat die sources geen goeie documentatie hebben, en dat je als je op google ofzo zoekt meteen een volledig wiskundige uitleg krijgt met integralen etc.

Mijn vraag aan jullie:

Kan iemand mij uitleggen (aan de hand van GOED GEDOCUMENTEERDE voorbeelden) hoe die FFT psies werkt?

Alvast bedankt...

P.S.: Het liefst in Pascal...
Mag ook in andere taal, ik beheers ze vrijwel allemaal, maar pascal (of delphi/kylix) blijft mijn favoriet.
(Je mag me ook die klote pointers van C++ uitleggen, dan wordt dat men favoriet (laatste poging ze te begrijpen was 2 jaar geleden dus moet toch maar weer es kijken))

[star-saber]

dat zal niet mee vallen
FFT krijg je op de hts

[joker1977]

Op maandag 01 juli 2002 23:43 schreef RRazoRR het volgende:
op google ofzo zoekt meteen een volledig wiskundige uitleg krijgt met integralen etc.

Mijn vraag aan jullie:

Kan iemand mij uitleggen (aan de hand van GOED GEDOCUMENTEERDE voorbeelden) hoe die FFT psies werkt?

Tja, gezien het feit dat een (Fast) Fourier transformatie álles met integralen heeft te maken zal een uitleg zonder integralen niet zo veel nut hebben.

Simpel gesproken is een Fourier-transformatie een wiskundig proces waar men iedere functie (die zichzelf herhaalt, dus periodiek is) in termen van sinus en cosinus schrijft (met verschillende argumenten in de (co)sinus ---> de diverse frequenties).

De FFT is dan een 'fast' variant van dit proces, die door zijn karakter per uitstek geschikt is om door een computer te worden uitgerekend.

Ik vrees dat, gezien je leeftijd en dus je wiskundige achtergrond, een uitgebreidere uitleg helaas vooralsnog boven je wiskundig begrip zou gaan.

Je kunt even gaan kijken naar 'DFT' (discrete fourier transform) waar je veel met sommaties (de 'sigma') werkt ipv. de integralen. Dat is misschien makkelijker te bevatten.

--> http://astronomy.swin.edu.au/~pbourke/analysis/dft/ met daaronder nog wat sources van DFT en ook FFT

[Soultaker]

Ik vond dit wel een aardige tutorial:
http://www.relisoft.com/Science/Physics/sound.html

[MSalters]

Op maandag 01 juli 2002 23:54 schreef joker1977 het volgende:

Simpel gesproken is een Fourier-transformatie een wiskundig proces waar men iedere functie (die zichzelf herhaalt, dus periodiek is) in termen van sinus en cosinus schrijft (met verschillende argumenten in de (co)sinus ---> de diverse frequenties).

De FFT is dan een 'fast' variant van dit proces, die door zijn karakter per uitstek geschikt is om door een computer te worden uitgerekend.

Je kunt even gaan kijken naar 'DFT' (discrete fourier transform) waar je veel met sommaties (de 'sigma') werkt ipv. de integralen. Dat is misschien makkelijker te bevatten.

Je zit mis met de positie van de FFT. De FFT is net zoals alle (digitale) computer fourier transformaties een DFT; continue fourier transformaties ziijn analoog cq gebruiken integralen.
Het idee van de FFT is dat je bepaalde gemeenschappelijke termen in de sommatie maar een keer uitrekent, maar hoe dat ook al weer precies ging? 't Is alweer 4 jaar geleden dat ik voor het laatst gekeken heb. In elk geval is de "gewone DFT" een ongeoptimaliseerd algoritme wat dezelfde uitkomst geeft, maar beter te begrijpen is.

[Verwijderd]

Een DFT is O(N^2), de FFT doet het zelfde in O(N log N). Kijk eens op http://www.dspguide.com voor een redelijke uitleg (PDF bestanden)

[Verwijderd]

Nou zoals al eerder gezegd: FFT is een geoptimaliseerde variant op DFT.

Wat je eigenlijk doet is sinussen met oplopende frequentie over het geluidsfragment leggen en kijken welke sinus (met die ene frequentie) het beste overeenkomt met het geluidsfragment. Je zou dit natuurlijk kunnen doen door gewoon het verschil van de sinus en het geluidsfragment op elk punt uit te rekenen en bij elkaar op te tellen (en het zou misschien nog wel werken ook), maar met fourier-transformatie vermenigvuldigen ze de twee functies (de sinus en het geluidsfragment met elkaar). Als alles netjes 'in de pas' loopt komen de negatieve delen van de sinus op dezelfde plaats als de negatieve delen van het geluidsfragment en dan krijg je (min maal min = plus) iets positiefs. Door nu te alles te sommeren (Riemann som) krijg je de oppervlakte onder de grafiek en dit is dus een maat voor hoe sterk een frequentie in het geluidsfragment aanwezig is. Integreren is niks anders dan oneindig veel oneindig kleine stukjes sommeren. Aangezien dit numeriek niet lukt, ga je sommeren. Dat is de D(iscreet) in DFT. Dit is makkelijk te implementeren. FFT ben ik zelf ook wel eens mee bezig geweest, maar het is me nog niet gelukt te achterhalen hoe ze alle dingen verwisselen om het probleem sneller op te lossen.

[Martin Sturm]

FFT is een variant van DFT waarbij de DFT steeds wordt opgesplits in twee delen net zolang tot er slechts 2 termen overblijven. Dit is voor een computer veel sneller te verwerken dan een 'normale' DFT. Het is alleen ff niet zo dat je het in een klein verhaaltje uitlegt, want ik heb er een half jaar les in gehad, en nog met moeite m'n tentamen gehaald

(Bij ons is het stof van het 4e jaar Elektrotechniek)

[Verwijderd]

Gewoon die tonen opemen en weer afspelen voor de hoorn van de telefoon

[Verwijderd]

Tis eigenlijk niet zo moeilijk om te realiseren, Texas Instruments heeft een aantal chipjes om dat spul te genereren en lezen. In hun databoeken daarover staat een hoop uitleg over de combinaties van sinusjes, frequenties, toleranties van storing, routines om ze te herkennen (dsp, x86 en 68000 geloof ik) etc. Die databoeken kan je vrij opvragen per post, of als pdf (on request heb ik ze nog --> mail me)
Deze is trouwens ook niet verkeerd: http://www.isip.msstate.edu/conferences/dsp95/paper_dtmf.pdf