Transformada de Fourier discreta

En matemàtiques, la transformada discreta de Fourier o DFT (de l'anglés, discrete Fourier transform) és un tipo de transformada discreta utilisada en l'anàlisis de Fourier. Transforma una funció matemàtica en una atra, obtenint una representació en el domini de la freqüència, sent la funció original una funció en el domini del temps. Pero la DFT requerix que la funció d'entrada siga una seqüència discreta i de duració finita. Dites seqüències se solen generar a partir del mostreig d'una funció contínua, com pot ser la veu humana. Al contrari que la transformada de Fourier en temps discret (DTFT), esta transformació únicament evalua suficients components frecuenciales per a reconstruir el segment finito que s'analisa. Utilisar la DFT implica que el segment que s'analisa és un únic periodo d'una senyal periòdica que s'estén de forma infinita; si açò no es complix, es deu utilisar una finestra per a reduir els espurios de l'espectre. Per la mateixa raó, la DFT inversa (IDFT) no pot reproduir el domini del temps complet, a no ser que l'entrada siga periòdica indefinidament. Per estes raons, es diu que la DFT és una transformada de Fourier per a anàlisis de senyals de temps discret i domini finito. Les funcions sinusoidals base que sorgixen de la descomposició tenen les mateixes propietats.

L'entrada de la DFT és una seqüència finita d'número real o complexos, de modo que és ideal per a processar informació almagasenada en soports digitals. En particular, la DFT s'utilisa comunament en processat digital de senyals i atres camps relacionats dedicats a analisar les freqüències que conté una senyal muestreada, també per a resoldre equacions diferencials parcials, i per a portar a terme operacions com convoluciones o multiplicacions de grans número entero. Un factor molt important per a este tipo d'aplicacions és que la DFT pot ser calculada de forma eficient en la pràctica utilisant l'algoritme de la transformada ràpida de Fourier o FFT (Fast Fourier Transform).

Els algoritmes FFT s'utilisen tan habitualment per a calcular DFTs que el terme "FFT" moltes voltes s'utilisa en lloc de "DFT" en llenguage coloquial. Formalment, hi ha una diferència clara: "DFT" fa alusió a una transformació o funció matemàtica, independentment de cóm es calcule, mentres que "FFT" es referix a una família específica d'algoritmes per a calcular DFTs.

Definició

La seqüència de N número complejo x₀, ..., x_N−1 es transforma en la seqüència de N número complejo X₀, ..., X_N−1 per mig de la DFT en la fòrmula:

$X_k=\sum _{n=0}^{N-1}{x}_n{e}^{-\frac{2\pi i}{N}kn}k=0,\dots ,N-1$

a on i és l'unitat imaginària i $e^{\frac{2\pi i}{N}}$ és la N-ésima raïl de l'unitat. (Esta expressió es pot escriure també en térmens d'una matriu DFT; quan s'escala de forma apropiada es convertix en una matriu unitària i X_k pot llavors ser interpretat com els coeficients de x en una base ortonormal.)

La transformada es denota a voltes pel símbol $ℱ$, igual que en $𝐗=ℱ\left\{𝐱\right\}$ o $ℱ\left(𝐱\right)$ o $ℱ𝐱$.

La transformada inversa de Fourier discreta (IDFT) ve donada per

$x_n=\frac{1}{N}\sum _{k=0}^{N-1}{X}_k{e}^{\frac{2\pi i}{N}kn}n=0,\dots ,N-1.$

Una descripció simple d'estes equacions és que els número complejo $X_k$ representen l'amplitut i fase de diferents components sinusoidals de la senyal d'entrada $x_n$. La DFT calcula $X_k$ a partir de $x_n$, mentres que la IDFT mostra cóm calcular $x_n$ com la suma de components sinusoidals $(1/N)X_k{e}^{\frac{2\pi i}{N}kn}$ en una freqüència de $k/N$ cicles per mostra. Escrivint les equacions d'esta manera, estem fent un us extensiu de la fòrmula de Euler per a expressar sinusoide en térmens d'exponents complexes, la qual cosa és molt més senzill de manipular. De la mateixa manera, escrivint $X_k$ en forma polar, obtenim una sinudoide d'amplitut $A_k/N$ i fase ${\varphi }_k$ a partir del mòdul i argument complexos de $X_k$, respectivament:

$A_k=|X_k|=\sqrt{\mathrm{Re}(X_k{)}^2+\mathrm{Im}(X_k{)}^2},$

${\phi }_k=\arg (X_k)=\mathrm{atan2}(\mathrm{Im}(X_k),\mathrm{Re}(X_k)),$

a on nuguen2 és la forma bi-argumental de la funció arcotangente. Note's que el factor de normalisació que multiplica a la DFT i la IDFT (que són 1 i 1/N) i els signes dels exponents es coloquen merament per conveni, i varien depenent de l'aplicació. L'únic requisit per a este conveni és que la DFT i la IDFT tinguen exponents de signe opost i que el producte dels seus factors de normalisació siga 1/N. Una normalisació de $1/\sqrt{N}$ per a abdós DFT i IDFT fa les transformades unitàries, la qual cosa té certes ventages teòriques, pero sol ser més pràctic a l'hora d'efectuar operacions numèriques en l'ordenador efectuar l'escalat d'una sola volta (i un escalat unitari sol ser convenient en atres ocasions).

(El conveni del signe negatiu en l'exponent sol ser adequat perque significa que $X_k$ és l'amplitut d'una "freqüència positiva" $2\pi k/N$. De forma equivalent, la DFT se sol considerar com un filtre adaptat: quan es busca una freqüència de +1, es correlaciona la senyal d'entrada en una freqüència de −1.)

En avant, els térmens "seqüència" i "vector" seran considerats equivalents.

Propietats

Completitud

La transformada discreta de Fourier és una transformació llineal i invertible.

$ℱ:{ℂ}^N\to {ℂ}^N$

a on C denota el cos dels número complejo. En atres paraules, per a cada N > 0, qualsevol vector complex N-dimensional té una DFT i una IDFT que consistixen també en vectores complexos N-dimensionals.

Ortogonalidad

Els vectores $e^{\frac{2\pi i}{N}kn}$ formen una base ortogonal sobre el cos dels vectores complexos N-dimensionals:

$\sum _{n=0}^{N-1}\left(e^{\frac{2\pi i}{N}kn}\right)\left(e^{-\frac{2\pi i}{N}{k}^{\prime }n}\right)=N{\delta }_{k{k}^{\prime }}$

a on ${\delta }_{k{k}^{\prime }}$ és la delta de Kronecker. Esta condició de ortogonalidad pot ser utilisada per a obtindre la fòrmula de la IDFT a partir de la definició de la DFT, i és equivalent a la propietat d'unicitat.

Les teoremes de Plancherel i Parseval

Si X_k i I_k són les DFTs de x_n i i_n respectivament, llavors el teorema de Plancherel establix que:

$\sum _{n=0}^{N-1}{x}_n{y}_n^{*}=\frac{1}{N}\sum _{k=0}^{N-1}{X}_k{Y}_k^{*}$

a on l'asterisc denota conjugació complexa. El teorema de Parseval és un cas especial de la teorema de Plancherel, i diu que:

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

Estes teoremes són també equivalents a la condició d'unicitat.

Periodicitat

Si l'expressió que definix la DFT s'evalua per a tots els sancers k en lloc d'únicament per a $k=0,\dots ,N-1$, la seqüència infinita resultant és una extensió periòdica de la DFT, de periodo N.

Esta periodicitat pot demostrar-se directament a partir de la definició:

$X_{k+N}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\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}\underset{1}{\underbrace{e^{-2\pi in}}}=\sum _{n=0}^{N-1}{x}_n{e}^{-\frac{2\pi i}{N}kn}=X_k.$

De forma similar, es pot demostrar que la fòrmula de la IDFT du a una extensió periòdica.

Teorema del desplaçament

Multiplicant $x_n$ per una fase llineal $e^{\frac{2\pi i}{N}nm}$ per a qualsevol sancer m equival a un desplaçament circular de l'eixida $X_k$: $X_k$ es reemplaça per $X_{k-m}$, a on el subíndex es repetix periòdicament (periodo N). De forma similar, un desplaçament circular de l'entrada $x_n$ equival a multiplicar l'eixida $X_k$ per una fase llineal. Matemàticament, si $\{x_n\}$ representa el vector x llavors:

si $ℱ(\{x_n\}{)}_k=X_k$

llavors $ℱ(\{x_n\cdot e^{\frac{2\pi i}{N}nm}\}{)}_k=X_{k-m}$

i $ℱ(\{x_{n-m}\}{)}_k=X_k\cdot e^{-\frac{2\pi i}{N}km}$

Teorema de la convolución circular i teorema de la correlació creuada

El teorema de la convolución per a les transformada de Fourier contínua i discreta indica que una convolución de dos seqüències infinites es pot obtindre com la transformada inversa del producte de les transformades de cada una d'elles. En seqüències i transformades de llongitut N, la convolución circular es definix:

$\begin{array}{cc}{ℱ}^{-1}{\left\{𝐗\mathbf{\cdot }𝐘\right\}}_n& \stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\frac{1}{N}\sum _{k=0}^{N-1}{X}_k\cdot Y_k\cdot e^{\frac{2\pi i}{N}kn}\\ & =\frac{1}{N}\sum _{k=0}^{N-1}\left(\sum _{l=0}^{N-1}{x}_l{e}^{-\frac{2\pi i}{N}kl}\right)\cdot \left(\sum _{m=0}^{N-1}{y}_m{e}^{-\frac{2\pi i}{N}km}\right)\cdot e^{\frac{2\pi i}{N}kn}\\ & =\sum _{l=0}^{N-1}{x}_l\sum _{m=0}^{N-1}{y}_m\left(\frac{1}{N}\sum _{k=0}^{N-1}{e}^{\frac{2\pi i}{N}k(n-l-m)}\right).\end{array}$

El número entre paréntesis és 0 per a tots els valors de m llevat aquells de la forma $n-l-pN$, a on p és un sancer qualsevol. En estes posicions val 1. Pot ser per tant reemplaçat per una suma infinita de deltes de Kronecker. Note's que es poden estendre els llímits de m fins a infinit, sent les seqüències x i i definides nules fora de [0,N-1]:

$\begin{array}{cc}{ℱ}^{-1}{\left\{𝐗\mathbf{\cdot }𝐘\right\}}_n& =\sum _{l=0}^{N-1}{x}_l\sum _{m=-\mathrm{\infty }}^{\mathrm{\infty }}{y}_m\left(\sum _{p=-\mathrm{\infty }}^{\mathrm{\infty }}{\delta }_{m,(n-l-pN)}\right)\\ & =\sum _{l=0}^{N-1}{x}_l\sum _{p=-\mathrm{\infty }}^{\mathrm{\infty }}\underset{y_{n-l-pN}}{\underbrace{(\sum _{m=-\mathrm{\infty }}^{\mathrm{\infty }}{y}_m\cdot {\delta }_{m,(n-l-pN)})}}\\ & =\sum _{l=0}^{N-1}{x}_l\left(\sum _{p=-\mathrm{\infty }}^{\mathrm{\infty }}{y}_{n-l-pN}\right)\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}(𝐱\mathbf{*}{𝐲}_{𝐍}{)}_n,\end{array}$

que és la convolución de la seqüència $𝐱$ en la seqüència $𝐲$ que està estesa periòdicament i definida:

$({𝐲}_{𝐍}{)}_n\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\sum _{p=-\mathrm{\infty }}^{\mathrm{\infty }}{y}_{(n-pN)}=y_{n(modN)}.$

També es pot demostrar que:

${ℱ}^{-1}{\left\{{𝐗}^{\mathbf{*}}\mathbf{\cdot }𝐘\right\}}_n=\sum _{l=0}^{N-1}{x}_l^{*}\cdot (y_N{)}_{n+l}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}(𝐱\mathbf{\star }{𝐲}_{𝐍}{)}_n,$

que és la correlació creuada de  $𝐱$  i  ${𝐲}_{𝐍}.$

Una evaluació directa de la convolución requerix $O(N^2)$ operacions per a una seqüència d'entrada de llongitut N. El método indirecte, usant transformades, pot traure profit de la transformada ràpida de Fourier (FFT), que necessita solament $O(N\log N)$ operacions, de modo que es conseguix una eficiència molt major. Ademés, les convoluciones poden ser utilisades per a calcular de forma eficient DFTs per mig del algoritme FFT de Rader i l'algoritme FFT de Bluestein.

S'han creat atres métodos que usen la convolución circular com a part d'un procés eficient que obté convoluciones normals (no circulares) en una seqüència $𝐱$ o $𝐲$ potencialment molt més llarga que N. Abdós métodos es coneixen com overlap-save i overlap-add.

Dualitat de la teorema de la convolución

És possible demostrar que:

$ℱ{\left\{𝐱\mathbf{\cdot }𝐲\right\}}_k\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\sum _{n=0}^{N-1}{x}_n\cdot y_n\cdot e^{-\frac{2\pi i}{N}kn}$

$=\frac{1}{N}(𝐗\mathbf{*}{𝐘}_{𝐍}{)}_k,$   que és la convolución circular de $𝐗$ i $𝐘$.

Polinomi d'interpolació trigonométrica

El polinomi interpolador trigonométrico

$p(t)=\frac{1}{N}[X_0+X_1{e}^{it}+\cdots +X_{N/2-1}{e}^{(N/2-1)it}+X_{N/2}\cos (Nt/2)+X_{N/2+1}{e}^{(-N/2+1)it}+\cdots +X_{N-1}{e}^{-it}]$ per a N parell,

$p(t)=\frac{1}{N}[X_0+X_1{e}^{it}+\cdots +X_{\lfloor N/2\rfloor }{e}^{\lfloor N/2\rfloor it}+X_{\lfloor N/2\rfloor +1}{e}^{-\lfloor N/2\rfloor it}+\cdots +X_{N-1}{e}^{-it}]$ per a N impar,

a on els coeficients X_k vénen daus per la DFT de x_n anterior, satisfà la propietat d'interpolació $p(2\pi n/N)=x_n$ per a $n=0,\dots ,N-1$.

Per a N parell, vore que la Freqüència de Nyquist $\frac{X_{N/2}}{N}\cos (Nt/2)$ es maneja de forma especial.

Esta interpolació no és única: el aliasing implica que es podria sumar N a qualsevol freqüència complexa sinusoidal (per eixemple, canviant $e^{-it}$ per $e^{i(N-1)t}$ ) sense que s'altere la propietat d'interpolació, pero donant valors diferents entre $x_n$ punts. De tots modos, açò té dos propietats interessants. En primer lloc, consistix en sinusoide les freqüències dels quals tenen les magnituts més chicotetes possibles: l'interpolació és llimitada en banda. I en segon lloc, si $x_n$ són número real, llavors $p(t)$ és també real.

En contrast, el polinomi d'interpolació trigonométrica més obvi és el que el ranc del qual de freqüències va de 0 a N-1 (en lloc de $-N/2$ to $+N/2$ com s'ha vist prèviament), similar la fòrmula de la DFT inversa. Esta interpolació no minimisa la pendent, i en general no pren valors reals per a un $x_n$ real; el seu us és un error comú.

La DFT unitària

Una atra forma d'interpretar la DFT és donant-se conte de que pot expressar-se com una matriu de Vandermonde:

$𝐅=\left[\begin{array}{cccc}{\omega }_N^{0\cdot 0}& {\omega }_N^{0\cdot 1}& \dots & {\omega }_N^{0\cdot (N-1)}\\ {\omega }_N^{1\cdot 0}& {\omega }_N^{1\cdot 1}& \dots & {\omega }_N^{1\cdot (N-1)}\\ ⋮& ⋮& \ddots & ⋮\\ {\omega }_N^{(N-1)\cdot 0}& {\omega }_N^{(N-1)\cdot 1}& \dots & {\omega }_N^{(N-1)\cdot (N-1)}\end{array}\right]$

a on

${\omega }_N=e^{-2\pi i/N}$

és una raïl de l'unitat. La transformada inversa ve llavors donada per l'inversa de la matriu anterior:

${𝐅}^{-1}=\frac{1}{N}{𝐅}^{*}$

En constants de normalisació unitàries $1/\sqrt{N}$, la DFT es convertix en una transformació unitària, definida per una matriu unitària:

$𝐔=𝐅/\sqrt{N}$

${𝐔}^{-1}={𝐔}^{*}$

$|\det (𝐔)|=1$

a on det()  és el determinant. Dit determinant és el producte dels valors propis, que sempre són $\pm 1$ o $\pm i$. En un espai vectorial real, una transformació unitària pot vore's simplement com una rotació rígida del sistema de coordenades, i totes les propietats d'esta rotació rígida poden trobar-se en la DFT unitària. l'ortogonalidad de la DFT es convertix ara en ortonormalidad.

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

Si $𝐗$ es definix com la DFT unitària del vector $𝐱$ llavors

$X_k=\sum _{n=0}^{N-1}{U}_{kn}{x}_n$

i el Teorema de Plancherel s'expressa com:

$\sum _{n=0}^{N-1}{x}_n{y}_n^{*}=\sum _{k=0}^{N-1}{X}_k{Y}_k^{*}$

Si veem la DFT simplement com una transformació de coordenades que simplement expressa els components d'un vector en un nou sistema de coordenades, llavors lo anterior és la demostració de que el producte escalar de dos vectores es conserva en una transformació unitària de la DFT. Per al cas especial $𝐱=𝐲$, açò implica que la llongitut del vector també es manté—açò és el Teorema de Parseval:

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

Vore també

• Image digital