Matriz DFT

Transformada de Fourier discreta expresada como una matriz

En matemáticas aplicadas, una matriz DFT es una expresión de una transformada de Fourier discreta (DFT) como una matriz de transformación , que se puede aplicar a una señal a través de la multiplicación de matrices .

Definición

Una DFT de N puntos se expresa como la multiplicación de , donde es la señal de entrada original, es la matriz DFT cuadrada de N por N y es la DFT de la señal. ${\displaystyle X=Wx}$ ${\displaystyle x}$ ${\displaystyle W}$ ${\displaystyle X}$

La matriz de transformación se puede definir como , o equivalentemente: ${\displaystyle W}$ ${\displaystyle W=\left({\frac {\omega ^{jk}}{\sqrt {N}}}\right)_{j,k=0,\ldots ,N-1}}$

${\displaystyle W={\frac {1}{\sqrt {N}}}{\begin{bmatrix}1&1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\omega ^{3}&\cdots &\omega ^{N-1}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&\cdots &\omega ^{2(N-1)}\\1&\omega ^{3}&\omega ^{6}&\omega ^{9}&\cdots &\omega ^{3(N-1)}\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\end{bmatrix}}}$,

donde es una raíz N primitiva de la unidad en la que . Podemos evitar escribir exponentes grandes para usar el hecho de que para cualquier exponente tenemos la identidad Esta es la matriz de Vandermonde para las raíces de la unidad, hasta el factor de normalización. Tenga en cuenta que el factor de normalización delante de la suma ( ) y el signo del exponente en ω son simplemente convenciones y difieren en algunos tratamientos. Toda la siguiente discusión se aplica independientemente de la convención, con como máximo ajustes menores. Lo único importante es que las transformadas directa e inversa tienen exponentes de signo opuesto y que el producto de sus factores de normalización sea 1/ N . Sin embargo, la elección aquí hace que la matriz DFT resultante sea unitaria , lo que es conveniente en muchas circunstancias. ${\displaystyle \omega =e^{-2\pi i/N}}$ ${\displaystyle i^{2}=-1}$ ${\displaystyle \omega }$ ${\displaystyle x}$ ${\displaystyle \omega ^{x}=\omega ^{x{\bmod {N}}}.}$ ${\displaystyle 1/{\sqrt {N}}}$ ${\displaystyle 1/{\sqrt {N}}}$

Los algoritmos de transformada rápida de Fourier utilizan las simetrías de la matriz para reducir el tiempo de multiplicación de un vector por esta matriz, a partir del tiempo habitual . Se pueden aplicar técnicas similares para multiplicaciones por matrices como la matriz de Hadamard y la matriz de Walsh . ${\displaystyle O(N^{2})}$

Ejemplos

Dos puntos

La DFT de dos puntos es un caso simple, en el que la primera entrada es la DC (suma) y la segunda entrada es la AC (diferencia).

${\displaystyle W={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}}$

La primera fila realiza la suma y la segunda fila realiza la diferencia.

El factor de es hacer que la transformación sea unitaria (ver más abajo). ${\displaystyle 1/{\sqrt {2}}}$

De cuatro puntos

La matriz DFT de cuatro puntos en el sentido de las agujas del reloj es la siguiente:

${\displaystyle W={\frac {1}{\sqrt {4}}}{\begin{bmatrix}\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}\\\omega ^{0}&\omega ^{1}&\omega ^{2}&\omega ^{3}\\\omega ^{0}&\omega ^{2}&\omega ^{4}&\omega ^{6}\\\omega ^{0}&\omega ^{3}&\omega ^{6}&\omega ^{9}\\\end{bmatrix}}={\frac {1}{\sqrt {4}}}{\begin{bmatrix}1&1&1&1\\1&-i&-1&i\\1&-1&1&-1\\1&i&-1&-i\end{bmatrix}}}$

dónde . ${\displaystyle \omega =e^{-{\frac {2\pi i}{4}}}=-i}$

Ocho puntos

El primer caso no trivial de potencia entera de dos es para ocho puntos:

${\displaystyle W={\frac {1}{\sqrt {8}}}{\begin{bmatrix}\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}\\\omega ^{0}&\omega ^{1}&\omega ^{2}&\omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\\omega ^{0}&\omega ^{2}&\omega ^{4}&\omega ^{6}&\omega ^{8}&\omega ^{10}&\omega ^{12}&\omega ^{14}\\\omega ^{0}&\omega ^{3}&\omega ^{6}&\omega ^{9}&\omega ^{12}&\omega ^{15}&\omega ^{18}&\omega ^{21}\\\omega ^{0}&\omega ^{4}&\omega ^{8}&\omega ^{12}&\omega ^{16}&\omega ^{20}&\omega ^{24}&\omega ^{28}\\\omega ^{0}&\omega ^{5}&\omega ^{10}&\omega ^{15}&\omega ^{20}&\omega ^{25}&\omega ^{30}&\omega ^{35}\\\omega ^{0}&\omega ^{6}&\omega ^{12}&\omega ^{18}&\omega ^{24}&\omega ^{30}&\omega ^{36}&\omega ^{42}\\\omega ^{0}&\omega ^{7}&\omega ^{14}&\omega ^{21}&\omega ^{28}&\omega ^{35}&\omega ^{42}&\omega ^{49}\\\end{bmatrix}}={\frac {1}{\sqrt {8}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &-i&-i\omega &-1&-\omega &i&i\omega \\1&-i&-1&i&1&-i&-1&i\\1&-i\omega &i&\omega &-1&i\omega &-i&-\omega \\1&-1&1&-1&1&-1&1&-1\\1&-\omega &-i&i\omega &-1&\omega &i&-i\omega \\1&i&-1&-i&1&i&-1&-i\\1&i\omega &i&-\omega &-1&-i\omega &-i&\omega \\\end{bmatrix}}}$

dónde

${\displaystyle \omega =e^{-{\frac {2\pi i}{8}}}={\frac {1}{\sqrt {2}}}-{\frac {i}{\sqrt {2}}}}$

(Tenga en cuenta que .) ${\displaystyle \omega ^{8+n}=\omega ^{n}}$

Evaluando el valor de , obtenemos: ${\displaystyle \omega }$

${\displaystyle W={\frac {1}{\sqrt {8}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&{\frac {1-i}{\sqrt {2}}}&-i&{\frac {-1-i}{\sqrt {2}}}&-1&{\frac {-1+i}{\sqrt {2}}}&i&{\frac {1+i}{\sqrt {2}}}\\1&-i&-1&i&1&-i&-1&i\\1&{\frac {-1-i}{\sqrt {2}}}&i&{\frac {1-i}{\sqrt {2}}}&-1&{\frac {1+i}{\sqrt {2}}}&-i&{\frac {-1+i}{\sqrt {2}}}\\1&-1&1&-1&1&-1&1&-1\\1&{\frac {-1+i}{\sqrt {2}}}&-i&{\frac {1+i}{\sqrt {2}}}&-1&{\frac {1-i}{\sqrt {2}}}&i&{\frac {-1-i}{\sqrt {2}}}\\1&i&-1&-i&1&i&-1&-i\\1&{\frac {1+i}{\sqrt {2}}}&i&{\frac {-1+i}{\sqrt {2}}}&-1&{\frac {-1-i}{\sqrt {2}}}&-i&{\frac {1-i}{\sqrt {2}}}\\\end{bmatrix}}}$

La siguiente imagen representa la DFT como una multiplicación de matrices, con elementos de la matriz representados por muestras de exponenciales complejos:

La parte real (onda coseno) se representa mediante una línea continua y la parte imaginaria (onda seno) mediante una línea discontinua.

La fila superior es todo unos (escalado por para unitaridad), por lo que "mide" el componente de CC en la señal de entrada. La siguiente fila son ocho muestras de un ciclo negativo de una exponencial compleja, es decir, una señal con una frecuencia fraccionaria de −1/8, por lo que "mide" cuánta "fuerza" hay en la frecuencia fraccionaria +1/8 en la señal. Recuerde que un filtro adaptado compara la señal con una versión invertida en el tiempo de lo que estamos buscando, por lo que cuando buscamos fracfreq. 1/8 comparamos con fracfreq. −1/8, por lo que es por eso que esta fila es una frecuencia negativa . La siguiente fila son dos ciclos negativos de una exponencial compleja, muestreada en ocho lugares, por lo que tiene una frecuencia fraccionaria de −1/4 y, por lo tanto, "mide" hasta qué punto la señal tiene una frecuencia fraccionaria de +1/4. ${\displaystyle 1/{\sqrt {8}}}$

A continuación se resume cómo funciona la DFT de 8 puntos, fila por fila, en términos de frecuencia fraccionaria:

• 0 mide cuánta CC hay en la señal
• −1/8 mide qué parte de la señal tiene una frecuencia fraccionaria de +1/8
• −1/4 mide qué parte de la señal tiene una frecuencia fraccionaria de +1/4
• −3/8 mide qué parte de la señal tiene una frecuencia fraccionaria de +3/8
• −1/2 mide qué parte de la señal tiene una frecuencia fraccionaria de +1/2
• −5/8 mide qué parte de la señal tiene una frecuencia fraccionaria de +5/8
• −3/4 mide qué parte de la señal tiene una frecuencia fraccionaria de +3/4
• −7/8 mide qué parte de la señal tiene una frecuencia fraccionaria de +7/8

De manera equivalente, se puede decir que la última fila tiene una frecuencia fraccionaria de +1/8 y, por lo tanto, mide qué parte de la señal tiene una frecuencia fraccionaria de -1/8. De esta manera, se podría decir que las filas superiores de la matriz "miden" el contenido de frecuencia positiva en la señal y las filas inferiores miden el componente de frecuencia negativa en la señal.

Transformada unitaria

La DFT es (o puede ser, mediante una selección adecuada de la escala) una transformada unitaria, es decir, que preserva la energía. La elección adecuada de la escala para lograr la unitaridad es , de modo que la energía en el dominio físico sea la misma que la energía en el dominio de Fourier, es decir, para satisfacer el teorema de Parseval . (Otras escalas no unitarias también se utilizan comúnmente para conveniencia computacional; por ejemplo, el teorema de convolución adopta una forma ligeramente más simple con la escala que se muestra en el artículo sobre la transformada de Fourier discreta ). ${\displaystyle 1/{\sqrt {N}}}$

Otras propiedades

Para conocer otras propiedades de la matriz DFT, incluidos sus valores propios, conexión con convoluciones, aplicaciones, etc., consulte el artículo sobre la transformada de Fourier discreta .

Un caso límite: el operador de Fourier

El operador de Fourier

La noción de una transformada de Fourier se generaliza fácilmente . Una generalización formal de la DFT de N puntos se puede imaginar tomando N arbitrariamente grande. En el límite, la rigurosa maquinaria matemática trata a estos operadores lineales como las llamadas transformadas integrales . En este caso, si hacemos una matriz muy grande con exponenciales complejos en las filas (es decir, partes reales de coseno y partes imaginarias de seno), y aumentamos la resolución sin límite, nos acercamos al núcleo de la ecuación integral de Fredholm de segundo tipo, es decir, el operador de Fourier que define la transformada de Fourier continua. Una porción rectangular de este operador de Fourier continuo se puede mostrar como una imagen, análoga a la matriz DFT, como se muestra a la derecha, donde el valor de píxel en escala de grises denota una cantidad numérica.

Véase también

• Transformación multidimensional
• Matrices de reloj y de desplazamiento
• Teorema de Chebotarev sobre las raíces de la unidad

Referencias

• Yip, PC; Rao, K. Ramamohan, eds. (2001). "2. La transformada de Fourier discreta". Manual de transformada y compresión de datos . CRC Press. doi :10.1201/9781315220529. ISBN. 978-1-315-22052-9.– Un tratamiento de la DFT basado en gran medida en la matriz DFT.

Enlaces externos

• Operador de Fourier y diezmado en el tiempo (DIT)