Vikipedio:Projekto matematiko/Rapida fourier-a konverto

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Rapida fourier-a konverto
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

rapida fourier-a konverto (_FFT_) estas kompetenta algoritmo al komputi la diskreta fourier-a konverto (_DFT_) kaj ĝia inverso. _FFTs_ estas de granda graveco al larĝa (diversaj, diversaĵo) de aplikoj, de cifereca signal-prilaborado al solvantaj partaj diferencialaj ekvacioj al (algoritmoj, algoritmas) por rapide multiplikante granda (entjeroj, entjeras). Ĉi tiu artikolo priskribas la (algoritmoj, algoritmas), kies estas multaj; vidi diskreta fourier-a konverto por propraĵoj kaj aplikoj de la (konverti, konverto).

Estu x₀, ...., x_n-1 esti kompleksaj nombroj. La _DFT_ estas difinita per la formulo

$f_j = \sum_{k=0}^{n-1} x_k e^{-{2\pi i \over n} jk } \qquad j = 0,\dots,n-1.$

(Komputanta, Pritaksanta) ĉi tiuj (sumoj, sumas) rekte devus preni O(n²) aritmetika (operacioj, operacias) (vidi Granda a skribmaniero). _FFT_ estas algoritmo al komputi la sama rezulto en nur O(n logo n) (operacioj, operacias). En ĝenerala, tia (algoritmoj, algoritmas) dependi sur la faktorigo de n, sed (kontraŭ populara _misconception_) estas O(n logo n) _FFTs_ por ĉiuj n, (eĉ, ebena, para) primo n.

Ekde la inverso _DFT_ estas la sama kiel la _DFT_, sed kun la kontraŭa signo en la eksponento kaj 1/n faktoro, (ĉiu, iu) _FFT_ algoritmo povas facile esti adaptita por ĝi kiel bone.

Enhavo

1 La _Cooley_-_Tukey_ algoritmo
2 Alia _FFT_ (algoritmoj, algoritmas)
3 _FFT_ (algoritmoj, algoritmas) specialigita por (reala, reela) kaj/aŭ simetriaj datumoj
4 Akurateco kaj proksimumaj kalkuladoj
5 Multdimensia _FFT_ (algoritmoj, algoritmas)
6 Referencoj
7 Ekstera (ligoj, ligas)

[redaktu] La _Cooley_-_Tukey_ algoritmo

Ĉefa artikolo: _Cooley_-_Tukey_ _FFT_ algoritmo.

Per malproksime la plej komuna _FFT_ estas la _Cooley_-_Tukey_ algoritmo. Ĉi tiu estas dividu kaj regu algoritmo (tiu, ke, kiu) rekursie rompas suben _DFT_ de (ĉiu, iu) _composite_ amplekso n = n₁n₂ enen multaj (pli minuskla, pli malgranda) _DFTs_ de ampleksoj n₁ kaj n₂, laŭ kun O(n) (multiplikoj, multiplikas) per komplekso (radikoj, radikas) de unueco tradicie (nomita, vokis) _twiddle_ (faktoroj, faktoras).

Ĉi tiu maniero (kaj la ĝenerala ideo de _FFT_) estis popularigita per eldono de J. W. _Cooley_ kaj J. W. _Tukey_ en 1965, sed ĝi estis poste esplorita (tiu, ke, kiu) tiuj du (aŭtoroj, aŭtoras) havita sendepende rao-inventita algoritmo sciata al Carl Friedrich Gauss ĉirkaŭ 1805 (kaj sinsekve _rediscovered_ kelkfoje en (limigita, limigis) (formoj, formas)).

La plej konata uzi de la _Cooley_-_Tukey_ algoritmo estas al dividi la (konverti, konverto) enen du (pecoj, pecas) de amplekso $n / 2$ je ĉiu (ŝtupo, paŝi), kaj estas pro tio (limigita, limigis) al povo-de-du ampleksoj, sed (ĉiu, iu) faktorigo povas esti uzita en ĝenerala (kiel estis sciata al ambaŭ Gaŭso kaj _Cooley_/_Tukey_). Ĉi tiuj estas (nomita, vokis) la bazo-2 kaj (miksita, miksis)-bazo (okazoj, skatoloj, kestoj, kestas, okazas), respektive (kaj alia (rikordaj kazoj, variantoj, variantas) havi ilia posedi (nomoj, nomas) kiel bone). Kvankam la baza ideo estas rekursie, plej tradicia (realigoj, realigas) reordigi la algoritmo al eviti eksplicita rekursio. Ankaŭ, ĉar la _Cooley_-_Tukey_ algoritmo rompas la _DFT_ enen (pli minuskla, pli malgranda) _DFTs_, ĝi povas esti kombinita arbitre kun (ĉiu, iu) alia algoritmo por la _DFT_, kiel tiuj priskribis pli sube.

[redaktu] Alia _FFT_ (algoritmoj, algoritmas)

Ĉefa (artikoloj, artikloj): Primo-faktora FFT algoritmo, _Bruun_'s _FFT_ algoritmo, _Rader_'s _FFT_ algoritmo, _Bluestein_'s _FFT_ algoritmo.

Estas alia _FFT_ (algoritmoj, algoritmas) klara de _Cooley_-_Tukey_. Por $n = n 1 n 2$ kun interprimo $n 1$ kaj $n 2$ , unu povas uzi la Primo-Faktoro (Bona-Tomaso) algoritmo (_PFA_), bazita sur la Ĉinia Resta Teoremo, al faktorigi la _DFT_ simile al _Cooley_-_Tukey_ sed sen la _twiddle_ (faktoroj, faktoras). La _Rader_-_Brenner_ algoritmo (1976) estas _Cooley_-_Tukey_Eca faktorigo sed kun pure imaginara _twiddle_ (faktoroj, faktoras), reduktanta (multiplikoj, multiplikas) je la kosti de (multigita, pligrandiĝita) (aldonoj, aldonas, adicioj, adicias) kaj reduktis cifereca stabileco. (Algoritmoj, Algoritmas) (tiu, ke, kiu) rekursie faktorigi la _DFT_ enen (pli minuskla, pli malgranda) (operacioj, operacias) escepte _DFTs_ inkluzivi la _Bruun_ kaj _QFT_ (algoritmoj, algoritmas). (La _Rader_-_Brenner_ kaj _QFT_ (algoritmoj, algoritmas) estita proponita por povo-de-du ampleksoj, sed ĝi estas ebla (tiu, ke, kiu) ili povis esti adaptita al ĝenerala _composite_ $n$ . _Bruun_'s algoritmo aplikas al ajna (eĉ, ebena, para) _composite_ ampleksoj.) _Bruun_'s algoritmo, en aparta, estas bazita sur (interpretado, interpretanta) la _FFT_ kiel rekursie faktorigo de la polinomo $z n - 1$ , ĉi tie enen (reala, reela)-koeficiento (polinomoj, polinomas) de la (formo, formi) $z m - 1$ kaj $z 2 m + a z m + 1$ . Alia polinoma starpunkto estas ekspluatita per la _Winograd_ algoritmo, kiu faktorigas $z n - 1$ enen _cyclotomic_ (polinomoj, polinomas)—ĉi tiuj ofte havi koeficientoj de 1, 0, aŭ −1, kaj pro tio postuli kelkaj (se (ĉiu, iu)) (multiplikoj, multiplikas), (do, tiel) _Winograd_ povas kutimi ricevi minimuma-multipliko _FFTs_ kaj estas ofte kutima trovi kompetenta (algoritmoj, algoritmas) por malgranda (faktoroj, faktoras). Ja, _Winograd_ montris (tiu, ke, kiu) la _DFT_ povas esti komputita kun nur $O (n)$ (multiplikoj, multiplikas), kondukante al pruvita _achievable_ suba baro sur la nombro de (malracia, malracionala) (multiplikoj, multiplikas) por povo-de-du ampleksoj; bedaŭrinde, ĉi tiu venas je la kosti de multaj pli (aldonoj, aldonas, adicioj, adicias), _tradeoff_ jam ne preferable sur moderna (proceziloj, procezas, traktiloj, traktas, procesoroj, procesoras, datumtraktiloj, datumtraktas) kun aparataro (multiplikantoj, multiplikantas). En aparta, _Winograd_ ankaŭ (konstruas, faras) uzi de la _PFA_ kaj ankaŭ algoritmo per _Rader_ por _FFTs_ de primo ampleksoj. _Rader_'s algoritmo, ekspluatanta la ekzisto de generilo por la multiplika grupo module primo $n$ , ekspresoj _DFT_ de prima amplekso $n$ kiel cikla rulumo de (_composite_) amplekso $n - 1$ , kiu povas tiam esti komputita per paro de ordinara _FFTs_ tra la ruluma teoremo (kvankam _Winograd_ uzas aliaj rulumaj manieroj). Alia primo-amplekso _FFT_ estas pro al L. Mi. _Bluestein_, kaj estas iam (nomita, vokis) la (pepi, ĉirpi)-z algoritmo; ĝi ankaŭ rao-ekspresoj _DFT_ kiel rulumo, sed ĉi tiu tempo de la sama amplekso (kiu povas esti nulo-vatita al povo de du kaj (komputis, pritaksita) per bazo-2 _Cooley_-_Tukey_ _FFTs_, ekzemple), tra la idento $j k = - (j - k) 2 / 2 + j 2 / 2 + k 2 / 2$ .

[redaktu] _FFT_ (algoritmoj, algoritmas) specialigita por (reala, reela) kaj/aŭ simetriaj datumoj

En multaj aplikoj, la enigaĵo por la _DFT_ estas pure (reala, reela), en kiu (kesto, okazo) la (eligas, eligoj) kontentigi la simetrio

$f_{n-j} = f_j^*,$

kaj kompetenta _FFT_ (algoritmoj, algoritmas) havi estas (dizajnita, desegnita) por ĉi tiu situacio (vidi e.g. _Sorensen_, 1987). Unu (maniero, proksimiĝi, proksimiĝo) konsistas de prenante ordinara algoritmo (e.g. _Cooley_-_Tukey_) kaj forprenanta la redunda (partoj, partas) de la kalkulado, (konservanta, savanta) malglate faktoro de du ĝustatempe kaj memoro. Alternative, ĝi estas ebla al (ekspreso, esprimi) (eĉ, ebena, para)-longo (reala, reela)-(enigo, enigi) _DFT_ kiel komplekso _DFT_ de duono la longo (kies (reala, reela) kaj imaginaraj partoj estas la (eĉ, ebena, para)/neparaj eroj de la originala (reala, reela) datumoj), sekvis per O(n) (afiŝo, posteno)-procezante (operacioj, operacias).

Ĝi estis iam kredis (tiu, ke, kiu) (reala, reela)-(enigo, enigi) _DFTs_ povis esti pli kompetente komputita per la Diskreta _Hartley_ (konverti, konverto) (_DHT_), sed ĝi estis sinsekve argumentita (tiu, ke, kiu) specialigita (reala, reela)-(enigo, enigi) _DFT_ algoritmo (_FFT_) povas tipe troviĝi (tiu, ke, kiu) postulas malpli (operacioj, operacias) ol la (korespondanta, respektiva) _DHT_ algoritmo (_FHT_) por la sama nombro de (enigoj, enigas). _Bruun_'s algoritmo (pli supre) estas alia maniero (tiu, ke, kiu) estis (komence, fonte) proponis al preni avantaĝo de (reala, reela) (enigoj, enigas), sed ĝi havas ne (pruvita, pruvis) populara.

Estas plui _FFT_ (specialecoj, specialecas) por la (okazoj, skatoloj, kestoj, kestas, okazas) de (reala, reela) datumoj (tiu, ke, kiu) havi (eĉ, ebena, para)/nepara simetrio, en kiu (kesto, okazo) unu povas (konkeri, gajni) alia faktoro de (malglate) du ĝustatempe kaj memoro kaj la _DFT_ iĝas la diskreta kosinuso/sinusa konverto(s) (_DCT_/_DST_). Anstataŭ rekte (modifanta, aliiganta) _FFT_ algoritmo por ĉi tiuj (okazoj, skatoloj, kestoj, kestas, okazas), _DCTs_/_DSTs_ povas ankaŭ esti komputita tra _FFTs_ de (reala, reela) datumoj kombinita kun O(n) antaŭ/(afiŝo, posteno) procezante.

[redaktu] Akurateco kaj proksimumaj kalkuladoj

Ĉiuj de la _FFT_ (algoritmoj, algoritmas) diskutita (do, tiel) malproksime komputi la _DFT_ akurate (en akurata aritmetiko, kio estas (malzorganta, neglektanta) (glitpunkta, glitkoma) eraroj). Kelkaj "_FFT_" (algoritmoj, algoritmas) havi estas proponita, tamen, (tiu, ke, kiu) komputi la _DFT_ proksimume, kun eraro (tiu, ke, kiu) povas esti farita arbitre malgranda je la elspezo de (multigis, pligrandiĝita) (kalkuladoj, kalkuladas, komputoj, komputas). Tia (algoritmoj, algoritmas) komerco la ekarto por (multigis, pligrandiĝita) rapido aŭ aliaj propraĵoj. Ekzemple, aproksimi _FFT_ algoritmo per _Edelman_ _et_ _al_. (1999) (efektivigas, atingas) suba komunikado (postuloj, bezonoj, bezonas) por paralelo komputanta kun la helpi de rapida-multpolusa maniero. _Wavelet_-bazita aproksimi _FFT_ per _Guo_ kaj _Burrus_ (1996) prenas _sparse_ (enigoj, enigas)/(eligas, eligoj) (tempo/frekvenca lokaligo) enen (konto, kalkulo) pli kompetente ol estas ebla kun akurata _FFT_. Alia algoritmo por aproksimi kalkulado de subaro de la _DFT_ (eligas, eligoj) estas pro al _Shentov_ _et_ _al_. (1995). Nur la _Edelman_ algoritmo (laboroj, laboras) egale bone por _sparse_ kaj ne-_sparse_ datumoj, tamen, ekde ĝi estas bazita sur la _compressibility_ (rango _deficiency_) de la Fourier-a matrica sin iom ol la _compressibility_ (_sparsity_) de la datumoj.

(Eĉ, Ebena, Para) la "akurata" _FFT_ (algoritmoj, algoritmas) havi eraroj kiam finia-precizeco (glitpunkta, glitkoma) aritmetiko estas uzita, sed ĉi tiuj eraroj estas tipe sufiĉe malgranda; plej _FFT_ (algoritmoj, algoritmas), e.g. _Cooley_-_Tukey_, havi bonegaj ciferecaj propraĵoj. La supera baro sur la relativa eraro por la _Cooley_-_Tukey_ algoritmo estas O(ε logo n), (komparita, komparis) al O(ε n^3/2) por la _naïve_ _DFT_ formulo ((Ĝentlemano, Ĝentilhomo) kaj _Sande_, 1966), kie ε estas la maŝino (glitpunkta, glitkoma) relativa precizeco. Fakte, la radiko (meznombro, signifi) kvadrato (_rms_) eraroj estas multa pli bona ol ĉi tiuj superaj baroj, estante nur O(ε √logo n) por _Cooley_-_Tukey_ kaj O(ε √n) por la _naïve_ _DFT_ (_Schatzman_, 1996). Ĉi tiuj rezultoj, tamen, estas tre delikata al la akurateco de la _twiddle_ (faktoroj, faktoras) uzita en la _FFT_ (kio estas la trigonometria funkcio (valoroj, valoras)), kaj ĝi estas ne nekutima por _incautious_ _FFT_ (realigoj, realigas) al havi multa pli malbona akurateco, e.g. se ili uzi malpreciza trigonometria rekursieco (formuloj, formulas). Iu _FFTs_ escepte _Cooley_-_Tukey_, kiel la _Rader_-_Brenner_ algoritmo, estas _intrinsically_ malpli stabila.

En fikspunkta aritmetiko, la finia-precizecaj eraroj akumulis per _FFT_ (algoritmoj, algoritmas) estas pli malbona, kun _rms_ eraroj kreskanta kiel O(√n) por la _Cooley_-_Tukey_ algoritmo (_Welch_, 1969). Ankaŭ, (eĉ, ebena, para) (efektiviganta, atinganta) ĉi tiu akurateco postulas zorga atento al (krustanta, skalanta) por ke minimumigi la malprofito de precizeco, kaj fikspunkto _FFT_ (algoritmoj, algoritmas) engaĝi _rescaling_ je ĉiu intera stadio de (malkomponaĵoj, malkomponaĵas) ŝati _Cooley_-_Tukey_.

Al kontroli la praveco de _FFT_ realigo, rigora garantias povas esti ricevita en O(n logo n) tempo per simpla proceduro kontrolanta la lineareco, impulso-respondo, kaj tempo-(ŝovi, ŝovo) propraĵoj de la (konverti, konverto) sur hazarda (enigoj, enigas) (_Ergün_, 1995).

[redaktu] Multdimensia _FFT_ (algoritmoj, algoritmas)

Kiel difinis en la multdimensia _DFT_ artikolo, la multdimensia _DFT_

$f_\mathbf{j} = \sum_{\mathbf{k}=0}^{\mathbf{n}-1} e^{-2\pi i \mathbf{j} \cdot (\mathbf{k} / \mathbf{n})} x_\mathbf{k}$

(konvertas, konvertoj) tabelo $x_\mathbf{k}$ kun $d$ -dimensia vektoro de indeksoj $\mathbf{k}=(k_1 = 0 \ldots n_1-1, \cdots, k_d = 0 \ldots n_d-1)$ per aro de $d$ (nestita, nestis) (sumadoj, sumadas). Ekvivalente, ĝi estas simple la komponaĵo de vico de $d$ unu-dimensia _DFTs_, (aperis, plenumita) laŭ unu dimensio je tempo (en (ĉiu, iu) (mendi, ordo)).

Ĉi tiu _compositional_ starpunkto (tuj, senpere) provizas la plej simpla kaj plej komuna multdimensia _DFT_ algoritmo, sciata kiel la (linio, vico)-kolumno algoritmo (post la du-dimensia (kesto, okazo), pli sube). Tio estas, unu simple plenumas vico de $d$ unu-dimensia _FFTs_ (per (ĉiu, iu) de la pli supre (algoritmoj, algoritmas)): unua vi (konverti, konverto) laŭ la $k 1$ dimensio, tiam laŭ la $k 2$ dimensio, kaj tiel plu (aŭ reale, (ĉiu, iu) (ordenanta, mendanta, ordanta, dimensianta, komandanta, ordigo) estos laboro). Ĉi tiu maniero estas facile montrita al havi la kutima $O (N log N)$ komplekseco, kie $N = n_1 n_2 \cdots n_d$ estas la tuteca nombro de datumaj punktoj konvertis. En aparta, estas $N / n 1$ (konvertas, konvertoj) de amplekso $n 1$ , _etcetera_, (do, tiel) la komplekseco de la vico de _FFTs_ estas:

$N/n_1 O(n_1 \log n_1) + \cdots + N/n_d O(n_d \log n_d) = O(N [\log n_1 + \cdots + \log n_d]) = O(N \log N).$

En du (dimensioj, dimensias), la $x_\mathbf{k}$ povas esti vidita kiel $n_1 \times n_2$ matrico, kaj ĉi tiu algoritmo korespondas al unua plenumante la _FFT_ de ĉiu (linioj, vicoj, linias, vicas) kaj tiam de ĉiuj kolumnoj (aŭ (malvirto, ŝraŭbtenilo) _versa_), de ĉi tie la nomo.

En pli ol du (dimensioj, dimensias), ĝi estas ofte avantaĝa por kaŝmemora lokeco al grupo la (dimensioj, dimensias) rekursie. Ekzemple, tri-dimensia _FFT_ povus unua (aperi, plenumi) du-dimensia _FFTs_ de ĉiu _planar_ "tranĉaĵo" por ĉiu (fiksis, neŝanĝebligita) $k 1$ , kaj tiam (aperi, plenumi) la unu-dimensia _FFTs_ laŭ la $k 1$ direkto. Pli ĝenerale, (asimptote) (optima, optimala) kaŝmemoro-_oblivious_ algoritmo konsistas de rekursie dividanta la (dimensioj, dimensias) enen du (grupoj, grupas) $(k_1, \cdots, k_{d/2})$ kaj $(k_{d/2+1}, \cdots, k_d)$ (tiu, ke, kiu) estas konvertita rekursie ((rondiganta, rondigo) se $d$ estas ne (eĉ, ebena, para)) (vidi _Frigo_ kaj _Johnson_, 2005). Ankoraŭ, ĉi tiu restas simpla variado de la (linio, vico)-kolumna algoritmo (tiu, ke, kiu) finfine postulas nur unu-dimensia _FFT_ algoritmo kiel la bazo (kesto, okazo), kaj ankoraŭ havas $O (N log N)$ komplekseco. Ankoraŭ alia variado estas al (aperi, plenumi) matrico (transponoj, transponas) en inter konvertanta sinsekva (dimensioj, dimensias), tiel ke la (konvertas, konvertoj) operacii sur _contiguous_ datumoj; ĉi tiu estas aparte grava por ekster-de-kerno kaj distribuis memoro (situacioj, situacias) kie atinganta ne-_contiguous_ datumoj estas ege temporaba.

Estas alia multdimensia _FFT_ (algoritmoj, algoritmas) (tiu, ke, kiu) estas klara de la (linio, vico)-kolumna algoritmo, kvankam ĉiuj de ilin havi $O (N log N)$ komplekseco. Eble la plej simpla ne-(linio, vico)-kolumno _FFT_ estas la vektoro-bazo _FFT_ algoritmo, kiu estas ĝeneraligo de la ordinara _Cooley_-_Tukey_ algoritmo kie unu (akvodislimoj, akvodislimas, divizoras, dividas) la (konverti, konverto) (dimensioj, dimensias) per vektoro $\mathbf{r}=(r_1, r_2, \cdots, r_d)$ de _radices_ je ĉiu (ŝtupo, paŝi). (Ĉi tiu (majo, povas) ankaŭ havi kaŝmemoro (beneficoj, beneficas).) La plej simpla (kesto, okazo) de vektoro-bazo estas kie ĉiuj de la _radices_ estas egala (e.g. vektoro-bazo-2 (akvodislimoj, akvodislimas, divizoras, dividas) ĉiuj de la (dimensioj, dimensias) per du), sed ĉi tiu estas ne necesa. Vektora bazo kun nur sola ne-unua bazo je tempo, kio estas $\mathbf{r}=(1, \cdots, 1, r, 1, \cdots, 1)$ , estas esence (linio, vico)-kolumna algoritmo. Alia, pli komplika, manieroj inkluzivi polinomo (konverti, konverto) (algoritmoj, algoritmas) pro al _Nussbaumer_ (1977), kiu vido la (konverti, konverto) en (termoj, kondiĉoj, terminoj, termas, terminas) de (rulumoj, rulumas) kaj (polinomoj, polinomas) (produktoj, produktas, produktaĵoj, produktaĵas, produtoj, produtas). Vidi _Duhamel_ kaj _Vetterli_ (1990) por pli informo kaj referencoj.

[redaktu] Referencoj

Marmeladoj W. _Cooley_ kaj Johano W. _Tukey_, "An algoritmo por la maŝina kalkulo de kompleksa Serio de Fourier," Math. _Comput_. 19, 297–301 (1965).
Carl Friedrich Gauss, "_Nachlass_: _Theoria_ _interpolationis_ _methodo_ _nova_ _tractata_," _Werke_ bando 3, 265–327 (_Königliche_ _Gesellschaft_ _der_ _Wissenschaften_, Göttingen, 1866). Vidi ankaŭ Sinjoro T. _Heideman_, Don/Doña H. _Johnson_, kaj C. S. _Burrus_, "Gaŭso kaj la historio de la rapida fourier-a konverto," IEEE _ASSP_ Revuo 1 (4), 14–21 (1984).
P. _Duhamel_ kaj Sinjoro _Vetterli_, "Rapidaj fourier-aj konvertoj: (lernilo, studa) (revuo, recenzi) kaj (ŝtato, stato, stati) de la arto," Signali Procezante 19, 259–299 (1990).
W. Sinjoro (Ĝentlemano, Ĝentilhomo) kaj G. _Sande_, "Rapidaj fourier-aj konvertoj—por amuzado kaj (profito, profiti)," _Proc_. _AFIPS_ 29, 563–578 (1966).
H. _Guo_, G. A. _Sitton_, kaj C. S. _Burrus_, "La Rapida Diskreta Fourier-a (Konverti, Konverto)," _Proc_. IEEE _Conf_. _Acoust_. Parolado kaj _Sig_. Procezante (_ICASSP_) 3, 445–448 (1994).
H. V. _Sorensen_, Don/Doña L. _Jones_, Sinjoro T. _Heideman_, kaj C. S. _Burrus_, "(Reala, Reela)-valora rapida fourier-a konverto (algoritmoj, algoritmas)," IEEE _Trans_. _Acoust_. Parolado _Sig_. Procezante _ASSP_-35, 849–863 (1987).
A. _Edelman_, P. _McCorquodale_, kaj S. Toledo, "La estonta rapida fourier-a konverto?" _SIAM_ J. _Sci_. Komputanta 20, 1094–1114 (1999).
H. _Guo_ kaj C. S. _Burrus_, "Rapida aproksimi Konverto de Fourier tra _wavelets_ (konverti, konverto)," _Proc_. _SPIE_ _Intl_. _Soc_. _Opt_. _Eng_. 2825, 250–259 (1996).
O. V. _Shentov_, S. K. _Mitra_, U. _Heute_, kaj A. N. _Hossen_, "_Subband_ _DFT_. Mi. Difino, (interpretadoj, interpretadas) kaj (vastigaĵoj, vastigaĵas)," Signali Procezante 41 (3), 261–277 (1995).
Marmeladoj C. _Schatzman_, "Akurateco de la diskreta fourier-a konverto kaj la rapida fourier-a konverto," _SIAM_ J. _Sci_. _Comput_. 17 (5), 1150–1166 (1996).
Peniseta Don/Doña _Welch_, "A fikspunkta rapida fourier-a konverta erara analitiko," IEEE _Trans_. (Aŭdi(o), Aŭda) _Electroacoustics_ 17 (2), 151–157 (1969).
_Funda_ _Ergün_, "(Testante, Testado) multvarieblaj linearaj funkcioj: _Overcoming_ la generila botelkolo," _Proc_. 27-a _ACM_ Simpozio sur la Teorio de Komputanta, 407–416 (1995).
H. J. _Nussbaumer_, "Cifereca filtranta uzanta polinomo (konvertas, konvertoj)," Elektronika Latvo. 13 (13), 386-387 (1977).
_Matteo_ _Frigo_ kaj _Steven_ G. _Johnson_: _FFTW_, http://www._fftw_._org_/. Libera (Ĝenerala Publika GNU-Permesilo) C biblioteko por komputantaj diskretaj fourier-aj konvertoj en unu aŭ pli (dimensioj, dimensias), de ajna amplekso. Ankaŭ Sinjoro _Frigo_ kaj S. G. _Johnson_, "La Dizajno kaj Realigo de _FFTW3_," Paperoj de la IEEE 93 (2), 216–231 (2005).
N. _Brenner_ kaj C. _Rader_, "A Nova Principo por Rapida Fourier-a Transformo", IEEE Akustiko, Parolado & Signali Procezante 24 (3), 264-266 (1976).
Tomaso H. Cormen-a, Karlo E. _Leiserson_, _Ronald_ L. _Rivest_, kaj _Clifford_ Stein-a. Enkonduko al (Algoritmoj, Algoritmas), (Sekundo, Dua) Redakcio. _MIT_ Premi kaj _McGraw_-Monteto, 2001. ISBN 0262032937. Ĉapitro 30: (Polinomoj, Polinomas) kaj la _FFT_, _pp_.822–848.

[redaktu] Ekstera (ligoj, ligas)

Elŝutita el "http://eo.wikipedia.org../../../p/r/o/Vikipedio%7EProjekto_matematiko_Rapida_fourier-a_konverto_ef1e.html"

Kategorioj: Artikoloj por polurado kaj movo | Fourier-a analizo | Signal-prilaborado