Transformată Fourier discretă

În matematică , în special în analiza Fourier , transformata Fourier discretă , numită și DFT (acronim al termenului englezesc Transformată Fourier discretă ), este un tip particular de transformată Fourier . Este, de asemenea, un caz special al transformării zeta .

Este o transformare care convertește o colecție finită de probe la fel de distanțate ale unei funcții într-o colecție de coeficienți ai unei combinații liniare de sinusoide complexe , ordonată pe măsură ce crește frecvența. În mod similar cu transformata Fourier, este un mod de a reprezenta o funcție (a cărei variabilă este adesea timpul) în domeniul frecvenței . Frecvențele sinusoidelor combinației liniare (periodice) produse de transformare sunt multipli întregi ai unei frecvențe fundamentale, a căror perioadă este lungimea întregului interval de eșantionare, durata semnalului.

Acesta diferă de transformarea Fourier în timp discret prin faptul că funcția de intrare și funcția produsă sunt secvențe finite și, prin urmare, pot fi considerate ca o transformare pentru analiza Fourier a funcțiilor pe un domeniu limitat și discret.

Spre deosebire de transformata Fourier continuă, prin urmare, DFT necesită ca intrare o funcție discretă ale cărei valori sunt în general complexe și diferite de zero și au o durată limitată. Acest lucru face DFT ideal pentru procesarea informațiilor pe un computer . În special, transformata Fourier discretă este utilizată pe scară largă în domeniul procesării digitale a semnalului și în câmpuri corelate pentru a analiza frecvențele conținute într-un semnal, pentru a rezolva ecuații diferențiale parțiale și pentru a efectua alte operații, cum ar fi convoluția sau multiplicarea. numere întregi. La baza acestor utilizări se află capacitatea de a calcula eficient DFT folosind algoritmi de transformare Fourier rapidă .

Definiție

Succesiunea de $Nu.$ ${\ displaystyle N}$ $Nu.$ numere complexe $x_{0},x_{1},\dots ,x_{N-1}$ ${\ displaystyle x_ {0}, x_ {1}, \ dots, x_ {N-1}}$ $x_ {0}, x_ {1}, \ dots, x _ {{N-1}}$ se transformă în secvența de $Nu.$ ${\ displaystyle N}$ $Nu.$ numere complexe $X_{0},X_{1},\dots ,X_{N-1}$ ${\ displaystyle X_ {0}, X_ {1}, \ dots, X_ {N-1}}$ $X_ {0}, X_ {1}, \ dots, X _ {{N-1}}$ din transformata Fourier discretă conform formulei: ^[1]

X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-ik{\frac {2\pi }{N}}n}\qquad k=0,\dots ,N-1

{\ displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} x_ {n} e ^ {- ik {\ frac {2 \ pi} {N}} n} \ qquad k = 0 , \ dots, N-1}

{\ displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} x_ {n} e ^ {- ik {\ frac {2 \ pi} {N}} n} \ qquad k = 0 , \ dots, N-1}

unde este $the$ ${\ displaystyle i}$ $the$ este unitatea imaginară e $e^{\frac {2\pi i}{N}}$ ${\ displaystyle e ^ {\ frac {2 \ pi i} {N}}}$ $e ^ {{{\ frac {2 \ pi i} {N}}}}$ este o rădăcină a unității a N-a primitivă. Transformarea este adesea reprezentată de simbol ${\mathcal {F}}$ ${\ displaystyle {\ mathcal {F}}}$ ${\ mathcal {F}}$ , folosite ca $\mathbf {X} ={\mathcal {F}}\left\{\mathbf {x} \right\}$ ${\ displaystyle \ mathbf {X} = {\ mathcal {F}} \ left \ {\ mathbf {x} \ right \}}$ ${\ mathbf {X}} = {\ mathcal {F}} \ left \ {{\ mathbf {x}} \ right \}$ sau ${\mathcal {F}}\left(\mathbf {x} \right)$ ${\ displaystyle {\ mathcal {F}} \ left (\ mathbf {x} \ right)}$ ${\ mathcal {F}} \ left ({\ mathbf {x}} \ right)$ sau ${\mathcal {F}}\mathbf {x}$ ${\ displaystyle {\ mathcal {F}} \ mathbf {x}}$ ${\ mathcal {F}} {\ mathbf {x}}$ .

Transformata Fourier discretă descrie complet transformata Fourier discretă în timp (DTFT) a unei secvențe periodice cu perioada N, care are un spectru de frecvență discret. În plus, oferă probe de lungime finită echidistante ale DTFT. Aceasta este corelația încrucișată a secvenței de intrare și a undei sinusoidale de frecvență complexă $k/N$ ${\ displaystyle k / N}$ $k / N$ .

Este, de asemenea, analogul discret al formulei pentru coeficienții seriei Fourier , care este inversul transformatei Fourier discrete (uneori abreviată la IDFT, din Transformarea Fourier discretă inversă ):

x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}e^{{\frac {2\pi i}{N}}kn}\qquad n=0,\dots ,N-1

{\ displaystyle x_ {n} = {\ frac {1} {N}} \ sum _ {k = 0} ^ {N-1} X_ {k} e ^ {{\ frac {2 \ pi i} {N }} kn} \ qquad n = 0, \ dots, N-1}

{\ displaystyle x_ {n} = {\ frac {1} {N}} \ sum _ {k = 0} ^ {N-1} X_ {k} e ^ {{\ frac {2 \ pi i} {N }} kn} \ qquad n = 0, \ dots, N-1}

O descriere simplă a acestor ecuații este că numerele complexe $X_{k}$ ${\ displaystyle X_ {k}}$ $X_ {k}$ reprezintă amplitudinea și faza diferitelor componente sinusoidale ale semnalului de intrare $x_{n}$ ${\ displaystyle x_ {n}}$ $x_ {n}$ . DFT calculează $X_{k}$ ${\ displaystyle X_ {k}}$ $X_ {k}$ Având în vedere $x_{n}$ ${\ displaystyle x_ {n}}$ $x_ {n}$ , în timp ce IDFT calculează $x_{n}$ ${\ displaystyle x_ {n}}$ $x_ {n}$ ca suma componentelor sinusoidale $(1/N)X_{k}e^{{\frac {2\pi i}{N}}kn}$ ${\ displaystyle (1 / N) X_ {k} e ^ {{\ frac {2 \ pi i} {N}} kn}}$ $(1 / N) X_ {k} e ^ {{{\ frac {2 \ pi i} {N}} kn}}$ de frecvență $k/N$ ${\ displaystyle k / N}$ $k / N$ cicluri pe probă. Scriind ecuațiile în această formă, formula lui Euler este utilizată pentru a exprima sinusioizi în termeni de exponențiale complexe, care sunt mai ușor de manipulat. Exprimând $X_{k}$ ${\ displaystyle X_ {k}}$ $X_ {k}$ în formă polară , este astfel posibil să se obțină amplitudinea sinusoidelor $A_{k}$ ${\ displaystyle A_ {k}}$ $A_ {k}$ iar faza $\phi _{k}$ ${\ displaystyle \ phi _ {k}}$ $\ phi _ {k}$ din modul și argument al $X_{k}$ ${\ displaystyle X_ {k}}$ $X_ {k}$ , respectiv:

A_{k}=|X_{k}|={\sqrt {\operatorname {Re} (X_{k})^{2}+\operatorname {Im} (X_{k})^{2}}}\qquad \varphi _{k}=\arg(X_{k})=\operatorname {atan2} {\big (}\operatorname {Im} (X_{k}),\operatorname {Re} (X_{k}){\big )}

{\ displaystyle A_ {k} = | X_ {k} | = {\ sqrt {\ operatorname {Re} (X_ {k}) ^ {2} + \ operatorname {Im} (X_ {k}) ^ {2} }} \ qquad \ varphi _ {k} = \ arg (X_ {k}) = \ operatorname {atan2} {\ big (} \ operatorname {Im} (X_ {k}), \ operatorname {Re} (X_ { k}) {\ big)}}

A_ {k} = | X_ {k} | = {\ sqrt {\ operatorname {Re} (X_ {k}) ^ {2} + \ operatorname {Im} (X_ {k}) ^ {2}}} \ qquad \ varphi _ {k} = \ arg (X_ {k}) = \ operatorname {atan2} {\ big (} \ operatorname {Im} (X_ {k}), \ operatorname {Re} (X_ {k}) {\ mare)}

Rețineți că factorii de normalizare care înmulțesc DFT și IDFT (aici $1$ ${\ displaystyle 1}$ $1$ Și $1/N$ ${\ displaystyle 1 / N}$ $1 / N$ ) și semnele exponenților sunt convenții și pot fi diferite în unele texte. Singurele cerințe ale acestor convenții sunt că DFT și IDFT trebuie să aibă exponenți de semn opus și că produsul factorilor trebuie să fie $1/N$ ${\ displaystyle 1 / N}$ $1 / N$ . Un factor de normalizare $1/{\sqrt {N}}$ ${\ displaystyle 1 / {\ sqrt {N}}}$ $1 / {\ sqrt {N}}$ atât pentru DFT, cât și pentru IDFT, transformările sunt unitare , ceea ce are unele avantaje în tratamentul teoretic, totuși este adesea mai practic în operațiile numerice să se realizeze normalizările o singură dată ca în expresiile prezentate aici.

Trebuie remarcat faptul că transformata Fourier discretă este direct implementabilă pe un computer, deoarece necesită un număr finit de operații, spre deosebire de serie sau transformata Fourier care necesită calculul integralelor sau sumelor de serii. Cu toate acestea, calculul DFT nu este niciodată implementat conform definiției date aici, dar este preferabil să se utilizeze algoritmi optimizați care necesită mai puțin efort de calcul. Timpul de calcul necesar pentru DFT cu definiția dată aici este direct proporțional cu $N^{2}$ ${\ displaystyle N ^ {2}}$ $N ^ {2}$ , pentru algoritmi optimizați (numiți transformată Fourier rapidă sau în engleză FFT (de la Transformarea Fourier rapidă ) este proporțional cu $N\log _{2}(N)$ ${\ displaystyle N \ log _ {2} (N)}$ $N \ log _ {2} (N)$ și, prin urmare, avantajul utilizării acestora este mai mare cu atât este mai mare $Nu.$ ${\ displaystyle N}$ $Nu.$ .

DFT poate fi exprimat și sub formă de matrice prin așa-numita matrice Fourier . Mai mult, poate fi generalizat permițând schimbări de timp ale unui factor $la$ ${\ displaystyle a}$ $la$ și / sau în frecvență cu un factor $b$ ${\ displaystyle b}$ $b$ . În acest caz, se numește DFT generalizat sau GDFT ( DFT generalizat ) și are aceleași proprietăți ca DFT tradițional:

X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}(k+b)(n+a)}\qquad k=0,\dots ,N-1.

{\ displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} x_ {n} e ^ {- {\ frac {2 \ pi i} {N}} (k + b) (n + a)} \ qquad k = 0, \ dots, N-1.}

{\ displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} x_ {n} e ^ {- {\ frac {2 \ pi i} {N}} (k + b) (n + a)} \ qquad k = 0, \ dots, N-1.}

Este adesea folosit pentru a traduce cu un factor $1/2$ ${\ displaystyle 1/2}$ $1/2$ , obținând de exemplu pentru $a=1/2$ ${\ displaystyle a = 1/2}$ $a = 1/2$ un semnal care este antiperiodic în domeniul frecvenței, adică $X_{k+N}=-X_{k}$ ${\ displaystyle X_ {k + N} = - X_ {k}}$ $X _ {{k + N}} = - X_ {k}$ .

Transformat în dimensiuni multiple

Transformata Fourier discretă a unui vector $x_{n_{1},n_{2},\dots ,n_{d}}$ ${\ displaystyle x_ {n_ {1}, n_ {2}, \ dots, n_ {d}}}$ $x _ {{n_ {1}, n_ {2}, \ dots, n_ {d}}}$ funcția d variabile discrete $n_{\ell }=0,1,\dots ,N_{\ell }-1$ ${\ displaystyle n _ {\ ell} = 0,1, \ dots, N _ {\ ell} -1}$ $n _ {\ ell} = 0,1, \ dots, N _ {\ ell} -1$ , cu $\ell \in \{1,2,\dots ,d\}$ ${\ displaystyle \ ell \ in \ {1,2, \ dots, d \}}$ $\ ell \ in \ {1,2, \ dots, d \}$ , este definit ca:

X_{k_{1},k_{2},\dots ,k_{d}}=\sum _{n_{1}=0}^{N_{1}-1}\left(\omega _{N_{1}}^{~k_{1}n_{1}}\sum _{n_{2}=0}^{N_{2}-1}\left(\omega _{N_{2}}^{~k_{2}n_{2}}\cdots \sum _{n_{d}=0}^{N_{d}-1}\omega _{N_{d}}^{~k_{d}n_{d}}\cdot x_{n_{1},n_{2},\dots ,n_{d}}\right)\right)

{\ displaystyle X_ {k_ {1}, k_ {2}, \ dots, k_ {d}} = \ sum _ {n_ {1} = 0} ^ {N_ {1} -1} \ left (\ omega _ {N_ {1}} ^ {~ k_ {1} n_ {1}} \ sum _ {n_ {2} = 0} ^ {N_ {2} -1} \ left (\ omega _ {N_ {2}} ^ {~ k_ {2} n_ {2}} \ cdots \ sum _ {n_ {d} = 0} ^ {N_ {d} -1} \ omega _ {N_ {d}} ^ {~ k_ {d} n_ {d}} \ cdot x_ {n_ {1}, n_ {2}, \ dots, n_ {d}} \ right) \ right)}

X _ {{k_ {1}, k_ {2}, \ dots, k_ {d}}} = \ sum _ {{n_ {1} = 0}} ^ {{N_ {1} -1}} \ left (\ omega _ {{N_ {1}}} ^ {{~ k_ {1} n_ {1}}} \ sum _ {{n_ {2} = 0}} ^ {{N_ {2} -1}} \ left (\ omega _ {{N_ {2}}} ^ {{~ k_ {2} n_ {2}}} \ cdots \ sum _ {{n_ {d} = 0}} ^ {{N_ {d} - 1}} \ omega _ {{N_ {d}}} ^ {{~ k_ {d} n_ {d}}} \ cdot x _ {{n_ {1}, n_ {2}, \ dots, n_ { d}}} \ right) \ right)

unde este $\omega _{N_{\ell }}=\exp(-2\pi i/N_{\ell })$ ${\ displaystyle \ omega _ {N _ {\ ell}} = \ exp (-2 \ pi i / N _ {\ ell})}$ $\ omega _ {{N _ {\ ell}}} = \ exp (-2 \ pi i / N _ {\ ell})$ . Mai compact, definitoriu $\mathbf {n} =(n_{1},n_{2},\dots ,n_{d})$ ${\ displaystyle \ mathbf {n} = (n_ {1}, n_ {2}, \ dots, n_ {d})}$ ${\ mathbf {n}} = (n_ {1}, n_ {2}, \ dots, n_ {d})$ Și $\mathbf {k} =(k_{1},k_{2},\dots ,k_{d})$ ${\ displaystyle \ mathbf {k} = (k_ {1}, k_ {2}, \ dots, k_ {d})}$ ${\ mathbf {k}} = (k_ {1}, k_ {2}, \ dots, k_ {d})$ ca d- vectori dimensionali cu un indice variind de la 0 la $\mathbf {N} -1$ ${\ displaystyle \ mathbf {N} -1}$ ${\ mathbf {N}} - 1$ , unde este:

\mathbf {N} -1=(N_{1}-1,N_{2}-1,\dots ,N_{d}-1)

{\ displaystyle \ mathbf {N} -1 = (N_ {1} -1, N_ {2} -1, \ dots, N_ {d} -1)}

{\ mathbf {N}} - 1 = (N_ {1} -1, N_ {2} -1, \ dots, N_ {d} -1)

avem:

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

{\ displaystyle X _ {\ mathbf {k}} = \ sum _ {\ mathbf {n} = 0} ^ {\ mathbf {N} -1} e ^ {- 2 \ pi i \ mathbf {k} \ cdot (\ mathbf {n} / \ mathbf {N})} x _ {\ mathbf {n}}}

X _ {{\ mathbf {k}}} = \ sum _ {{{\ mathbf {n}} = 0}} ^ {{{\ mathbf {N}} - 1}} și ^ {{- 2 \ pi i {\ mathbf {k}} \ cdot ({\ mathbf {n}} / {\ mathbf {N}})}} x _ {{\ mathbf {n}}}

unde diviziunea $\mathbf {n} /\mathbf {N}$ ${\ displaystyle \ mathbf {n} / \ mathbf {N}}$ ${\ mathbf {n}} / {\ mathbf {N}}$ Și $\mathbf {n} /\mathbf {N} =(n_{1}/N_{1},\dots ,n_{d}/N_{d})$ ${\ displaystyle \ mathbf {n} / \ mathbf {N} = (n_ {1} / N_ {1}, \ dots, n_ {d} / N_ {d})}$ ${\ mathbf {n}} / {\ mathbf {N}} = (n_ {1} / N_ {1}, \ dots, n_ {d} / N_ {d})$ .

Transformarea inversă este, în mod similar cu cazul unidimensional:

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} }

{\ displaystyle 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}} }

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}}}

Transformata Fourier discretă în dimensiuni multiple exprimă intrarea ca o combinație liniară de unde plane sau sinusoide multidimensionale, a căror direcție de oscilație în spațiu este $\mathbf {k} /\mathbf {N}$ ${\ displaystyle \ mathbf {k} / \ mathbf {N}}$ ${\ mathbf {k}} / {\ mathbf {N}}$ și lățime $X_{\mathbf {k} }$ ${\ displaystyle X _ {\ mathbf {k}}}$ $X _ {{\ mathbf {k}}}$ .

Proprietate

Transformata Fourier discretă este o transformare liniară inversabilă ${\mathcal {F}}\colon \mathbb {C} ^{N}\to \mathbb {C} ^{N}$ ${\ displaystyle {\ mathcal {F}} \ colon \ mathbb {C} ^ {N} \ to \ mathbb {C} ^ {N}}$ ${\ mathcal {F}} \ colon {\ mathbb {C}} ^ {N} \ to {\ mathbb {C}} ^ {N}$ care se bucură de proprietățile prezentate mai jos.

Ortogonalitate

Purtători $u_{k}=\left[e^{{\frac {2\pi i}{N}}kn}\;|\;n=0,1,\ldots ,N-1\right]^{T}$ ${\ displaystyle u_ {k} = \ left [e ^ {{\ frac {2 \ pi i} {N}} kn} \; | \; n = 0,1, \ ldots, N-1 \ right] ^ {T}}$ $u_ {k} = \ left [e ^ {{{frac {2 \ pi i} {N}} kn}} \; | \; n = 0,1, \ ldots, N-1 \ right] ^ { T}$ formează o bază ortogonală pe setul de vectori complecși de dimensiune N:

u_{k}^{T}u_{k'}^{*}=\sum _{n=0}^{N-1}\left(e^{{\frac {2\pi i}{N}}kn}\right)\left(e^{{\frac {2\pi i}{N}}(-k')n}\right)=\sum _{n=0}^{N-1}e^{{\frac {2\pi i}{N}}(k-k')n}=N~\delta _{kk'}

{\ displaystyle u_ {k} ^ {T} u_ {k '} ^ {*} = \ sum _ {n = 0} ^ {N-1} \ left (e ^ {{\ frac {2 \ pi i} {N}} kn} \ right) \ left (e ^ {{\ frac {2 \ pi i} {N}} (- k ') n} \ right) = \ sum _ {n = 0} ^ {N -1} e ^ {{\ frac {2 \ pi i} {N}} (kk ') n} = N ~ \ delta _ {kk'}}

u_ {k} ^ {T} u _ {{k '}} ^ {*} = \ sum _ {{n = 0}} ^ {{N-1}} \ left (e ^ {{{\ frac { 2 \ pi i} {N}} kn}} \ right) \ left (e ^ {{{frac {2 \ pi i} {N}} (- k ') n}} \ right) = \ sum _ {{n = 0}} ^ {{N-1}} e ^ {{{\ frac {2 \ pi i} {N}} (k-k ') n}} = N ~ \ delta _ {{kk'} }

unde este $~\delta _{kk'}$ ${\ displaystyle ~ \ delta _ {kk '}}$ $~ \ delta _ {{kk '}}$ este delta Kronecker . Această condiție permite derivarea formulei pentru IDFT din definiția DFT.

Teoremele Plancherel și Parseval

Același subiect în detaliu: Teorema lui Plancherel și Teorema lui Parseval .

De sine $X_{k}$ ${\ displaystyle X_ {k}}$ $X_ {k}$ Și $Y_{k}$ ${\ displaystyle Y_ {k}}$ $Y_ {k}$ sunt transformatele discrete Fourier ale $x_{n}$ ${\ displaystyle x_ {n}}$ $x_ {n}$ Și $y_{n}$ ${\ displaystyle y_ {n}}$ $y_ {n}$ Teorema lui Plancherel afirmă că:

\sum _{n=0}^{N-1}x_{n}y_{n}^{*}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}

{\ displaystyle \ sum _ {n = 0} ^ {N-1} x_ {n} y_ {n} ^ {*} = {\ frac {1} {N}} \ sum _ {k = 0} ^ { N-1} X_ {k} Y_ {k} ^ {*}}

\ sum _ {{n = 0}} ^ {{N-1}} x_ {n} y_ {n} ^ {*} = {\ frac {1} {N}} \ sum _ {{k = 0} } ^ {{N-1}} X_ {k} Y_ {k} ^ {*}

unde asteriscul denotă conjugarea complexă . Teorema lui Parseval este un caz special al teoremei lui Plancherel:

\sum _{n=0}^{N-1}|x_{n}|^{2}={\frac {1}{N}}\sum _{k=0}^{N-1}|X_{k}|^{2}

{\ displaystyle \ sum _ {n = 0} ^ {N-1} | x_ {n} | ^ {2} = {\ frac {1} {N}} \ sum _ {k = 0} ^ {N- 1} | X_ {k} | ^ {2}}

\ sum _ {{n = 0}} ^ {{N-1}} | x_ {n} | ^ {2} = {\ frac {1} {N}} \ sum _ {{k = 0}} ^ {{N-1}} | X_ {k} | ^ {2}

Periodicitate

Dacă evaluați definiția DFT pentru toate numerele întregi $k$ ${\ displaystyle k}$ $k$ în loc de pentru $k=0,\dots ,N-1$ ${\ displaystyle k = 0, \ dots, N-1}$ $k = 0, \ dots, N-1$ secvența infinită rezultată este o extensie periodică cu perioada N a DFT. Periodicitatea poate fi arătată după cum urmează:

X_{k+N}\ {\stackrel {\mathrm {def} }{=}}\ \sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}(k+N)n}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}kn}\underbrace {e^{-2\pi in}} _{1}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}kn}=X_{k}

{\ displaystyle X_ {k + N} \ {\ stackrel {\ mathrm {def}} {=}} \ \ sum _ {n = 0} ^ {N-1} x_ {n} e ^ {- {\ frac {2 \ pi i} {N}} (k + N) n} = \ sum _ {n = 0} ^ {N-1} x_ {n} e ^ {- {\ frac {2 \ pi i} { N}} kn} \ underbrace {e ^ {- 2 \ pi in}} _ {1} = \ sum _ {n = 0} ^ {N-1} x_ {n} e ^ {- {\ frac {2 \ pi i} {N}} kn} = X_ {k}}

X _ {{k + N}} \ {\ stackrel {{\ mathrm {def}}} {=}} \ \ sum _ {{n = 0}} ^ {{N-1}} x_ {n} e ^ {{- {\ frac {2 \ pi i} {N}} (k + N) n}} = \ sum _ {{n = 0}} ^ {{N-1}} x_ {n} e ^ {{- {\ frac {2 \ pi i} {N}} kn}} \ underbrace {e ^ {{- 2 \ pi in}}} _ {{1}} = \ sum _ {{n = 0} } ^ {{N-1}} x_ {n} e ^ {{- {\ frac {2 \ pi i} {N}} kn}} = X_ {k}

În mod similar, transformarea discretă inversă este extinsă periodic.

Traducere

Înmulțirea secvenței $x_{n}$ ${\ displaystyle x_ {n}}$ $x_ {n}$ pentru o fază liniară $e^{{\frac {2\pi i}{N}}nm}$ ${\ displaystyle e ^ {{\ frac {2 \ pi i} {N}} nm}}$ $e ^ {{{\ frac {2 \ pi i} {N}} nm}}$ , cu $m$ ${\ displaystyle m}$ $m$ întreg, se obține traducerea circulară a transformatei $X_{k}$ ${\ displaystyle X_ {k}}$ $X_ {k}$ . În mod similar, traducerea circulară a $x_{n}$ ${\ displaystyle x_ {n}}$ $x_ {n}$ corespunde multiplicării lui $X_{k}$ ${\ displaystyle X_ {k}}$ $X_ {k}$ pentru o fază liniară. În mod explicit, dacă:

{\mathcal {F}}(\{x_{n}\})_{k}=X_{k}

{\ displaystyle {\ mathcal {F}} (\ {x_ {n} \}) _ {k} = X_ {k}}

{\ mathcal {F}} (\ {x_ {n} \}) _ {k} = X_ {k}

asa de:

{\mathcal {F}}(\{x_{n}\cdot e^{{\frac {2\pi i}{N}}nm}\})_{k}=X_{k-m}\qquad {\mathcal {F}}(\{x_{n-m}\})_{k}=X_{k}\cdot e^{-{\frac {2\pi i}{N}}km}

{\ displaystyle {\ mathcal {F}} (\ {x_ {n} \ cdot e ^ {{\ frac {2 \ pi i} {N}} nm} \}) _ {k} = X_ {km} \ qquad {\ mathcal {F}} (\ {x_ {nm} \}) _ {k} = X_ {k} \ cdot e ^ {- {\ frac {2 \ pi i} {N}} km}}

{\ mathcal {F}} (\ {x_ {n} \ cdot e ^ {{{\ frac {2 \ pi i} {N}} nm}} \}) _ {k} = X _ {{km} } \ qquad {\ mathcal {F}} (\ {x _ {{nm}} \}) _ {k} = X_ {k} \ cdot e ^ {{- {\ frac {2 \ pi i} {N }} km}}

Convoluție circulară și corelație încrucișată

Același subiect în detaliu: Convoluție și corelație încrucișată .

Teorema convoluției pentru transformata Fourier în timp discret arată cum convoluția a două secvențe infinite poate fi văzută ca transformarea inversă a produsului transformărilor individuale. Dacă secvențele au lungime finită N avem:

{\mathcal {F}}^{-1}\left\{\mathbf {X\cdot Y} \right\}_{n}\ =\sum _{l=0}^{N-1}x_{l}\cdot (y_{N})_{n-l}\ \ {\stackrel {\mathrm {def} }{=}}\ \ (\mathbf {x*y_{N}} )_{n}

{\ displaystyle {\ mathcal {F}} ^ {- 1} \ left \ {\ mathbf {X \ cdot Y} \ right \} _ {n} \ = \ sum _ {l = 0} ^ {N-1 } x_ {l} \ cdot (y_ {N}) _ {nl} \ \ {\ stackrel {\ mathrm {def}} {=}} \ \ (\ mathbf {x * y_ {N}}) _ {n }}

{\ mathcal {F}} ^ {{- 1}} \ left \ {{\ mathbf {X \ cdot Y}} \ right \} _ {n} \ = \ sum _ {{l = 0}} ^ { {N-1}} x_ {l} \ cdot (y_ {N}) _ {{nl}} \ \ {\ stackrel {{\ mathrm {def}}} {=}} \ \ ({\ mathbf {x * y_ {N}}}) _ {n}

Aceasta este convoluția succesiunii $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ cu o succesiune $\mathbf {y}$ ${\ displaystyle \ mathbf {y}}$ ${\ mathbf {y}}$ extins prin însumare periodică :

(\mathbf {y_{N}} )_{n}\ {\stackrel {\mathrm {def} }{=}}\ \sum _{p=-\infty }^{\infty }y_{(n-pN)}=y_{n(modN)}

{\ displaystyle (\ mathbf {y_ {N}}) _ {n} \ {\ stackrel {\ mathrm {def}} {=}} \ \ sum _ {p = - \ infty} ^ {\ infty} y_ { (n-pN)} = y_ {n (modN)}}

({\ mathbf {y_ {N}}}) _ {n} \ {\ stackrel {{\ mathrm {def}}} {=}} \ \ sum _ {{p = - \ infty}} ^ {{\ infty}} y _ {{(n-pN)}} = y _ {{n (modN)}}

În mod similar, corelația încrucișată a $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ Și $\mathbf {y_{N}}$ ${\ displaystyle \ mathbf {y_ {N}}}$ ${\ mathbf {y_ {N}}}$ este dat de:

{\mathcal {F}}^{-1}\left\{\mathbf {X^{*}\cdot Y} \right\}_{n}=\sum _{l=0}^{N-1}x_{l}^{*}\cdot (y_{N})_{n+l}\ \ {\stackrel {\mathrm {def} }{=}}\ \ (\mathbf {x\star y_{N}} )_{n}

{\ displaystyle {\ mathcal {F}} ^ {- 1} \ left \ {\ mathbf {X ^ {*} \ cdot Y} \ right \} _ {n} = \ sum _ {l = 0} ^ { N-1} x_ {l} ^ {*} \ cdot (y_ {N}) _ {n + l} \ \ {\ stackrel {\ mathrm {def}} {=}} \ \ (\ mathbf {x \ stea y_ {N}}) _ {n}}

{\ mathcal {F}} ^ {{- 1}} \ left \ {{\ mathbf {X ^ {*} \ cdot Y}} \ right \} _ {n} = \ sum _ {{l = 0} } ^ {{N-1}} x_ {l} ^ {*} \ cdot (y_ {N}) _ {{n + l}} \ \ {\ stackrel {{\ mathrm {def}}} {=} } \ \ ({\ mathbf {x \ star y_ {N}}}) _ {n}

Evaluarea directă a ambelor sume necesită $O(N^{2})$ ${\ displaystyle O (N ^ {2})}$ $O (N ^ {2})$ operații pentru o secvență de ieșire lungă N.

În plus, se arată că:

{\mathcal {F}}\left\{\mathbf {x\cdot y} \right\}_{k}\ {\stackrel {\mathrm {def} }{=}}\sum _{n=0}^{N-1}x_{n}\cdot y_{n}\cdot e^{-{\frac {2\pi i}{N}}kn}={\frac {1}{N}}(\mathbf {X*Y_{N}} )_{k}

{\ displaystyle {\ mathcal {F}} \ left \ {\ mathbf {x \ cdot y} \ right \} _ {k} \ {\ stackrel {\ mathrm {def}} {=}} \ sum _ {n = 0} ^ {N-1} x_ {n} \ cdot y_ {n} \ cdot e ^ {- {\ frac {2 \ pi i} {N}} kn} = {\ frac {1} {N} } (\ mathbf {X * Y_ {N}}) _ {k}}

{\ mathcal {F}} \ left \ {{\ mathbf {x \ cdot y}} \ right \} _ {k} \ {\ stackrel {{\ mathrm {def}}} {=}} \ sum _ { {n = 0}} ^ {{N-1}} x_ {n} \ cdot y_ {n} \ cdot e ^ {{- {\ frac {2 \ pi i} {N}} kn}} = {\ frac {1} {N}} ({\ mathbf {X * Y_ {N}}}) _ {k}

Aceasta este convoluția circulară a $\mathbf {X}$ ${\ displaystyle \ mathbf {X}}$ ${\ mathbf {X}}$ Și $\mathbf {Y}$ ${\ displaystyle \ mathbf {Y}}$ ${\ mathbf {Y}}$ .

DFT unitar

DFT poate fi exprimat ca o matrice Vandermonde :

\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}}

{\ displaystyle \ 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}}}

{\ 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}}

unde este:

\omega _{N}=e^{-2\pi i/N}\,

{\ displaystyle \ omega _ {N} = e ^ {- 2 \ pi i / N} \,}

\ omega _ {N} = e ^ {{- 2 \ pi i / N}} \,

Transformarea inversă este dată de matricea inversă :

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

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

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

DFT devine o transformare unitară utilizând coeficienți de normalizare egali cu $1/{\sqrt {N}}$ ${\ displaystyle 1 / {\ sqrt {N}}}$ $1 / {\ sqrt {N}}$ . Unitatea DFT este definită după cum urmează de matricea unității :

\mathbf {U} =\mathbf {F} /{\sqrt {N}}\qquad \mathbf {U} ^{-1}=\mathbf {U} ^{*}\qquad |\det(\mathbf {U} )|=1

{\ displaystyle \ mathbf {U} = \ mathbf {F} / {\ sqrt {N}} \ qquad \ mathbf {U} ^ {- 1} = \ mathbf {U} ^ {*} \ qquad | \ det ( \ mathbf {U}) | = 1}

{\ mathbf {U}} = {\ mathbf {F}} / {\ sqrt {N}} \ qquad {\ mathbf {U}} ^ {{- 1}} = {\ mathbf {U}} ^ {* } \ qquad | \ det ({\ mathbf {U}}) | = 1

Determinantul este produsul valorilor proprii , care sunt întotdeauna $\pm 1$ ${\ displaystyle \ pm 1}$ $\ pm 1$ Și $\pm i$ ${\ displaystyle \ pm i}$ $\ pm i$ .

Prin urmare, ortogonalitatea DFT, menționată mai sus, poate fi exprimată și prin condiția ortonormalității:

\sum _{m=0}^{N-1}U_{km}U_{mn}^{*}=\delta _{kn}

{\ displaystyle \ sum _ {m = 0} ^ {N-1} U_ {km} U_ {mn} ^ {*} = \ delta _ {kn}}

\ sum _ {{m = 0}} ^ {{N-1}} U _ {{km}} U _ {{mn}} ^ {*} = \ delta _ {{kn}}

Dacă și $\mathbf {X}$ ${\ displaystyle \ mathbf {X}}$ ${\ mathbf {X}}$ este definit ca unitatea DFT a $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ asa de:

X_{k}=\sum _{n=0}^{N-1}U_{kn}x_{n}

{\ displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} U_ {kn} x_ {n}}

X_ {k} = \ sum _ {{n = 0}} ^ {{N-1}} U _ {{kn}} x_ {n}

și teorema lui Plancherel poate fi, prin urmare, exprimată și ca:

\sum _{n=0}^{N-1}x_{n}y_{n}^{*}=\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}

{\ displaystyle \ sum _ {n = 0} ^ {N-1} x_ {n} y_ {n} ^ {*} = \ sum _ {k = 0} ^ {N-1} X_ {k} Y_ { k} ^ {*}}

\ sum _ {{n = 0}} ^ {{N-1}} x_ {n} y_ {n} ^ {*} = \ sum _ {{k = 0}} ^ {{N-1}} X_ {k} Y_ {k} ^ {*}

Dacă vizualizați DFT ca o transformare de coordonate care determină doar componentele unui vector într-un nou sistem de coordonate , relația de mai sus arată cum produsul punct al doi vectori este păstrat sub o unitate DFT. În cazul în care $\mathbf {x} =\mathbf {y}$ ${\ displaystyle \ mathbf {x} = \ mathbf {y}}$ ${\ mathbf {x}} = {\ mathbf {y}}$ aceasta implică faptul că lungimea unui vector nu se modifică, conform teoremei lui Parseval :

\sum _{n=0}^{N-1}|x_{n}|^{2}=\sum _{k=0}^{N-1}|X_{k}|^{2}

{\ displaystyle \ sum _ {n = 0} ^ {N-1} | x_ {n} | ^ {2} = \ sum _ {k = 0} ^ {N-1} | X_ {k} | ^ { 2}}

\ sum _ {{n = 0}} ^ {{N-1}} | x_ {n} | ^ {2} = \ sum _ {{k = 0}} ^ {{N-1}} | X_ { k} | ^ {2}

Vectori proprii și valori proprii

Același subiect în detaliu: vector propriu și valoare proprie .

Luați în considerare transformarea unitară $\mathbf {U}$ ${\ displaystyle \ mathbf {U}}$ ${\ mathbf {U}}$ definit anterior pentru DFT de lungime N:

\mathbf {U} _{m,n}={\frac {1}{\sqrt {N}}}\omega _{N}^{(m-1)(n-1)}={\frac {1}{\sqrt {N}}}e^{-{\frac {2\pi i}{N}}(m-1)(n-1)}

{\ displaystyle \ mathbf {U} _ {m, n} = {\ frac {1} {\ sqrt {N}}} \ omega _ {N} ^ {(m-1) (n-1)} = { \ frac {1} {\ sqrt {N}}} e ^ {- {\ frac {2 \ pi i} {N}} (m-1) (n-1)}}

{\ mathbf {U}} _ {{m, n}} = {\ frac 1 {{\ sqrt {N}}}} \ omega _ {N} ^ {{(m-1) (n-1)} } = {\ frac 1 {{\ sqrt {N}}}} e ^ {{- {\ frac {2 \ pi i} N} (m-1) (n-1)}}

Matricea asociată satisface ecuația:

\mathbf {U} ^{4}=\mathbf {I}

{\ displaystyle \ mathbf {U} ^ {4} = \ mathbf {I}}

{\ mathbf {U}} ^ {4} = {\ mathbf {I}}

care poate fi arătat luând în considerare a face actorie $\mathbf {U}$ ${\ displaystyle \ mathbf {U}}$ ${\ mathbf {U}}$ datele inițiale sunt obținute de patru ori. Din aceasta rezultă că valorile proprii $\lambda$ ${\ displaystyle \ lambda}$ $\ lambda$ satisface ecuația:

\lambda ^{4}=1

{\ displaystyle \ lambda ^ {4} = 1}

\ lambda ^ {4} = 1

Prin urmare, valorile proprii ale $\mathbf {U}$ ${\ displaystyle \ mathbf {U}}$ ${\ mathbf {U}}$ sunt a patra rădăcină a unității : $\lambda$ ${\ displaystyle \ lambda}$ $\ lambda$ este +1, −1, i sau - i . Deoarece există patru valori proprii distincte pentru o matrice $N\times N$ ${\ displaystyle N \ times N}$ $N \ ori N$ , posedă o anumită multiplicitate algebrică. Tabelul următor arată multiplicitatea valorilor proprii $\lambda$ ${\ displaystyle \ lambda}$ $\ lambda$ a matricei $\mathbf {U}$ ${\ displaystyle \ mathbf {U}}$ ${\ mathbf {U}}$ care reprezintă unitatea DFT în funcție de lungime $Nu.$ ${\ displaystyle N}$ $Nu.$ a transformării:


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

În mod echivalent, polinomul caracteristic al $\mathbf {U}$ ${\ displaystyle \ mathbf {U}}$ ${\ mathbf {U}}$ Și:

\det(\lambda I-\mathbf {U} )=(\lambda -1)^{\left\lfloor {\tfrac {N+4}{4}}\right\rfloor }(\lambda +1)^{\left\lfloor {\tfrac {N+2}{4}}\right\rfloor }(\lambda +i)^{\left\lfloor {\tfrac {N+1}{4}}\right\rfloor }(\lambda -i)^{\left\lfloor {\tfrac {N-1}{4}}\right\rfloor }

{\ displaystyle \ det (\ lambda I- \ mathbf {U}) = (\ lambda -1) ^ {\ left \ lfloor {\ tfrac {N + 4} {4}} \ right \ rfloor} (\ lambda + 1) ^ {\ left \ lfloor {\ tfrac {N + 2} {4}} \ right \ rfloor} (\ lambda + i) ^ {\ left \ lfloor {\ tfrac {N + 1} {4}} \ dreapta \ rfloor} (\ lambda -i) ^ {\ left \ lfloor {\ tfrac {N-1} {4}} \ right \ rfloor}}

\ det (\ lambda I - {\ mathbf {U}}) = (\ lambda -1) ^ {{\ left \ lfloor {\ tfrac {N + 4} {4}} \ right \ rfloor}} (\ lambda +1) ^ {{\ left \ lfloor {\ tfrac {N + 2} {4}} \ right \ rfloor}} (\ lambda + i) ^ {{\ left \ lfloor {\ tfrac {N + 1} { 4}} \ right \ rfloor}} (\ lambda -i) ^ {{\ left \ lfloor {\ tfrac {N-1} {4}} \ right \ rfloor}}

Nu se cunoaște nicio formulă analitică simplă pentru a calcula vectorii proprii, care nu sunt unici, deoarece fiecare combinație liniară de vectori proprii asociați cu aceeași valoare proprie este un vector propriu numai pentru acea valoare proprie.

Relația cu transformarea continuă

Același subiect în detaliu: Transformata Fourier .

Sus: funcție

x(t)

{\ displaystyle x (t)}

x (t)

și repetarea sa periodică. Jos: transformat

X(\omega )

{\ displaystyle X (\ omega)}

X (\ omega)

din

x(t)

{\ displaystyle x (t)}

x (t)

și repetarea sa periodică în domeniul frecvenței. Rețineți absența aliasingului în ambele cazuri.

Pentru a arăta relația cu versiunea continuă a transformatei Fourier considerăm o funcție $x(t)$ ${\ displaystyle x (t)}$ $x (t)$ cu transformata Fourier $X(\omega )$ ${\ displaystyle X (\ omega)}$ $X (\ omega)$ , iar repetările periodice sunt construite:

x_{p}(t)=\sum _{i=-\infty }^{+\infty }x\left(t-iT_{p}\right)\qquad X_{p}(\omega )=\sum _{i=-\infty }^{+\infty }X\left(\omega -i\omega _{p}\right)

{\ displaystyle x_ {p} (t) = \ sum _ {i = - \ infty} ^ {+ \ infty} x \ left (t-iT_ {p} \ right) \ qquad X_ {p} (\ omega) = \ sum _ {i = - \ infty} ^ {+ \ infty} X \ left (\ omega -i \ omega _ {p} \ right)}

x_ {p} (t) = \ sum _ {{i = - \ infty}} ^ {{+ \ infty}} x \ left (t-iT_ {p} \ right) \ qquad X_ {p} (\ omega ) = \ sum _ {{i = - \ infty}} ^ {{+ \ infty}} X \ left (\ omega -i \ omega _ {p} \ right)

cu puncte $T_{p}$ ${\ displaystyle T_ {p}}$ $T_ {p}$ Și $\omega _{p}$ ${\ displaystyle \ omega _ {p}}$ $\ omega _ {p}$ legate de relație $T_{p}\omega _{p}=2\pi N$ ${\ displaystyle T_ {p} \ omega _ {p} = 2 \ pi N}$ $T_ {p} \ omega _ {p} = 2 \ pi N$ . De asemenea, indică:

\Delta t={\frac {T_{p}}{N}}={\frac {2\pi }{\omega _{p}}}\qquad \Delta \omega ={\frac {\omega _{p}}{N}}={\frac {2\pi }{T_{p}}}

{\ displaystyle \ Delta t = {\ frac {T_ {p}} {N}} = {\ frac {2 \ pi} {\ omega _ {p}}} \ qquad \ Delta \ omega = {\ frac {\ omega _ {p}} {N}} = {\ frac {2 \ pi} {T_ {p}}}}

\ Delta t = {\ frac {T_ {p}} {N}} = {\ frac {2 \ pi} {\ omega _ {p}}} \ qquad \ Delta \ omega = {\ frac {\ omega _ { p}} {N}} = {\ frac {2 \ pi} {T_ {p}}}

care satisfac relația $\Delta t\cdot \Delta \omega ={\frac {2\pi }{N}}$ ${\ displaystyle \ Delta t \ cdot \ Delta \ omega = {\ frac {2 \ pi} {N}}}$ $\ Delta t \ cdot \ Delta \ omega = {\ frac {2 \ pi} {N}}$ , definim cele două n-ples de numere:

\Delta t\cdot x_{p}(n\Delta t)\quad n=0,1,\dots ,N-1\qquad X_{p}(q\Delta \omega )\quad q=0,1,\dots ,N-1

{\ displaystyle \ Delta t \ cdot x_ {p} (n \ Delta t) \ quad n = 0,1, \ dots, N-1 \ qquad X_ {p} (q \ Delta \ omega) \ quad q = 0 , 1, \ dots, N-1}

\ Delta t \ cdot x_ {p} (n \ Delta t) \ quad n = 0,1, \ dots, N-1 \ qquad X_ {p} (q \ Delta \ omega) \ quad q = 0,1, \ dots, N-1

Apoi, se mențin următoarele egalități:

\Delta t\cdot x_{p}(n\Delta t)={\mathcal {F}}_{d}^{-1}(X_{p}(q\Delta \omega ))\qquad X_{p}(q\Delta \omega )={\mathcal {F}}_{d}(\Delta t\cdot x_{p}(n\Delta t))

{\ displaystyle \ Delta t \ cdot x_ {p} (n \ Delta t) = {\ mathcal {F}} _ {d} ^ {- 1} (X_ {p} (q \ Delta \ omega)) \ qquad X_ {p} (q \ Delta \ omega) = {\ mathcal {F}} _ {d} (\ Delta t \ cdot x_ {p} (n \ Delta t))}

\ Delta t \ cdot x_ {p} (n \ Delta t) = {\ mathcal {F}} _ {d} ^ {{- 1}} (X_ {p} (q \ Delta \ omega)) \ qquad X_ {p} (q \ Delta \ omega) = {\ mathcal {F}} _ {d} (\ Delta t \ cdot x_ {p} (n \ Delta t))

Dacă nu există suprapuneri nici în domeniul timpului, nici în domeniul frecvenței, este posibil să se obțină transformarea continuă din cea discretă.

Notă

^ Eric Weisstein, MathWorld - Transformarea Fourier discretă , la mathworld.wolfram.com , 2012.

Bibliografie

(EN) E. Oran Brigham, Transformata Fourier rapidă și aplicațiile sale, Englewood Cliffs, NJ, Prentice Hall, 1988, ISBN 0-13-307505-2 .
( EN ) Oppenheim, Alan V; Schafer, RW; și Buck, JR, Procesarea semnalului în timp discret , Upper Saddle River, NJ, Prentice Hall, 1999, ISBN 0-13-754920-2 .
( EN ) Steven W. Smith, Capitolul 8: Transformarea Fourier discretă , în The Scientist and Engineer's Guide to Digital Signal Processing , Second, San Diego, California, California Technical Publishing, 1999, ISBN 0-9660176-3-3 .
( EN ) Thomas H. Cormen , Charles E. Leiserson, Ronald L. Rivest și Clifford Stein, Capitolul 30: Polinomii și FFT , în Introducere în algoritmi , în al doilea rând, MIT Press și McGraw-Hill, 2001, pp. 822–848, ISBN 0-262-03293-7 . în special secțiunea 30.2: DFT și FFT, pp. 830–838.
( EN ) P. Duhamel, B. Piron și JM Etcheto, despre calculul DFT invers , în IEEE Trans. Acust., Speech and Mr. Processing , voi. 36, n. 2, 1988, pp. 285-286, DOI : 10.1109 / 29.1519 .
( EN ) JH McClellan și TW Parks, valori proprii și vectori proprii ai transformării Fourier discrete , în IEEE Trans. Audio electroacust. , vol. 20, nr. 1, 1972, pp. 66–74, DOI : 10.1109 / TAU.1972.1162342 .
(EN) Bradley W. Dickinson și Kenneth Steiglitz, vectori proprii și funcții ale transformatei Fourier discrete , în IEEE Trans. Acust., Speech and Mr. Processing , voi. 30, n. 1, 1982, pp. 25–31, DOI : 10.1109 / TASSP.1982.1163843 . (Rețineți că această lucrare are o greșeală aparentă în tabelul său cu multiplicitățile valorii proprii: coloanele + i / - i sunt schimbate. Tabelul corect poate fi găsit în McClellan și Parks, 1972 și este ușor confirmat numeric.)
( EN ) FA Grünbaum, Vectorii proprii ai transformatei Fourier discrete , în J. Math. Anal. Aplic. , vol. 88, nr. 2, 1982, pp. 355–363, DOI : 10.1016 / 0022-247X (82) 90199-8 .
( EN ) Natig M. Atakishiyev și Kurt Bernardo Wolf, Fractional Fourier-Kravchuk transform , în J. Opt. Soc. Am. A , vol. 14, n. 7, 1997, pp. 1467–1477, DOI : 10.1364 / JOSAA.14.001467 .
( EN ) C. Candan, MA Kutay și HMOzaktas, Transformarea Fourier fracționată discretă , în IEEE Trans. despre procesarea semnalului , vol. 48, nr. 5, 2000, pp. 1329–1337, DOI : 10.1109 / 78.839980 .
( EN ) Magdy Tawfik Hanna, Nabila Philip Attalla Seif și Waleed Abd El Maguid Ahmed, vectori proprii hermite -gaussieni ai matricei de transformate discrete Fourier bazate pe descompunerea cu valoare singulară a matricilor sale de proiecție ortogonală , în IEEE Trans. Circ. Syst. Eu , vol. 51, nr. 11, 2004, pp. 2245–2254, DOI : 10.1109/TCSI.2004.836850 .
( EN ) Shamgar Gurevich and Ronny Hadani, On the diagonalization of the discrete Fourier transform , in Applied and Computational Harmonic Analysis , vol. 27, n. 1, 2009, pp. 87–99, DOI : 10.1016/j.acha.2008.11.003 , arXiv : 0808.3281 , preprint at.
( EN ) Shamgar Gurevich, Ronny Hadani, and Nir Sochen, The finite harmonic oscillator and its applications to sequences, communication and radar , in IEEE Transactions on Information Theory , vol. 54, n. 9, 2008, pp. 4239–4253, DOI : 10.1109/TIT.2008.926440 , arXiv : 0808.1495 , preprint at.
( EN ) Juan G. Vargas-Rubio and Balu Santhanam, On the multiangle centered discrete fractional Fourier transform , in IEEE Sig. Proc. Lett. , vol. 12, n. 4, 2005, pp. 273–276, DOI : 10.1109/LSP.2005.843762 .
( EN ) J. Cooley, P. Lewis, and P. Welch, The finite Fourier transform , in IEEE Trans. Audio Electroacoustics , vol. 17, n. 2, 1969, pp. 77–85, DOI : 10.1109/TAU.1969.1162036 .
( EN ) FN Kong, Analytic Expressions of Two Discrete Hermite-Gaussian Signals , in IEEE Trans. Circuits and Systems –II: Express Briefs. , vol. 55, n. 1, 2008, pp. 56–60, DOI : 10.1109/TCSII.2007.909865 .

Voci correlate

Collegamenti esterni

( EN ) Matlab tutorial on the Discrete Fourier Transformation , su nbtwiki.net .
( EN ) Interactive flash tutorial on the DFT , su fourier-series.com . URL consultato l'11 giugno 2013 (archiviato dall' url originale il 23 maggio 2016) .
( EN ) Mathematics of the Discrete Fourier Transform by Julius O. Smith III , su ccrma.stanford.edu .
( EN )Fast implementation of the DFT - coded in C and under General Public License (GPL) , su fftw.org .
( EN ) The DFT “à Pied”: Mastering The Fourier Transform in One Day , su dspdimension.com .
( EN ) Explained: The Discrete Fourier Transform , su web.mit.edu .

Portale Matematica : accedi alle voci di Wikipedia che trattano di matematica

[mathworld-1] Eric Weisstein, MathWorld - Transformarea Fourier discretă , la mathworld.wolfram.com , 2012.

[1]