iPon Hírek

Gyorsnál is gyorsabb Fourier-transzformáció

Dátum | 2012. 01. 20.
Szerző | Jools
Csoport | IT VILÁG

A Fourier-transzformáció egyike a legalapvetőbb koncepcióknak az információtudományban. Segítségével egy szabálytalan jelet leírhatunk periodikus jelek összegeként. Mindenütt használják a jelfeldolgozásban, de többek közt kép- és hangfájlok tömörítésében, differenciálegyenletek megoldásában és a tőzsdei árfolyamok ingadozásának leírásában is gyakran alkalmazzák.

Elterjedt használatát a hatvanas években kidolgozott gyors Fourier-transzformáció nevű algoritmus (FFT) teszi lehetővé, amely automatikusan elvégzi a jelfelbontást. Megalkotása óta időről időre felmerül azonban a kérdés: van-e még gyorsabb módszer a művelet elvégzésére?


A héten Japánban megrendezett Symposium on Discrete Algorithms (SODA) alkalmából az MIT kutatói egy új algoritmust mutattak be, amely számos alkalmazásában gyorsabbnak bizonyult az FFT-nél. Egyes feladatoknál tízszeres gyorsaságot is elértek. Az új módszer különösen jól hasznosítható lesz a képi információk tömörítésében, lehetővé téve például az okostelefonokon keresztüli videófájl-küldést az akkuk lemerülése és a havi adatforgalom „elfogyasztása” nélkül.

Ahogy az FFT, az új algoritmus is digitális jeleken működik: mintákat vesz a jelből és a frekvenciák súlyozott összegeként állítja elő az új értékeket. Súlyozott abból a szempontból, hogy némely frekvenciák fontosabban, mint mások, amelyek közt akadnak minimális információveszteséggel elhagyhatók is. Ezért is hasznos a transzformáció a tömörítésnél. Ha elképzelünk egy 8x8-as pixelblokkot, azt felfoghatjuk egy 64 különböző szignálból álló jelsornak, ezt összeadva 64 különböző frekvenciával dolgozunk. De ahogy az MIT kutatói rámutattak: ezen frekvenciák közül 57 nyugodtan elhagyható a képminőség észrevehető romlása nélkül.


Azokat a jeleket, amelyek néhány frekvenciával leírhatók veszteségek nélkül, ritkás jeleknek nevezzük. Az új algoritmus gyorsan felméri a jelek leginkább súlyozandó frekvenciáit: így minél ritkásabb a jel, annál gyorsabban dolgozik. A módszer során kisebb sávszélességű szeletekre bontják a jelet, hogy az egyes szeletek egyetlen súlyozott frekvenciával leírhatók legyenek. Dina Katabi, Piotr Indyk, Eric Price és Haitham Hassanieh egy olyan algoritmust dolgoztak ki tehát, amely nagyon gyorsan kiválogatja, hogy mi is kell nekünk feltétlenül egy adott jelből.
 

Új hozzászólás írásához előbb jelentkezz be!

Eddigi hozzászólások

6. Svidi
2012.01.20. 16:22
Wow. BME után oda megyek tanulni
 
Válasz írásához előbb jelentkezz be!
5. rastawicc
2012.01.20. 21:30
Íme a fejlődés.
 
Válasz írásához előbb jelentkezz be!
4. Resike
2012.01.21. 22:27
Csupán 50 évbe telt.
 
Válasz írásához előbb jelentkezz be!
3. Smoke
2012.01.22. 01:07
Egy kis pontosítás: Jelenleg fizikailag digitális jelet nem vagyunk képesek előállítani, csak az analógot digitálisnak értelmezni. Az ábrák is mind analóg jeleket ábrázolnak.
 
Válasz írásához előbb jelentkezz be!
2. Resike
2012.01.22. 01:26
Nyilván, de nincs is rá szükség.
 
Válasz írásához előbb jelentkezz be!
1. agyturbini...
2012.01.23. 09:40
Van egy kerdesem: miert nem hasznalunk analog Szamitogepeket?
Erteam azt hogy a Biniaris rendszer szep es jo egyszeru programozni, de egy analog szamitogep fenyevekkel mgyorsabb mint akarmelyik digitalis tarsa es hat mivel az elet minden teruleten analog jelek vannak igy az atalakitassal sem kell szenvedni.
 
Válasz írásához előbb jelentkezz be!