Diskreetne Fourier' teisendus

Diskreetne Fourier' teisendus (lühend DFT inglise keele sõnadest "discrete Fourier transform") on pideva Fourier' teisenduse vaste digiteeritud (ajas diskreeditud ja nivoos kvanditud) funktsioonide ja signaalide jaoks. Teatud tingimustel 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.
DFT on kõige olulisem diskreetne teisendus, mida kasutatakse Fourier' analüüsi teostamiseks paljudes praktilistes rakendustes. Signaalitöötluses on iga signaal funktsioon, millest võetakse proove (lugemeid signaali väärtustest) diskreetimissagedustel. Analüüsi objektideks võivad olla näiteks helilaine, raadiosignaal või muutuvad temperatuurinäidud. Pilditöötluses võivad proovid olla pikslite väärtused rasterkujutise igas reas või veerus. DFT-d kasutatakse ka selleks, et lahendada efektiivselt diferentsiaalvõrrandeid ja teha teisi toiminguid, nagu konvolutsioon ja suurte arvude korrutamine.
Kuna DFT tegeleb piiratud andmemahtudega, saab seda rakendada, arvutades numbriliste algoritmide abil või kasutades sihtotstarbelist riistvara. Need rakendused kasutavad tavaliselt Fourier' kiirteisendust ehk kiiret Fourier' teisendust ("Fast Fourier Transform", FFT), mis põhineb teisendamiseks vajalike arvutuste mahu vähendamisel teatud (korduvate) tulemuste (korduva) ärakasutamise teel või mõne spetsiifilise vaheteisenduse kasutamise teel.
Mõiste.
"N" kompleksarvude jada formula_1 teisendatakse N-perioodiliseks kompleksarvude jadaks:
formula_2 (täisarvud)   
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.
Diskreetne Fourier' teisendus on tavaliselt tähistatud tähega formula_3, kus formula_4 või formula_5 või formula_6.
Definitsioonivõrrandit võib tõlgendada või tuletada mitmel viisil, näiteks:
formula_8
mis on ka N-perioodiline. formula_9 domeenis on see definitsiooni valemi pöördteisendus. Selle tõlgenduse järgi on iga formula_10 kompleksne number, mis kodeerib funktsiooni formula_11 komplekssesse siinuselisse komponenti  formula_12 nii amplituudi kui ka faasi. Siinuse sagedus on k/N. Amplituud ja faas vastavad võrranditele:
formula_13
formula_14
kus atan2 on arkustangensi funktsioon kahe argumendi jaoks.
Euleri valemi abil saab DFT valemi teisendada trigonomeetriliseks vormiks, mida kasutatakse inseneride arvutlustes ja infotehnoloogias:
Fourier teisendus:
formula_15
Pöördteisendus:
formula_16
kus
formula_17 on proovide arv
formula_18 on hetkel töödeldava proovi number (0, ..., formula_19)
formula_11 on signaali väärtus hetkel formula_18
formula_22 on sagedus (0 Hz kuni formula_19 Hz) töötlemise hetkel
formula_10 on sagedusega formula_22 signaali (amplituudi ja faasi väljendav kompleksarv.
Omadused.
Täielikkus.
Diskreetne Fourier' teisendus on pööratav lineaarne teisendus
formula_26
kus formula_27 on kompleksarvude hulk. See tähendab, et iga "N" &gt; 0, "N"-mõõtmeline kompleksvektor omab DFT-d ja PDFT-d (pöördteisendust), mis on omakorda N-mõõtmelised kompleksvektorid.
Ortogonaalsus.
Vektorid formula_28 moodustavad ortogonaalse baasi üle N-mõõtmeliste kompleksvektorite hulga:
formula_29
kusformula_30 on Kronecker delta. (Viimane samm on triviaalsete formula_31 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.
Planchereli teoreem ja Parsevali teoreem.
Kui "X""k" ja "Y""k" on vastavalt "x""n" ja "y""n" teisendused, siis ütleb Parsevali teoreem, et:
formula_32
kus tärn tähendab kompleksset konjugatsiooni. Parsevali teoreemi selline erijuht, kus "x""n" = "y""n", on Planchereli teoreem, mis väidab:
formula_33
Perioodilisus.
Perioodilisust võib näha otse definitsioonist:
 formula_34
Samas on näha, et pöördteisenduse võrrand viib perioodilisele laiendamisele.
Nihe.
Korrutades formula_11 lineaarse faasiga formula_36 mingi täisarvu "m" järgi vastab nihkele väljundis formula_10: formula_10, mis asendatakse formula_39, kus indeks on tõlgendatud kui absoluutväärtus "N" (perioodiliselt). Samamoodi nihe sisendis formula_11 vastab väljundi formula_10 korrutamisele lineaarse faasiga. Matemaatiliselt, kui formula_42 tähistab vektorit x, siis
kui formula_43
siis formula_44
ja formula_45
Ringkonvolutsiooni teoreem ja ristkorrelatsiooni teoreem.
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. Kui vaadelda DTF-d ja pöörd-DTF-d, võib seda kirjutada järgmiselt:
formula_46
mis on konvolutsioon formula_47 ja formula_48 jadade vahel pikendatud perioodilise liitmisega:
formula_49
Ristkorrelatsioon formula_47  ja  formula_51  vahel on selline:
formula_52
Konvolutsiooni teoreemi duaalsus.
Võib ka tõestada, et:
formula_53 mis on ringikujuline konvolutsioon formula_54 ja formula_55 vahel.
formula_56 paaris "N"-i jaoks,
formula_57 paaritu "N"-i jaoks,
Trigonomeetriline interpolatsiooni polünoom.
kus koefitsiendid "X""k" on eespool oleva "x""n" DFT ja rahuldavad interpoleerimist formula_58 formula_59 jaoks.
Paaris "N-i" puhul tuleb tähele panna, et Nyquist komponenti formula_60 käsitletakse eraldi.
Ühtne DFT.
Teise võimalusena saab DFT-d väljendada DFT maatriksi abil ehk Vandermonde maatriksina, mille võttis kasutusele Sylvester 1867. aastal.
formula_61
kus
formula_62
on primitiivne "N"-is ühe juur.
Pöördteisendus on selle maatriksi pöördmaatriks:
formula_63
Ühtse normaliseerimise konstantidega formula_64 saab DFT ühtseks teisenduseks, mis on defineeritud ühtse maatriksi abil:
formula_65
formula_66
formula_67
kus "det()" on maatriksi determinant. Determinant on omaväärtuste tulemus, mis on kas formula_68 või formula_69. Ortogonaalsust väljendab nüüd ortonormaalsuse tingimus.
formula_70
Kui X on ühtne vektori x DFT, siis
formula_71
ja Planchereli teoreem on väljendatud niimoodi:
formula_72
Erijuhul formula_73 on see Parsevali teoreem
formula_74
Pöördvõrdelise DFT avaldamine DFT kaudu.
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.
formula_75
Teiseks võib ka ümber pöörata sisendid ja väljundid:
formula_76
Viimaseks võime vahetada omavahel reaal- ja imaginaarsignaali osad:
formula_77
Kus "swap"(formula_11) on formula_11, milles on reaal- ja imaginaar-osad omavahel niimoodi vahetatud: formula_80 "swap"(formula_11) on formula_82. Samas, "swap"(formula_11) on võrdne formula_84.
Omaväärtused ja omavektorid.
DFT maatriksi omaväärtused on lihtsad ja hästi tuntud, kusjuures omavektorid on keerulised ja neid pole veel täiesti uuritud.
Kui DFT ühtne vorm formula_85 pikkusega "N" on selline":"
formula_86
See maatriks vastab maatriksite polünomiaalsele võrrandile:
formula_87
See tähendab, et omaväärtused formula_88 võrrandile on:
formula_89
Samas on formula_85 omaväärtused neljandad ühe juured: formula_88 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.
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:
Määramatuse printsiip.
Kui juhuslik suurus "Xk" on piiratud:
formula_92
siis 
formula_93 
võib esindada diskreetse tõenäosuse "n"-i massi-funktsiooni koos tõenäosuse massi-funktsiooni funktsiooniga, mis on saadud transformeeritud muutujast,
formula_94
Pidevate funktsioonide formula_95 ja formula_96 jaoks väidab Heisenbergi määramatuse printsiip, et
formula_97
kus formula_98 ja formula_99 on formula_100 ja formula_101 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.
Diskreetsel juhul on Shannoni entroopiad 
formula_102
ja
formula_103
ja entroopialine määramatuse printsiip muutub
formula_104
Reaalse sisendiga DFT.
Kui formula_105 on reaalarvud, nagu nad on tavalises olukorras, siis DFT allub sümmeetriale:
formula_106  kus formula_107 tähendab kompleksset konjugatsiooni.
"X""0" ja "X""N/2" on reaalsed väärtused ja ülejäänud DFT on täielikult määratud ainult "N/2-1" kompleksarvudega.
Üldistatud DFT (nihkunud ja mittelineaarne faas).
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:
formula_108
Kõige tihedamini kasutatakse nihet formula_109 proovi võrra. Tavaline DFT vastab perioodilisele signaalile nii aja kui ka sageduse domeenis, formula_110 formula_111 esitab vastu perioodilist signaali (formula_112) ja vastupidi, kui formula_113 formula_114. On olemas ka erijuht formula_115, 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.
Teine huvitav juhtum on, kui formula_116, 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.
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.
Mitmemõõtmeline DFT.
Tavaline DFT tegeleb ühemõõtmelisega andmete massiiviga formula_11 kuna see on funktsioon täpselt ühe diskreetse muutujaga "n". Mitmemõõtmeline DFT tegeleb mitmemõõtmelise massiiviga formula_118 ja avaldub "d" diskreetsete muutujatega funktsiooniks formula_119 iga formula_120 formula_121 sees on defineeritud:
formula_122
kus formula_123 ja "d" väljundi indeksid on formula_124. Natuke kompaktsemalt on see väljendatud kui vektor, kus formula_125 ja formula_126 on "d"-mõõtmelised vektorid indeksitega nullist formula_127, kus formula_128:
formula_129
kus formula_130 on formula_131 ja summa tähistab pesastatud summeerimist üleval olevas valemis.
Pöördvõrdeline mitmemõõtmeline DFT avaldub samamoodi nagu ühe mõõtme korral:
formula_132
DFT väljendab sisendit formula_11 sinusoidide superpositsiooniga, mitmemõõtmeline DFT väljendab sisendit tasandi lainete superpositsiooniga, või mitmemõõtmeliste sinusoididega. Ostsillatsiooni suund on formula_134 ja amplituudid on formula_135. See lagunemine omab suurt tähtsust paljudel aladel, alustades digitaalsest pilditöötlusest (kahemõõtmeline) kuni diferentsiaalvõrrandite lahendamiseni. Tulemus on jagatud tasandite lainetele.
Mitmemõõtmeline DFT võib olla arvutatud kui iga mõõtme ühemõõtmelise DFT-de kompositsioon. Kahemõõtmelise DFT puhul formula_136 on formula_137sõltumatu ridade DFT-d (näiteks mööda formula_138) arvutatud esimesena uueks massiiviks formula_139. Järgmisena formula_140 sõltumatu veergude DFT-d (mööda formula_141) arvutatakse, et saada lõpptulemust formula_142. Võib teha ka vastupidi ja esimesena arvutada veerud ja pärast read. Järjekord pole oluline, sest lõpus arvutatakse pesastatud summa.
Ü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.
Reaalse sisendiga mitmemõõtmeline DFT.
Kui sisend koosneb reaalsetest arvudest formula_118, DFT väljund omab konjugatiivset sümmeetriat nagu ühemõõtmelisel juhul:
formula_144
kus tärn tähendab kompleksset konjugatsiooni ja formula_120-is indeks on absoluutväärtus formula_146 (iga formula_147 jaoks).
Kiire DFT.
Kiire Fourier' teisendus (Fast Fourier Transform = FFT) põhineb teisendamiseks vajalike arvutuste mahu vähendamisel 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.
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).
FFT kasutatavus on praktikas laialdane (heli- ja sidetehnika, jm), kuna paljudel juhtudel suurt 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.
Kiire DFT arvutamiseks kasutatakse mitu algoritmi: Cooley-Tukey FFT, Prime-factor FFT, Bruun's FFT, Rader's FFT, ja Bluestein's FFT.
Rakendused.
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 .
Spektraalanalüüs.
Kui DFT-d kasutatakse spektraalanalüüsiks, siis formula_148 jada tavaliselt kujutab piiratud koguse ühtlaste aja vahedega paigutatud mingi signaali proove formula_149, kus "t" on aeg. Üleminek pidevalt ajalt proovidele muudab formula_149 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.
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.
Andmete pakkimine.
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.
Osatuletistega diferentsiaalvõrrandid.
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 formula_151, mis on diferentseerimise tulemuste funktsioonide hulk: formula_152. Seega Fourier' esindamises, diferentseerimine on lihtne – see on korrutamine väärtusega formula_153. 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.
Polünoomiline korrutamine.
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" &gt; deg("a"("x")) + deg("b"("x")). Siis,
formula_154
Kus c on koefitsientide vektor "c"("x"), ja konvolutsiooni operaator formula_155 on
formula_156
Aga konvolutsioon muutub korrutamiseks DFT all:
formula_157
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
formula_158
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 formula_159 olema väiksem täisarv, mis on suurem, kui sisend-polünoomi algtegurite summa.
Suurte täisarvude korrutamine.
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 väikese keerukusega nn "carry"-paljundamine.
Konvolutsioon.
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.
Üldistused.
Esinduse teooria.
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 C"n" või lõplikku tsüklilise kompleksarvude rühma funktsioon f, Z"n" → C. "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.
Muud valdkonnad.
Palju DFT omadustest sõltuvad ainult sellest, et formula_160 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)).
Muud piiratud rühmad.
Tavaline DFT tegeleb "x"0, "x"1, …, "x""N"−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
formula_161
Siis tavalist DFT-d vaadeldakse tsüklilise rühma Fourier' teisendusena, ja mitmemõõtmeline DFT on tsükliliste rühmade summa Fourier' teisendus.