Transformada de Fourier discreta

Para otros usos de este término, véase Transformación (desambiguación).

En matemáticas, la transformada discreta de Fourier o DFT (del inglés, discrete Fourier transform) es un tipo de transformada discreta utilizada en el análisis de Fourier. Transforma una función matemática en otra, obteniendo una representación en el dominio de la frecuencia, siendo la función original una función en el dominio del tiempo. Pero la DFT requiere que la función de entrada sea una secuencia discreta y de duración finita. Dichas secuencias se suelen generar a partir del muestreo de una función continua, como puede ser la voz humana. Al contrario que la transformada de Fourier en tiempo discreto (DTFT), esta transformación únicamente evalúa suficientes componentes frecuenciales para reconstruir el segmento finito que se analiza. Utilizar la DFT implica que el segmento que se analiza es un único período de una señal períodica que se extiende de forma infinita; si esto no se cumple, se debe utilizar una ventana para reducir los espúreos del espectro. Por la misma razón, la DFT inversa (IDFT) no puede reproducir el dominio del tiempo completo, a no ser que la entrada sea periódica indefinidamente. Por estas razones, se dice que la DFT es una transformada de Fourier para análisis de señales de tiempo discreto y dominio finito. Las funciones sinusoidales base que surgen de la descomposición tienen las mismas propiedades.

La entrada de la DFT es una secuencia finita de números reales o complejos, de modo que es ideal para procesar información almacenada en soportes digitales. En particular, la DFT se utiliza comúnmente en procesado digital de señales y otros campos relacionados dedicados a analizar las frecuencias que contiene una señal muestreada, también para resolver ecuaciones diferenciales parciales, y para llevar a cabo operaciones como convoluciones o multiplicaciones de enteros largos. Un factor muy importante para este tipo de aplicaciones es que la DFT puede ser calculada de forma eficiente en la práctica utilizando el algoritmo de la transformada rápida de Fourier o FFT (Fast Fourier Transform).

Los algoritmos FFT se utilizan tan habitualmente para calcular DFTs que el término "FFT" muchas veces se utiliza en lugar de "DFT" en lenguaje coloquial. Formalmente, hay una diferencia clara: "DFT" hace alusión a una transformación o función matemática, independientemente de cómo se calcule, mientras que "FFT" se refiere a una familia específica de algoritmos para calcular DFTs.

Definición

La secuencia de N números complejos x₀, ..., x_N−1 se transforma en la secuencia de N números complejos X₀, ..., X_N−1 mediante la DFT con la fórmula:

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

donde i es la unidad imaginaria y $e^{\frac{2 \pi i}{N}}$ es la N-ésima raíz de la unidad. (Esta expresión se puede escribir también en términos de una matriz DFT; cuando se escala de forma apropiada se convierte en una matriz unitaria y X_k puede entonces ser interpretado como los coeficientes de x en una base ortonormal.)

La transformada se denota a veces por el símbolo $\mathcal{F}$, igual que en $\mathbf{X} = \mathcal{F} \left \{ \mathbf{x} \right \}$ o $\mathcal{F} \left ( \mathbf{x} \right )$ o $\mathcal{F} \mathbf{x}$.

La transformada inversa de Fourier discreta (IDFT) viene dada por

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

Una descripción simple de estas ecuaciones es que los números complejos X_k representan la amplitud y fase de diferentes componentes sinusoidales de la señal de entrada x_n. La DFT calcula X_k a partir de x_n, mientras que la IDFT muestra cómo calcular x_n como la suma de componentes sinusoidales $(1/N) X_k e^{\frac{2\pi i}{N}k n}$ con una frecuencia de k / N ciclos por muestra. Escribiendo las ecuaciones de este modo, estamos haciendo un uso extensivo de la fórmula de Euler para expresar sinusoides en términos de exponentes complejas, lo cual es mucho más sencillo de manipular. Del mismo modo, escribiendo X_k en forma polar, obtenemos una sinudoide de amplitud A_k / N y fase ϕ_k a partir del módulo y argumento complejos de X_k, respectivamente:

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

$\varphi_k = \arg(X_k) = \operatorname{atan2}\big( \operatorname{Im}(X_k), \operatorname{Re}(X_k) \big),$

donde atan2 es la forma bi-argumental de la función arcotangente. Nótese que el factor de normalización que multiplica a la DFT y la IDFT (que son 1 y 1/N) y los signos de los exponentes se colocan meramente por convenio, y varían dependiendo de la aplicación. El único requisito para este convenio es que la DFT y la IDFT tengan exponentes de signo opuesto y que el producto de sus factores de normalización sea 1/N. Una normalización de $1/\sqrt{N}$ para ambas DFT y IDFT hace las transformadas unitarias, lo cual tiene ciertas ventajas teóricas, pero suele ser más práctico a la hora de efectuar operaciones numéricas con el ordenador efectuar el escalado de una sóla vez (y un escalado unitario suele ser conveniente en otras ocasiones).

(El convenio del signo negativo en el exponente suele ser adecuado porque significa que X_k es la amplitud de una "frecuencia positiva" 2πk / N. De forma equivalente, la DFT se suele considerar como un filtro adaptado: cuando se busca una frecuencia de +1, se correla la señal de entrada con una frecuencia de −1.)

En adelante, los términos "secuencia" y "vector" serán considerados equivalentes.

Propiedades

Completitud

La transformada discreta de Fourier es una transformación lineal e invertible.

$\mathcal{F}\colon\mathbb{C}^N \to \mathbb{C}^N$

donde C denota el cuerpo de los números complejos. En otras palabras, para cada N > 0, cualquier vector complejo N-dimensional tiene una DFT y una IDFT que consisten también en vectores complejos N-dimensionales.

Ortogonalidad

Los vectores $e^{ \frac{2\pi i}{N} kn}$ forman una base ortogonal sobre el cuerpo de los vectores complejos N-dimensionales:

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

donde $~\delta_{kk'}$ es la delta de Kronecker. Esta condición de ortogonalidad puede ser utilizada para obtener la fórmula de la IDFT a partir de la definición de la DFT, y es equivalente a la propiedad de unicidad.

Los teoremas de Plancherel y Parseval

Si X_k y Y_k son las DFTs de x_n y y_n respectivamente, entonces el teorema de Plancherel establece que:

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

donde el asterisco denota conjugación compleja. El teorema de Parseval es un caso especial del teorema de Plancherel, y dice que:

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

Estos teoremas son también equivalentes a la condición de unicidad.

Periodicidad

Si la expresión que define la DFT se evalúa para todos los enteros k en lugar de únicamente para $k = 0, \dots, N-1$, la secuencia infinita resultante es una extensión periódica de la DFT, de período N.

Esta periodicidad puede demostrarse directamente a partir de la definición:

$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} k n} \underbrace{e^{-2 \pi i n}}_{1} = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} k n} = X_k.$

De forma similar, se puede demostrar que la fórmula de la IDFT lleva a una extensión periódica.

Teorema del desplazamiento

Multiplicando x_n por una fase lineal $e^{\frac{2\pi i}{N}n m}$ para cualquier entero m equivale a un desplazamiento circular de la salida X_k: X_k se reemplaza por X_{k − m}, donde el subíndice se repite periódicamente (período N). De forma similar, un desplazamiento circular de la entrada x_n equivale a multiplicar la salida X_k por una fase lineal. Matemáticamente, si {x_n} representa el vector x entonces:

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

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

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

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

El teorema de la convolución para las transformada de Fourier continua y discreta indica que una convolución de dos secuencias infinitas se puede obtener como la transformada inversa del producto de las transformadas de cada una de ellas. Con secuencias y transformadas de longitud N, la convolución circular se define:

$\begin{align} \mathcal{F}^{-1} \left \{ \mathbf{X\cdot Y} \right \}_n \ &\stackrel{\mathrm{def}}{=} \frac{1}{N} \sum_{k=0}^{N-1} X_k \cdot Y_k \cdot e^{\frac{2\pi i}{N} k n}\\ &= \frac{1}{N} \sum_{k=0}^{N-1} \left(\sum_{l=0}^{N-1} x_l e^{-\frac{2 \pi i}{N} k l}\right) \cdot \left(\sum_{m=0}^{N-1} y_m e^{-\frac{2 \pi i}{N} k m}\right) \cdot e^{\frac{2\pi i}{N} k n}\\ &= \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{align}$

El número entre paréntesis es 0 para todos los valores de m excepto aquellos de la forma n − l − pN, donde p es un entero cualquiera. En estas posiciones vale 1. Puede ser por tanto reemplazado por una suma infinita de deltas de Kronecker. Nótese que se pueden extender los límites de m hasta infinito, siendo las secuencias x e y definidas nulas fuera de [0,N-1]:

$\begin{align} \mathcal{F}^{-1} \left \{ \mathbf{X\cdot Y} \right \}_n &= \sum_{l=0}^{N-1} x_l \sum_{m=-\infty}^{\infty} y_m \left( \sum_{p=-\infty}^{\infty} \delta_{m,(n-l-pN)} \right) \\ &= \sum_{l=0}^{N-1} x_l \sum_{p=-\infty}^{\infty} \underbrace{\left(\sum_{m=-\infty}^{\infty} y_m \cdot \delta_{m,(n-l-pN)}\right)}_{y_{n-l-pN}} \\ &= \sum_{l=0}^{N-1} x_l \left(\sum_{p=-\infty}^{\infty} y_{n-l-pN}\right) \ \stackrel{\mathrm{def}}{=} \ (\mathbf{x * y_N})_n\ , \end{align}$

que es la convolución de la secuencia $\mathbf{x}$ con la secuencia $\mathbf{y}$ que está extendida periódicamente y definida:

$(\mathbf{y_N})_n \ \stackrel{\mathrm{def}}{=} \ \sum_{p=-\infty}^{\infty} y_{(n-pN)} = y_{n (mod N)}. \,$

También se puede demostrar que:

$\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\ ,$

que es la correlación cruzada de  $\mathbf{x}$  y  $\mathbf{y_N}.$

Una evaluación directa de la convolución requiere O(N²) operaciones para una secuencia de entrada de longitud N. El método indirecto, usando transformadas, puede sacar provecho de la transformada rápida de Fourier (FFT), que necesita tan sólo O(Nlog N) operaciones, de modo que se consigue una eficiencia mucho mayor. Además, las convoluciones pueden ser utilizadas para calcular de forma eficiente DFTs mediante el algoritmo FFT de Rader y el algoritmo FFT de Bluestein.

Se han creado otros métodos que usan la convolución circular como parte de un proceso eficiente que obtiene convoluciones normales (no circulares) con una secuencia $\mathbf{x}$ o $\mathbf{y}$ potencialmente mucho más larga que N. Ambos métodos se conocen como overlap-save y overlap-add.^[1]

Dualidad del teorema de la convolución

Es posible demostrar que:

$\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} k n}$

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

Polinomio de interpolación trigonométrica

El polinomio interpolador trigonométrico

$p(t) = \frac{1}{N} \left[ 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} \right]$ para N par,

$p(t) = \frac{1}{N} \left[ 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} \right]$ para N impar,

donde los coeficientes X_k vienen dados por la DFT de x_n anterior, satisface la propiedad de interpolación p(2πn / N) = x_n para $n=0,\ldots,N-1$.

Para N par, véase que la Frecuencia de Nyquist $\frac{X_{N/2}}{N} \cos(Nt/2)$ se maneja de forma especial.

Esta interpolación no es única: el aliasing implica que se podría sumar N a cualquier frecuencia compleja sinusoidal (por ejemplo, cambiando e ^{− it} por e^{i(N − 1)t} ) sin que se altere la propiedad de interpolación, pero dando valores diferentes entre x_n puntos. De todos modos, esto tiene dos propiedades interesantes. En primer lugar, consiste en sinusoides cuyas frecuencias tienen las magnitudes más pequeñas posibles: la interpolación es limitada en banda. Y en segundo lugar, si x_n son números reales, entonces p(t) es también real.

En contraste, el polinomio de interpolación trigonométrica más obvio es el que cuyo rango de frecuencias va de 0 a N-1 (en lugar de − N / 2 to + N / 2 como se ha visto previamente), similar a la fórmula de la DFT inversa. Esta interpolación no minimiza la pendiente, y en general no toma valores reales para un x_n real; su uso es un error común.

La DFT unitaria

Otra forma de interpretar la DFT es dándose cuenta que en puede expresarse como una matriz de 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}$

donde

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

es una raíz de la unidad. La transformada inversa viene entonces dada por la inversa de la matriz anterior:

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

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

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

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

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

donde det()  es el determinante. Dicho determinante es el producto de los valores propios, que siempre son $\pm 1$ o $\pm i$. En un espacio vectorial real, una transformación unitaria puede verse simplemente como una rotación rígida del sistema de coordenadas, y todas las propiedades de esta rotación rígida pueden hallarse en la DFT unitaria. La ortogonalidad de la DFT se convierte ahora en ortonormalidad.

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

Si $\mathbf{X}$ se define como la DFT unitaria del vector $\mathbf{x}$ entonces

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

y el Teorema de Plancherel se expresa como:

$\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 expresa los componentes de un vector en un nuevo sistema de coordenadas, entonces lo anterior es la demostración de que el producto escalar de dos vectores se conserva en una transformación unitaria de la DFT. Para el caso especial $\mathbf{x} = \mathbf{y}$, esto implica que la longitud del vector también se mantiene—esto es el Teorema de Parseval:

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

Véase también

• Imagen digital

Referencias

1. ↑ T. G. Stockham, Jr., "High-speed convolution and correlation," in 1966 Proc. AFIPS Spring Joint Computing Conf. Reprinted in Digital Signal Processing, L. R. Rabiner and C. M. Rader, editors, New York: IEEE Press, 1972.