Sneller algoritme voor Fourier-transformaties ontwikkeld

Onderzoekers van het Massachusetts Institute of Technology hebben een nieuw algoritme ontwikkeld om Fourier-transformaties toe te passen op digitale data. Daarmee zou data beter en sneller gecomprimeerd kunnen worden.

De onderzoekers presenteerden hun algoritme tijdens het SODA, ofwel het Symposium on Discrete Algorithms, dat in de afgelopen dagen werd gehouden door de Association for Computing Machinery. De MIT-medewerkers ontwikkelden een zogeheten fast Fourier transform-algoritme dat een snelheidswinst van een factor tien ten opzichte van de huidige fft-algoritmes mogelijk maakt. Vooral de compressie van beeldmateriaal zou van het nieuwe algoritme kunnen profiteren.

Fourier-transformaties worden gebruikt bij het omzetten van analoge signalen in digitale data en worden onder meer toegepast bij signaalverwerking, maar spelen ook een rol bij de compressie van beelden. Een complex signaal wordt met fft gereduceerd tot een aantal eenvoudig digitaal te representeren componenten. Daarvoor wordt een analoog sample opgedeeld in kleine stukjes, waarna de stukjes worden geanalyseerd en geconverteerd naar een digitaal signaal.

De MIT-onderzoekers ontwikkelden allereerst een beter filter om het analoge signaal zonder signaalverlies in deeltjes op te splitsen. Vervolgens werden de resterende frequenties geanalyseerd en gewogen, waarbij alleen de frequenties met een grote bijdrage aan het signaal behouden bleven. Het algoritme analyseert de frequenties hiertoe niet alleen in signaalsterkte, maar ook in tijd, om fluctuaties te ondervangen. Dit wegen van de frequenties en het negeren van onbelangrijke of informatiearme frequenties, maakt de fft van het MIT-team geschikt voor compressie.

Het bouwen van een complex signaal uit eenvoudige componenten

Reacties (81)

[.oisyn]

Fourier-transformaties worden gebruikt om analoge signalen om te zetten in digitale data en worden onder meer toegepast bij signaalverwerking

Beetje rare opmerking. Waar Fourier-transformaties voor worden gebruikt is het omzetten van tijddomein (zoals samples in een waveform) naar frequentiedomein en weer terug. Niet om analoge data naar digitale data te converteren oid.

[BeerenburgCola]

Hier wilde ik net ook op reageren. Het hele verhaal over FT en FFT dat gebruik wordt om te digitalizeren klopt niet.

Ook deze zin:

Een complex signaal wordt met fft gereduceerd tot een aantal eenvoudig digitaal te representeren componenten. Daarvoor wordt een analoog sample opgedeeld in kleine stukjes, waarna de stukjes worden geanalyseerd en geconverteerd naar een digitaal signaal.

Dit slaat ook nergens op. Een "analoog" sample kan niet door FFT opgedeeld worden in "kleine" stukjes. Ook is een "analoog sample" tegenstrijdig (hoewel theoretisch niet onmogelijk).

Bij A/D (Analoog Digitaal) conversie kan namelijk per definite geen "FFT" gebruikt worden want een FFT kan alleen toegepast worden op een digitaal signaal.
Het "Fast" gedeelte van de FFT (Fast Fourier Transformaite) kan alleen op een discreet (dus gesampled, dus al gedigitaliseerd) signaal toegepast worden.

Het lijkt er op dat dit gedeelte er bij verzonnen is, want in het engelse artikel word A/D conversie helemaal niet genoemd.

Quote het artikel:

Like the FFT, the new algorithm works on digital signals.

Het nieuwe algoritme wordt gebruikt bij digitale signalen.

Edit: en meer:

De MIT-onderzoekers ontwikkelden allereerst een beter filter om het analoge signaal zonder signaalverlies in deeltjes op te splitsen.

Nee, ze filteren het al digitale signaal. Er komt geen analoog signaal aan te pas.
Het lijkt erop dat ze een reeks van digitale smallband filters toepassen om zo de relevante frequenties te vinden.

The first is to divide a signal into narrower slices of bandwidth,

Er wordt hier niet expliciet gesproken over analoge signalen.

[Reactie gewijzigd door BeerenburgCola op 23 juli 2024 09:25]

[GrowMyHair]

Ik neem aan dat waar ze analoog signaal schrijven, ze het discrete-tijd signaal bedoelen. Waar ze digitaal signaal schrijven bedoelen ze het getransformeerde signaal.

Met deze 'kleine' substitutie is het verhaal een stuk minder verwarrend.


@hieronder: Ik zeg niet dat het correct verwoord is, maar ik ga ervan uit dat ze het op deze manier bedoeld hebben. Voor mensen die niet zo thuis zijn in signaalanalyse technieken als jij zijn bovenstaande begrippen een stuk losser gedefinieerd.

[Reactie gewijzigd door GrowMyHair op 23 juli 2024 09:25]

[BeerenburgCola]

Er word in het (engelse) artikel maar één keer het woord "analog" gebruikt:

A digital signal is just a series of numbers — discrete samples of an analog signal,

Je kunt "analoog signaal" niet vervangen met "discrete-tijd" want analoog is juist tegenstrijdig met "discreet". Analoog impliceert (over het algemeen) een continue signaal en discreet is het tegengestelde van continue. (Hoewel je in theorie weer wel een discreet analoog signaal kunt hebben, maar dan ben je wel heel raar bezig)

En een digitaal signaal hoeft helemaal niet "getransformeerd" zijn.

Edit: @hierboven: Als je inderdaad de definitie(s) van "analoog" en "analoge" loslaat en leest als "oorspronkelijk/origineel" klopt de tekst iets meer ja.

[Reactie gewijzigd door BeerenburgCola op 23 juli 2024 09:25]

[Terracotta]

De opmerking is wel juist. Het is een veelgebruikte techniek, in plaats van samples in het tijdsdomein te moeten opslagen, slaat men componenten van de fourier getransformeerde op. M.a.w. men slaagt het frequentiedomein op en niet het tijdsdomein. Wat heeft de omzetting naar het frequentiedomein voor nut als het enige dat je doet het terug omzetten naar het tijdsdomein bevat? Het frequentiedomein bevat evenveel informatie en is eenvoudiger digitaal voor te stellen alsmede eenvoudiger te analyser dan een gewone tijdsdomein sampling van het signaal.

[zerokill]

Niet helemaal waar. Analoge signalen omzetten naar digitale signalen zal altijd gebeuren met een AD convertor. Daar heeft fourier transformaties echt helemaal niks mee te maken.

zoals .oisyn zegt worden fourier transformaties gebruikt voor het omzetten van het tijdsdomein naar het frequentiedomein en vice versa.

Het frequentiedomein bevat inderdaad exact dezelfde data als het tijdsdomein maar in het frequentiedomein zijn bepaalde berekeningen makkelijker uit te voeren. Denk aan signaal bewerking.

Wat ik in ieder geval probeer te zeggen is: Analoog of digitaal staat hier helemaal los van. FFT is sowieso een type discreet fourier transformatie waar woord discreet betekent dat we het hebben over een signaal met vaste niveaus (oa gedigitaliseerde signalen) in tegenstelling tot continu (analoge signalen).

[Reactie gewijzigd door zerokill op 23 juli 2024 09:25]

[pe1dnn]

Ik heb altijd begrepen dat je die Fourier-transformaties uitvoert om een digitaal signaal veel compacter op te slaan. In het frequentie domein kun je de golfvorm veel gemakkelijker beschrijven dan in het tijd domein. Bijvoorbeeld een 1 kHz sinus is als frequentie gewoon een sinus met een periode tijd van 1 ms. Maar als ik op 44 kHz sample en hier alle samples zou moeten opnoemen dan leest echt niemand dit stuk meer, veel te veel.

Om het even heel erg concreet te maken: je doet die omzetting als je van WAV (gesampled PCM signaal) naar .mp3 gaat (vele malen compacter). Dus eigenlijk gebruikt iedereen dit inmiddels vrijwel dagelijks.

Hier een heel oud artikel in de Guardian: http://www.guardian.co.uk...apr/04/internetnews.maths

Nog aan aanvulling: Die 1 kHz sinus die ik beschreef is ook veel nauwkeuriger een sinus dan die 44 kHz samples. Als je de sample rate wil veranderen is dat heel handig: sample->frequentie domein-->andere sample rate. Het is "schaalbaar" zeg maar. Ook het loslaten van filters is veel gemakkelijker, dus de digitale equalizer die tegenwoordig overal in zit heeft die omzetting nodig. Kortom erg technisch en wiskundig maar van onschatbare waarde.

[Reactie gewijzigd door pe1dnn op 23 juli 2024 09:25]

[Zoijar]

Ik heb altijd begrepen dat je die Fourier-transformaties uitvoert om een digitaal signaal veel compacter op te slaan. In het frequentie domein kun je de golfvorm veel gemakkelijker beschrijven dan in het tijd domein.

Het is eigenlijk niets meer dan een verandering van (lineaire functie) basis. In plaats van een discreet signaal/functie te beschrijven als combinatie van impuls-functies (i.e. 1,0,0,0,... 0,1,0,0,0..., 0,0,1,0,0,0...) beschrijf je het als combinatie van sinusoiden. Dat is wat het is, maar dat geeft niet zo duidelijk aan wat je ermee kunt doen. In het algemeen is de representatie in die andere basis niet kleiner. Wat wel zo is, is dat de meeste energie (informatie) van het signaal in de eerste paar basis functies wordt gevangen. Je kan dus een groot deel weggooien zonder al te veel informatie te verliezen. fft is overigens ook een special case van (discrete) wavelet transformaties. Het lijkt een heel magisch en ingewikkeld iets, maar eigenlijk is het dus vrij simpel, niet heel anders dan een vector roteren en projecteren.

Die eigenschap van veel variantie in de eerste componenten is handig, maar waar een fft echt heel nuttig is, is dat convolutie gedaan kan worden als puntsgewijs vermenigvuldigen. Bijvoorbeeld het vermenigvuldigen van twee grote getallen is convolutie en kost O(N^2) tijd. Echter in het fourier domein kan je het doen in O(n). Een fft kost je O(n log n) ( kleiner dan O(n^2)) en dus kan je met behulp van een fft vermenigvuldigen in O(n log n) ipv O(N^2). Dat is een gigantische speedup.

[Terracotta]

Het gaat om de opslag, niet om de omzetting (tuurlijk wordt de omzetting naar digitaal met een AD convertor gedaan, ik sprak de eerste keer dan ook al over SAMPLES (as in: discrete momentopnames die je kan opslaan als je wil). Je kan dan beter je fourier componenten opslagen, dan de samples, je gaat veel minder geheugen innemen bij de (digitale) opslag (zie jpeg als je het niet volgt). De stelling dat fourier transformatie nuttig is voor digitale opslag blijft dus wel geldig, dat het nodig is werd nergens beweerd.

[.oisyn]

Your missing the point. Of je sensoren nou tijds- of frequentiesamples opvangen, zij doen de omzetting naar "digitale data". Op het moment dat je die digitale data in een andere vorm wilt hebben, dán pas gebruik je een discrete FT. Maar dan ís het dus al digitale data, en je zet het niet om naar digitale data. Natuurlijk heb je ook analoge FT's in hardware (zoals bijv. toegepast in synthesizers), maar die hebben ook een analoge output en vallen compleet buiten de context van dit artikel.

[Reactie gewijzigd door .oisyn op 23 juli 2024 09:25]

[Terracotta]

You're missing the point sir. Het artikel zegt enkel dat FT nuttig is voor digitale opslag, niet dat het nodig is. De FFT's werken trouwens op discrete samples waardoor je inderdaad al een omzetting naar digitaal gemaakt hebt. Maar voor de opslag van elk efficient algoritme doet men FFT's of iets gelijkaardig. Voor de opslag van je foto in je cell-phone kan deze snelheidswinst dus zeer handig zijn.

[Sissors]

Als je het artikel had gelezen wist je dat er letterlijk stond dat een FFT wordt gebruikt om een analoog signaal om te zetten in digitale data. Dat is op gewoon geen enkele manier goed te praten, want het heeft er helemaal niks mee te maken.

[Terracotta]

"Fourier-transformaties worden gebruikt om analoge signalen om te zetten in digitale data en worden onder meer toegepast bij signaalverwerking, maar spelen ook een rol bij de compressie van beelden."

Er staat nergens letterlijk FFT, enkel FT. Je discretisatie kan je theoretisch perfect na een continue FT doen waarna je kan samplen in het frequentie domein, dit is praktisch gezien echter gewoon niet de beste keuze. Wat hier gezegd wordt is dat je analoge tijdsdomein signaal in digitale vorm vaak uit discrete fourier componenten bestaat, die dan gebruikt worden voor de analyse of voor opslag. Natuurlijk is de pure AD conversie de discretisatie (in tijd of frequentie domein, zelf te kiezen). Breder genomen is de FT echter een belangrijke stap in digitale verwerking van analoge signalen.

[.oisyn]

Er staat nergens letterlijk FFT

Het onderwerp van het artikel is het algoritme voor een snellere DFT. Waarom zouden ze er dan ineens een ander type FT bij betrekken?

Je discretisatie kan je theoretisch perfect na een continue FT doen waarna je kan samplen in het frequentie domein

Klopt, maar dan zet de continue FT alsnog geen analoog signaal om in digitale data.

[MSalters]

FFT is een specifiek (computer)algoritme om DFT's uit te voeren. DFT staat namelijk voor Discrete Fourier Transformatie, dat wil zeggen een FT op een digitaal signaal. FFT is een algoritme om de interim resultaten van een DFT zo te ordenen dat je geen dubbel werk uitvoert, wat een naieve implementatie van DFT wel doet.

[.oisyn]

You're missing the point sir.

Hoe kan ik het punt dat ik zelf maakte nou missen? Wat jij zegt trek ik helemaal niet in twijfel. Ik heb het enkel over het door mij gequotete stuk in het artikel, wat gewoon niet klopt. Een FT doet nooit een conversie van analoog naar digitaal. Leuk dat je een FT kan gebruiken om de data (die al in digitale vorm leeft) om te zetten naar iets wat bruikbaarder is, maar daar heb ik het helemaal niet over.

[Reactie gewijzigd door .oisyn op 23 juli 2024 09:25]

[Terracotta]

Het punt van de door u gequote zin mist ge wel, die is dat een analoog signaal in digitale vorm vaak door discrete fourier componenten wordt benaderd/voorgesteld. De pure AD-conversie is inderdaad de discretisatiestap, maar als men een analoog signaal digitaal opslaagt/bewerkt is dit vaak met de fourier componenten, wat de auteur van het artikel probeert uit te leggen.

[Niet Henk]

Niet zo heel raar. Als je een analoog audio-signaal vast wil leggen bijvoorbeeld, kan je dit doen door Fourier-transformaties voor de geluidstrilling per interval op te slaan. De meeste analoge signalen zijn trillingen, die je met een Fourier-transformatie makkelijk digitaal kan opslaan.

Natuurlijk is het niet heel exact verwoord, maar wel makkelijk begrijpbaar.

OT: Fourier transformaties gaan al vrij snel en laag CPU-intensief. Het is zeker als je dit grootschalig kan toepassen wel handig, maar ik betwijfel of we er snel iets van zullen merken. Ik ben wel benieuwd naar de betere compressie, als dit inhoud dat lossless audiobestanden voortaan veel kleiner kunnen worden, is dit een erg mooie ontwikkeling.

[ovigo]

Er staat juist dat ze sneller zijn door onbelangrijke frequenties niet mee te rekenen. Dit betekent dus dat de data die je eruit krijgt per definitie niet lossless
Waar ik zelf ook benieuwd naar ben is of dit nog toepassingen gaat hebben in de algoritmiek van vermenigvuldiging van Floats in processors. Gek genoeg is dit namelijk (met de oude technieken al) sneller om via een FFT te doen. Snellere multiply worden we natuurlijk allemaal blij van als tweakers:)

[Nordlys]

Volgens mij was één van de snelste implementaties voor Fourier-transformaties toch wel FFTW: http://www.fftw.org/. De snelheidswinst is heel erg welkom, want deze libraries worden vaak gebruikt in situaties waar je heel wat van deze berekeningen per seconde uitvoert. Voorbeeldje hiervan is het simuleren van bewegingen van vloeistoffen, waar Jos Stam een algoritme voor heeft ontwikkeld die gebruik maakt van fft's.

[Verwijderd]

Ander voorbeeld is deze implementatie van FFT:
http://graphics.ucsd.edu/...05/jdewall/tessendorf.pdf

In de link van Jos Stam wordt ook naar bovenstaande verwezen.

Ben benieuwd of dit versneld algoritme implementeerbaar is in dit soort toepassingen.

[BeerenburgCola]

Nitpick:
Ik ondek zo 1,2,3 niet een implementatie van het FFT algoritme.
Wel wordt het toegepast (gebruikt).

[BeerenburgCola]

Edit (Vorige verhaal klopte niet):
Je zou het nieuwe algoritme misschien kunnen combineren met ideeën uit FFTW zoals radix optimalisaties.

[Reactie gewijzigd door BeerenburgCola op 23 juli 2024 09:25]

[Emmef]

(1) Sneller algorithme voor Fourier transformatie?
Nee, want deze transform gooit informatie weg, een Fourier transform niet. Het is ook geen vervanging van de (discrete-tijd) Fast Fourier Transform. Deze verliest ook informatie, maar dat komt door kwantisatie en eindige numeriek nauwkeurigheid. Een FFT wordt domweg uitgerekend, zonder analyse (weging -> filtering) van het signaal, zoals in deze methode wordt beschreven.

(2) Handig voor MP3?
Het is helemaal niet gezegd dat de toegepaste "weging" en het behoud van "belangrijke" frequenties hetzelfde werkt als de psycho-akoustische modelering die in MP3's wordt gebruikt. MP3 gebruikt overigens MDCT (Modified Discrete Cosine Transform).

[MBV]

Klik de bron maar eens aan. Zelfs als k dicht bij n komt is het sneller dan FFT, beweren ze.

[GrowMyHair]

De onderzoekers hebben een algoritme bedacht om sneller dan tot nu toe mogelijk een gedeeltelijke DFT uit te rekenen. Ze gaan er van uit dat de uitkomst slechts bestaat uit een beperkt aantal relevante waarden. En als dat zo is, dan kunnen ze die waarden een stuk sneller dan tot nu toe mogelijk, nauwkeurig uitrekenen.
Het is dus geen volledige vervanger van het FFT algoritme, dat heel snel een volledige DFT uitrekent. Vaak is het echter wel zo dat je slechts in een beperkt aantaal waarden geinteresseerd bent en in deze gevallen ben je met het nieuwe algoritme dus een stuk sneller klaar. (Voor veel toepassingen is het FFT algoritme sowieso al heel snel.) In het geval van data compressie via Fourier transformaties ga je er sowieso vanuit dat er maar een beperkt aantal relevante waarden zijn; als dat niet zo is valt er niets te comprimeren.

Voor de wiskundigen, hier staat hun artikel: http://arxiv.org/pdf/1201.2501v1

[Verwijderd]

Enige idee of dit later wordt verwerkt in X-ray Diffraction? Het nemen van een x-ray kan uren/dagen duren voordat het signaal is verwerkt.

[Iska]

Hoe bedoel je? Refereer je naar de medische toepassingen van x-ray of een ander type?

[Verwijderd]

DIt is meer in de zin van het analyseren van materie. In specifiek heb ik het hier over X-ray Crystallography. Neem bijvoorbeeld superconducters, om de crystal structure van deze materie te vinden moet er een x-ray van worden genomen. Lees dit is niet dezelfde x-ray als die je in de ziekenhuis krijgt. Het is wel van dezelfde golflengte. Maar het gaat hier dan om een moleculair level. De X-ray kan uren to dagen duren. En een ton aan data geven, en het versnellen van FT is wel erg handig. Besides, dit geldt niet alleen voor X-ray diffraction, FT wordt gebruikt in IR, MSpec, UV-vis in veel spectrocpische technieken.

[Wh4ck0]

Als FFT hier het grootste struikelblok bij is, dan neem ik aan dat dat dan ook een factor 10 sneller is.

[humbug]

Dat hangt er maar sterk vanaf. Dit algoritme is snel omdat het data weggooit. Of dat zomaar voor deze toepassing geschikt is kan je niet zo 1,2,3 zeggen.

[Verwijderd]

Dit algoritme is snel omdat het data weggooit.

De al-om bekende FFT gooit ook data weg, dus dat dit algoritme data weg-gooit is niet de reden dat het 10x zo snel is.

Dit geld trouwens wel voor elke (F)FT dat je een bepaald deel van de data weg-haalt immers de representatie is totaal anders en je werkt een analoog signaal toe naar een digitaal domein, dat gaat altijd gepaard met verliezen/veranderingen.
Overigens, zolang dat binnen je spec valt is dit geen probleem.

[ILUsion]

Klassieke FFT-algoritmes gooien géén informatie weg, of toch indien je oneindige precisie veronderstelt zoals reeds gezegd. Maar zelfs in double precision, kom je niet snel aan precisieproblemen, vijftien/zestien digits is meer dan wat je normaalgezien nodig hebt.

Het is bovendien compleet foutief dat de FFT handelt over het omzetten van analoge data naar digitale data. Omzetten van analoog naar digitaal is quantisatie en sampling, twee technieken die vaak wel in combinatie met de FFT gebruikt worden, maar niet in de FFT zelf voorkomen.

Quantisatie is het omzetten van een analoge amplitude naar een discrete amplitude. Sampling is het bemonsteren van een signaal, dus een signaal dat in continue tijd leeft, op bepaalde tijdstippen bijhoudt en het op discrete tijdsmomenten bijhoudt. Een signaal dat zowel in amplitude als in tijd discreet is, kan je digitaal noemen.

Wiskundig gezien kan de FFT werken met alle signalen die discreet in de tijd zijn (dus enkel sampling is een vereiste). Niets houdt je tegen om analytisch de FFT in oneindige precisie te berekenen, maar in de meeste praktische gevallen zal een FFT ofwel in eindige precisie ofwel in fixed point uitgerekend worden.

Ik heb dit nieuwe algoritme nog niet volledig bestudeerd, maar de winst is het gevolg van het feit dat dit om een sparse algoritme gaat. Er wordt dus wel degelijk een deel van de informatie verwaarloosd en hoe veel dat is zal uitmaken hoe veel sneller dit is dan de gewone FFT.

[FRidh]

De verliezen komen NIET door de FFT of DFT. Een DFT is slechts een manier om data (tijddomein) te presenteren in een ander domein (frequentiedomein). De data kan tussen de domeinen probleemloos worden uitgewisseld.

De verliezen waar jij over spreekt komen door het quantiseren, het converteren van analoog naar digitaal signaal.

[gvdmaat]

Het staat ook wel een beetje vreemd in de tekst:

"Fourier-transformaties worden gebruikt om analoge signalen om te zetten in digitale data en worden onder meer toegepast bij signaalverwerking, maar spelen ook een rol bij de compressie van beelden. Een complex signaal wordt met fft gereduceerd tot een aantal eenvoudig digitaal te representeren componenten. Daarvoor wordt een analoog sample opgedeeld in kleine stukjes, waarna de stukjes worden geanalyseerd en geconverteerd naar een digitaal signaal"

Dat stukje klopt natuurlijk van geen kant. Zoals je al zegt is de Fourier Transformatie niets anders dan het omzetten van (strikt genomen continue dus analoog) signaal in het tijdsdomein naar het frequentie domein en vice versa. De DFT en de FFT kunnen worden toegepast op gediscretiseerde data dus digitaal en hebben an sich niets te maken met het discretiseren van het signaal zelf.

Blijkbaar hebben ze dus het discretiseren van data versneld en gebruiken ze een ander filter om de discrete data te analyseren

[Peppi78]

Ik ben het niet met je eens dat de FFT informatie weggooit. Als je namelijk een FFT doet, kun je via de inverse FFT weer EXACT je oorspronklijke signaal terugkrijgen.
Oftewel x = IFFT(FFT(x));

(Hierbij ga ik er uiteraard wel vanuit dat er met oneindige precisie wordt gerekend, dus geen kwantisatie van tussenresultaten).

Ik vraag me ook werkelijk af of het hier wel om de FFT gaat. De FFT is namelijk een reken routine waar al zeer veel onderzoek naar is gedaan om de hoeveelheid rekenwerk te minimaliseren. En nu claimen zij het een factor 10 sneller te kunnen, waarbij de snelheids winst data-afhankelijk is? Dat is verdacht...

Als ik het orignele artikel goed begrijp dan is het ook niet exact de FFT, maar een benadering hiervan, waarbij alle irrelevante data weg wordt gegooid.

[thomascsmits]

Het probleem zit hem niet zo zeer in de FFT maar in het feit dat je met een omweg een schatting moet geven voor de fase.

[matzo]

Wet van Ahmdal: 1/((1-P)+P/s). Zelfs als FFT je grootste struikelblok is, zal een factor 10 versnelling nooit het geheel met een factor 10 versnellen. Tenzij je niets anders moet doen dan FFT's uiteraard.

[Molybdenum]

Beetje rare uitleg. Röntgen diffractie is zoals de naam zegt: diffractie van Röntgen straling aan een kristalrooster of andere repeterende structuur op Angstrom/nanometerschaal.
Een diffractogram opnemen komt neer op het meten van de reflecties als functie van de hoek van inval. Het is dus niet het 'nemen van een X-ray'.
Staat helemaal los van het maken van een Röntgen foto. Dat is namelijk een fotografische techniek, waarbij je gebruikt maakt van transmissie/absorptie van Röntgen straling.

Fourier analyse is een standaard techniek dat gebruikt wordt om spectrogrammen te analyseren en kan ook gebruikt worden in Röntgen diffractie. Het maken van een Fourier transformatie van een Röntgen foto voegt niet veel toe.

[shakedown]

Bij röntgenonderzoek wordt geen Fourier transformatie gebruikt. Bij MRI wel.

Het signaal dat door de MRI scanner (RF antennes) uit het lichaam wordt opgevangen is een signaal zoals in het onderste plaatje. Dat signaal wordt door middel van fourier transformatie uit elkaar gepluisd en zo worden de zuivere sinus en co-sinus signalen gevonden. Deze informatie wordt gebruikt om het k-vlak in te vullen en het beeld dat we kennen als MRI plaatje wordt getoond.

(heel summiere uitleg)

Tegenwoordig zijn de MRI computers snel genoeg en kunnen we zonder probleem de signalen ontcijferen.

Fourier transformatie kennen we allemaal. We maken er regelmatig gebruik van. De gewone FM radio maakt hier ook gebruik van. Het signaal dat door de radio-stations wordt opgevangen wordt door je antenne opgevangen, ontcijfert en naar je speakers gestuurd.

[Lunacy]

Ik zie niet in waarom je FT zou nodig hebben in een analoge FM ontvanger hoor?
En "ontcijfert" lijkt me ook niet de juiste term, lijkt wel alsof het signaal geencrypteert door de ether gestuurd zou worden. Het wordt gewoon gedemoduleerd..

[Reactie gewijzigd door Lunacy op 23 juli 2024 09:25]

[achtbaanfreak]

Eehm, nou kijk. Bij MRI wordt, dacht ik, de spin van de waterstof atomen omgedraaid door een sterk magnetisch veld. Als het magnetischveld stopt zal een aantal waterstofatomen (of allemaal?) terugvallen in "begin" spin. Hierbij zal energie vrij komen (deze spin is het laagste energie niveau, anders zullen ze er niet naar toe terugvallen, iets met entropie als ik me niet vergis). Deze energie wordt uitgezonden in de vorm van elektromagnetische straling. Dit is in wezen niks anders dan FM radio golven (of AM of welke vorm van radiogolven dan ook) alleen op een andere frequentie. De antennes van de MRI scanner zullen naast de straling van de waterstof atomen ook een heleboel andere crap opvangen. Dat is nou eenmaal t leven van een electrical engineer. Je hebt overal om je heen bronnen die storing veroorzaken. Denk aan bv gsm straling, radio, maar ook het stopcontact zelf en omdat een MRI met gigantische stromen werkt zal de MRI ook op zichzelf storen. Juist om deze reden is Fourier erg handig omdat je via Fourier de frequenties eruit kan pikken die voor jou interessant zijn en de rest vrij makkelijk kan negeren (het eruit vissen van de voor jou interessante frequenties zou je best wel als, zoals jij het noemt, encrypten kunnen zien). Vroeger leverde fourier nog wel eens problemen op omdat de computingpower niet beschikbaar was. Maar sinds de eerste fft (fast fourier tranformation) algoritmes en de steeds toenemende processorkracht is dit tegenwoordig nauwelijks een probleem meer. Maar des al niet te min is sneller natuurlijk altijd beter en goedkoper (minder zware hardware nodig).

Ik moet toegeven dat ik zelf weinig tot geen kennis van MRI heb (dus er kunnen op dat vlak best wat fouten in mijn verhaal staan), maar ik studeer Electrical Engineering aan de Universiteit Twente dus heb heel wat kennis van EM-golven, Fourier transformaties en alle meuk die daarbij komt kijken.

[Reactie gewijzigd door achtbaanfreak op 23 juli 2024 09:25]

[ovigo]

Je hebt gelijk, je MRI verhaal is niet geheel correct.
In een magneetveld zijn er twee toestanden: met het magnetische veld mee en ertegenin (ookwel up en down) met het magnetische veld mee kost minder energie, dus zijn er volgens de Boltzmann verdeling meer spins die met het veld mee staan als er tegenin. Door nu een RF-puls het sampel in te jagen, kan je de spins ompolen. De spins staan echter niet parallel met het magnetische veld: ze tollen er een beetje omheen, met een frequentie die evenredig is met het magneetveld, de Larmorfrequentie.
Door het ompolen met het veld raken de spins echter in sync: de fase wordt gelijk, waardoor er een netto roterend signaal ontstaat.

De positie van de spins wordt daadwerkelijk in de frequentie van de spinprecessie gecodeert, door met spoelen een gradient aan te leggen. Ik zou even moeten nakijken of het weer uitgezonden signaal eigenlijk wel radiogolven zijn, we gebruiken alleen de magnetische component in MRI in ieder geval. Dit wordt uitgezonden op (grofweg) dezelfde frequentie, alleen met kleine afwijkingen door de gradient.

Om nu het aantal spins in een pixel (striktgenomen een voxel omdat we in 3D werken) te bepalen is een 2D fourier transform nodig. Hiermee wordt namelijk bepaald een hoe groot deel van het signaal een bepaalde frequentie had en dus in een bepaald deel van de gradient zat. Deze filtert echter maar weinig ruis weg: naast het feit dat je alleen in het gebruikte frequentiegebied kijkt, raak je geen ruis kwijt.

De gigantische stromen van de MRI zelf zijn trouwens een relatief klein probleem: omdat het grootste deel van het Magneetveld (de 1,5 of 3 of 5 of zelfs 8 Tesla) constant is en in supergeleidende spoelen opgewekt wordt, is de stroom vrijwel constant, en geeft dit dus geen storing.

Ik vraag me af of dit daadwerkelijk gaat helpen voor MRI: ook de componenten die relatief weinig aan het signaal bijdragen zijn juist voor een scherp beeld van belang.

[achtbaanfreak]

Die waterstof atomen sturen een foton weg (anders zouden ze radioactief moeten vervallen en dat is niet mogelijk voor een waterstof atoom (isotopen niet meegerekend)). Dit is gewoon een EM-golf. Vaak wordt hiervan het elektrische deel gebruikt om hem te detecteren, al kan je ook gewoon het magnetische deel van de EM-golf gebruiken om hem te detecteren. Dit gebeurt voornamelijk bij lage frequenties omdat je anders een tientallen of soms wel honderden meters lange antenne nodig hebt om het elektrische deel fatsoenlijk op te pakken (het is ideaal als de antenne in dit geval de lengte heeft van de golflengte).

Maar het is inderdaad de vraag hoeveel MRI aan deze ontwikkeling zal hebben, al kan je met slimme/goede algoritmes je apparatuur soms vele malen beter maken. Zo is Thales bezig om het bereik van hun Smart-L radar van 400-500km te vergroten naar 2000km puur door betere en slimmere algoritmes te gebruiken. Dit is natuurlijk een hele andere tak van sport. Maar het blijft een moeilijkebezigheid om bruikbare frequentie componenten door te laten en onbruikbare frequenties volledig te onderdrukken en als ik dit bericht zo lees kan dit nieuwe algoritme hier een handje bij helpen.

[ovigo]

Fair point. Radioactief verval kan het inderdaad in ieder geval niet zijn.

Het punt bij MRI is trouwens ook dat het niet echt zo is dat er frequentie componenten zijn die wel gewenst zijn en componenten die niet gewenst zijn, maar dat welke frequentiecomponenten er in je ontvangen signaal zitten, je data is. (in dit geval trouwens echt altijd gemeten met een spoel, niet met een antenne) De Fourier transform is een hard deel van je data verzamelen, niet een verbeteringsalgoritme.
Maar ik denk inderdaad ook dat er op algoritmes bij MRI nog wel iets te winnen zal zijn.

[.oisyn]

Ik zie niet in waarom je FT zou nodig hebben in een analoge FM ontvanger hoor?

Omdat je geïnteresseerd bent in de frequentieschommelingen van een draaggolf. De hoeveelheid dat je frequentie schommelt, dat is in feite de amplitude van de geluidsgolf.

[sleeplift]

In een analoge FM-ontvanger wordt er echt niet aan Fourieranalyse gedaan hoor

Wat Lunacy zegt klopt: het signaal wordt gewoonweg gedemoduleerd met behulp van analoge componenten.

[BeerenburgCola]

Als je een FFT loslaat op een FM signaal ben je je frequentie schommeling kwijt.
Wat je dan wél ziet is welke frequentie schommelingen in het gehele signaal gebruikt worden.

Een Frequentie spectrum van een FM gemoduleerd signaal ziet er ook erg vreemd uit en je kunt er niet handig je originele signaal uit halen.
Hier kon ik eentje vinden: http://cnyack.homestead.c...oll_Vertical900x600_1.gif

[Reactie gewijzigd door BeerenburgCola op 23 juli 2024 09:25]

[BeerenburgCola]

Fourier Transformate (FT) heeft niks te maken met FM.

[Reactie gewijzigd door BeerenburgCola op 23 juli 2024 09:25]

[Verwijderd]

Bij rontgenonderzoek worden wel Fouriertransformaties toegepast. Onder anderen in het filteren van de data.

Als je een CT scan doet, zal de data omgezet worden in het frequentiedomein om er vervolgens filters op toe te passen (Low-/high pass filters). Dit is hetzelfde principe als in vrijwel elke andere beeldbewerkingstechniek.

Dit maakt het mogelijk om beter bot dan wel weefsel te zien van een CT scan en om ruis te onderdrukken.

[Reactie gewijzigd door Verwijderd op 23 juli 2024 09:25]

[BeerenburgCola]

Je hoeft niet eerst een beeld te transformeren naar het frequentie domein om aan low-highpass filtering te doen.
Simpel low pass filtering gaat sneller, orde=O(n) op het originele beeld i.p.v. éérst een FFT te doen, orde=O(n log(n)).

Wel kan ik mij voorstellen dat er ook gefilterd wordt in het frequentie domein en dus ook (F)FT gebruikt wordt bij het analyseren van röntgen beelden.

[Reactie gewijzigd door BeerenburgCola op 23 juli 2024 09:25]

[DwarV]

Hij bedoelt de wetenschappelijke toepassing. Bijvoorbeeld om kristalstructuren van eiwitten en dergelijke te bepalen.

[thomascsmits]

Waarom is dit irrelevant, ik vind het een hele goeie vraag? Probleem wat je met XRD en fourier-transformaties hebt is dat de data voor de fase verloren gaat in het experiment. Dat is wel weer te schatten met wat methodes maar tot dan vraag ik mij af of de techniek in het artikel veel gaat schelen kwa kosten en tijd.

[Gropah]

10x klinkt spectaculair, maar informatica technische gezien is het dat niet. 10x sneller kun je ook bereiken met een 10x zo snelle computer. Het wordt pas leuk als ze van orde N^2, beter bekend als grote O notatie O(N^2), naar orde N (O(N)) gaan. Dan heb je meer gedaan dan simpel weg een constante weghalen, verkleinen. Nog beter wordt het als ze naar sqrt(N), log(N) of 1 gaan

Blijft alsnog leuk om te zien btw dat sommige dingen die redelijk voor granted zijn alsnog zo aan gesleuteld word. Iemand btw enig idee waarneer we dit algoritme in bijv programma's zoals Xsplit gaan zien? Juist daar is die 10x zo snel een groot voordeel, aangezien de consumenten PC's veel gelimiteerder zijn.

[GrowMyHair]

In dit geval gaan ze van het bekende O(n log n) voor het FFT algoritme naar O(k log n) voor het nieuwe algoritme. Hierin is n natuurlijk de totale signaallengte en k is in dit geval het aantal relevante waarden van de DFT.

edit:
Ter info, als de DFT direct uit zou rekenen kom je uit op O(n²).

[Reactie gewijzigd door GrowMyHair op 23 juli 2024 09:25]

[BeerenburgCola]

Nu schat ik volledig met de "natte vinger" methode maar het signaal opslitsen in "k" bandbreedtes waar je alsnog een FFT op moet doen komt op mij over als orde:O(n log n)/k

Edit: Mijn schatting klopt niet nee.

Volgens het artikel :

• An O(k log n)-time algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and
• An O(k log n log(n/k))-time algorithm for general input signals.

[Reactie gewijzigd door BeerenburgCola op 23 juli 2024 09:25]

[GrowMyHair]

Ik kan je natte vinger methode niet helemaal volgen. Je conclusie komt in ieder geval niet overeen met de bevindingen aan het MIT.

De details zijn hier te vinden: http://arxiv.org/pdf/1201.2501v1

[Delgul]

Lijkt me een soort van 'lossy' fft inderdaad. Je verliest dus informatie, maar als je daarmee een boel snelheid wint en het hoeft niet al te precies kan dit wel eens een dikke doorbraak zijn...

[Rannasha]

Lijkt me een soort van 'lossy' fft inderdaad. Je verliest dus informatie, maar als je daarmee een boel snelheid wint en het hoeft niet al te precies kan dit wel eens een dikke doorbraak zijn...

Iedere discrete fourier transformatie met een eindig aantal coefficienten is lossy. Je hebt immers maar een beperkte hoeveelheid coefficienten om het signaal in "op te slaan".

[BeerenburgCola]

Nee.
Als je een FFT doet op een eindig discreet signaal (n samples) dan kun je losless een inverse doen op het resulterende Frequentie Spectrum, mits deze dezelfde hoeveelheid coëfficiënten heeft (ook n).
De grap is dat je deze met dezelfde FFT kunt doen en alleen een normalisatie trucje hoeft toe te passen.

[Reactie gewijzigd door BeerenburgCola op 23 juli 2024 09:25]

[MSalters]

Dat is alleen waar zonder afrondfouten. Het probleem is niet het aantal coefficienten, maar het aantal bits per coefficient. Het simpele voorbeeld is een 1,0,0,1,0,0 (enz) signaal. Je krijgt dan een FFT coefficient van 1/3. De input past in een eindige hoeveelheid bits, maar de output niet (1/3 is niet representeerbaar in een eindig aantal bits).

[BeerenburgCola]

Species5618 heeft het over het aantal coëfficiënten, niet over de mogelijke float afrondings fouten.
Als je een signaal, bijvoorbeeld een 16 bits audio signaal, met double precision (64 bits) bewerkt zijn de "afrondings fouten" veroorzaakt door floating point berekeningen verwaarloosbaar.

Anders gezegd: als je een 16 bits waarde (sample) omzet naar een frequentie coëfficiënt met een double precision van van 64 bits, krijg je bij een reverse FFT exact je 16 bits waarde terug (na conversie).

Je moet er alleen voor zorgen dat de precisie van je frequentie componenten hoger zijn dan de relevante resolutie van je oorspronkelijke (tijd) signaal. Dit kun je berekenen.
Audio software rekent tegenwoordig al met 32 bits of hogere (64 bits) precisie om dit soort "afronding fouten" tegen te gaan.

[Reactie gewijzigd door BeerenburgCola op 23 juli 2024 09:25]

[Wh4ck0]

Volgens mij is het juist minder lossy. Omdat je verschillende technieken samenvoegt, in plaats van dat je een hele nauwkeurige FFT gebruikt, bouw je de gegevens op uit meerdere delen.

[BeerenburgCola]

Wat ze doen is juist de minder belangrijke frequenties eruit filteren. Dus juist méér lossy dan een evt. lossy compressie algoritme wat er ná komt.
Er wordt van te voren meer (weg)gefilterd.

[Reactie gewijzigd door BeerenburgCola op 23 juli 2024 09:25]

[stoepie2002]

Mooie techniek. Dan kan in eenzelfde CPU/DSP (of ander soortige rekenunit) met de zelfde kwaliteit worden gewerkt tegen een veel lager verbruik (minder mW). Niet alleen goed voor portable devices, maar ook meer algemeen "in producten".

Of je neemt een factor tien zwakkere CPU/DSP (etc) en komt er ook mee weg: lagere kosten en ook lager verbruik....

OF je kunt met bestaande CPU/DSP technieken multipass gaan doen icm hogere resoluties.

Dit klinkt echt goed!

[Reactie gewijzigd door stoepie2002 op 23 juli 2024 09:25]

[Calavoow]

Het nadeel zou natuurlijk kunnen zijn dat het bepalen van deze 'zwaarwegende' frequenties resulteert in een grote last op de CPU, danwel een groot circuit. Zoals ook genoemd in het bronartikel, is deze technologie nog in ontwikkeling en feitelijk het hart van deze nieuwe techniek.
Ook al zou dit het geval zijn, dan is het alsnog zeer toepasbaar op bijvoorbeeld compressie van muziek (mp3) en images.

[0rbit]

Wordt in veel digitale toepassingen niet sowieso de DCT gebruikt?

[MSalters]

Ja. Zowel MP3 als JPEG gebruiken de DCT. Nu zijn die algoritmes sterk verwant - beiden representeren een inputsignaal als de som van periodieke functies, alleen gebruikt de DFT ook sinussen (cq. imaginaire exponenten). Als je kijkt hoe het MIT hun snelheidswinst bereikt (voorfilteren om te bepalen welke frequenties uberhaupt in het signaal zitten), dan ligt het voor de hand om aan te nemen dat een vergelijkbare versnelling mogelijk is voor DCTs.

[markg85]

Tweakers, de titel is misleidend en de uitleg al helemaal. Het is niet per definitie 10x sneller, maar kan tot 10x sneller zijn in sommige gevallen!

De bron zegt:

Under some circumstances, the improvement can be dramatic — a tenfold increase in speed.

[Reactie gewijzigd door markg85 op 23 juli 2024 09:25]