Fast and Fourier

Paul
hace 1 día
4 Min. de lectura

Gaurkoan ere algoritmo batekin natorkizue. Oraingo honetan konputazio kuantikoa albo batera utzita, algoritmo klasiko batekin arituko gara. Algoritmo honek Fourierren Transformatu Azkarra du izena, Fast Fourier Transform edo FFT ingelesez. Ez dakit algoritmo honek duen garrantzia bere osotasunean azaltzeko gai izango naizen, baina hurrengo lerroetan horretan saiatuko naiz. Uhinak, maiztasunak eta trigonometria izango dira saltsa honen osagai.

1.Fourierren Analisia

Joseph Fourier XVIII. mendeko matematikari eta fisikari frantsesa izan zen, eta oso tipo azkarra gainera. Funtzio periodikoak (T periodoro errepikatzen diren horiek) maiztasun ezberdineko funtzio trigonometriko sinpleen (sinuen eta kosinuen) batura gisa deskonposatzeko metodo bat proposatu zuen. Demagun hurrengo funtzio periodikoa dugula:

2. irudia: T=2 periodoko funtzio periodiko bat.

Funtzio horri f deituko diogu eta t aldagaiaren menpekoa da. Orduan, Fourierren arabera, modu honetan idatz dezakegu funtzio berbera:

Adierazpen horrek Fourierren seriea izena du, a eta b koefizienteei anplitude deritze eta ω terminoei maiztasuna. Hortaz, batukari honek maiztasun ezberdineko sinuak eta kosinuak batzen ditu, non bakoitzaren anplitudeak determinatzen duen oszilazioen tamaina. Baina, nola kalkula ditzakegu anplitude horien balioak, batura guztiak funtzio originalaren itxura har dezan? Ba integral hauen bitartez:

Ados, lasai. Ez duzue zertan ulertu zergatik kalkulatzen diren anplitudeak modu honetan, horretarako lan ederrak hartu zituen Fourier jaunak! Momentuz, koefiziente horiek kalkulatzeko metodo bat existitzen dela jakitearekin nahikoa, nahiz eta metodo hori garatzeko kalkulu asko egin behar direla dirudien.

Erakutsi berri dizuedan deskonposaketa hau, ordea, batukariak N= ∞ termino dituenean soilik da zehatza. Batukariak termino kopuru finitua duenean, hurbilpen bat besterik ez da, eta zenbat eta batugai gehiago kontuan hartu, orduan eta errore txikiagoa izango dugu.

3.irudia: Fourierren seriaren hurbilpena, terminoak gehitu ahala

2. Diskretutik jarraitura:

Fourierren seriea oso emaitza dotorea da, baina Eulerren formulari [1] esker, modu konpaktuagoa ezagutzen dugu deskonposaketa berdina adierazteko:

Orain, eta txaparekin amaitzeko, azken xehetasun bat. Hasieran aipatu dugu f funtzioa periodikoa dela, baina errealitatean gutxitan egingo dugu topo mota horretako funtzioekin. Deskonposatu nahi dugun funtzioa ez bada periodikoa, funtzioa periodo infinituko tarte batean behatzen ari garela suposatuko dugu. Hori horrela bada, eta maiztasunaren definizioan periodoa zatitzailean agertzen dela kontuan izanda, maiztasun diskretu baten (n) eta hurrengoaren (n+1) arteko tartea infinituki txikia bihurtzen da. Ondorioz, maiztasun posible guztiek espektro jarraitu bat osatzen dute, eta Fourierren serieko batukaria integral baten bitartez egin dezakegu.

Orain, anplitudeak deskribatzen zituzten koefizienteek (cn) funtzio jarraitu bat osatzen dute. Funtzio hauxe bera da f-ren Fourierren transformatua. Funtzio originalaren beste adierazpen bat besterik ez da, oraingoan, maiztasun jakineko funtzio trigonometrikoen batura jarraitu moduan idatzita. Funtzio originala t aldagaiaren munduan bizi da, horren transformatua aldiz, maiztasunen munduan. Hona hemen Python bidez egin dudan adibide bat:

4.Irudia: Ezkerrean, maiztasun ezberdineko bi funtzio sinusoidal eta haien batura. Eskuinean, baturaren Fourierren transformatua. Transformatuaren grafikoan untzio sinusoidalen maiztasunetan muturreko balioak ikus daitezke.

3. Uhinak

Oso ondo, orain funtzio trigonometrikoen bitartez funtzio orokorrak hurbiltzen dakigu, baina hori zertarako? Zerk du sinu, kosinu edo funtzio esponentzial konplexu itxura? Hori da, uhinek! Normalean naturatik jasotzen ditugun uhinak, bai mekanikoak (irakurri Ixaken artikulua) eta bai elektromagnetikoak (eta Liberena), maiztasun determinatu bateko uhin “lauen” batura gisa iristen zaigu. Beraz, Fourierren transformatuaren bitartez jasotzen ditugun uhin multzoetan zein maiztasuneko oszilazioak, eta bakoitzetik zenbat, dauden jakin dezakegu.

Eta ez hori bakarrik, alderantzizkoa ere egin dezakegu! Maiztasun jakin bakoitzetik zenbateko intentsitatea nahi dugun finkatuz, maiztasunaren domeinuko funtzioan transformazioak eginez, uhin multzoaren originalaren itxura eralda dezakegu. Musikaren munduan apur bat ibili bazarete, ekualizazio hitza noizbait entzungo zenuten. Ekualizatzerakoan, esku artean dugun soinu uhinaren Fourierren transformatua egiten da uneoro, eta maiztasunaren espektroan aldaketak egin ondoren, berriro transformatzen da soinu uhin gisa igortzeko. Modu horretan, ahotsa prozesatzen ari bagara, adibidez, giza ahotsaren espektrotik kanpo geratzen diren maiztasunen intentsitatea jaits dezakegu, eta ondorioz zarata nabarmenki ezabatu.

4. Fourierren Transformatu Azkarra

Lehenengo atalean aipatu dudan bezala, Fourierren transformatua egiteko kalkulu asko egin behar dira. Normalki, naturatik datozkigun datuak aztertzerakoan denboran zehar hedatutako balio jakinak jasotzen dira. N puntuko lagin baten Fourierren transformatua egiteak, orokorrean, N karratu pauso eskatzen ditu (ikusi nire aurreko artikulua, algoritmoen konplexutasuna nola aztertzen den azaltzen baitut). Balio hori erraldoia bihur daiteke lagina handia bada, ordenagailuentzat ere handiegia agian. Orain imaginatu uneoro aldatzen ari den seinale baten transformatua egitea: kalkuluak izugarri luzatuko lirateke. James Cooley eta John Tukey matematikari estatubatuarrek, ordea, zorionez, 1965. urtean algoritmo berri bat proposatu zuten, Fourierren transformatua egiteko kalkulu kopurua nabarmenki murrizten duena. Algoritmo berri honek Nlog(N) pausu behar ditu, eta hasiera batean ezberdintasunak horrenbestekoa ez dirudien arren, laginaren tamaina handitu ahala ikaragarria bihurtzen da. Horregatik, algoritmo honi Fourierren Transformatu Azkarra deitzen zaio.

6.Irudia: Fourierren transformatu azkarraren eta metodo orokorraren konplexutasun konputazionalen arteko ezberdintasuna, laginaren tamainaren arabera.

Aurrerapen honek, ordenagailuek kalkuluak egiteko duten gaitasunaren hazkuntzarekin batera, Fourierren trasformatua segituan egiteko gaitasuna ekarri digu eta aplikazio izugarriak garatzeko aukera eman digu:

Telekomunikazioen garapena ahalbidetu du, Wifi edo 5G moduko seinaleak etengabe eta berehala prozesatzeko aukera ematen baitu.
Izarretatik datorren argiaren maiztasunak deskoponsatuta, bertan dauden elementuak identifika ditzakegu. Fourierren transformatu azkarraren bitartez ikerkuntza izugarri azkartu da.
Musika elektronikoaren eta audio grabazioen atzean beti dago Fourierren transformaturen bat.
Irudiak, bideoak, audioak eta beste hainbat fitxategi digital konprimatzeko, Fourierren transformatuaren bitartez ekarpen txikieneko maiztasunak ezaba ditzakegu.
Radarrek objektu baten abiadura determinatzeko Doppler efektua [2] aztertzen dute. Horretarako, radarretik igorri eta objektu higikarian islatutako seinale baten maiztasuna nola aldatzen den behatzen da.
Konputazio kuantikoan Fourierren transformatua egiten duen subrutina bat existitzen da, Quantum Fourier Transform deiturikoa. Algoritmo kuantiko askoren zati garrantzitsua da (Shorrena, besteak beste) eta abantaila kuantikoaren iturrietako bat da.

Eta motz geratu naiz! Horren garrantzitsua izan da algoritmo hau, non batzuek munduko algoritmo garrantzitsuena dela dioten!

5. Joko bat

Ohartu naiz testuan zehar maiztasuna askotan aipatu dudala. Horregatik, honako jokoa proposatzen dut: hurrengo maiztasuna guztien artean maitasuna <3 gorde dut. Ea aurkitzen duzun (ezin da ctrl+F erabili).

maiztasuna_maiztasuna__maiztasuna__maiztasuna___maiztasuna___maiztasuna__maiztasuna_maiztasuna___maiztasuna__maiztasuna_maiztasuna___maiztasuna_maiztasuna__maiztasuna___maiztasuna___maiztasuna__maiztasuna_maiztasuna__maiztasuna__maiztasuna___maiztasuna___maiztasuna___maiztasuna_maiztasuna__maiztasuna_maiztasuna_maiztasuna___maiztasuna___maiztasuna__maiztasuna_maiztasuna___maiztasuna_maiztasuna___maiztasuna___maiztasuna__maiztasuna_maiztasuna_maiztasuna_maiztasuna__maiztasuna___maiztasuna__maiztasuna___maiztasuna__maiztasuna___maiztasuna___maiztasuna___maiztasuna_maiztasuna_maiztasuna___maiztasuna__maiztasuna_maiztasuna_maiztasuna__maiztasuna__maiztasuna__maiztasuna_maiztasuna__maiztasuna___maiztasuna_maiztasuna_maiztasuna___maiztasuna___maiztasuna___maiztasuna___maiztasuna_maiztasuna___maiztasuna__maiztasuna__maiztasuna_maiztasuna__maiztasuna__maiztasuna___maiztasuna_maiztasuna___maiztasuna__maiztasuna___maiztasuna__maiztasuna___maiztasuna__maiztasuna___maiztasuna__maiztasuna__maiztasuna_maiztasuna_maiztasuna___maiztasuna___maiztasuna_maiztasuna__maiztasuna__maiztasuna_maiztasuna_maiztasuna___maiztasuna___maiztasuna_maiztasuna_maiztasuna_maiztasuna___maiztasuna__maiztasuna___maiztasuna__maiztasuna_maiztasuna__maiztasuna__maiztasuna___maiztasuna___maiztasuna__maiztasuna_maiztasuna___maiztasuna__maitasuna_maiztasuna___maiztasuna_maiztasuna__maiztasuna___maiztasuna___maiztasuna__maiztasuna_maiztasuna__maiztasuna__maiztasuna___maiztasuna___maiztasuna___maiztasuna_maiztasuna__maiztasuna_maiztasuna_maiztasuna___maiztasuna___maiztasuna__maiztasuna_maiztasuna___maiztasuna_maiztasuna___maiztasuna___maiztasuna__maiztasuna_maiztasuna_maiztasuna_maiztasuna__maiztasuna___maiztasuna__maiztasuna___maiztasuna__maiztasuna___maiztasuna___maiztasuna___maiztasuna_maiztasuna_maiztasuna___maiztasuna__maiztasuna_maiztasuna_maiztasuna__maiztasuna__maiztasuna__maiztasuna_maiztasuna__maiztasuna___maiztasuna_maiztasuna_maiztasuna___maiztasuna___maiztasuna___maiztasuna___maiztasuna_maiztasuna___maiztasuna__maiztasuna__maiztasuna_maiztasuna__maiztasuna__maiztasuna___maiztasuna_maiztasuna___maiztasuna__maiztasuna___maiztasuna__maiztasuna___maiztasuna__maiztasuna___maiztasuna__maiztasuna__maiztasuna_maiztasuna_maiztasuna___maiztasuna___maiztasuna_maiztasuna__maiztasuna__maiztasuna_maiztasuna_maiztasuna___maiztasuna___maiztasuna_maiztasuna_maiztasuna_maiztasuna___maiztasuna__maiztasuna___maiztasuna