Vikipedio:Projekto matematiko/Diskreta 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
Diskreta 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.

En matematiko, la diskreta fourier-a konverto (_DFT_), iam (nomita, vokis) la finia Konverto de Fourier, estas Konverto de Fourier larĝe (dungis, dungita) en signal-prilaborado kaj rilatantaj kampoj al analizi la (frekvencoj, frekvencas) enhavita en specimenis signali, solvi partaj diferencialaj ekvacioj, kaj al (aperi, plenumi) alia (operacioj, operacias) kiel (rulumoj, rulumas). La _DFT_ povas esti komputita kompetente en praktika uzanta rapida fourier-a konverto (_FFT_) algoritmo.

La vico de N kompleksaj nombroj x₀, ..., x_N−1 estas konvertita enen la vico de N kompleksaj nombroj X₀, ..., X_N−1 per la _DFT_ laŭ la formulo:

$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} k n} \quad \quad k = 0, \dots, N-1$

kie e estas la bazo de la natura logaritmo, mi estas la imaginara unuo ( $i 2 = - 1$ ), kaj π estas Pi. La (konverti, konverto) estas iam signifis per la simbolo $\mathcal{F}$ , kiel en $\mathbf{X} = \mathcal{F}(\mathbf{x})$ aŭ $\mathcal{F} \mathbf{x}$ .

La inversa diskreta fourier-a konverto (_IDFT_) estas donita per

$x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k e^{\frac{2\pi i}{N} k n} \quad \quad n = 0,\dots,N-1.$

(Tononomo, Noto, Noti) (tiu, ke, kiu) la normaliga faktoro multiplikante la _DFT_ kaj _IDFT_ (ĉi tie 1 kaj 1/N) kaj la signoj de la eksponentoj estas nure (konvencioj, konvencias), kaj diferenci en iu (kuracadoj, kuracadas). La nur (postuloj, bezonoj, bezonas) de ĉi tiuj (konvencioj, konvencias) estas (tiu, ke, kiu) la _DFT_ kaj _IDFT_ havi kontraŭa-signaj eksponentoj kaj (tiu, ke, kiu) la (produkto, produto) de ilia normaligo (faktoroj, faktoras) esti 1/N. Normaligo de $1/\sqrt{N}$ por ambaŭ la _DFT_ kaj _IDFT_ (konstruas, faras) la (konvertas, konvertoj) unuargumenta, kiu havas iu teoria (avantaĝoj, avantaĝas), sed ĝi estas ofte pli praktika en cifereca kalkulado al (aperi, plenumi) la (krustanta, skalanta) ĉiuj senprokraste kiel pli supre (kaj unuo (krustanta, skalanta) povas esti oportuna en alia (vojoj, vojas)).

(La konvencio de negativa signo en la eksponento estas ofte oportuna ĉar ĝi (meznombroj, meznombras, signifas) (tiu, ke, kiu) $X k$ estas la (argumento, polusa angulo, amplitudo) de "pozitiva frekvenco" $2π k / N$ . Ekvivalente, la _DFT_ estas ofte penso de kiel (alumetis, svatita, maĉita, konkursita, kongruita) filtrilo: kiam (aspektanta, rigardanta) por frekvenco de +1, unu _correlates_ la rentanta signali kun frekvenco de −1.)

En jena diskuto la (termoj, kondiĉoj, terminoj, termas, terminas) "vico" kaj "vektoro" estos esti konsiderata _interchangeable_.

[redaktu] Propraĵoj

[redaktu] Pleneco

La diskreta fourier-a konverto estas inversigebla, lineara transformo

$\mathcal{F}:\mathbf{C}^N \to \mathbf{C}^N$

kun C signifanta la aro de kompleksaj nombroj. En alia (vortoj, vortas), por (ĉiu, iu) N > 0, N-dimensia kompleksa vektoro havas _DFT_ kaj _IDFT_ kiu estas laŭvice N-dimensia komplekso (vektoroj, vektoras).

[redaktu] Orteco

La (vektoroj, vektoras) exp(2πmi kn/N) (formo, formi) perpendikulara bazo super la aro de N-dimensia komplekso (vektoroj, vektoras):

$\sum_{n=0}^{N-1} \left(e^{ \frac{2\pi i}{N} kn}\right) \left(e^{-\frac{2\pi i}{N} k'n}\right) =N~\delta_{kk'}$

kie δ_kn estas la Delto de Kronecker.

[redaktu] La _Plancherel_ teoremo kaj _Parseval_'s teoremo

Se X_k kaj Y_k estas la _DFTs_ de x_n kaj y_n respektive tiam ni havi la _Plancherel_ teoremo:

$\sum_{n=0}^{N-1} x_n y^*_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k Y^*_k$

kie la stelo signifas kompleksa konjugo. _Parseval_'s teoremo estas speciala okazo de la _Plancherel_ teoremo kaj ŝtatoj:

$\sum_{n=0}^{N-1} |x_n|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X_k|^2.$

[redaktu] La (ŝovi, ŝovo) teoremo

Multiplikante $x n$ per lineara fazo $exp(2π i n m / N)$ por iu entjero $m$ korespondas al cirkulera skipo de la (eligi, eligo) $X k$ : $X k$ estas (anstataŭigita, anstataŭigis) per $X k - m$ , kie la suba indico estas interpretita module $N$ (kio estas _periodically_). Simile, cirkulera skipo de la (enigo, enigi) $x n$ korespondas al multiplikante la (eligi, eligo) $X k$ per lineara fazo. Matematike, se ${x n}$ prezentas la vektoro x tiam

se $\mathcal{F}(\{x_n\})_k=X_k$

tiam $\mathcal{F}(\{ x_n e^{\frac{2\pi i}{N}n m} \})_k=X_{k-m}$

kaj $\mathcal{F}(\{x_{n-m}\})_k=X_k e^{-\frac{2\pi i}{N}k m}$

[redaktu] Periodeco

Ĝi estas montrita en la Diskret-tempa fourier-a konverto (_DTFT_) artikolo (tiu, ke, kiu) la Konverto de Fourier de diskreta tempa vico estas perioda. Finia longa vico estas (justa, ĵus) speciala okazo. Kio estas, ĝi estas malfinia vico de nula enhavanta regiono (_aka_ fenestro) en kiu ne-nulo (valoroj, valoras) (majo, povas) okazi. (Do, Tiel) $X(\omega)\,$ , la _DTFT_ de la (finia vico, finilonga vico) $x[n]\,$ , estas perioda. Ne surprize, la _DFT_ estas perioda; e.g. $X[k+N] = X[k]\,$ . Malpli evidenta, eble, estas (tiu, ke, kiu) la inverso _DFT_ estas ankaŭ perioda; e.g., $x[n+N] = x[n]\,$ . Ĝi estas _periodically_ etendis versio de la (finia vico, finilonga vico).

La _DTFT_ de la _periodically_ etendis vico estas nulo-valora escepti je la diskreta aro de (frekvencoj, frekvencas) specimenita per la _DFT_. Kio estas, ĝi estas efike identa al la _DFT_. La _DTFT_ de la (finia vico, finilonga vico) havas alia ne-nulo (valoroj, valoras), sed ĝi estas ankoraŭ identa al la _DFT_ je la (frekvencoj, frekvencas) specimenita per la _DFT_. (Do, Tiel) la ekarto de $X[k]\,$ , kiel proksimuma kalkulado al $X(\omega)\,$ , (mensogoj, mensogas, kuŝas) en la forestas ne-nulo (valoroj, valoras), ne en la $X[k]\,$ koeficientoj. En (termoj, kondiĉoj, terminoj, termas, terminas) de la inverso _DFT_, (tiu, ke, kiu) ekarto iĝas la perioda vastigaĵo de la (finia vico, finilonga vico).

Kutime, $x[n]\,$ estas ŝanĝo de pli longa, eble malfinio, vico, kies _DTFT_ estas nur aproksimis per $X(\omega)\,$ . En (tiu, ke, kiu) (kesto, okazo), kompreneble, $X[k]\,$ ankaŭ estas nur proksimuma kalkulado al [specimenoj de] la originala _DTFT_.

La (ŝovi, ŝovo) teoremo, pli supre, estas ankaŭ esprimo de la implica periodeco de la inverso _DFT_, ĉar ĝi montras (tiu, ke, kiu) la _DFT_ (argumentoj, argumentas, polusaj anguloj, amplitudoj, amplitudas) $|X[k]|\,$ estas naiva per cirkulero (perioda) (ŝovi, ŝovo) de la (enigoj, enigas), kiu estas simple elekto de fonto kaj pro tio nur afektas la fazo. Periodaj randaj kondiĉoj ludi grava rolo en multaj aplikoj de la _DFT_. Kiam solvantaj diferencialaj ekvaciaj ili permesi periodaj randaj kondiĉoj al esti aŭtomate kontentigita, kaj tial povas esti utila propraĵo. Vidu ankaŭ jenon: la aplikoj sekcio pli sube.

[redaktu] Kromnomanta

Klare diskreta-tempa vico ne povas konfiti kiel multa detalo kiel kontinua-tempa funkcio. La frekvenca domajno manifest(aĵ)o de (tiu, ke, kiu) fakto estas la periodeco de $X(\omega)\,$ kaj $X[k]\,$ , _vs_. la _unlimited_ unikeco de kontinua tempa Konverto de Fourier. La fakto (tiu, ke, kiu) aparta frekvenca komponanto (aperas, ŝajnas, aspektas) _periodically_ je $k\,$ , $k\pm N$ , $k\pm 2N$ , kaj tiel plu nur diras ni la ebla (frekvencoj, frekvencas) de la originala fonto. Kutime nur unu de ilin estas la originala, kaj la (restaĵo, ripozi) estas adekvate (nomita, vokis) (alnomoj, kromnomoj). _Collateral_ informo estas ĝenerale (bezonata, bezonis) al interpreti la multvaloreco (analoga al (interpretado, interpretanta) la du (radikoj, radikas) de kvadrata ekvacio). Ekzemplo de _collateral_ informo estas (tiu, ke, kiu) la $x[n]\,$ vico prezentas la ciferecigis (eligi, eligo) de _lowpass_ kontraŭ-kromnomada filtrilo.

Tempo-domajna prezento de la frekvenco (komponantoj, komponantas) listita pli supre estas:

$x[n] = e^{j \frac{2\pi}{N}(k + L\cdot N)n}\,$ , $L=0\,$ , $\pm 1\,$ , $\pm 2\,$ , kaj tiel plu

Ĉiuj (valoroj, valoras) de $L\,$ produkti la sama $x[n]\,$ vico. Ĝi estas neebla al difini (justa, ĵus) de la vica kio la originala $L\,$ -valoro estis. (Do, Tiel) la _DFT_ (senvualigas, rivelas) ilin ĉiuj, (justa, ĵus) kiel la kvadrata formulo (senvualigas, rivelas) la ambigua (radikoj, radikas) de ekvacio.

[redaktu] Cirkulera ruluma teoremo kaj kruc-korelacia teoremo

La cikla rulumo x*y de la du (vektoroj, vektoras) x = x_k kaj y = y_n estas la vektoro x*y kun (komponantoj, komponantas)

$(\mathbf{x*y})_n = \sum_{m=0}^{N-1} x_m y_{n-m} \quad \quad n = 0,\dots,N-1$

kie ni daŭri y cikle tiel ke

$y_{-m} = y_{N-m}\quad\quad~~~~~~~~~~ m = 0, ..., N-1$

La diskreta fourier-a konverto (kurbiĝoj, kurbiĝas, turnas, tornas, kurbigas) cikla (rulumoj, rulumas) enen laŭkomponanta multipliko. Tio estas, se $z_n = (\mathbf{x*y})_n$ tiam

$Z_k=X_k Y_k \quad \quad~~~~~~~~~~ k = 0,\dots,N-1$

kie (majusklo, grandaj literoj) (X, Y, Z) prezenti la _DFTs_ de (vicoj, vicas) (prezentita, prezentis) per malgrandaj literoj (x, y, z). (Tononomo, Noto, Noti) (tiu, ke, kiu) se malsama normaliga konvencio estas adoptita por la _DFT_ (e.g., la unuargumenta normaligo), tiam tie estos en ĝenerala esti konstanta faktoro multiplikante la pli supre rilato.

La direkta pritakso de la ruluma sumado, pli supre, devus postuli $O (N 2)$ (operacioj, operacias), sed la _DFT_ (tra _FFT_) provizas $O (N log N)$ maniero al komputi la sama aĵo. Male, (rulumoj, rulumas) povas kutimi kompetente komputi _DFTs_ tra _Rader_'s _FFT_ algoritmo kaj _Bluestein_'s _FFT_ algoritmo.

Vidu ankaŭ jenon:: Ruluma teoremo

En analoga maniero, ĝi povas esti montrita (tiu, ke, kiu) se $z n$ estas la kruc-korelacio de $x n$ kaj $y n$ :

$z_n=(\mathbf{x\star y})_n = \sum_{m=0}^{N-1}x_m^*\,y_{m+n}$

kie la (sumo, sumi) estas denove cikla en m, tiam la diskreta fourier-a konverto de $z n$ estas:

$Z_k = X_k^*\,Y_k$

kie (majusklo, grandaj literoj) estas denove kutima signifi la diskreta fourier-a konverto.

[redaktu] Interrilato al trigonometria interpolo (polinomoj, polinomas)

La funkcio

$p(t) = \frac{f_0}{N} + \frac{f_1}{N} e^{it} + \frac{f_2}{N} e^{2it} + \cdots + \frac{f_{N-1}}{N} e^{(N-1)it}$

kies koeficientoj f_k /N estas donita per la _DFT_ de x_n, pli supre, estas (nomita, vokis) la trigonometria interpola polinomo de grado N − 1. Ĝi estas la unika funkcio de ĉi tiu (formo, formi) (tiu, ke, kiu) (verigas, kontentigas) la propraĵo: p(2πn/N) = x_n por n = 0, ..., N − 1.

Pro kromnomanta, tamen, la (formo, formi) de la trigonometria interpola polinomo estas ne unika, en (tiu, ke, kiu) (ĉiu, iu) de la (frekvencoj, frekvencas) povas esti (skipita, ŝovita) per (ĉiu, iu) multaj de N dum (argumentanta, fleganta) la propraĵo p(2πn/N) = x_n . En aparta, jeno (formo, formi) estas ofte (preferita, pliamita):

$p(t) = \frac{f_0}{N} + \frac{f_1}{N} e^{it} + \cdots + \frac{f_{N/2}}{N} \cos(Nt/2) + \frac{f_{N/2+1}}{N} e^{(-N/2+1)it} + \cdots + \frac{f_{N-1}}{N} e^{-it}$

por (ebena, para, eĉ) $N$ (kie la _Nyquist_ (argumento, polusa angulo, amplitudo) $f N / 2$ devus esti ansita speciale) aŭ, por nepara $N$ :

$p(t) = \frac{f_0}{N} + \frac{f_1}{N} e^{it} + \cdots + \frac{f_{\lfloor N/2 \rfloor}}{N} e^{\lfloor N/2 \rfloor it} + \frac{f_{\lfloor N/2 \rfloor+1}}{N} e^{(-\lceil N/2 \rceil+1)it} + \cdots + \frac{f_{N-1}}{N} e^{-it}$

Ĉi tiuj lasta du (formoj, formas) havi la utila propraĵo (tiu, ke, kiu), se la $x n$ estas ĉiuj reelaj nombroj, tiam $p (t)$ estos esti (reala, reela) por ĉiuj $t$ kiel bone. Ili ankaŭ uzi la (plej minuskla, plej malgranda) ebla (frekvencoj, frekvencas) de la interpolanta _sinusoids_ ((bilanco, balancilo, bilanci) de pozitiva kaj negativa (frekvencoj, frekvencas) anstataŭ ĉiuj pozitiva (frekvencoj, frekvencas)), kaj (sekve, sinsekve) minimumigi la (meznombro, signifi)-kvadrata inklino $\int |p'(t)|^2 dt$ de la interpolis funkcio.

[redaktu] La unuargumenta _DFT_

Alia vojo de (aspektanta, rigardanta) je la _DFT_ estas al (tononomo, noto, noti) (tiu, ke, kiu) en la pli supre diskuto, la _DFT_ povas esti esprimita kiel _Vandermonde_ matrico:

$\mathbf{F} = \begin{bmatrix} \omega_N^{0 \cdot 0} & \omega_N^{0 \cdot 1} & \ldots & \omega_N^{0 \cdot (N-1)} \\ \omega_N^{1 \cdot 0} & \omega_N^{1 \cdot 1} & \ldots & \omega_N^{1 \cdot (N-1)} \\ \vdots & \vdots & \ddots & \vdots \\ \omega_N^{(N-1) \cdot 0} & \omega_N^{(N-1) \cdot 1} & \ldots & \omega_N^{(N-1) \cdot (N-1)} \\ \end{bmatrix}$

kie

$\omega_N = e^{-2 \pi i/N}\,$

estas primitivo _Nth_ radiko de unueco. La inverso (konverti, konverto) estas tiam donita per la inverso de la pli supre matrico:

$\mathbf{F}^{-1}=\frac{1}{N}\mathbf{F}^*$

Kun unuargumenta normaligo (konstantoj, konstantas) $1/\sqrt{N}$ , la _DFT_ iĝas unuargumenta transformo, difinis per unuargumenta matrico:

$\mathbf{U}=\mathbf{F}/\sqrt{N}$

$\mathbf{U}^{-1}=\mathbf{U}^*$

$\det(\mathbf{U})=1$

kie _det_() estas la determinanta funkcio. En (reala, reela) vektora spaco, unuargumenta transformo povas esti penso de kiel simple rigida turnado de la koordinatsistemo, kaj ĉiuj de la propraĵoj de rigida turnado povas troviĝi en la unuargumenta _DFT_.

La orteco de la _DFT_ estas nun esprimita kiel _orthonormality_ kondiĉo (kiu ekestas en multaj areoj de matematiko kiel priskribis en radiko de unueco):

$\sum_{m=0}^{N-1}U_{km}U_{mn}^*=\delta_{kn}$

Se $\mathbf{X}$ estas difinita kiel la unuargumenta _DFT_ de la vektoro $\mathbf{x}$ tiam

$X_k=\sum_{n=0}^{N-1} U_{kn}x_n$

kaj la _Plancherel_ teoremo estas esprimita kiel:

$\sum_{n=0}^{N-1}x_n y_n^* = \sum_{k=0}^{N-1}X_k Y_k^*$

Se ni vido la _DFT_ kiel (justa, ĵus) koordinata transformo kiu simple precizigas la (komponantoj, komponantas) de vektoro en nova koordinatsistemo, tiam la pli supre estas (justa, ĵus) la (propozicio, frazo, ordono) (tiu, ke, kiu) la skalara produto de du (vektoroj, vektoras) estas konfitita sub unuargumenta _DFT_ transformo. Por la speciala okazo $\mathbf{x} = \mathbf{y}$ , ĉi tiu (implicas, enhavas) (tiu, ke, kiu) la longo de vektoro estas konfitita kiel bone—ĉi tiu estas (justa, ĵus) _Parseval_'s teoremo:

$\sum_{n=0}^{N-1}|x_n|^2 = \sum_{k=0}^{N-1}|X_k|^2$

[redaktu] Esprimanta la inverso _DFT_ en (termoj, kondiĉoj, terminoj, termas, terminas) de la _DFT_

Utila propraĵo de la _DFT_ estas (tiu, ke, kiu) la inverso _DFT_ povas esti facile esprimita en (termoj, kondiĉoj, terminoj, termas, terminas) de la (antaŭen) _DFT_, tra kelkaj konata "(artifikoj, artifikas)". (Ekzemple, en (kalkuladoj, kalkuladas, komputoj, komputas), ĝi estas ofte oportuna al nur realigi rapida fourier-a konverto (korespondanta, respektiva) al unu (konverti, konverto) direkto kaj tiam al preni la alia (konverti, konverto) direkto de la unua.)

Unua, ni povas komputi la inverso _DFT_ per dorsflankanta la (enigoj, enigas):

$\mathcal{F}^{-1}(\{x_n\}) = \mathcal{F}(\{x_{N - n}\}) / N$

(Kiel kutima, la subaj indicoj estas interpretita module $n$ ; tial, por $n = 0$ , ni havi $x N - 0 = x 0$ .)

(Sekundo, Dua), unu povas ankaŭ konjugita la (enigoj, enigas) kaj (eligas, eligoj):

$\mathcal{F}^{-1}(\mathbf{x}) = \mathcal{F}(\mathbf{x}^*)^* / N$

Tria, varianto de ĉi tiu konjuga artifiko, kiu estas iam preferinda ĉar ĝi postulas ne ŝanĝo de la datumoj (valoroj, valoras), engaĝas svopanta (reala, reela) kaj imaginaraj partoj (kiu povas esti farita sur komputilo simple per (modifanta, aliiganta) (nadloj, nadlas)). Difini svopo( $x n$ ) kiel $x n$ kun ĝia (reala, reela) kaj imaginaraj partoj svopis—tio estas, se $x n = a + b i$ tiam svopo( $x n$ ) estas $b + a i$ . Ekvivalente, svopo( $x n$ ) egalas $i x_n^*$ . Tiam

$\mathcal{F}^{-1}(\mathbf{x}) = \textrm{swap}(\mathcal{F}(\textrm{swap}(\mathbf{x}))) / N$

Tio estas, la inverso (konverti, konverto) estas la sama kiel la antaŭen (konverti, konverto) kun la (reala, reela) kaj imaginaraj partoj svopis por ambaŭ (enigo, enigi) kaj (eligi, eligo), supren al normaligo (_Duhamel_ _et_ _al_., 1988).

La konjuga artifiko povas ankaŭ kutimi difini nova (konverti, konverto), proksime rilatanta al la _DFT_, tio estas _involutary_—tio estas, kiu estas ĝia posedi inverso. En aparta, $T(\mathbf{x}) = \mathcal{F}(\mathbf{x}^*) / \sqrt{N}$ estas klare ĝia posedi inverso: $T(T(\mathbf{x})) = \mathbf{x}$ . Proksime rilatanta _involutary_ transformo (per faktoro de (1+mi)/√2) estas $H(\mathbf{x}) = \mathcal{F}((1+i) \mathbf{x}^*) / \sqrt{2N}$ , ekde la $(1 + i)$ (faktoroj, faktoras) en $H(H(\mathbf{x}))$ malmendi la 2. Por (reala, reela) (enigoj, enigas) $\mathbf{x}$ , la reela parto de $H(\mathbf{x})$ estas neniu escepte la diskreta _Hartley_ (konverti, konverto), kiu estas ankaŭ _involutary_.

[redaktu] La (reala, reela) _DFT_

Se $x_0, \ldots, x_{N-1}$ estas reelaj nombroj, kiel ili ofte estas en praktikaj aplikoj, tiam la _DFT_ obeas la simetrio:

$X_k = X_{N-k}^* ,$

kie la stelo signifas kompleksa konjugo kaj la subaj indicoj estas interpretita module N.

Pro tio, la _DFT_ (eligi, eligo) por (reala, reela) (enigoj, enigas) estas duono redunda, kaj unu ricevas la plenumi informo per nur (aspektanta, rigardanta) je malglate duono de la (eligas, eligoj) $X_0, \ldots, X_{N-1}$ . En ĉi tiu (kesto, okazo), la "DC" ero $X 0$ estas pure (reala, reela), kaj por (ebena, para, eĉ) N la "_Nyquist_" ero $X N / 2$ estas ankaŭ (reala, reela), (do, tiel) estas akurate N ne-redundaj reelaj nombroj en la unua duono + _Nyquist_ ero de la komplekso (eligi, eligo) X.

Uzanta Eŭlera formulo, la interpolanta trigonometria polinomo povas tiam esti interpretita kiel (sumo, sumi) de sinuso kaj kosinusaj funkcioj.

[redaktu] Ĝeneraligita _DFT_

Ĝi estas ebla al (ŝovi, ŝovo) la (konverti, konverto) specimenanta ĝustatempe kaj/aŭ frekvenca domajno per iu (reala, reela) (skipoj, ŝovas, ŝovoj) a kaj b, respektive. Ĉi tiu estas iam sciata kiel ĝeneraligis _DFT_ (aŭ _GDFT_) kaj havas analogaj propraĵoj al la ordinara _DFT_:

$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} (k+b) (n+a)} \quad \quad k = 0, \dots, N-1$

Plej ofte, (skipoj, ŝovas, ŝovoj) de $1 / 2$ (duona specimeno) estas uzitaj. Dum la ordinara _DFT_ korespondas al perioda signali en ambaŭ tempo kaj frekvencaj domajnoj, $a = 1 / 2$ produktas signali tio estas kontraŭ-perioda en frekvenca domajno ( $X k + N = - X k$ ) kaj inverse por $b = 1 / 2$ . Tial, la specifa (kesto, okazo) de $a = b = 1 / 2$ estas sciata kiel nepara-tempa nepara-frekvenco diskreta fourier-a konverto (aŭ O² _DFT_). Tia (skipis, ŝovita) (konvertas, konvertoj) estas plej ofte uzita por simetriaj datumoj, al prezenti malsamaj randaj simetrioj, kaj por (reala, reela)-simetriaj datumaj ili esti konforma laŭ malsama (formoj, formas) de la diskreta kosinuso kaj sinusaj konvertoj.

La diskreta fourier-a konverto povas esti vidita kiel speciala okazo de la z-konverto, pritaksis sur la unuobla cirklo en la kompleksa ebeno.

[redaktu] Multdimensia _DFT_

La ordinara _DFT_ komputas la (konverti, konverto) de "unu-dimensia" _dataset_: vico (aŭ tabelo) $x n$ tio estas funkcio de unu diskreta (variablo, varianta) $n$ . Pli ĝenerale, unu povas difini la multdimensia _DFT_ de multdimensia tabelo $x_{n_1, n_2, \cdots, n_d}$ tio estas funkcio de $d$ diskreta (variabloj, variablas) $n_\ell = 0, 1, \cdots, N_\ell-1$ por $\ell$ en $1, 2, \cdots, d$ :

$X_{k_1, k_2, \cdots, k_d} = \sum_{n_1=0}^{N_1-1} \omega_{N_1}^{~k_1 n_1} \cdots \sum_{n_d=0}^{N_d-1} \omega_{N_d}^{~k_d n_d} x_{n_1, n_2, \cdots, n_d} \, ,$

kie $\omega_{N_\ell} = \exp(-2\pi i/N_\ell)$ kiel pli supre kaj la $d$ (eligi, eligo) indeksoj kuri de $k_\ell = 0, 1, \cdots, N_\ell-1$ . Ĉi tiu estas pli kompakte esprimita en vektora skribmaniero, kie $\mathbf{n} \equiv (n_1, n_2, \cdots, n_d)$ kaj $\mathbf{k} \equiv (k_1, k_2, \cdots, k_d)$ estas $d$ -dimensia (vektoroj, vektoras) de indeksoj de 0 al $\mathbf{N} - 1 \equiv (N_1 - 1, N_2 - 1, \cdots, N_d - 1)$ :

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

kie la divido $\mathbf{n} / \mathbf{N} \equiv (n_1/N_1, \cdots, n_d/N_d)$ estas (aperita, plenumita) ero-saĝa, kaj la (sumo, sumi) signifas la aro de (nestita, nestis) (sumadoj, sumadas) pli supre.

La inverso de la _multi_-dimensia _DFT_ estas, analoga al la unu-dimensia (kesto, okazo), donita per:

$x_\mathbf{n} = \frac{1}{\prod_{\ell=1}^d N_\ell} \sum_{\mathbf{k}=0}^{\mathbf{N}-1} e^{2\pi i \mathbf{n} \cdot (\mathbf{k} / \mathbf{N})} X_\mathbf{k} \, .$

La multdimensia _DFT_ havas simpla interpretado. (Justa, Ĵus) kiel la unu-dimensia _DFT_ ekspresoj la (enigo, enigi) $x n$ kiel superloko de _sinusoids_, la multdimensia _DFT_ ekspresoj la (enigo, enigi) kiel superloko de ebenaj ondoj, aŭ _sinusoids_ oscilanta laŭ la direkto $\mathbf{k} / \mathbf{N}$ en spaco kaj havanta (argumento, polusa angulo, amplitudo) $X_\mathbf{k}$ . Tia malkomponaĵo estas de granda graveco por ĉio de cifereca bildo procezante ( $d$ =2) al solvantaj partaj diferencialaj ekvacioj en tri (dimensioj, dimensias) ( $d$ =3) per rompanta la solvaĵo supren enen ebenaj ondoj.

Kompute, la multdimensia _DFT_ estas simple la komponaĵo de vico de unu-dimensia _DFTs_ laŭ ĉiu dimensio. Ekzemple, en la du-dimensia (kesto, okazo) $x_{n_1,n_2}$ unu povas unua komputi la $N 1$ sendependa _DFTs_ de la (linioj, vicoj, linias, vicas) (kio estas, laŭ $n 2$ ) al (formo, formi) nova tabelo $y_{n_1,k_2}$ , kaj tiam komputi la $N 2$ sendependa _DFTs_ de $y$ laŭ la kolumnoj (laŭ $n 1$ ) al (formo, formi) la fina rezulto $X_{k_1,k_2}$ . Aŭ, unu povas (konverti, konverto) la kolumnoj kaj tiam la (linioj, vicoj, linias, vicas)—la (mendi, ordo) estas indiferenta ĉar la (nestita, nestis) (sumadoj, sumadas) pli supre komutiĝi.

Pro ĉi tiu, donita vojo al komputi unu-dimensia _DFT_ (e.g. ordinara unu-dimensia _FFT_ algoritmo), unu (tuj, senpere) havas vojo al kompetente komputi la multdimensia _DFT_. Ĉi tiu estas sciata kiel (linio, vico)-kolumno algoritmo, kvankam estas ankaŭ _intrinsically_ _multi_-dimensia _FFT_ (algoritmoj, algoritmas).

[redaktu] Aplikoj

La _DFT_ havas vidita larĝa uzada transa granda nombro de kampoj; ni nur skizi kelkaj (ekzemploj, ekzemplas) pli sube (Vidu ankaŭ jenon: la referencoj je la fino). Ĉiuj aplikoj de la _DFT_ dependi krite sur la havebleco de rapida algoritmo al komputi diskretaj fourier-aj konvertoj kaj ilia (inversoj, inversas), rapida fourier-a konverto.

[redaktu] Spektra analitiko

Kiam la _DFT_ estas uzita por spektra analitiko, la $\{x_n\}\,$ vico kutime prezentas finia aro de unuforme-spacitaj tempo-specimenoj de iu signali $x(t)\,$ , kie t kompreneble prezentas tempo. La konvertiĝo de kontinua tempo al specimenoj (diskreta-tempo) ŝanĝas la suba Konverto de Fourier de x(t) enen diskret-tempa fourier-a konverto (_DTFT_), kiu ĝenerale sekvigas tipo de distordo (nomita, vokis) kromnomanta. Elekto de adekvata specimeno-kurzo (vidi _Nyquist_ frekvenco) estas la ŝlosilo al minimumiganta (tiu, ke, kiu) distordo. Simile, la konvertiĝo de tre longa (aŭ malfinio) vico al regebla amplekso sekvigas tipo de distordo (nomita, vokis) _leakage_, kiu estas (sin manifestis, manifestiĝita, manifestita) kiel malprofito de detalo (_aka_ rezolucio) en la _DTFT_. Elekto de adekvata sub-vica longo estas la primara ŝlosilo al minimumiganta (tiu, ke, kiu) efiki. Kiam la haveblaj datumoj (kaj tempo al proceza ĝi) estas pli ol la kvanto (bezonata, bezonis) al atingi la deziris klareco, norma tekniko estas al (aperi, plenumi) multaj _DFTs_. Se la deziris rezulto estas pova spektro, (averaĝanta, averianta, meznombranta) la grandeco (komponantoj, komponantas) de la multaj _DFTs_ estas ofte efika uzi de la superfluaj datumoj. Ĉi tiu tekniko estas referita al kiel la _Welch_ algoritmo.

Fina fonto de distordo (aŭ eble iluzio) estas la _DFT_ sin, ĉar ĝi estas (justa, ĵus) diskreta specimenanta de la _DTFT_, kiu estas funkcio de kontinua frekvenca domajno. (Tiu, Ke, Kiu) povas esti _mitigated_ per pligrandiĝanta la rezolucio de la _DFT_. (Tiu, Ke, Kiu) proceduro estas ilustrita en la diskret-tempa fourier-a konverta artikolo.

La proceduro estas iam referis al kiel nulo-vatanta, kiu estas aparta realigo uzita en (konjunkcio, aŭo, kajo) kun la rapida fourier-a konverto (_FFT_) algoritmo. La _inefficiency_ de plenumante (multiplikoj, multiplikas) kaj (aldonoj, aldonas, adicioj, adicias) kun nulo-valora "specimenoj" estas pli ol kompensi per la imanenta rendimento de la _FFT_.
Kiel jam (tononomis, notita), _leakage_ (trudas, altrudas) limigo sur la imanenta rezolucio de la _DTFT_. (Do, Tiel) estas praktika limigo al la benefico (tiu, ke, kiu) povas esti ricevita de monpuno-grenita _DFT_.

[redaktu] Datuma kunpremo

La kampo de cifereca signal-prilaborado fidas peze sur (operacioj, operacias) en la frekvenca domajno (kio estas sur la Konverto de Fourier). Ekzemple, kelkaj _lossy_ bildo kaj sonaj kunpremaj manieroj dungi la diskreta fourier-a konverto: la signali estas ektranĉi mallonga (segmentoj, segmentas), ĉiu estas konvertita, kaj tiam la Fourier-aj koeficientoj de alta (frekvencoj, frekvencas), kiu estas alprenita al esti _unnoticeable_, estas uzofinita. La _decompressor_ komputas la inverso (konverti, konverto) bazita sur ĉi tiu reduktis nombro de Fourier-aj koeficientoj. (Kunpremaj aplikoj ofte uzi specialigita (formo, formi) de la _DFT_, la diskreta kosinusa konverto aŭ iam la aliigita diskreta kosinusa konverto).

[redaktu] Partaj diferencialaj ekvacioj

Diskretaj fourier-aj konvertoj, aparte en pli ol unu dimensio, estas ofte kutima solvi partaj diferencialaj ekvacioj, kie denove la _DFT_ estas uzita kiel proksimuma kalkulado por la Serio de Fourier (kiu estas reakirita en la limigo de malfinio N). La kaŭzo estas (tiu, ke, kiu) ĝi elvolvas la signali en komplekso (eksponentoj, eksponentas, eksponentaj funkcioj, eksponencialoj, eksponencialas) e^_inx_, kiu estas propraj funkcioj de diferencialado: d/_dx_ e^_inx_ = en e^_inx_. Tial, en la Fourier-a prezento, lineara diferenciala ekvacio kun konstantaj koeficientoj estas konvertita enen facile solvebla algebra ekvacio. Unu tiam uzas la inverso _DFT_ al (konverti, konverto) la rezulta dorso enen la ordinara spaca prezento. Tia (maniero, proksimiĝi, proksimiĝo) estas (nomita, vokis) spektra maniero.

[redaktu] Multipliko de granda (entjeroj, entjeras)

La plej rapida sciata (algoritmoj, algoritmas) por la multipliko de granda (entjeroj, entjeras) aŭ (polinomoj, polinomas) estas bazita sur la diskreta fourier-a konverto: la (vicoj, vicas) de (ciferoj, ciferas) aŭ koeficientoj estas interpretita kiel (vektoroj, vektoras) kies rulumo (bezonas, bezonoj) al esti komputita; por ke fari ĉi tiu, ili estas unua Fourier-a-konvertis, tiam (obligis, multiplikita) laŭkomponanta, tiam konvertis dorso.

[redaktu] Konturo de _DFT_ polinoma multiplika algoritmo

Supozi ni deziri al komputi la polinomo (produkto, produto) c(x) = a(x) · b(x). La ordinara (produkto, produto) esprimo por la koeficientoj de c engaĝas lineara (necikla) rulumo, kie indeksoj ne "_wrap_ ĉirkaŭ." Ĉi tiu povas esti reskribita kiel cikla rulumo per prenante la koeficiento (vektoroj, vektoras) por a(x) kaj b(x) kun konstanto (termo, membro, flanko, termino) unua, tiam almuntantaj nuloj tiel ke la rezulta koeficiento (vektoroj, vektoras) a kaj b havi dimensio d > grado(a(x)) + grado(b(x)). Tiam,

$\mathbf{c} = \mathbf{a} * \mathbf{b}$

Kie c estas la vektoro de koeficientoj por c(x), kaj la ruluma operatoro $*\,$ estas difinita (do, tiel)

$c_n = \sum_{m=0}^{d-1}a_m b_{n-m\ \mathrm{mod}\ d} \qquad\qquad\qquad n=0,1,...,d-1$

Sed rulumo iĝas multipliko sub la _DFT_:

$\mathcal{F}(\mathbf{c}) = \mathcal{F}(\mathbf{a})\mathcal{F}(\mathbf{b})$

Ĉi tie la vektora produto estas prenita _elementwise_. Tial la koeficientoj de la (produkto, produto) polinomo c(x) estas (justa, ĵus) la (termoj, kondiĉoj, terminoj, termas, terminas) 0, ..., grado(a(x)) + grado(b(x)) de la koeficienta vektoro

$\mathbf{c} = \mathcal{F}^{-1}(\mathcal{F}(\mathbf{a})\mathcal{F}(\mathbf{b}))$

Kun Rapida fourier-a konverto, la rezultanta algoritmo prenas O(N logo N) aritmetiko (operacioj, operacias). Pro al ĝia simpleco kaj rapido, la _Cooley_-_Tukey_ _FFT_ algoritmo, kiu estas (limigita, limigis) al _composite_ ampleksoj, estas ofte elektita por la (konverti, konverto) operacio. En ĉi tiu (kesto, okazo), d devus elektiĝi kiel la (plej minuskla, plej malgranda) entjero pli granda ol la (sumo, sumi) de la (enigo, enigi) polinomo (gradoj, gradas) tio estas _factorizable_ enen malgrandaj primaj faktoroj (e.g. 2, 3, kaj 5, dependanta sur la _FFT_ realigo).

[redaktu] Iu diskreta fourier-a konverto (paroj, paras)

En jeno (baremo, tabelo, tablo) $ω N$ staras por $exp( - 2π i / N)$ , primitivo NOno radiko de unueco.

**Iu _DFT_ (paroj, paras)**
$x_n\equiv\frac{1}{N}\sum_{k=0}^{N-1}X_k \omega_N^{-kn}$	$X_k\equiv\sum_{n=0}^{N-1}x_n \omega_N^{kn}$	(Tononomo, Noto, Noti)
$x_n \omega_N^{-nk}$	$X_{n-k}\,$	(Ŝovi, Ŝovo) teoremo
$x_{n-k}\,$	$X_k \omega_N^{nk}$
$x_n \in \mathbf{R}$	$X_k=X_{N-k}^*\,$	(Reala, Reela) _DFT_
$a^n\,$	$\frac{1-a^N}{1-a\omega_N^k}$
${N-1 \choose n}\,$	$(1+\omega_N^k)^{N-1}\,$

[redaktu] Vidu ankaŭ jenon:

Derivaĵo de la diskreta fourier-a konverto La _DFT_ povas esti derivita kiel la kontinua fourier-a konverto de malfinio perioda (vicoj, vicas) de (impulsoj, impulsas).

[redaktu] Referencoj

_esp_. sekcio 30.2: La _DFT_ kaj _FFT_, _pp_.830–838.

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