Diskreetne Fourier' teisendus

Allikas: Vikipeedia
Fourier' teisenduse ja diskreetse Fourier' teisenduse vaheline suhe. Vasak verg: Pidev funktsioon (üles) ja tema Fourier' teisendus (all). Kesk-vasak veerg: Originaal funktsiooni perioodiline summeerimine (üles). Fourier' teisendus (all) on null v.a diskreetse punktide kohtadel. Pöördtransformatsioon on sinusoidide summa, nimetatud Fourier' rida. Kesk-parem veerg: Original funktsioon on diskreeditud (üles). Selle Fourier' teisendus (all) on originaal teisenduse perioodiline summa. Parem veerg: DFT (all) arvutab diskreedsed proove pidevast diskreetse aja Fourier' teisendusest. Pöörd DFT (üles) on originaal proovide perioodiline summeerimine. Kiire DFT arvutab ühe tsükli DFT-d ja pöörd DFT-d ühes pöörd DFT tsüklis.[1]
Fourier' teisenduse kujutis (üles) ja selle perioodiline summa (DTFT) all.[2]

Diskreetne Fourier' teisendus (DFT) on pideva Fourier' teisenduse vaste ajas ja nivoos diskreeditud (analoogsignaalist või funktsioonist teatud ajahetkedel võendatud (sampled) ja nivoos diskreeditud (digiteeritud)) funktsioonide ja signaalide jaoks. Teatud tingimuste täidetuse korral on DFT tulemused vastavuses pideva Fourier' teisenduse tulemustega. Kuid paljudel juhtudel on tulemused siiski oluliselt erinevad, mistõttu DFT tulemuste ülekandmisel analoogsignaalidele tuleb olla ettevaatlik.[3]

DFT on kõige olulisem diskreetne teisendus, mida kasutatakse Fourier' analüüsi teostamiseks paljudes praktilistes rakendustes.[4] Signaalitöötluses on iga signaal funktsioon, millest võetakse proov üle piiratud ajavahemikku.[5] Näideteks võivad olla helilaine, raadiosignaal või muutuvad temperatuurinäidud. Pilditöötluses võivad proovid olla pikslite väärtused igas reas või veerus rasterkujutisel. DFT-d kasutatakse ka selleks, et lahendada efektiivselt diferentsiaalvõrrandeid ja teha teisi toiminguid, nagu konvolitsioon ja suurte arvude korrutamine.[6]

Kuna DFT tegeleb piiratud andmemahtudega, saab seda rakendada arvutades numbriliste algoritmide abil või kasutades sihtotstarbelist riistvara. Need rakendused tavaliselt kasutavad kiiret Fourier' teisendust (Fast Fourier Transform = FFT), mis põhineb teisenduse teostamiseks vajalike arvutuste mahu vähendamises teatud (korduvate) tulemuste (korduva) ärakasutamise teel või mõne spetsiifilise vaheteisenduse kasutamise teel.[7]


Mõiste[muuda | muuda lähteteksti]

N kompleksarvude jada teisendatakse N-perioodiliseks kompleksarvude jadaks:

(täisarvud)   [märkus 1]

Perioodilisuse tõttu on tegelikult arvutatud domeen k [0, N – 1]. See on alati nii, kui DFT-d on rakendatud kiire Fourier' teisenduse kaudu. Muud domeenid on [-A / 2, N / 2-1] (N paaris) ja [- (N – 1) / 2, (N – 1) / 2] (N paaritu), kui vasak ja parem pool DFT väljundis on vahetatud.[1]

Diskreetne Fourier' teisendus on tavaliselt tähistatud tähega , kus või või .[märkus 2]

Definitsioonivõrrandit võib tõlgendada või tuletada mitmel erinevatel viisidel, näiteks[6]:

  • See kirjeldab täielikult diskreetse aja Fourier' N-perioodilist järjestust, mis sisaldab ainult diskreetse sageduse komponente.
  • Samuti tagab see ühtlaste vahekaugusega proove sisalduva pideva DFT antud piiratud pikkusega.
  • See on sisendandmete ristkorrelatsioon, ja kompleksne sinusoid sagedusel k/N. Seega see toimib nagu sobitatud filter sellele sagedusele.
  • See on diskreetne analoog Fourier' rea koefitsientide leidmise valemile:

mis on ka N-perioodiline. domeenis on see definitsiooni valemi pöördteisendus. Selle tõlgenduse järgi on iga kompleksne number, mis kodeerib funktsiooni kompleksesse siinuselisse komponenti   nii amplituudi kui ka faasi.[6] Siinuse sagedus on k/N. Amplituud ja faas vastavad võrranditele:
kus atan2 on arkustangensi funktsioon kahe argumendi jaoks.[8]

Euleri valemi abil saab DFT valemi teisendada trigonomeetriliseks vormiks, mida kasutatakse inseneride arvutlustes ja infotehnoloogias:

Fourier teisendus:

Pöördteisendus:

N = proovide arv
n = praegu töödeldava proovi number (0, ..., N − 1)
xn = signaali väärtus ajahetkel n
k = praegune sagedus (0 Hz kuni N-1 Hz)
Xk = sageduse k kogus signaalis (amplituud ja faas, kompleksarv)[9]

Omadused[muuda | muuda lähteteksti]

Täielikkus[muuda | muuda lähteteksti]

Diskreetne Fourier' teisendus on pööratav lineaarne teisendus

kus on kompleksarvude hulk. See tähendab, et iga N > 0, N-mõõtmeline kompleksvektor omab DFT-d ja PDFT-d (pöördteisendust), mis on omakorda N-mõõtmelised kompleksvektorid.[10]

Ortogonaalsus[muuda | muuda lähteteksti]

Vektorid moodustavad ortogonaalse baasi üle N-mõõtmeliste kompleksvektorite hulga:

kus on Kronecker delta. (Viimane samm on triviaalsete summa, kus 1+1+⋅⋅⋅=N, ja selline geomeetriline jada, millest saab summeerides saada kokku nulli.) Seda ortogonaalsuse tingimust saab kasutada selleks, et tuletada pöördteisenduse valemit DFT definitsioonist.[11]

Plancherel teoreem ja Parsevali teoreem[muuda | muuda lähteteksti]

Kui Xk ja Yk on vastavalt xn ja yn teisendused, siis ütleb Parsevali teoreem, et:

kus tärn tähendab kompleksset konjugatsiooni. Parsevali teoreemi selline erijuht, kus xn = yn, on Planchereli teoreem, mis väidab:

[12]

Perioodilisus[muuda | muuda lähteteksti]

Perioodilisust võib näha otse definitsioonist:

Samas on näha, et pöördteisenduse võrrand viib perioodilisele laiendamisele.[12]

Nihe[muuda | muuda lähteteksti]

Korrutades lineaarse faasiga mingi täisarvu m järgi vastab nihkele väljundis : , mis asendatakse , kus indeks on tõlgendatud kui absoluutväärtus N (perioodiliselt).[10] Samamoodi nihe sisendis vastab väljundi korrutamisele lineaarse faasiga. Matemaatiliselt, kui tähistab vektorit x, siis

kui
siis
ja [10]

Ringkonvolutsiooni teoreem ja ristkorrelatsiooni teoreem[muuda | muuda lähteteksti]

Konvolutsiooni teoreem diskreetse Fourier' teisenduse jaoks näitab, et kahe lõpmatu jada konvolutsiooni võib saada kahe üksiku teisenduse tulemuste pöördteisendusest. Kui järjestused on piiratud pikkustega N, siis tekib oluline lihtsustamine.[13] Kui vaadelda DTF-d ja pöörd-DTF-d, võib seda kirjutada järgmiselt:

mis on konvolutsioon ja jadade vahel pikendatud perioodilise liitmisega:

Ristkorrelatsioon   ja    vahel on selline:

[13]

Konvolutsiooni teoreemi duaalsus[muuda | muuda lähteteksti]

Võib ka tõestada, et:

mis on ringikujuline konvolutsioon ja vahel.[14]

Trigonomeetriline interpolatsiooni polünoom[muuda | muuda lähteteksti]

paaris N-i jaoks,
paaritu N-i jaoks,

kus koefitsiendid Xk on eespool oleva xn DFT ja rahuldavad interpoleerimist jaoks.[15]

Paaris N-i puhul tuleb tähele panna, et Nyquist komponenti käsitletakse eraldi.[15]

Ühtne DFT[muuda | muuda lähteteksti]

Teise võimalusena saab DFT-d väljendada DFT maatriksi abil ehk Vandermonde maatriksina, mille võttis kasutusele Sylvester 1867. aastal.

kus

on primitiivne N-is ühe juur.[16]

Pöördteisendus on selle maatriksi pöördmaatriks:

Ühtse normaliseerimise konstantidega saab DFT ühtseks teisenduseks, mis on defineeritud ühtse maatriksi abil:

kus det() on maatriksi determinant. Determinant on omaväärtuste tulemus, mis on kas või . Ortogonaalsust väljendab nüüd ortonormaalsuse tingimus.[16]

Kui X on ühtne vektori x DFT, siis

ja Planchereli teoreem on väljendatud niimoodi:

Erijuhul on see Parsevali teoreem

[17]

Pöördvõrdelise DFT avaldamine DFT kaudu[muuda | muuda lähteteksti]

Kasulik DFT omadus on see, et pöördteisendust saab kergesti väljendada tavalise DFT kaudu, kasutades allolevaid nippe:

Esiteks saame arvutada pöördvõrdeline DFT, pöörates vastupidi kõik peale ühe sisendi.[11]

Teiseks võib ka ümber pöörata sisendid ja väljundid:

Viimaseks võime vahetada omavahel reaal- ja imaginaarsignaali osad:

Kus swap() on , milles on reaal- ja imaginaar-osad omavahel niimoodi vahetatud: swap() on . Samas, swap() on võrdne .[18]

Omaväärtused ja omavektorid[muuda | muuda lähteteksti]

DFT maatriksi omaväärtused on lihtsad ja hästi tuntud, kusjuures omavektorid on keerulised ja neid pole veel täiesti uuritud.[19]

Kui DFT ühtne vorm pikkusega N on selline:

See maatriks vastab maatriksite polünomiaalsele võrrandile:

See tähendab, et omaväärtused võrrandile on:

Samas on omaväärtused neljandad ühe juured: on +1, −1, +i, või −i.

Kuna on olemas ainult neli omaväärtust, siis need omavad mitmesust, mis annab omavektorite numbri igale omaväärtusele.[19]

Paljususe probleemi lahendasid McClellan ja Parks, samas ekvivalentse probleemi lahendas varem Gauss. Mitmesus sõltub absoluutväärtusest N ja on näidatud järgmises tabelis[20]:

suurus N λ = +1 λ = −1 λ = -i λ = +i
4m m + 1 m m m − 1
4m + 1 m + 1 m m m
4m + 2 m + 1 m + 1 m m
4m + 3 m + 1 m + 1 m + 1 m

Määramatuse printsiip[muuda | muuda lähteteksti]

Kui juhuslik suurus Xk on piiratud:

siis

võib esindada diskreetse tõenäosuse n-i massi-funktsiooni koos tõenäosuse massi-funktsiooni funktsiooniga, mis on saadud transformeeritud muutujast[21],

Pidevate funktsioonide ja jaoks väidab Heisenbergi määramatuse printsiip, et

kus ja on ja erinevused, koos võrdsusega, mis on saavutatud sobivalt normaliseeritud Gaussi jaotusest.

Hirschmanni entroopialine ebakindlus omab kasulikku analoogi ka DFT puhul. Hirschmani määramatuse printsiip on väljendatud Shannoni entroopia poolest kahe tõenäosusfunktsiooni abil.[21]

Diskreetsel juhul on Shannoni entroopiad

ja

ja entroopialine määramatuse printsiip muutub

[22]

Reaalse sisendiga DFT[muuda | muuda lähteteksti]

Kui on reaalarvud, nagu nad on tavalises olukorras, siis DFT allub sümmeetriale:

  kus tähendab kompleksset konjugatsiooni.[23]

X0 ja XN/2 on reaalsed väärtused ja ülejäänud DFT on täielikult määratud ainult N/2-1 kompleksarvudega.[23]

Üldistatud DFT (nihkunud ja mittelineaarne faas)[muuda | muuda lähteteksti]

On võimalik nihutada teisenduse proovivõttu aja ja/või sageduspiirkonna mingi a ja b väärtuse võrra. Seda nimetatakse tavaliselt üldistatud DFT-ks (GDFT inglise keeles) või nihutatud DFT-ks. Üldistatud DFT omab analoogsed omadusi nagu tavaline DFT[24]:

Kõige tihedamini kasutatakse nihet proovi võrra. Tavaline DFT vastab perioodilisele signaalile nii aja kui ka sageduse domeenis, esitab vastu perioodilist signaali () ja vastupidi, kui . On olemas ka erijuht , mida on nimetatud paaritu aja ja sagedusega DFT-ks (O2 DFT inglise keeles). Selliseid teisendusi kasutatakse sümmeetriliste signaalide puhul, et esitada erinevaid piirsümmeetriad. Reaalsignaalide puhul vastavad need erinevatele siinus- ja koosinus-signaalidele.[25]

Teine huvitav juhtum on, kui , mida nimetatakse tsentreeritud DFT-ks (CDFT inglise keeles). See DFT omab kasulikku omadust: kui N on nelja korrutis, siis kõik neli tema ühisväärtust omavad võrdset mitmesust.[24]

Diskreetset Fourier' teisendust võib vaadelda z-teisenduse erijuhuna, mida hinnatakse ühikringil komplekstasandil; z-teisendused vastavad kompleksnihetele a ja b, nagu on näidatud eespool.[25]

Mitmemõõtmeline DFT[muuda | muuda lähteteksti]

Tavaline DFT tegeleb ühemõõtmelisega andmete massiiviga kuna see on funktsioon täpselt ühe diskreetse muutujaga n. Mitmemõõtmeline DFT tegeleb mitmemõõtmelise massiiviga ja avaldub d diskreetsete muutujatega funktsiooniks iga sees on defineeritud:

kus ja d väljundi indeksid on .[26] Natuke kompaktsemalt on see väljendatud kui vektor, kus ja on d-mõõtmelised vektorid indeksitega nullist , kus :

kus on ja summa tähistab pesastatud summeerimist üleval olevas valemis.[26]

Pöördvõrdeline mitmemõõtmeline DFT avaldub samamoodi nagu ühe mõõtme korral:

DFT väljendab sisendit sinusoidide superpositsiooniga, mitmemõõtmeline DFT väljendab sisendit tasandi lainete superpositsiooniga, või mitmemõõtmeliste sinusoididega. Ostsillatsiooni suund on ja amplituudid on . See lagunemine omab suurt tähtsust paljudel aladel, alustades digitaalsest pilditöötlusest (kahemõõtmeline) kuni diferentsiaalvõrrandite lahendamiseni. Tulemus on jagatud tasandite lainetele.[26]

Mitmemõõtmeline DFT võib olla arvutatud kui iga mõõtme ühemõõtmelise DFT-de kompositsioon. Kahemõõtmelise DFT puhul on sõltumatu ridade DFT-d (näiteks mööda ) arvutatud esimesena uueks massiiviks . Järgmisena sõltumatu veergude DFT-d (mööda ) arvutatakse, et saada lõpptulemust . Võib teha ka vastupidi ja esimesena arvutada veerud ja pärast read. Järjekord pole oluline, sest lõpus arvutatakse pesastatud summa[26].

Ühemõõtmelise DFT arvutamise algoritm on piisav selleks, et arvutada ka mitmemõõtmelised DFT-d. Selle algoritmi nimetuseks on rea-veeru algoritm. On olemas ka mõned teised algoritmid mitmemõõtmeliste DFT-de arvutamiseks.[26]

Reaalse sisendiga mitmemõõtmeline DFT[muuda | muuda lähteteksti]

Kui sisend koosneb reaalsetest arvudest , DFT väljund omab konjugatiivset sümmeetriat nagu ühemõõtmelisel juhul:

kus tärn tähendab kompleksset konjugatsiooni ja -is indeks on absoluutväärtus (iga jaoks).[26]

Kiire DFT[muuda | muuda lähteteksti]

Kiire Fourier' teisendus (Fast Fourier Transform = FFT) põhineb teisendamiseks vajalike arvutuste mahu vähendamises teatud (korduvate) tulemuste (korduva) ärakasutamise teel või mõne spetsiifilise vaheteisenduse kasutamise teel. Seetõttu on FFT reeglina kasutatav vaid diskreeditud funktsioonide ja signaalide puhul. Siiski on ka analoogtehnikas mõned signaalitöötluse võtted vaadeldavad kui FFT teatud vormid.[27]

FFT kasutatavusse ja FFT abil saadud tulemustesse tuleb seetõttu suhtuda vajaliku kriitilisusega, kuna lisaks diskreetmisest tulenevatele iseärasustele tuleb lisaks arvesse võtta veel ka FFT enda olemusest tulenevaid iseärasusi (lühike ajaintervall ja sellest tulenevalt nn. vaatluse akna(funktsiooni) kasutamine, sünkroonsuse probleemid).[27]

FFT kasutatavus on praktikas laialdane (heli- ja sidetehnika, jm.), kuna paljudel juhtudel kõrget täpsust selle mõõtetehnilises mõttes ei nõuta (heli puhul loetakse piisavaks 1dB ehk ~10% täpsust). Arvutuse täpsuse probleemid on aga üldjuhul lahendatavad.[27]

Kiire DFT arvutamiseks kasutatakse mitu algoritmi: Cooley-Tukey FFT, Prime-factor FFTBruun's FFTRader's FFT, ja Bluestein's FFT.[27]

Rakendused[muuda | muuda lähteteksti]

DFT on kasutatud paljudel aladel ja siin on näidatud ainult tähtsamad neist. Peaaegu kõik DFT rakendused otseselt põhinevad sellel põhimõttel, et DFT-d ja pöörd-DFT on võimalik efektiivselt arvutada Kiire Fourier' teisenduse abil .[28]

Spektraalanalüüs[muuda | muuda lähteteksti]

Kui DFT-d kasutatakse spektraalanalüüsiks, siis jada tavaliselt kujutab piiratud koguse ühtlaste aja vahedega paigutatud mingi signaali proove , kus t on aeg. Üleminek pidevalt ajalt proovidele muudab Fourier' teisendust Diskreetse aja Fourier teisenduseks (DTFT), mis tavaliselt tähendab deformeerimist (aliasing inglise keeles). Deformeerimise minimeerimiseks tuleb õigesti valida proovide võitmise sagedust, arvestades Nyquist-i sagedust. Samas, tuleb proovide jada konverteerida väga suurest(või lõpmatust) sobivaks, et vältida teist deformeerimist, nimetatud lekkimine, ehk resolutsiooni kaotamine DFT-s. Kui kättesaadav andmete hulk on liiga väike, või andmete töötlemiseks (vajaliku resolutsiooni leidmiseks) pole piisavalt aega, kasutatakse mitu DFT-d spektrogrammi tegemiseks. Tulemusena on võimsuse spekter kus esineb müra ja/või juhuslikud andmed, mida saab filtreerida mitu DFT tulemuste võrdlemisega. See protseduur vähendab spektri dispersiooni ja on nimetatud perioodgrammiks. Tuntud näited selle meetodi kasutamisest on Welchi ja Bartletti meetodid. Üldine meetod võimsuse spektri hindamiseks lärmaka signaali puhul on nimetatud spektraalne hindamine.[29]

DFT ise on lõplik moonutamise allikas, sest DFT on ainult diskreetne proovide võtmine pidevast funktsioonist. Seda on võimalik leevendada DFT resolutsiooni suurendamisega.[30]

Andmete pakkimine[muuda | muuda lähteteksti]

Digitaalse signaalitöötluse valdkond põhineb sagedusdomeenis toimuvates operatsioonides (Fourier' teisenduse tulemustes). Näiteks andmekaostega piltide töötlus ja heli pakkimise meetodid kasutavad DFT-d: signaal on lõigatud lühikesteks segmentideks (proovide võtmine), iga lõik on transformeeritud, ja siis peaaegu märkamatu kõrgesageduslikud Fourier' koefitsiendid, kõrvaldatakse. Dekompressor arvutab pöördtransformatsiooni, mis põhineb uutel DFT väärtustel. Pakkimise rakendused kasutavad sageli spetsialiseeritud DFT vormi, diskreetse koosinus teisendust, või juba seda modifitseeritud versiooni. Mõned suhteliselt hiljutised kokkupakkimisalgoritmid kasutavad nn laineke teisendust, mis annab ühtlasema kompromissi aja ja sageduse domeenide vahel. JPEG2000 juhul, see väldib vigaste piltide tekkimist, mis ilmuvad, kui pildid on liiga palju tihendatud algse JPEG pakkimise tõttu.[31]

Osatuletistega diferentsiaalvõrrandid[muuda | muuda lähteteksti]

Diskreetne Fourier' teisendust kasutatakse sageli osatuletistega diferentsiaalvõrrandite ahendamisel, kus DFT-d kasutatakse Fourier' rea liigikaudseks arvutamiseks. Selle lähenemise eeliseks on see, et signaali laiendatakse kompleks eksponentideks , mis on diferentseerimise tulemuste funktsioonide hulk: . Seega Fourier' esindamises, diferentseerimine on lihtne – see on korrutamine väärtusega . Lineaarne diferentsiaalvõrrand konstantsete kordajatega muundub kergesti lahendatavaks algebraliseks võrrandiks. Tulemuse tagasi aja domeeni teisendamiseks tuleb kasutada pöörd teisendust. Seda ka nimetatakse spektraalmeetodiks ehk spektraalanalüüsiks.[32]

Polünoomiline korrutamine[muuda | muuda lähteteksti]

Oletame, et me soovime arvutada polünoomi c(x) = a(x) · b(x). Tavaline koefitsientide c väljend hõlmab lineaarset (atsüklilist) konvolutsiooni. Seda saab kirjutada tsüklilise konvolutsiooni kasutades, kui võtta koefitsient vektoriteks a(x) ja b(x) pideva väljendiga esimeseks, seejärel lisades nulle nii, et tulemus koefitsient vektorid a ja b on mõõtmes d > deg(a(x)) + deg(b(x)). Siis,

Kus c on koefitsientide vektor c(x), ja konvolutsiooni operaator on

Aga konvolutsioon muutub korrutamiseks DFT all:

Siin on vektor võetud elemendi kaupa. Seega polünoomi koefitsiendid c(x) on vaid 0, ..., deg(a(x)) + deg(b(x)) ja koefitsient vektorist on

Kiire DFT algoritmi kasutuses ajaline keerukus on O (N log N). Teisenduse operatsiooni jaoks tavaliselt kasutatakse Cooley-Tukey FFT algoritmi, sest see on lihtne ja suhteliselt kiire. Sel juhul peab olema väiksem täisarv, mis on suurem, kui sisend-polünoomi algtegurite summa.[33]

Suurte täisarvude korrutamine[muuda | muuda lähteteksti]

Kõige kiirem tuntud algoritmidest väga suurte täisarvude korrutamiseks on polünoomide korrutamise meetod. Täisarve võib käsitleda, kui polünoomide väärtused väärtustatud konkreetse arvu alusel, koos polünoomi koefitsientidega, mis on selle arvu numbrid. Pärast polünoomilist korrutamist lõpetab korrutamise suhteliselt madala keerukusega nn carry-paljundamine.[34]

Konvolutsioon[muuda | muuda lähteteksti]

Kuna konvolutsioon on sagedus domeenis lihtsalt korrutamine, siis palju lihtsam on teisendada sisendid DFT abil, järgmisena teha korrutist ja viimasena teisendada tulemust pöördteisendusega tagasi aja domeeni.[35]

Olulised DFT paarid[muuda | muuda lähteteksti]

Nimetus
Nihe
Reaalne DFT
Geomeetriline progressioon
Binominaalne teoreem
on W punktiline ristkujuline aknafunktsioon keskpunktiga n=0, kus W on paaritu reaalarv, ja on sinc funktsioon.
Skaleeritud Gaussi funktsioonide diskreetimine ja perioodiline liitmine, kus .

Üldistused[muuda | muuda lähteteksti]

Esinduse teooria[muuda | muuda lähteteksti]

DFT-d võib tõlgendada kui kompleksset piiratud tsüklilise rühma esinduse teooriat. Teisisõnu, n kompleksarvude jada võib olla tõlgendatud nägu n-mõõtmeline kompleksne ruum Cn või lõplikku tsüklilise kompleksarvude rühma funktsioon f, ZnC. f on tsükliline piiratud rühma klassi funktsioon, ning seda saab väljendada taandumatu tähemärkide lineaarse kombinatsioonina selles rühmas. Need märgid on ühe juured.[36]

Muud valdkonnad[muuda | muuda lähteteksti]

Palju DFT omadustest sõltuvad ainult sellest, et on primitiivsed ühe juured. Need omadused on täielikkus, ortogonaalsus, Plancherel/Parseval, perioodilisus, nihe, konvolutsioon ja paljud kiire DFT algoritmid. Seetõttu DFT-d võib defineerida ühe juure mõiste kasutades ka muudes valdkondades. Neid üldistusi tavaliselt nimetatakse number-teoreetilised teisendused (number-theoretic transforms (NTT)).[37]

Muud piiratud rühmad[muuda | muuda lähteteksti]

Tavaline DFT tegeleb x0, x1, …, xN−1 kompleksarvude jadaga, mis võib olla vaadeldud funktsioonina {0, 1, …, N − 1} → C. Mitmemõõtmeline DFT tegeleb mitmemõõtmeliste jadadega, mis võivad olla vaadeldud funktsioonidena

Siis tavalist DFT-d vaadeldakse tsüklilise rühma Fourier' teisendusena, ja mitmemõõtmeline DFT on tsükliliste rühmade summa Fourier' teisendus.[38]

Märkused[muuda | muuda lähteteksti]

  1. Selles kontekstis defineeritakse nägu N-is primitiivne ühe juur, , saab järgmist vormi:
  2. DFT definitsiooni saab ka kirjeldada DFT maatriksi abil nagu lineaarne transformatsioon piiratud-mõõtmelises vektorruumis. Kui DFT on skaleeritud sobivalt, siis see muutub ühtlaseks maatriksiks ja XK on x koefitsiendid ortonormaalsel alusel.

Viited[muuda | muuda lähteteksti]

  1. 1,0 1,1 Smith, Steven W. (1999). "Chapter 8: The Discrete Fourier Transform". The Scientist and Engineer's Guide to Digital Signal Processing (trükk: Second). San Diego, Calif.: California Technical Publishing. ISBN 0-9660176-3-3. Vaadatud 31-10-2016. 
  2. Smith, Steven W. (1999). "Chapter 8: The Discrete Fourier Transform". The Scientist and Engineer's Guide to Digital Signal Processing (trükk: Second). San Diego, Calif.: California Technical Publishing. ISBN 0-9660176-3-3. Vaadatud 31-10-2016. 
  3. >Brigham, E. Oran (1988). The fast Fourier transform and its applications. Englewood Cliffs, N.J.: Prentice Hall. ISBN 0-13-307505-2. 
  4. Strang, Gilbert (1994). "Wavelets". American Scientist 82 (3): 253. Vaadatud 31-10-2016. "This is the most important numerical algorithm of our lifetime..." 
  5. Sahidullah; Saha, Goutam (2012). "A Novel Windowing Technique for Efficient Computation of MFCC for Speaker Recognition". IEEE Signal Processing Letters 20: 149–152. Vaadatud 31-10-2016. 
  6. 6,0 6,1 6,2 Бахурин Сергей (2015). "Дискретное преобразование Фурье (ДПФ)". Vaadatud 31-10-2016. 
  7. J. Cooley, P. Lewis, and P. Welch (1969). "The finite Fourier transform". IEEE Trans. Audio Electroacoustics 17 (2): 77–85. 
  8. Oppenheim, Alan V.; Schafer, R. W.; and Buck, J. R. (1999). Discrete-time signal processing. Upper Saddle River, N.J.: Prentice Hall. 
  9. Ricardo, Henry J. (2016). A Modern Introduction to Differential Equations. p. 428. 
  10. 10,0 10,1 10,2 Бахурин Сергей (2015). "Свойства дискретного преобразования Фурье (ДПФ)". Vaadatud 31-10-2016. 
  11. 11,0 11,1 P. Duhamel; B. Piron; J. M. Etcheto (1988). "On computing the inverse DFT". IEEE Trans. Acoust., Speech and Sig. Processing 36 (2): 285–286. 
  12. 12,0 12,1 Juan G. Vargas-Rubio; Balu Santhanam (2005). "On the multiangle centered discrete fractional Fourier transform". IEEE Sig. Proc. Lett. 12 (4): 273–276. 
  13. 13,0 13,1 Nussbaumer, Henri J. (1982). Fast Fourier Transform and Convolution Algorithms. (trükk: Second Corrected and Updated Edition.). Springer-Verlag. pp. pp. 134–137. 
  14. Arfken, G. (1985) "Convolution Theorem." §15.5 in Mathematical Methods for Physicists, 3rd ed. Orlando, FL: Academic Press, pp. 810-814, Vaadatud 2016-10-31
  15. 15,0 15,1 G.B. Wright, M. Javed, H. Montanelli, and L.N. Trefethen,(2015), "Extension of Chebfun to periodic functions," SIAM. J. Sci. Comput., 37 , C554-C573 Vaadatud 31-10-2016
  16. 16,0 16,1 Kamisetty Ramam Rao; Patrick C. Yip (2000). The Transform and Data Compression Handbook. CRC Press. ISBN 978-1-4200-3738-8. Vaadatud 31-10-2016. 
  17. Julius O. Smith (2007). Mathematics of the Discrete Fourier Transform (DFT): With Audio Applications. Julius Smith. ISBN 978-0-9745607-4-8. Vaadatud 31-10-2016. 
  18. TE 302 DISCRETE SIGNALS AND SYSTEMS 2004, Vaadatud 31-10-2016
  19. 19,0 19,1 J. H. McClellan; T. W. Parks (1972). "Eigenvalues and eigenvectors of the discrete Fourier transformation". IEEE Trans. Audio Electroacoust. 20 (1): 66–74. 
  20. Magdy Tawfik Hanna, Nabila Philip Attalla Seif, and Waleed Abd El Maguid Ahmed (2004). "Hermite-Gaussian-like eigenvectors of the discrete Fourier transform matrix based on the singular-value decomposition of its orthogonal projection matrices". IEEE Trans. Circ. Syst. I 51 (11): 2245–2254. 
  21. 21,0 21,1 Massar, S.; Spindel, P. (2008). "Uncertainty Relation for the Discrete Fourier Transform". Physical Review Letters 100 (19). 
  22. DeBrunner, Victor; Havlicek, Joseph P.; Przebinda, Tomasz; Özaydin, Murad (2005). "Entropy-Based Uncertainty Measures for , and With a Hirschman Optimal Transform for ". IEEE Transactions on Signal Processing 53 (8): 2690. Vaadatud 31-10-2016. 
  23. 23,0 23,1 Donoho, D.L.; Stark, P.B (1989). "Uncertainty principles and signal recovery". SIAM Journal on Applied Mathematics 49 (3): 906–931. 
  24. 24,0 24,1 Santhanam, Balu; Santhanam, Thalanayar S. (1988) "Discrete Gauss-Hermite functions and eigenvectors of the centered discrete Fourier transform", Proceedings of the 32nd IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2007, SPTM-P12.4), vol. III, pp. 1385-1388. Vaadatud 31-10-2016
  25. 25,0 25,1 Akansu, Ali N.; Agirman-Tosun, Handan (2010) "Generalized Discrete Fourier Transform With Nonlinear Phase", IEEE Transactions on Signal Processing, vol. 58, no. 9, pp. 4547-4556, Vaadatud 31-10-2016
  26. 26,0 26,1 26,2 26,3 26,4 26,5 Richard tolimieri; Myoung An; Chao Lu (2012). Mathematics of Multidimensional Fourier Transform Algorithms. Springer Science & Business Media. ISBN 978-1-4684-0205-6. Vaadatud 31-10-2016. 
  27. 27,0 27,1 27,2 27,3 C. Sidney Burrus, , Ivan Selesnick, Markus Pueschel, Matteo Frigo, and Steven G. Johnson (2008). Fast Fourier Transforms, Connexions, Vaadatud 31-10-2016
  28. J. Cooley, P. Lewis, and P. Welch (1969). "The finite Fourier transform". IEEE Trans. Audio Electroacoustics 17 (2): 77–85. 
  29. Smith, Steven W. (1999). "Chapter 8: The Discrete Fourier Transform". The Scientist and Engineer's Guide to Digital Signal Processing (trükk: Second). San Diego, Calif.: California Technical Publishing. ISBN 0-9660176-3-3. Vaadatud 31-10-2016. 
  30. Shamgar Gurevich; Ronny Hadani; Nir Sochen (2008). "The finite harmonic oscillator and its applications to sequences, communication and radar". IEEE Transactions on Information Theory 54 (9): 4239–4253. 
  31. David Salomon (20-03-2007). Data Compression: The Complete Reference. Springer Science & Business Media. ISBN 978-1-84628-603-2. Vaadatud 31-10-2016. 
  32. Nakhle H. Asmar (2016). "10". Partial Differential Equations with Fourier Series and Boundary Value Problems: Third Edition. Courier Dover Publications. ISBN 978-0-486-80737-9. Vaadatud 31-10-2016. 
  33. J.A. Storer (2001). "5". An Introduction to Data Structures and Algorithms. Springer Science & Business Media. ISBN 978-0-8176-4253-2. Vaadatud 31-10-2016. 
  34. Umberto Cherubini; Giovanni Della Lunga; Sabrina Mulinacci; Pietro Rossi (2010). Fourier Transform Methods in Finance. John Wiley & Sons. p. 208. ISBN 978-0-470-68492-4. Vaadatud 31-10-2016. 
  35. Smith, Stephen W (1997). "13.Convolution". The Scientist and Engineer's Guide to Digital Signal Processing (trükk: 1). California Technical Publishing. ISBN 0966017633. Vaadatud 31-10-2016. 
  36. Serre, Jean-Pierre: ''Linear Representations of Finite Groups.'' Springer Verlag, New York 1977, ISBN 0-387-90190-6.Jean-Pierre Serre (2012). Linear Representations of Finite Groups. Springer Science & Business Media. ISBN 978-1-4684-9458-7. Vaadatud 31-10-2016. 
  37. Vladimir P. Gerdt; Wolfram Koepf; Ernst W. Mayr; Evgenii V. Vorozhtsov (2013). Computer Algebra in Scientific Computing: 15th International Workshop, CASC 2013, Berlin, Germany, September 9-13, 2013, Proceedings. Springer. ISBN 978-3-319-02297-0. Vaadatud 31-10-2016. 
  38. Fourier Analysis on Finite Groups and Applications, ISBN 978-0-521-45718-7 

Välislingid[muuda | muuda lähteteksti]