Warning: Undefined array key "bio" in /home/techwatch/domains/test.bits-chips.nl/public_html/wp-content/plugins/wpcodebox2/src/Runner/QueryRunner.php(126) : eval()'d code on line 13
Author:
Reading time: 4 minutes
De uitvinding van de fast Fourier transformation maakte het mogelijk om met een computer een signaal op te delen in deelfrequenties. Daarmee werd digitale signaalverwerking voor het eerst mogelijk. Een team van MIT-onderzoekers heeft nu een verbetering gepresenteerd die het algoritme voor de meeste praktijkgevallen tot nog wel een ordegrootte kan versnellen.
Eigenlijk waren James Cooley en John Tukey niet de eersten die de fast Fourier transformation of FFT uit vonden in 1965. 160 jaar eerder had Carl Friedrich Gauss al hetzelfde gedaan en na hem nog een aantal anderen. Maar Cooley en Tukey kwamen met hun ontdekking op een moment dat de wereld er iets aan had. De computer was net uitgevonden en de eerste gebruikers zagen in de FFT een aanpak om digitale signalen te analyseren en te bewerken – iets wat met de standaard Fourier-transformaties te lang zou duren.
Het is niet overdreven om te stellen dat de FFT het fundament vormt voor digitale signaalverwerking. Joseph Fourier bedacht in de negentiende eeuw dat je elke continue lijngrafiek van een signaal tegen de tijd ook op kan schrijven als de som van een aantal sinusoïden, als je de frequenties en amplitudes hiervan juist kiest. Een Fourier-transformatie draait om het vinden van deze deelfrequenties.
Het aantal sinusoïden dat nodig is om voor een bepaald signaal, is in het slechtste geval oneindig – niet heel praktisch voor digitale signaalverwerking. Gelukkig bestaan digitale signalen uit slechts een beperkt aantal punten, en dat is binnen de Fourier-analyse een apart geval; dan kan dat herschreven worden als een som van even zo veel opeenvolgende frequenties. Het resultaat van de transformatie is een lijst die specificeert in welke mate elk van de frequenties bijdraagt aan het totale signaal.
Die eigenschap wordt veelvuldig gebruikt in digitale signaalverwerking, bijvoorbeeld voor het wegfilteren of juist versterken van bepaalde frequentiebanden. Overigens hoeft de methode niet alleen gebruikt te worden voor signalen in de tijd. Voor beeldverwerking worden allerlei bewerkingen uitgevoerd op een frequentieanalyse van het tweedimensionale beeld – een blokje van typisch 8 bij 8 pixels vormt het signaal.
De methode ligt ook ten grondslag aan (lossy) datacompressie voor multimedia; na een Fourier-analyse van een typisch muziekstuk zal blijken dat het merendeel van de frequenties zo‘n kleine rol speelt, dat ze makkelijk weggelaten kunnen worden. Alledaagse signalen heten sparse (dungezaaid) te zijn. In een blokje beeldmateriaal van 8 bij 8 pixels, zijn er gemiddeld slechts 7 van belang.
Overlappen
Deze eigenschap van de meeste alledaagse signalen trok al sinds de jaren negentig de aandacht van wiskundigen. Als de meeste signalen toch niet interessant zijn, zou de FFT ze dan niet simpelweg kunnen negeren om de boel nog eens te versnellen, was de gedachte. Alleen, hoe kom je er achter welke signalen interessant zijn zonder eerst een FFT uit te voeren? Er zijn hiervoor verschillende aanpakken ontwikkeld, maar die waren in de praktijk nog niet goed toepasbaar. Ze werkten namelijk alleen als het signaal daadwerkelijk flink dungezaaid is. Is dat niet het geval, dan werden de algoritmes al snel veel minder efficiënt dan FFT.
Een team van het MIT heeft nu op het Symposium on Discrete Algortihms (Soda) in Japan methodes gepresenteerd om hier wel efficiënt mee om te gaan. De basis is om het signaal eerst op te delen in een beperkt aantal frequentiebanden. Bij dungezaaide signalen is de kans groot dat zo‘n band hooguit één signaal van betekenis bevat. Vervolgens kan daar actief naar gezocht worden om de waarde ervan te bepalen.
Het opdelen van een signaal in frequentiebanden gaat via filters. Maar daar kleeft een probleem aan. Richting de rand van de filters worden frequenties namelijk afgezwakt. Een sterke frequentie te dicht bij de rand van het filter kan daardoor buiten de boot vallen. Het MIT-team lost dat op door de filters op een slimme manier een beetje te laten overlappen: frequenties aan de rand worden niet te veel afgezwakt, maar de frequentiebanden hebben wel redelijk scherpe randen.
Als de bundels eenmaal gekozen zijn, dan moet het algoritme nog de waarde van het significante signaal in elke bundel bepalen. In de Soda-aanpak gebruiken de onderzoekers daar een binary search voor: deel de frequentieband in twee en gooi de helft weg waar niks interessants in zit, net zolang totdat de juiste frequentie is gevonden. In een ongepubliceerd artikel hebben ze al een sterke verbetering hiervoor bedacht met een truc uit de draadloze communicatie. Het signaal wordt hier op een paar punten bemonsterd om te bepalen waar in de cyclus het signaal is. Gekoppeld aan de tijd geeft dit de frequentie van de band, dus van het dominante signaal.
Ook de voorgangers van het MIT-algoritme gebruikten filters en het opdelen van frequentiebanden bij hun aanpak, maar zetten een iteratieve methode met meerdere stappen om de betekenisvolle frequenties te vinden. Daar gaat veel computertijd aan verloren. Het MIT-algoritme vindt ze in een enkele stap, zodat er veel meer ruimte ’overblijft‘. Daardoor blijft het algoritme over een brede reeks van signaaldichtheid goed presteren, tot een ordegrootte meer dan bij voorgaande technieken. Pas aan de uiteinden – als bijna alle frequentiebanden een rol van betekenis spelen – wordt de efficiëntie kleiner dan een standaard FFT. De onderzoekers denken dan ook dat hun aanpak kan leiden tot efficiëntere multimedia-afhandeling. Met de druk waaronder elektronicafabrikanten staan om meer features in een kleiner energiebudget te proppen is dat een welkome verbetering.
