Transformada discreta de Fourier

Tipo de transformada de Fourier en matemáticas discretas

Fig 1: Relación entre la transformada de Fourier (continua) y la transformada de Fourier discreta.
Izquierda: una función continua (arriba) y su transformada de Fourier (abajo).
Centro izquierda: suma periódica de la función original (arriba). La transformada de Fourier (abajo) es cero excepto en puntos discretos. La transformada inversa es una suma de sinusoides llamada serie de Fourier .
Centro derecha: la función original está discretizada (multiplicada por un peine de Dirac ) (arriba). Su transformada de Fourier (abajo) es una suma periódica ( DTFT ) de la transformada original.
Derecha: La DFT (abajo) calcula muestras discretas de la DTFT continua. La DFT inversa (arriba) es una suma periódica de las muestras originales. El algoritmo FFT calcula un ciclo de la DFT y su inverso es un ciclo de la DFT inversa.

Fig 2: Representación de una transformada de Fourier (arriba a la izquierda) y su suma periódica (DTFT) en la esquina inferior izquierda. Las secuencias espectrales en (a) arriba a la derecha y (b) abajo a la derecha se calculan respectivamente a partir de (a) un ciclo de la suma periódica de s(t) y (b) un ciclo de la suma periódica de la secuencia s(nT) . Las fórmulas respectivas son (a) la integral de serie de Fourier y (b) la sumatoria DFT . Sus similitudes con la transformada original, S(f), y su relativa facilidad computacional son a menudo la motivación para calcular una secuencia DFT.

En matemáticas , la transformada discreta de Fourier ( DFT ) convierte una secuencia finita de muestras equiespaciadas de una función en una secuencia de la misma longitud de muestras equiespaciadas de la transformada de Fourier de tiempo discreto (DTFT), que es una transformación de valores complejos. función de la frecuencia. El intervalo en el que se muestrea la DTFT es el recíproco de la duración de la secuencia de entrada. ^{[A] [1]}   Una DFT inversa (IDFT) es una serie de Fourier , que utiliza las muestras de DTFT como coeficientes de sinusoides complejas en las frecuencias de DTFT correspondientes. Tiene los mismos valores de muestra que la secuencia de entrada original. Por lo tanto, se dice que la DFT es una representación en el dominio de la frecuencia de la secuencia de entrada original. Si la secuencia original abarca todos los valores distintos de cero de una función, su DTFT es continua (y periódica) y la DFT proporciona muestras discretas de un ciclo. Si la secuencia original es un ciclo de una función periódica, la DFT proporciona todos los valores distintos de cero de un ciclo DTFT.

La DFT es la transformada discreta más importante y se utiliza para realizar análisis de Fourier en muchas aplicaciones prácticas. ^[2] En el procesamiento de señales digitales , la función es cualquier cantidad o señal que varía con el tiempo, como la presión de una onda sonora , una señal de radio o lecturas diarias de temperatura , muestreadas durante un intervalo de tiempo finito (a menudo definido por una ventana función ^[3] ). En el procesamiento de imágenes , las muestras pueden ser los valores de píxeles a lo largo de una fila o columna de una imagen rasterizada . La DFT también se utiliza para resolver eficientemente ecuaciones diferenciales parciales y para realizar otras operaciones como convoluciones o multiplicación de números enteros grandes.

Dado que trata con una cantidad finita de datos, puede implementarse en computadoras mediante algoritmos numéricos o incluso hardware dedicado . Estas implementaciones suelen emplear algoritmos eficientes de transformada rápida de Fourier (FFT); ^[4] tanto es así que los términos "FFT" y "DFT" a menudo se usan indistintamente. Antes de su uso actual, es posible que el inicialismo "FFT" también se haya utilizado para el término ambiguo " transformada de Fourier finita ".

La DFT tiene muchas aplicaciones, incluidas las puramente matemáticas sin interpretación física. Pero físicamente se puede relacionar con el procesamiento de señales como una versión discreta (es decir, muestras) de la transformada de Fourier de tiempo discreto (DTFT), que es una función continua y periódica. La DFT calcula N muestras equiespaciadas de un ciclo de la DTFT. (ver Fig.2 y § Muestreo de DTFT )

Definición

La transformada discreta de Fourier transforma una secuencia de N números complejos en otra secuencia de números complejos, que está definida por: ${\displaystyle \left\{\mathbf {x} _{n}\right\}:=x_{0},x_{1},\ldots ,x_{N-1}}$ ${\displaystyle \left\{\mathbf {X} _{k}\right\}:=X_{0},X_{1},\ldots ,X_{N-1},}$

Transformada discreta de Fourier

La transformación a veces se indica con el símbolo , como en o o . ^[B] ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \mathbf {X} ={\mathcal {F}}\left\{\mathbf {x} \right\}}$ ${\displaystyle {\mathcal {F}}\left(\mathbf {x} \right)}$ ${\displaystyle {\mathcal {F}}\mathbf {x} }$

La ecuación 1 se puede interpretar o derivar de varias maneras, por ejemplo:

• Describe completamente la transformada de Fourier en tiempo discreto (DTFT) de una secuencia periódica, que comprende sólo componentes de frecuencia discreta. ^[C] ( Usando el DTFT con datos periódicos ) ${\displaystyle N}$
• También puede proporcionar muestras espaciadas uniformemente de la DTFT continua de una secuencia de longitud finita. ( § Muestreo de la DTFT )
• Es la correlación cruzada de la secuencia de entrada , y una sinusoide compleja en la frecuencia. Por lo tanto, actúa como un filtro adaptado para esa frecuencia. ${\displaystyle x_{n}}$ ${\textstyle {\frac {k}{N}}.}$
• Es el análogo discreto de la fórmula de los coeficientes de una serie de Fourier :

  ${\displaystyle C_{k}={\frac {1}{P}}\int _{P}x(t)e^{-i2\pi {\tfrac {k}{P}}t}\,dt.}$

La ecuación 1 también se puede evaluar fuera del dominio , y esa secuencia extendida es periódica . En consecuencia, a veces se utilizan otras secuencias de índices, como (si es par) y (si es impar), lo que equivale a intercambiar las mitades izquierda y derecha del resultado de la transformación. ^[5] ${\displaystyle k\in [0,N-1]}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\textstyle \left[-{\frac {N}{2}},{\frac {N}{2}}-1\right]}$ ${\displaystyle N}$ ${\textstyle \left[-{\frac {N-1}{2}},{\frac {N-1}{2}}\right]}$ ${\displaystyle N}$

La transformada inversa viene dada por:

transformada inversa

Ecuación 2 . también es periódico (en el índice n). En la ecuación 2 , cada uno es un número complejo cuyas coordenadas polares son la amplitud y la fase de un componente sinusoidal complejo de una función (consulte la serie discreta de Fourier ). La frecuencia de la sinusoide son ciclos por muestra. ${\displaystyle N}$ ${\displaystyle X_{k}}$ ${\displaystyle \left(e^{i2\pi {\tfrac {k}{N}}n}\right)}$ ${\displaystyle x_{n}.}$ ${\displaystyle k}$ ${\displaystyle N}$

El factor de normalización que multiplica DFT e IDFT (aquí 1 y ) y los signos de los exponentes son las convenciones más comunes . Los únicos requisitos reales de estas convenciones son que DFT e IDFT tengan exponentes de signos opuestos y que el producto de sus factores de normalización sea unitario. Una normalización poco común de tanto para DFT como para IDFT hace que el par de transformadas sea unitario. ${\displaystyle {\tfrac {1}{N}}}$ ${\displaystyle {\tfrac {1}{N}}.}$ ${\displaystyle {\sqrt {\tfrac {1}{N}}}}$

Ejemplo

Este ejemplo demuestra cómo aplicar la DFT a una secuencia de longitud y el vector de entrada. ${\displaystyle N=4}$

$${\displaystyle \mathbf {x} ={\begin{pmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\begin{pmatrix}1\\2-i\\-i\\-1+2i\end{pmatrix}}.}$$

Calcular el DFT de usar la Ec.1 ${\displaystyle \mathbf {x} }$

$${\displaystyle {\begin{aligned}X_{0}&=e^{-i2\pi 0\cdot 0/4}\cdot 1+e^{-i2\pi 0\cdot 1/4}\cdot (2-i)+e^{-i2\pi 0\cdot 2/4}\cdot (-i)+e^{-i2\pi 0\cdot 3/4}\cdot (-1+2i)=2\\X_{1}&=e^{-i2\pi 1\cdot 0/4}\cdot 1+e^{-i2\pi 1\cdot 1/4}\cdot (2-i)+e^{-i2\pi 1\cdot 2/4}\cdot (-i)+e^{-i2\pi 1\cdot 3/4}\cdot (-1+2i)=-2-2i\\X_{2}&=e^{-i2\pi 2\cdot 0/4}\cdot 1+e^{-i2\pi 2\cdot 1/4}\cdot (2-i)+e^{-i2\pi 2\cdot 2/4}\cdot (-i)+e^{-i2\pi 2\cdot 3/4}\cdot (-1+2i)=-2i\\X_{3}&=e^{-i2\pi 3\cdot 0/4}\cdot 1+e^{-i2\pi 3\cdot 1/4}\cdot (2-i)+e^{-i2\pi 3\cdot 2/4}\cdot (-i)+e^{-i2\pi 3\cdot 3/4}\cdot (-1+2i)=4+4i\end{aligned}}}$$

resultados en

$${\displaystyle \mathbf {X} ={\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{pmatrix}}={\begin{pmatrix}2\\-2-2i\\-2i\\4+4i\end{pmatrix}}.}$$

Propiedades

Linealidad

La DFT es una transformación lineal, es decir, si y , entonces para cualquier número complejo : ${\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}}$ ${\displaystyle {\mathcal {F}}(\{y_{n}\})_{k}=Y_{k}}$ ${\displaystyle a,b}$

${\displaystyle {\mathcal {F}}(\{ax_{n}+by_{n}\})_{k}=aX_{k}+bY_{k}}$

Inversión de tiempo y frecuencia.

Invertir el tiempo (es decir, reemplazar por ) ^[D] en corresponde a invertir la frecuencia (es decir, por ). ^{[6] : p.421} Matemáticamente, si representa el vector x entonces ${\displaystyle n}$ ${\displaystyle N-n}$ ${\displaystyle x_{n}}$ ${\displaystyle k}$ ${\displaystyle N-k}$ ${\displaystyle \{x_{n}\}}$

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

entonces ${\displaystyle {\mathcal {F}}(\{x_{N-n}\})_{k}=X_{N-k}}$

Conjugación en el tiempo

Si entonces . ^{[6] : pág.423} ${\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}}$ ${\displaystyle {\mathcal {F}}(\{x_{n}^{*}\})_{k}=X_{N-k}^{*}}$

Parte real e imaginaria

Esta tabla muestra algunas operaciones matemáticas en el dominio del tiempo y los efectos correspondientes en su DFT en el dominio de la frecuencia. ${\displaystyle x_{n}}$ ${\displaystyle X_{k}}$

Ortogonalidad

Los vectores forman una base ortogonal sobre el conjunto de N -vectores complejos dimensionales: ${\displaystyle u_{k}=\left[\left.e^{{\frac {i2\pi }{N}}kn}\;\right|\;n=0,1,\ldots ,N-1\right]^{\mathsf {T}}}$

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

¿Dónde está el delta del Kronecker ? (En el último paso, la suma es trivial si , donde es 1 + 1 + ⋯ = N , y en caso contrario es una serie geométrica que se puede sumar explícitamente para obtener cero). Esta condición de ortogonalidad se puede utilizar para derivar la fórmula para el IDFT de la definición de DFT, y es equivalente a la propiedad de unitaridad a continuación. ${\displaystyle \delta _{kk'}}$ ${\displaystyle k=k'}$

El teorema de Plancherel y el teorema de Parseval

Si y son las DFT de y respectivamente, entonces el teorema de Parseval establece: ${\displaystyle X_{k}}$ ${\displaystyle Y_{k}}$ ${\displaystyle x_{n}}$ ${\displaystyle y_{n}}$

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

donde la estrella denota conjugación compleja . El teorema de Plancherel es un caso especial del teorema de Parseval y establece:

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

Estos teoremas también son equivalentes a la condición unitaria siguiente.

Periodicidad

La periodicidad se puede mostrar directamente a partir de la definición:

${\displaystyle X_{k+N}\ \triangleq \ \sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}(k+N)n}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}kn}\underbrace {e^{-i2\pi n}} _{1}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}kn}=X_{k}.}$

De manera similar, se puede demostrar que la fórmula IDFT conduce a una extensión periódica.

Teorema de cambio

Multiplicar por una fase lineal para algún número entero m corresponde a un desplazamiento circular de la salida : se reemplaza por , donde el subíndice se interpreta en módulo N (es decir, periódicamente). De manera similar, un desplazamiento circular de la entrada corresponde a multiplicar la salida por una fase lineal. Matemáticamente, si representa el vector x entonces ${\displaystyle x_{n}}$ ${\displaystyle e^{{\frac {i2\pi }{N}}nm}}$ ${\displaystyle X_{k}}$ ${\displaystyle X_{k}}$ ${\displaystyle X_{k-m}}$ ${\displaystyle x_{n}}$ ${\displaystyle X_{k}}$ ${\displaystyle \{x_{n}\}}$

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

entonces ${\displaystyle {\mathcal {F}}\left(\left\{x_{n}\cdot e^{{\frac {i2\pi }{N}}nm}\right\}\right)_{k}=X_{k-m}}$

y ${\displaystyle {\mathcal {F}}\left(\left\{x_{n-m}\right\}\right)_{k}=X_{k}\cdot e^{-{\frac {i2\pi }{N}}km}}$

Teorema de convolución circular y teorema de correlación cruzada

El teorema de convolución para la transformada de Fourier en tiempo discreto (DTFT) indica que se puede obtener una convolución de dos secuencias como la transformada inversa del producto de las transformadas individuales. Se produce una simplificación importante cuando una de las secuencias es N-periódica, denotada aquí porque es distinta de cero solo en frecuencias discretas (ver DTFT § Datos periódicos ), y por lo tanto también lo es su producto con la función continua.   Eso conduce a una simplificación considerable de la transformada inversa. ${\displaystyle y_{_{N}},}$ ${\displaystyle \scriptstyle {\text{DTFT}}\displaystyle \{y_{_{N}}\}}$ ${\displaystyle \scriptstyle {\text{DTFT}}\displaystyle \{x\}.}$

${\displaystyle x*y_{_{N}}\ =\ \scriptstyle {\rm {DTFT}}^{-1}\displaystyle \left[\scriptstyle {\rm {DTFT}}\displaystyle \{x\}\cdot \scriptstyle {\rm {DTFT}}\displaystyle \{y_{_{N}}\}\right]\ =\ \scriptstyle {\rm {DFT}}^{-1}\displaystyle \left[\scriptstyle {\rm {DFT}}\displaystyle \{x_{_{N}}\}\cdot \scriptstyle {\rm {DFT}}\displaystyle \{y_{_{N}}\}\right],}$

donde es una suma periódica de la secuencia : ${\displaystyle x_{_{N}}}$ ${\displaystyle x}$ ${\displaystyle (x_{_{N}})_{n}\ \triangleq \sum _{m=-\infty }^{\infty }x_{(n-mN)}.}$

Habitualmente, las sumas DFT y DFT inversa se toman en el dominio . Al definir esas DFT como y , el resultado es : ${\displaystyle [0,N-1]}$ ${\displaystyle X}$ ${\displaystyle Y}$

${\displaystyle (x*y_{_{N}})_{n}\triangleq \sum _{\ell =-\infty }^{\infty }x_{\ell }\cdot (y_{_{N}})_{n-\ell }=\underbrace {{\mathcal {F}}^{-1}} _{\rm {DFT^{-1}}}\left\{X\cdot Y\right\}_{n}.}$

En la práctica, la secuencia suele tener una longitud N o menos, y es una extensión periódica de una secuencia de N longitud , que también se puede expresar como una función circular : ${\displaystyle x}$ ${\displaystyle y_{_{N}}}$ ${\displaystyle y}$

${\displaystyle (y_{_{N}})_{n}=\sum _{p=-\infty }^{\infty }y_{(n-pN)}=y_{(n\operatorname {mod} N)},\quad n\in \mathbb {Z} .}$

Entonces la convolución se puede escribir como :

${\displaystyle {\mathcal {F}}^{-1}\left\{X\cdot Y\right\}_{n}=\sum _{\ell =0}^{N-1}x_{\ell }\cdot y_{_{(n-\ell )\operatorname {mod} N}}}$

lo que da lugar a la interpretación como una convolución circular de y ^{[7] [8]} A menudo se utiliza para calcular eficientemente su convolución lineal. (ver Convolución circular , Algoritmos de convolución rápida y Guardar superposición ) ${\displaystyle x}$ ${\displaystyle y.}$

De manera similar, la correlación cruzada de y viene dada por : ${\displaystyle x}$ ${\displaystyle y_{_{N}}}$

${\displaystyle (x\star y_{_{N}})_{n}\triangleq \sum _{\ell =-\infty }^{\infty }x_{\ell }^{*}\cdot (y_{_{N}})_{n+\ell }={\mathcal {F}}^{-1}\left\{X^{*}\cdot Y\right\}_{n}.}$

Unicidad de la transformada discreta de Fourier

Como se vio arriba, la transformada discreta de Fourier tiene la propiedad fundamental de llevar la convolución al producto por componentes. Una pregunta natural es si es el único con esta habilidad. Se ha demostrado ^{[9] [10]} que cualquier transformación lineal que convierta la convolución en un producto puntual es la DFT hasta una permutación de coeficientes. Dado que el número de permutaciones de n elementos es igual a n!, existe exactamente n! mapas lineales e invertibles con la misma propiedad fundamental que la DFT con respecto a la convolución.

Dualidad del teorema de convolución

También se puede demostrar que :

${\displaystyle {\mathcal {F}}\left\{\mathbf {x\cdot y} \right\}_{k}\ \triangleq \sum _{n=0}^{N-1}x_{n}\cdot y_{n}\cdot e^{-i{\frac {2\pi }{N}}kn}}$

${\displaystyle ={\frac {1}{N}}(\mathbf {X*Y_{N}} )_{k},}$que es la convolución circular de y . ${\displaystyle \mathbf {X} }$ ${\displaystyle \mathbf {Y} }$

Polinomio de interpolación trigonométrica

El polinomio de interpolación trigonométrica

${\displaystyle p(t)={\begin{cases}{\frac {1}{N}}\left[X_{0}+X_{1}e^{i2\pi t}+\cdots +X_{N/2-1}e^{i2\pi (N/2-1)t}+X_{N/2}\cos(N\pi t)+X_{N/2+1}e^{-i2\pi (N/2-1)t}+\cdots +X_{N-1}e^{-i2\pi t}\right]&N{\text{ even}}\\{\frac {1}{N}}\left[X_{0}+X_{1}e^{i2\pi t}+\cdots +X_{(N-1)/2}e^{i2\pi (N-1)t}+X_{(N+1)/2}e^{-i2\pi (N-1)t}+\cdots +X_{N-1}e^{-i2\pi t}\right]&N{\text{ odd}}\end{cases}}}$

donde los coeficientes X _k están dados por la DFT de x _n anterior, satisface la propiedad de interpolación para . ${\displaystyle p(n/N)=x_{n}}$ ${\displaystyle n=0,\ldots ,N-1}$

Incluso para N , observe que el componente Nyquist se maneja de manera especial. ${\textstyle {\frac {X_{N/2}}{N}}\cos(N\pi t)}$

Esta interpolación no es única : el alias implica que se podría agregar N a cualquiera de las frecuencias sinusoidales complejas (por ejemplo, cambiar a ) sin cambiar la propiedad de interpolación, pero dando diferentes valores entre los puntos. La elección anterior, sin embargo, es típica porque tiene dos propiedades útiles. En primer lugar, consta de sinusoides cuyas frecuencias tienen las magnitudes más pequeñas posibles: la interpolación está limitada por banda . En segundo lugar, si son números reales, entonces también lo son. ${\displaystyle e^{-it}}$ ${\displaystyle e^{i(N-1)t}}$ ${\displaystyle x_{n}}$ ${\displaystyle x_{n}}$ ${\displaystyle p(t)}$

Por el contrario, el polinomio de interpolación trigonométrica más obvio es aquel en el que las frecuencias varían de 0 a (en lugar de aproximadamente a como se indicó anteriormente), similar a la fórmula DFT inversa. Esta interpolación no minimiza la pendiente y, por lo general, no tiene un valor real real ; su uso es un error común. ${\displaystyle N-1}$ ${\displaystyle -N/2}$ ${\displaystyle +N/2}$ ${\displaystyle x_{n}}$

La DFT unitaria

Otra forma de ver la DFT es observar que en la discusión anterior, la DFT se puede expresar como la matriz DFT , una matriz de Vandermonde , introducida por Sylvester en 1867,

${\displaystyle \mathbf {F} ={\begin{bmatrix}\omega _{N}^{0\cdot 0}&\omega _{N}^{0\cdot 1}&\cdots &\omega _{N}^{0\cdot (N-1)}\\\omega _{N}^{1\cdot 0}&\omega _{N}^{1\cdot 1}&\cdots &\omega _{N}^{1\cdot (N-1)}\\\vdots &\vdots &\ddots &\vdots \\\omega _{N}^{(N-1)\cdot 0}&\omega _{N}^{(N-1)\cdot 1}&\cdots &\omega _{N}^{(N-1)\cdot (N-1)}\\\end{bmatrix}}}$

donde es una raíz N primitiva de la unidad . ${\displaystyle \omega _{N}=e^{-i2\pi /N}}$

Por ejemplo, en el caso de que , y ${\displaystyle N=2}$ ${\displaystyle \omega _{N}=e^{-i\pi }=-1}$

${\displaystyle \mathbf {F} ={\begin{bmatrix}1&1\\1&-1\\\end{bmatrix}},}$

(que es una matriz de Hadamard ) o cuando, como en la transformada discreta de Fourier § Ejemplo anterior, y ${\displaystyle N=4}$ ${\displaystyle \omega _{N}=e^{-i\pi /2}=-i}$

${\displaystyle \mathbf {F} ={\begin{bmatrix}1&1&1&1\\1&-i&-1&i\\1&-1&1&-1\\1&i&-1&-i\\\end{bmatrix}}.}$

La transformada inversa viene dada por la inversa de la matriz anterior,

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

Con constantes de normalización unitarias , la DFT se convierte en una transformación unitaria , definida por una matriz unitaria: ${\textstyle 1/{\sqrt {N}}}$

${\displaystyle {\begin{aligned}\mathbf {U} &={\frac {1}{\sqrt {N}}}\mathbf {F} \\\mathbf {U} ^{-1}&=\mathbf {U} ^{*}\\\left|\det(\mathbf {U} )\right|&=1\end{aligned}}}$

¿ Dónde está la función determinante ? El determinante es el producto de los valores propios, que son siempre o como se describe a continuación. En un espacio vectorial real, se puede considerar una transformación unitaria como simplemente una rotación rígida del sistema de coordenadas, y todas las propiedades de una rotación rígida se pueden encontrar en la DFT unitaria. ${\displaystyle \det()}$ ${\displaystyle \pm 1}$ ${\displaystyle \pm i}$

La ortogonalidad de la DFT ahora se expresa como una condición de ortonormalidad (que surge en muchas áreas de las matemáticas como se describe en raíz de la unidad ):

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

Si X se define como la DFT unitaria del vector x , entonces

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

y el teorema de Parseval se expresa como

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

Si vemos la DFT simplemente como una transformación de coordenadas que simplemente especifica los componentes de un vector en un nuevo sistema de coordenadas, entonces lo anterior es solo la afirmación de que el producto escalar de dos vectores se conserva bajo una transformación DFT unitaria. Para el caso especial , esto implica que la longitud de un vector también se conserva; esto es solo el teorema de Plancherel , ${\displaystyle \mathbf {x} =\mathbf {y} }$

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

Una consecuencia del teorema de convolución circular es que la matriz DFT F diagonaliza cualquier matriz circulante .

Expresar la DFT inversa en términos de la DFT

Una propiedad útil de la DFT es que la DFT inversa se puede expresar fácilmente en términos de la DFT (directa), mediante varios "trucos" bien conocidos. (Por ejemplo, en los cálculos, a menudo es conveniente implementar solo una transformada rápida de Fourier correspondiente a una dirección de transformación y luego obtener la otra dirección de transformación a partir de la primera).

Primero, podemos calcular la DFT inversa invirtiendo todas las entradas menos una (Duhamel et al. , 1988):

${\displaystyle {\mathcal {F}}^{-1}(\{x_{n}\})={\frac {1}{N}}{\mathcal {F}}(\{x_{N-n}\})}$

(Como es habitual, los subíndices se interpretan en módulo N ; por lo tanto, para , tenemos ). ${\displaystyle n=0}$ ${\displaystyle x_{N-0}=x_{0}}$

En segundo lugar, también se pueden conjugar las entradas y salidas:

${\displaystyle {\mathcal {F}}^{-1}(\mathbf {x} )={\frac {1}{N}}{\mathcal {F}}\left(\mathbf {x} ^{*}\right)^{*}}$

En tercer lugar, una variante de este truco de conjugación, que a veces es preferible porque no requiere modificación de los valores de los datos, implica intercambiar partes reales e imaginarias (lo que se puede hacer en una computadora simplemente modificando los punteros ). Defina como con sus partes real e imaginaria intercambiadas, es decir, si entonces es . Equivalentemente, es igual a . Entonces ${\textstyle \operatorname {swap} (x_{n})}$ ${\displaystyle x_{n}}$ ${\displaystyle x_{n}=a+bi}$ ${\textstyle \operatorname {swap} (x_{n})}$ ${\displaystyle b+ai}$ ${\textstyle \operatorname {swap} (x_{n})}$ ${\displaystyle ix_{n}^{*}}$

${\displaystyle {\mathcal {F}}^{-1}(\mathbf {x} )={\frac {1}{N}}\operatorname {swap} ({\mathcal {F}}(\operatorname {swap} (\mathbf {x} )))}$

Es decir, la transformada inversa es la misma que la transformada directa con las partes real e imaginaria intercambiadas tanto para la entrada como para la salida, hasta una normalización (Duhamel et al. , 1988).

El truco de la conjugación también se puede utilizar para definir una nueva transformada, estrechamente relacionada con la DFT, que sea involutiva , es decir, que sea su propia inversa. En particular, es claramente su propio inverso: . Una transformación involutiva estrechamente relacionada (por un factor de ) es , ya que los factores en cancelan el 2. Para entradas reales , la parte real de no es otra que la transformada discreta de Hartley , que también es involutiva. ${\displaystyle T(\mathbf {x} )={\mathcal {F}}\left(\mathbf {x} ^{*}\right)/{\sqrt {N}}}$ ${\displaystyle T(T(\mathbf {x} ))=\mathbf {x} }$ ${\textstyle {\frac {1+i}{\sqrt {2}}}}$ ${\displaystyle H(\mathbf {x} )={\mathcal {F}}\left((1+i)\mathbf {x} ^{*}\right)/{\sqrt {2N}}}$ ${\displaystyle (1+i)}$ ${\displaystyle H(H(\mathbf {x} ))}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle H(\mathbf {x} )}$

Valores propios y vectores propios

Los valores propios de la matriz DFT son simples y bien conocidos, mientras que los vectores propios son complicados, no únicos y son objeto de investigación en curso.

Considere la forma unitaria definida anteriormente para la DFT de longitud N , donde ${\displaystyle \mathbf {U} }$

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

Esta matriz satisface la ecuación polinómica matricial :

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

Esto se puede ver en las propiedades inversas anteriores: operar dos veces da los datos originales en orden inverso, por lo que operar cuatro veces devuelve los datos originales y, por lo tanto, es la matriz de identidad . Esto significa que los valores propios satisfacen la ecuación: ${\displaystyle \mathbf {U} }$ ${\displaystyle \mathbf {U} }$ ${\displaystyle \lambda }$

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

Por lo tanto, los valores propios de son las raíces cuartas de la unidad : es +1, −1, + i o − i . ${\displaystyle \mathbf {U} }$ ${\displaystyle \lambda }$

Dado que sólo hay cuatro valores propios distintos para esta matriz, tienen cierta multiplicidad . La multiplicidad da el número de vectores propios linealmente independientes correspondientes a cada valor propio. (Hay N vectores propios independientes; una matriz unitaria nunca es defectuosa ). ${\displaystyle N\times N}$

El problema de su multiplicidad fue resuelto por McClellan y Parks (1972), aunque posteriormente se demostró que era equivalente a un problema resuelto por Gauss (Dickinson y Steiglitz, 1982). La multiplicidad depende del valor de N módulo 4 y viene dada por la siguiente tabla:

Dicho de otra manera, el polinomio característico de es: ${\displaystyle \mathbf {U} }$

${\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}}\right\rfloor }(\lambda -i)^{\left\lfloor {\tfrac {N-1}{4}}\right\rfloor }.}$

No se conoce ninguna fórmula analítica sencilla para los vectores propios generales. Además, los vectores propios no son únicos porque cualquier combinación lineal de vectores propios para el mismo valor propio también es un vector propio para ese valor propio. Varios investigadores han propuesto diferentes opciones de vectores propios, seleccionados para satisfacer propiedades útiles como la ortogonalidad y tener formas "simples" (por ejemplo, McClellan y Parks, 1972; Dickinson y Steiglitz, 1982; Grünbaum, 1982; Atakishiyev y Wolf, 1997; Candan et al. al. , 2000; Hanna et al. , 2004; Gurevich y Hadani, 2008).

Un enfoque sencillo es discretizar una función propia de la transformada continua de Fourier , de las cuales la más famosa es la función gaussiana . Dado que la suma periódica de la función significa discretizar su espectro de frecuencia y la discretización significa la suma periódica del espectro, la función gaussiana discretizada y sumada periódicamente produce un vector propio de la transformada discreta:

• ${\displaystyle F(m)=\sum _{k\in \mathbb {Z} }\exp \left(-{\frac {\pi \cdot (m+N\cdot k)^{2}}{N}}\right).}$

La expresión en forma cerrada de la serie se puede expresar mediante las funciones theta de Jacobi como

• ${\displaystyle F(m)={\frac {1}{\sqrt {N}}}\vartheta _{3}\left({\frac {\pi m}{N}},\exp \left(-{\frac {\pi }{N}}\right)\right).}$

Se encontraron otros dos vectores propios analíticos de forma cerrada simples para el período especial N de DFT (Kong, 2008):

Para el período DFT N = 2 L + 1 = 4 K + 1, donde K es un número entero, el siguiente es un vector propio de DFT:

• ${\displaystyle F(m)=\prod _{s=K+1}^{L}\left[\cos \left({\frac {2\pi }{N}}m\right)-\cos \left({\frac {2\pi }{N}}s\right)\right]}$

Para el período DFT N = 2 L = 4 K , donde K es un número entero, el siguiente es un vector propio de DFT:

• ${\displaystyle F(m)=\sin \left({\frac {2\pi }{N}}m\right)\prod _{s=K+1}^{L-1}\left[\cos \left({\frac {2\pi }{N}}m\right)-\cos \left({\frac {2\pi }{N}}s\right)\right]}$

La elección de los vectores propios de la matriz DFT se ha vuelto importante en los últimos años para definir un análogo discreto de la transformada fraccionaria de Fourier : la matriz DFT se puede llevar a potencias fraccionarias exponenciando los valores propios (p. ej., Rubio y Santhanam, 2005). Para la transformada continua de Fourier , las funciones propias ortogonales naturales son las funciones de Hermite , por lo que se han empleado varios análogos discretos de éstas como vectores propios de la DFT, como los polinomios de Kravchuk (Atakishiyev y Wolf, 1997). Sin embargo, la "mejor" elección de vectores propios para definir una transformada de Fourier discreta fraccionaria sigue siendo una cuestión abierta.

Principios de incertidumbre

Principio de incertidumbre probabilística

Si la variable aleatoria X _k está restringida por

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

entonces

${\displaystyle P_{n}=|X_{n}|^{2}}$

puede considerarse que representa una función de masa de probabilidad discreta de n , con una función de masa de probabilidad asociada construida a partir de la variable transformada,

${\displaystyle Q_{m}=N|x_{m}|^{2}.}$

Para el caso de funciones continuas y , el principio de incertidumbre de Heisenberg establece que ${\displaystyle P(x)}$ ${\displaystyle Q(k)}$

${\displaystyle D_{0}(X)D_{0}(x)\geq {\frac {1}{16\pi ^{2}}}}$

donde y son las varianzas de y respectivamente, con la igualdad lograda en el caso de una distribución gaussiana adecuadamente normalizada . Aunque las varianzas pueden definirse de manera análoga para la DFT, un principio de incertidumbre análogo no es útil, porque la incertidumbre no será invariante al cambio. Aún así, Massar y Spindel han introducido un principio de incertidumbre significativo. ^[11] ${\displaystyle D_{0}(X)}$ ${\displaystyle D_{0}(x)}$ ${\displaystyle |X|^{2}}$ ${\displaystyle |x|^{2}}$

Sin embargo, la incertidumbre entrópica de Hirschman tendrá un análogo útil para el caso de la DFT. ^[12] El principio de incertidumbre de Hirschman se expresa en términos de la entropía de Shannon de las dos funciones de probabilidad.

En el caso discreto, las entropías de Shannon se definen como

${\displaystyle H(X)=-\sum _{n=0}^{N-1}P_{n}\ln P_{n}}$

y

${\displaystyle H(x)=-\sum _{m=0}^{N-1}Q_{m}\ln Q_{m},}$

y el principio de incertidumbre entrópica se convierte en ^[12]

${\displaystyle H(X)+H(x)\geq \ln(N).}$

La igualdad se obtiene para iguales a traslaciones y modulaciones de un peine de período de Kronecker adecuadamente normalizado donde es cualquier divisor entero exacto de . La función de masa de probabilidad será entonces proporcional a un peine de período de Kronecker adecuadamente trasladado . ^[12] ${\displaystyle P_{n}}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle N}$ ${\displaystyle Q_{m}}$ ${\displaystyle B=N/A}$

Principio de incertidumbre determinista

También existe un principio de incertidumbre determinista bien conocido que utiliza la escasez de señal (o el número de coeficientes distintos de cero). ^[13] Sea y el número de elementos distintos de cero de las secuencias de tiempo y frecuencia y , respectivamente. Entonces, ${\displaystyle \left\|x\right\|_{0}}$ ${\displaystyle \left\|X\right\|_{0}}$ ${\displaystyle x_{0},x_{1},\ldots ,x_{N-1}}$ ${\displaystyle X_{0},X_{1},\ldots ,X_{N-1}}$

${\displaystyle N\leq \left\|x\right\|_{0}\cdot \left\|X\right\|_{0}.}$

Como consecuencia inmediata de la desigualdad de las medias aritméticas y geométricas , también se tiene . Se demostró que ambos principios de incertidumbre son estrictos para secuencias de "valla" elegidas específicamente (trenes de impulsos discretos) y encuentran un uso práctico para aplicaciones de recuperación de señales. ^[13] ${\displaystyle 2{\sqrt {N}}\leq \left\|x\right\|_{0}+\left\|X\right\|_{0}}$

DFT de señales reales y puramente imaginarias.

• Si son números reales , como suele serlo en aplicaciones prácticas, entonces la DFT es incluso simétrica : ${\displaystyle x_{0},\ldots ,x_{N-1}}$ ${\displaystyle X_{0},\ldots ,X_{N-1}}$

${\displaystyle x_{n}\in \mathbb {R} \quad \forall n\in \{0,\ldots ,N-1\}\implies X_{k}=X_{-k\mod N}^{*}\quad \forall k\in \{0,\ldots ,N-1\}}$, donde denota conjugación compleja . ${\displaystyle X^{*}\,}$

De ello se deduce que incluso y tienen valores reales, y el resto de la DFT está completamente especificado solo por números complejos. ${\displaystyle N}$ ${\displaystyle X_{0}}$ ${\displaystyle X_{N/2}}$ ${\displaystyle N/2-1}$

• Si son números puramente imaginarios, entonces la DFT es simétrica impar : ${\displaystyle x_{0},\ldots ,x_{N-1}}$ ${\displaystyle X_{0},\ldots ,X_{N-1}}$

${\displaystyle x_{n}\in i\mathbb {R} \quad \forall n\in \{0,\ldots ,N-1\}\implies X_{k}=-X_{-k\mod N}^{*}\quad \forall k\in \{0,\ldots ,N-1\}}$, donde denota conjugación compleja . ${\displaystyle X^{*}\,}$

DFT generalizada (fase desplazada y no lineal)

Es posible cambiar el muestreo de transformada en el dominio del tiempo y/o de la frecuencia mediante algunos cambios reales a y b , respectivamente. Esto a veces se conoce como DFT generalizado (o GDFT ), también llamado DFT desplazado o DFT desplazado , y tiene propiedades análogas a las del DFT ordinario:

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

Lo más frecuente es que se utilicen turnos de (media muestra). Mientras que la DFT ordinaria corresponde a una señal periódica en el dominio del tiempo y la frecuencia, produce una señal que es antiperiódica en el dominio de la frecuencia ( ) y viceversa para . Por lo tanto, el caso específico de se conoce como transformada de Fourier discreta de frecuencia impar en tiempo impar (u O ² DFT). Estas transformaciones desplazadas se utilizan con mayor frecuencia para datos simétricos, para representar diferentes simetrías de límites, y para datos simétricos reales corresponden a diferentes formas de transformadas discretas de coseno y seno . ${\displaystyle 1/2}$ ${\displaystyle a=1/2}$ ${\displaystyle X_{k+N}=-X_{k}}$ ${\displaystyle b=1/2}$ ${\displaystyle a=b=1/2}$

Otra opción interesante es , que se llama DFT centrada (o CDFT ). La DFT centrada tiene la útil propiedad de que, cuando N es múltiplo de cuatro, sus cuatro valores propios (ver arriba) tienen multiplicidades iguales (Rubio y Santhanam, 2005) ^[14] ${\displaystyle a=b=-(N-1)/2}$

El término GDFT también se utiliza para las extensiones de fase no lineales de DFT. Por lo tanto, el método GDFT proporciona una generalización para transformaciones de bloques ortogonales de amplitud constante, incluidos los tipos de fase lineales y no lineales. GDFT es un marco para mejorar las propiedades en el dominio del tiempo y la frecuencia de la DFT tradicional, por ejemplo, correlaciones automáticas/cruzadas, mediante la adición de la función de conformación de fase correctamente diseñada (no lineal, en general) a las funciones de fase lineal originales (Akansu y Agirman-Tosun, 2010). ^[15]

La transformada discreta de Fourier puede verse como un caso especial de la transformada z , evaluada en el círculo unitario en el plano complejo; Las transformadas z más generales corresponden a los cambios complejos a y b anteriores.

DFT multidimensional

La DFT ordinaria transforma una secuencia o matriz unidimensional que es función de exactamente una variable discreta n . La DFT multidimensional de una matriz multidimensional que es función de d variables discretas para in se define por: ${\displaystyle x_{n}}$ ${\displaystyle x_{n_{1},n_{2},\dots ,n_{d}}}$ ${\displaystyle n_{\ell }=0,1,\dots ,N_{\ell }-1}$ ${\displaystyle \ell }$ ${\displaystyle 1,2,\dots ,d}$

${\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),}$

donde como arriba y los índices de producción d van desde . Esto se expresa de manera más compacta en notación vectorial , donde definimos y como vectores d -dimensionales de índices de 0 a , que definimos como : ${\displaystyle \omega _{N_{\ell }}=\exp(-i2\pi /N_{\ell })}$ ${\displaystyle k_{\ell }=0,1,\dots ,N_{\ell }-1}$ ${\displaystyle \mathbf {n} =(n_{1},n_{2},\dots ,n_{d})}$ ${\displaystyle \mathbf {k} =(k_{1},k_{2},\dots ,k_{d})}$ ${\displaystyle \mathbf {N} -1}$ ${\displaystyle \mathbf {N} -1=(N_{1}-1,N_{2}-1,\dots ,N_{d}-1)}$

${\displaystyle X_{\mathbf {k} }=\sum _{\mathbf {n} =\mathbf {0} }^{\mathbf {N} -1}e^{-i2\pi \mathbf {k} \cdot (\mathbf {n} /\mathbf {N} )}x_{\mathbf {n} }\,,}$

donde la división se define como que se realizará por elementos, y la suma denota el conjunto de sumas anidadas anteriores. ${\displaystyle \mathbf {n} /\mathbf {N} }$ ${\displaystyle \mathbf {n} /\mathbf {N} =(n_{1}/N_{1},\dots ,n_{d}/N_{d})}$

La inversa de la DFT multidimensional está, análoga al caso unidimensional, dada por:

${\displaystyle x_{\mathbf {n} }={\frac {1}{\prod _{\ell =1}^{d}N_{\ell }}}\sum _{\mathbf {k} =\mathbf {0} }^{\mathbf {N} -1}e^{i2\pi \mathbf {n} \cdot (\mathbf {k} /\mathbf {N} )}X_{\mathbf {k} }\,.}$

Así como la DFT unidimensional expresa la entrada como una superposición de sinusoides, la DFT multidimensional expresa la entrada como una superposición de ondas planas o sinusoides multidimensionales. La dirección de oscilación en el espacio es . Las amplitudes son . Esta descomposición es de gran importancia para todo, desde el procesamiento de imágenes digitales (bidimensionales) hasta la resolución de ecuaciones diferenciales parciales . La solución se divide en ondas planas. ${\displaystyle x_{n}}$ ${\displaystyle \mathbf {k} /\mathbf {N} }$ ${\displaystyle X_{\mathbf {k} }}$

La DFT multidimensional se puede calcular mediante la composición de una secuencia de DFT unidimensionales a lo largo de cada dimensión. En el caso bidimensional, las DFT independientes de las filas (es decir, a lo largo de ) se calculan primero para formar una nueva matriz . Luego, las DFT independientes de y a lo largo de las columnas (a lo largo de ) se calculan para formar el resultado final . Alternativamente, se pueden calcular primero las columnas y luego las filas. El orden es irrelevante porque las sumas anidadas anteriores conmutan . ${\displaystyle x_{n_{1},n_{2}}}$ ${\displaystyle N_{1}}$ ${\displaystyle n_{2}}$ ${\displaystyle y_{n_{1},k_{2}}}$ ${\displaystyle N_{2}}$ ${\displaystyle n_{1}}$ ${\displaystyle X_{k_{1},k_{2}}}$

Por tanto, un algoritmo para calcular una DFT unidimensional es suficiente para calcular eficientemente una DFT multidimensional. Este enfoque se conoce como algoritmo fila-columna . También existen algoritmos FFT intrínsecamente multidimensionales .

La DFT multidimensional de entrada real

Para datos de entrada que consisten en números reales , las salidas DFT tienen una simetría conjugada similar al caso unidimensional anterior: ${\displaystyle x_{n_{1},n_{2},\dots ,n_{d}}}$

${\displaystyle X_{k_{1},k_{2},\dots ,k_{d}}=X_{N_{1}-k_{1},N_{2}-k_{2},\dots ,N_{d}-k_{d}}^{*},}$

donde la estrella nuevamente denota conjugación compleja y el subíndice -ésimo se interpreta nuevamente en módulo (para ). ${\displaystyle \ell }$ ${\displaystyle N_{\ell }}$ ${\displaystyle \ell =1,2,\ldots ,d}$

Aplicaciones

La DFT se ha utilizado ampliamente en una gran cantidad de campos; A continuación sólo esbozamos algunos ejemplos (véanse también las referencias al final). Todas las aplicaciones de la DFT dependen crucialmente de la disponibilidad de un algoritmo rápido para calcular transformadas de Fourier discretas y sus inversas, una transformada rápida de Fourier .

Análisis espectral

Transformaciones discretas incrustadas en el tiempo y el espacio.

Cuando la DFT se utiliza para el análisis espectral de señales , la secuencia generalmente representa un conjunto finito de muestras de tiempo uniformemente espaciadas de alguna señal , donde representa el tiempo. La conversión de tiempo continuo a muestras (tiempo discreto) cambia la transformada de Fourier subyacente a una transformada de Fourier de tiempo discreto (DTFT), que generalmente implica un tipo de distorsión llamada aliasing . La elección de una frecuencia de muestreo adecuada (consulte Frecuencia de Nyquist ) es la clave para minimizar esa distorsión. De manera similar, la conversión de una secuencia muy larga (o infinita) a un tamaño manejable conlleva un tipo de distorsión llamada fuga , que se manifiesta como una pérdida de detalle (también conocida como resolución) en el DTFT. La elección de una longitud de subsecuencia adecuada es la clave principal para minimizar ese efecto. Cuando los datos disponibles (y el tiempo para procesarlos) son mayores que la cantidad necesaria para alcanzar la resolución de frecuencia deseada, una técnica estándar es realizar múltiples DFT, por ejemplo, para crear un espectrograma . Si el resultado deseado es un espectro de potencia y hay ruido o aleatoriedad en los datos, promediar los componentes de magnitud de las múltiples DFT es un procedimiento útil para reducir la varianza del espectro (también llamado periodograma en este contexto); dos ejemplos de tales técnicas son el método Welch y el método Bartlett ; El tema general de estimar el espectro de potencia de una señal ruidosa se llama estimación espectral . ${\displaystyle \{x_{n}\}}$ ${\displaystyle x(t)\,}$ ${\displaystyle t}$ ${\displaystyle x(t)}$

Una última fuente de distorsión (o quizás ilusión ) es la propia DFT, porque es solo un muestreo discreto de la DTFT, que es función de un dominio de frecuencia continuo. Esto se puede mitigar aumentando la resolución del DFT. Ese procedimiento se ilustra en § Muestreo de DTFT .

• El procedimiento a veces se denomina relleno con ceros , que es una implementación particular que se utiliza junto con el algoritmo de transformada rápida de Fourier (FFT). La ineficiencia de realizar multiplicaciones y sumas con "muestras" de valor cero está más que compensada por la eficiencia inherente de la FFT.
• Como ya se indicó, la fuga impone un límite a la resolución inherente de la DTFT, por lo que existe un límite práctico al beneficio que se puede obtener de una DFT de grano fino.

Óptica, difracción y tomografía.

La transformada discreta de Fourier se utiliza ampliamente con frecuencias espaciales para modelar la forma en que la luz, los electrones y otras sondas viajan a través de sistemas ópticos y se dispersan desde objetos en dos y tres dimensiones. El espacio vectorial dual (directo/recíproco) de objetos tridimensionales pone además a disposición una red recíproca tridimensional, cuya construcción a partir de sombras de objetos translúcidos (a través del teorema del corte de Fourier ) permite la reconstrucción tomográfica de objetos tridimensionales con una amplia gama de aplicaciones, por ejemplo en medicina moderna.

banco de filtros

Consulte § Bancos de filtros FFT y § Muestreo de DTFT .

Compresión de datos

El campo del procesamiento de señales digitales depende en gran medida de operaciones en el dominio de la frecuencia (es decir, de la transformada de Fourier). Por ejemplo, varios métodos de compresión de imágenes y sonido con pérdida emplean la transformada discreta de Fourier: la señal se corta en segmentos cortos, cada uno se transforma y luego se descartan los coeficientes de Fourier de las altas frecuencias, que se supone que son imperceptibles. El descompresor calcula la transformada inversa basándose en este número reducido de coeficientes de Fourier. (Las aplicaciones de compresión suelen utilizar una forma especializada de DFT, la transformada de coseno discreta o, a veces, la transformada de coseno discreta modificada ). Sin embargo, algunos algoritmos de compresión relativamente recientes utilizan transformadas wavelet , que ofrecen un compromiso más uniforme entre el dominio del tiempo y la frecuencia que el obtenido. cortando los datos en segmentos y transformando cada segmento. En el caso de JPEG2000 , esto evita las características de imagen falsas que aparecen cuando las imágenes están muy comprimidas con el JPEG original .

Ecuaciones diferenciales parciales

Las transformadas discretas de Fourier se suelen utilizar para resolver ecuaciones diferenciales parciales , donde nuevamente la DFT se utiliza como una aproximación para la serie de Fourier (que se recupera en el límite del infinito N ). La ventaja de este enfoque es que expande la señal en exponenciales complejas , que son funciones propias de diferenciación: . Por tanto, en la representación de Fourier, la diferenciación es simple: simplemente multiplicamos por . (Sin embargo, la elección de no es única debido al alias; para que el método sea convergente, se debe utilizar una elección similar a la de la sección de interpolación trigonométrica anterior). Una ecuación diferencial lineal con coeficientes constantes se transforma en una ecuación algebraica de fácil solución. ecuación. Luego se utiliza la DFT inversa para transformar el resultado nuevamente en la representación espacial ordinaria. Este enfoque se denomina método espectral . ${\displaystyle e^{inx}}$ ${\displaystyle {{\text{d}}{\big (}e^{inx}{\big )}}/{\text{d}}x=ine^{inx}}$ ${\displaystyle in}$ ${\displaystyle n}$

Multiplicación de polinomios

Supongamos que deseamos calcular el producto polinómico c ( x ) = a ( x ) · b ( x ). La expresión del producto ordinario para los coeficientes de c implica una convolución lineal (acíclica), donde los índices no "se enrollan". Esto se puede reescribir como una convolución cíclica tomando primero los vectores de coeficientes para a ( x ) y b ( x ) con término constante, luego agregando ceros para que los vectores de coeficientes resultantes a y b tengan dimensión d  > grados ( a ( x ) ) + grados( b ( x )) . Entonces,

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

Donde c es el vector de coeficientes para c ( x ), y el operador de convolución se define así ${\displaystyle *\,}$

${\displaystyle c_{n}=\sum _{m=0}^{d-1}a_{m}b_{n-m\ \mathrm {mod} \ d}\qquad \qquad \qquad n=0,1\dots ,d-1}$

Pero la convolución se convierte en multiplicación bajo la DFT:

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

Aquí el producto vectorial se toma por elementos. Por lo tanto, los coeficientes del polinomio producto c ( x ) son solo los términos 0, ..., grados ( a ( x )) + grados ( b ( x )) del vector de coeficientes

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

Con una rápida transformada de Fourier , el algoritmo resultante toma O ( N  log  N ) operaciones aritméticas. Debido a su simplicidad y velocidad, a menudo se elige para la operación de transformación el algoritmo Cooley-Tukey FFT , que está limitado a tamaños compuestos . En este caso, d debe elegirse como el entero más pequeño mayor que la suma de los grados del polinomio de entrada que se puede factorizar en factores primos pequeños (por ejemplo, 2, 3 y 5, dependiendo de la implementación de FFT).

Multiplicación de números enteros grandes

Los algoritmos más rápidos conocidos para la multiplicación de números enteros muy grandes utilizan el método de multiplicación polinomial descrito anteriormente. Los números enteros se pueden tratar como el valor de un polinomio evaluado específicamente en la base numérica, con los coeficientes del polinomio correspondientes a los dígitos en esa base (ej. ). Después de la multiplicación polinomial, un paso de propagación de acarreo de complejidad relativamente baja completa la multiplicación. ${\displaystyle 123=1\cdot 10^{2}+2\cdot 10^{1}+3\cdot 10^{0}}$

Circunvolución

Cuando los datos se convolucionan con una función con amplio soporte, como para reducir la resolución mediante una proporción de muestreo grande, debido al teorema de convolución y al algoritmo FFT, puede ser más rápido transformarlos, multiplicarlos puntualmente por la transformación del filtro y luego invertir transformarlo. Alternativamente, se obtiene un buen filtro simplemente truncando los datos transformados y volviendo a transformar el conjunto de datos acortado.

Algunos pares de transformadas discretas de Fourier

Generalizaciones

Teoría de la representación

La DFT se puede interpretar como una representación de valores complejos del grupo cíclico finito . En otras palabras, una secuencia de números complejos puede considerarse como un elemento de espacio complejo de dimensiones o, de manera equivalente, una función del grupo cíclico finito de orden a los números complejos . También lo es una función de clase en el grupo cíclico finito y, por tanto, puede expresarse como una combinación lineal de los caracteres irreducibles de este grupo, que son las raíces de la unidad. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \mathbb {C} ^{n}}$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle \mathbb {Z} _{n}\mapsto \mathbb {C} }$ ${\displaystyle f}$

Desde este punto de vista, se puede generalizar la DFT a la teoría de la representación en general, o más específicamente a la teoría de la representación de grupos finitos .

De manera más específica aún, se puede generalizar la DFT cambiando el objetivo (tomando valores en un campo distinto de los números complejos) o el dominio (un grupo distinto de un grupo cíclico finito), como se detalla en la continuación.

Otros campos

Muchas de las propiedades de la DFT sólo dependen del hecho de que es una raíz primitiva de unidad , a veces denotada o (de modo que ). Dichas propiedades incluyen las propiedades de integridad, ortogonalidad, Plancherel/Parseval, periodicidad, desplazamiento, convolución y unitaridad anteriores, así como muchos algoritmos FFT. Por esta razón, la transformada discreta de Fourier se puede definir utilizando raíces de unidad en campos distintos de los números complejos, y tales generalizaciones se denominan comúnmente transformadas de teoría de números (NTT) en el caso de campos finitos . Para obtener más información, consulte Transformada teórica de números y Transformada discreta de Fourier (general) . ${\displaystyle e^{-{\frac {i2\pi }{N}}}}$ ${\displaystyle \omega _{N}}$ ${\displaystyle W_{N}}$ ${\displaystyle \omega _{N}^{N}=1}$

Otros grupos finitos

La DFT estándar actúa sobre una secuencia x ₀ , x ₁ , ..., x _{N −1} de números complejos, que puede verse como una función {0, 1, ..., N − 1} → C . La DFT multidimensional actúa sobre secuencias multidimensionales, que pueden verse como funciones.

${\displaystyle \{0,1,\ldots ,N_{1}-1\}\times \cdots \times \{0,1,\ldots ,N_{d}-1\}\to \mathbb {C} .}$

Esto sugiere la generalización a transformadas de Fourier en grupos finitos arbitrarios , que actúan sobre funciones G → C donde G es un grupo finito . En este marco, la DFT estándar se ve como la transformada de Fourier en un grupo cíclico , mientras que la DFT multidimensional es una transformada de Fourier en una suma directa de grupos cíclicos.

Además, la transformada de Fourier puede realizarse en clases laterales de un grupo.

Alternativas

Existen varias alternativas al DFT para diversas aplicaciones, entre las que destacan las wavelets . El análogo de la DFT es la transformada wavelet discreta (DWT). Desde el punto de vista del análisis tiempo-frecuencia , una limitación clave de la transformada de Fourier es que no incluye información de ubicación , solo información de frecuencia y, por lo tanto, tiene dificultades para representar transitorios. Como las wavelets tienen ubicación además de frecuencia, son más capaces de representar la ubicación, a expensas de una mayor dificultad para representar la frecuencia. Para obtener más detalles, consulte la comparación de la transformada wavelet discreta con la transformada discreta de Fourier .

Ver también

• Matriz complementaria
• matriz DFT
• Transformada rápida de Fourier
• FTPACK
• FFTW
• Generalizaciones de matrices de Pauli
• Análisis espectral de mínimos cuadrados
• Lista de transformaciones relacionadas con Fourier
• Transformación multidimensional
• transformación de zak
• Transformada cuántica de Fourier

Notas

1. De manera equivalente, es la relación entre la frecuencia de muestreo y el número de muestras.
2. Como transformación lineal en un espacio vectorial de dimensión finita , la expresión DFT también se puede escribir en términos de una matriz DFT ; cuando se escala adecuadamente, se convierte en una matriz unitaria y, por lo tanto, X _k puede verse como coeficientes de x en una base ortonormal .
3. Los componentes distintos de cero de una DTFT de una secuencia periódica son un conjunto discreto de frecuencias idénticas a la DFT.
4. La inversión de tiempo para el DFT significa reemplazar por y no por para evitar índices negativos. ${\displaystyle n}$ ${\displaystyle N-n}$ ${\displaystyle n}$ ${\displaystyle -n}$

Referencias

1. Taboga, Marco (2021). “Transformada Discreta de Fourier - Frecuencias”, Conferencias sobre álgebra matricial. https://www.statlect.com/matrix-algebra/discrete-Fourier-transform-frequencies.
2. Strang, Gilbert (mayo-junio de 1994). "Ondas". Científico americano . 82 (3): 250–255. JSTOR  29775194. Este es el algoritmo numérico más importante de nuestra vida...
3. Sahidullah, Maryland; Saha, Goutam (febrero de 2013). "Una nueva técnica de ventanas para el cálculo eficiente de MFCC para el reconocimiento de hablantes". Cartas de procesamiento de señales IEEE . 20 (2): 149-152. arXiv : 1206.2437 . Código Bib : 2013ISPL...20..149S. doi :10.1109/LSP.2012.2235067. S2CID  10900793.
4. J. Cooley , P. Lewis y P. Welch (1969). "La transformada finita de Fourier". Transacciones IEEE sobre audio y electroacústica . 17 (2): 77–85. doi :10.1109/TAU.1969.1162036.{{cite journal}}: CS1 maint: multiple names: authors list (link)
5. "Desplazar el componente de frecuencia cero al centro del espectro - MATLAB fftshift". mathworks.com . Natick, MA 01760: MathWorks, Inc. Consultado el 10 de marzo de 2014 .{{cite web}}: CS1 maint: location (link)
6. Proakis, John G.; Manolakis, Dimitri G. (1996), Procesamiento de señales digitales: principios, algoritmos y aplicaciones (3 ed.), Upper Saddle River, Nueva Jersey: Prentice-Hall International, Bibcode :1996dspp.book.....P, ISBN 9780133942897, sAcfAQAAIAAJ
7. Oppenheim, Alan V .; Schafer, Ronald W .; Dólar, John R. (1999). Procesamiento de señales en tiempo discreto (2ª ed.). Upper Saddle River, Nueva Jersey: Prentice Hall. pag. 571.ISBN​ 0-13-754920-2.
8. McGillem, Clare D.; Cooper, George R. (1984). Análisis de sistemas y señales continuos y discretos (2 ed.). Holt, Rinehart y Winston. págs. 171-172. ISBN 0-03-061703-0.
9. Amiot, Emmanuel (2016). Música a través del Espacio Fourier. Ciencia de la música computacional. Zúrich: Springer. pag. 8. doi :10.1007/978-3-319-45581-5. ISBN 978-3-319-45581-5. S2CID  6224021.
10. Isabelle Baraquín; Nicolás Ratier (2023). "Singularidad de la transformada discreta de Fourier". Procesamiento de la señal . 209 : 109041. doi : 10.1016/j.sigpro.2023.109041. ISSN  0165-1684.
11. Massar, S.; Spindel, P. (2008). "Relación de incertidumbre para la transformada discreta de Fourier". Cartas de revisión física . 100 (19): 190401. arXiv : 0710.0723 . Código bibliográfico : 2008PhRvL.100s0401M. doi :10.1103/PhysRevLett.100.190401. PMID  18518426. S2CID  10076374.
12. DeBrunner, Víctor; Havlíček, Joseph P.; Przebinda, Tomasz; Özaydin, Murad (2005). "Medidas de incertidumbre basadas en entropía para L 2 ( R n ) , ℓ 2 ( Z ) {\displaystyle L^{2}(\mathbb {R} ^{n}),\ell ^{2}(\mathbb {Z } )} , y ℓ 2 ( Z / N Z ) {\displaystyle \ell ^{2}(\mathbb {Z} /N\mathbb {Z} )} con una transformada óptima de Hirschman para ℓ 2 ( Z / N Z ) { \displaystyle \ell ^{2}(\mathbb {Z} /N\mathbb {Z} )} " (PDF) . Transacciones IEEE sobre procesamiento de señales . 53 (8): 2690. Código bibliográfico : 2005ITSP...53.2690D. doi :10.1109/TSP.2005.850329. S2CID  206796625 . Consultado el 23 de junio de 2011 .
13. Donoho, DL; Stark, PB (1989). "Principios de incertidumbre y recuperación de señales". Revista SIAM de Matemática Aplicada . 49 (3): 906–931. doi :10.1137/0149053. S2CID  115142886.
14. Santhanam, Balu; Santhanam, Thalanayar S. "Funciones discretas de Gauss-Hermite y vectores propios de la transformada discreta de Fourier centrada", Actas de la 32ª Conferencia Internacional IEEE sobre Acústica, Habla y Procesamiento de Señales (ICASSP 2007, SPTM-P12.4), vol. III, págs. 1385-1388.
15. Akansu, Ali N.; Agirman-Tosun, Handan "Transformada de Fourier discreta generalizada con fase no lineal", Transacciones IEEE sobre procesamiento de señales , vol. 58, núm. 9, págs. 4547–4556, septiembre de 2010.

Otras lecturas

• Brigham, E. Orán (1988). La transformada rápida de Fourier y sus aplicaciones . Englewood Cliffs, Nueva Jersey: Prentice Hall. ISBN 978-0-13-307505-2.
• Smith, Steven W. (1999). "Capítulo 8: La transformada discreta de Fourier". La guía para científicos e ingenieros sobre el procesamiento de señales digitales (Segunda ed.). San Diego, California: Publicaciones técnicas de California. ISBN 978-0-9660176-3-2.
• Cormen, Thomas H .; Charles E. Leiserson ; Ronald L. Rivest ; Clifford Stein (2001). "Capítulo 30: Polinomios y FFT". Introducción a los algoritmos (Segunda ed.). MIT Press y McGraw-Hill. págs. 822–848. ISBN 978-0-262-03293-3.especialmente sección 30.2: DFT y FFT, págs. 830–838.
• P. Duhamel; B. Pirón; JM Etcheto (1988). "Sobre el cálculo de la DFT inversa". Transacciones IEEE sobre acústica, voz y procesamiento de señales . 36 (2): 285–286. doi :10.1109/29.1519.
• JH McClellan; Parques TW (1972). "Valores propios y vectores propios de la transformada discreta de Fourier". Transacciones IEEE sobre audio y electroacústica . 20 (1): 66–74. doi :10.1109/TAU.1972.1162342.
• Bradley W. Dickinson; Kenneth Steiglitz (1982). "Vectores propios y funciones de la transformada discreta de Fourier" (PDF) . Transacciones IEEE sobre acústica, voz y procesamiento de señales . 30 (1): 25–31. CiteSeerX  10.1.1.434.5279 . doi :10.1109/TASSP.1982.1163843.(Tenga en cuenta que este artículo tiene un aparente error tipográfico en su tabla de multiplicidades de valores propios: las columnas + i /− i están intercambiadas. La tabla correcta se puede encontrar en McClellan y Parks, 1972, y se confirma fácilmente numéricamente.)
• FA Grünbaum (1982). "Los vectores propios de la transformada discreta de Fourier". Revista de Análisis y Aplicaciones Matemáticas . 88 (2): 355–363. doi : 10.1016/0022-247X(82)90199-8 .
• Natig M. Atakishiyev; Kurt Bernardo Lobo (1997). "Transformada fraccionaria de Fourier-Kravchuk". Revista de la Sociedad Óptica de América A. 14 (7): 1467-1477. Código bibliográfico : 1997JOSAA..14.1467A. doi :10.1364/JOSAA.14.001467.
• C. Candán; MA Kutay; HMOzaktas (2000). "La transformada de Fourier fraccionaria discreta" (PDF) . Transacciones IEEE sobre procesamiento de señales . 48 (5): 1329-1337. Código bibliográfico : 2000ITSP...48.1329C. doi : 10.1109/78.839980. hdl : 11693/11130 . Archivado (PDF) desde el original el 21 de septiembre de 2017.
• Magdy Tawfik Hanna, Nabila Philip Attalla Seif y Waleed Abd El Maguid Ahmed (2004). "Vectores propios de tipo Hermite-Gaussiano de la matriz de transformada discreta de Fourier basados ​​​​en la descomposición en valores singulares de sus matrices de proyección ortogonales". Transacciones IEEE sobre circuitos y sistemas I: artículos habituales . 51 (11): 2245–2254. doi :10.1109/TCSI.2004.836850. S2CID  14468134.{{cite journal}}: CS1 maint: multiple names: authors list (link)
• Samgar Gurevich; Ronny Hadani (2009). "Sobre la diagonalización de la transformada discreta de Fourier". Análisis Armónico Aplicado y Computacional . 27 (1): 87–99. arXiv : 0808.3281 . doi :10.1016/j.acha.2008.11.003. S2CID  14833478. preimpresión en.
• Samgar Gurevich; Ronny Hadani; Nir Sochen (2008). "El oscilador armónico finito y sus aplicaciones a secuencias, comunicación y radar". Transacciones IEEE sobre teoría de la información . 54 (9): 4239–4253. arXiv : 0808.1495 . Código Bib : 2008arXiv0808.1495G. doi :10.1109/TIT.2008.926440. S2CID  6037080. preimpresión en.
• Juan G. Vargas Rubio; Balu Santhanam (2005). "Sobre la transformada de Fourier fraccionaria discreta centrada en múltiples ángulos". Cartas de procesamiento de señales IEEE . 12 (4): 273–276. Código Bib : 2005ISPL...12..273V. doi :10.1109/LSP.2005.843762. S2CID  1499353.
• FN Kong (2008). "Expresiones analíticas de dos señales hermite-gaussianas discretas". Transacciones IEEE sobre circuitos y sistemas II: resúmenes exprés . 55 (1): 56–60. doi :10.1109/TCSII.2007.909865. S2CID  5154718.

enlaces externos

• Explicación interactiva del DFT
• Tutorial de Matlab sobre la transformación discreta de Fourier Archivado el 4 de marzo de 2016 en Wayback Machine.
• Tutorial flash interactivo sobre DFT
• Matemáticas de la transformada discreta de Fourier por Julius O. Smith III
• FFTW: Rápida implementación del DFT - codificado en C y bajo Licencia Pública General (GPL)
• Paquete FFT de uso general: otra implementación rápida de DFT en C y FORTRAN, licencia permisiva
• Explicado: La transformada discreta de Fourier
• Transformada discreta de Fourier
• Indexación y desplazamiento de la transformada discreta de Fourier
• Propiedades de la transformada discreta de Fourier
• Transformada discreta generalizada de Fourier (GDFT) con fase no lineal