Transformada de Fourier discreta

Temas relacionados: Matemáticas

Antecedentes de las escuelas de Wikipedia

SOS Children, que corre cerca de 200 sos escuelas en el mundo en desarrollo, organizó esta selección. Apadrina un niño para hacer una diferencia real.

Transformadas de Fourier
Fourier continua transformar
Series de Fourier
Tiempo Transformada Discreta de Fourier
Transformada de Fourier discreta
Análisis de Fourier
Transformaciones relacionados

En matemáticas , la transformada discreta de Fourier (DFT) es una de las formas específicas de Análisis de Fourier. Como tal, se transforma una función a otra, que se llama el representación en el dominio de frecuencia, o simplemente la DFT, de la función original (que es a menudo una función en el dominio del tiempo). Sin embargo, la DFT requiere una función de entrada que es valores discretos y cuya no tienen un cero (finito) de duración limitada. Tales entradas son a menudo creadas por el muestreo de una función continua, como la voz de una persona. Y a diferencia de la de tiempo discreto transformada de Fourier (DTFT), sólo evalúa componentes de frecuencia suficientes para reconstruir el segmento finito que se analizó. Su transformada inversa no puede reproducir todo el dominio del tiempo, a menos que la entrada pasa a ser periódico (siempre). Por lo tanto, a menudo se dice que la DFT es una transformación para el análisis de Fourier de las funciones de tiempo discreto finito de dominio. Las funciones de base sinusoidales de la descomposición tienen las mismas propiedades.

Dado que la función de entrada es una secuencia finita de reales o números complejos , la DFT es ideal para procesamiento de la información almacenada en los ordenadores . En particular, la DFT se emplea extensamente en procesamiento de señales y campos relacionados para analizar las frecuencias de una muestreado señal, para resolver ecuaciones diferenciales parciales , y para realizar otras operaciones como circunvoluciones. La DFT se puede calcular de manera eficiente en la práctica el uso de un transformada rápida de Fourier (FFT) algoritmo.

Dado que los algoritmos FFT son tan comúnmente empleados para calcular la DFT, los dos términos se utilizan a menudo indistintamente en la configuración coloquiales, aunque hay una clara distinción: "DFT" se refiere a una transformación matemática, independientemente de cómo se calcula, mientras que "FFT" se refiere a uno cualquiera de varios algoritmos eficientes para la DFT. Esta distinción es aún más borrosa, sin embargo, por el sinónimo Fourier finita de transformación para la DFT, que aparentemente es anterior el término "transformada rápida de Fourier" (Cooley et al., 1969) pero tiene el mismo initialism.

Definición

La secuencia de n números complejos x _0, ..., x _{N -1} se transforma en la secuencia de n números complejos X _0, ..., X _{N -1} por el DFT de acuerdo con la fórmula:

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

donde $e ^ {\ frac {2 \ pi i} {N}}$ es un N-ésima primitiva raíz de la unidad.

El transformar a veces se denota por el símbolo $\ Mathcal {F}$ , Como 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} kn} \ quad \ n quad = 0, \ dots , N-1.$

Una simple descripción de estas ecuaciones es que los números complejos $X_k$ representar la amplitud y fase de los diferentes componentes sinusoidales de la "señal" de entrada $x_n$ . La DFT calcula la $X_k$ desde el $x_n$ , Mientras que la IDFT muestra cómo calcular el $x_n$ como una suma de componentes sinusoidales $X_k \ exp (2 \ pi i k n / N) / N$ con frecuencia $k / N$ ciclos por muestra. Al escribir las ecuaciones de esta forma, estamos haciendo un amplio uso de La fórmula de Euler para expresar sinusoides en términos de exponenciales complejas, que son mucho más fáciles de manipular. (De la misma manera, por escrito $X_k$ en forma polar , se obtiene inmediatamente la amplitud sinusoide de $| X_k |$ y la fase de la argumento complejo.) Una sutileza importante de esta representación, aliasing, se discute a continuación.

Tenga en cuenta que el factor de normalización multiplicando la DFT y IDFT (aquí 1 y 1 / N) y los signos de los exponentes no son más que convenciones, y difieren en algunos tratamientos. Los únicos requisitos de estas convenciones son que la DFT y IDFT tienen exponentes de distinto signo y que el producto de sus factores de normalización sean 1 / N. Una normalización de $1 / \ sqrt {N}$ tanto para la DFT y IDFT hace las transformaciones unitario, que tiene algunas ventajas teóricas, pero a menudo es más práctico en el cálculo numérico para llevar a cabo el escalado todos a la vez como anteriormente (y una escala unidad puede ser conveniente en otras formas).

(La convención de signo negativo en el exponente es a menudo conveniente porque significa que $X_k$ es la amplitud de una "frecuencia positiva" $2 \ pi k / N$ . De manera equivalente, la DFT es a menudo considerado como un filtro adaptado: cuando se busca una frecuencia de 1, uno se correlaciona la señal de entrada con una frecuencia de -1).

En la siguiente discusión de los términos "secuencia" y "vector" serán considerados intercambiables.

Propiedades

Lo completo

La transformada discreta de Fourier es un invertible, transformación lineal

$\ Mathcal {F}: \ mathbb {C} ^ N \ to \ mathbb {C} ^ N$

con $\ Mathbb {C}$ denota el conjunto de números complejos . En otras palabras, para cualquier n> 0, un vector dimensional N complejo tiene una DFT y una IDFT que son a su vez N -dimensional vectores complejos.

Ortogonalidad

Los vectores $e ^ {\ frac {2 \ pi i} {N} kn}$ para hombre base ortogonal sobre el conjunto de vectores complejos N -dimensional:

$\ 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 el Delta Kronecker. Esta condición de ortogonalidad se puede utilizar para derivar la fórmula para la IDFT de la definición de la DFT, y es equivalente a la propiedad unitaridad a continuación.

El teorema Plancherel y el teorema de Parseval

Si X e Y _{k k} son las DFT de x _n y y _n respectivamente, entonces el Plancherel teorema:

$\ 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 Parseval es un caso especial del teorema Plancherel y estados:

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

Estos teoremas son también equivalente a la condición unitaria a continuación.

Periodicidad

Si la expresión que define la DFT se evalúa para todos los números enteros $k$ en lugar de sólo para $k = 0, \ dots, N-1$ , Entonces la secuencia infinita resultante es una extensión periódica de la DFT, periódica con periodo N.

La periodicidad puede demostrarse directamente de la definición:

$X_ {k + N} = \ sum_ {n = 0} ^ {N-1} x_n e ^ {- \ frac {2 \ pi i} {N} n (k + N)} = \ sum_ {n = 0 } ^ {N-1} x_n e ^ {- \ frac {2 \ pi i} {N} kn} e ^ {- 2 \ pi} en = \ sum_ {n = 0} ^ {N-1} x_n correo ^ {- \ frac {2 \ pi i} {N}} = kn x_k$

donde hemos utilizado el hecho de que $e ^ {- 2 \ pi i} = 1$ . De la misma manera se puede demostrar que la fórmula IDFT conduce a una extensión periódica.

El teorema de cambio

Multiplicando $x_n$ por una fase lineal $e ^ {\ frac {2 \ pi i} {N} n m}$ para algún entero $m$ corresponde a un desplazamiento circular de la salida $X_k$ : $X_k$ se sustituye por $X_ {k-m}$ , Donde se interpreta el subíndice de módulo $N$ (Es decir, periódicamente). Del mismo modo, un desplazamiento circular de la entrada $x_n$ corresponde a la multiplicación de 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} nm} \}) _ k = X_ {km}$

y $\ Mathcal {F} (\ {x_ {nm} \}) _ k = x_k \ cdot e ^ {- \ frac {2 \ pi i} {N}} km$

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

La teorema de convolución para el tiempo continuo y discreto de Fourier transforma indica que una convolución de dos secuencias infinitas se puede obtener como la transformada inversa del producto de las transformadas individuales. Con secuencias y transformadas de longitud N, A surge la circularidad:

$\ 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} kn} \\ & = \ frac {1} { N} \ sum_ {k = 0} ^ {N-1} \ left (\ sum_ {l = 0} ^ {N-1} x_l e ^ {- \ frac {2 \ pi i} {N} kl} \ derecha) \ 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 (NLM)} \ right). \ End {align}$

La cantidad entre paréntesis es 0 para todos los valores de $m$ excepto las de la forma $n-l-pN$ , Donde $p$ es cualquier número entero. En esos valores, es 1. Por lo tanto, puede ser reemplazada por una suma infinita de Funciones delta Kronecker, y seguimos en consecuencia. Tenga en cuenta que también podemos extender los límites de $m$ hasta el infinito, con el entendimiento de que la $x$ y $y$ secuencias se definen como 0 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 (nl-PN)} \ right) \\ & = \ sum_ { l = 0} ^ {N-1} x_l \ sum_ {p = - \ infty} ^ {\ infty} \ left (\ sum_ {m = - \ infty} ^ {\ infty} y_m \ cdot \ delta_ {m ( nl-PN)} \ right) \\ & = \ sum_ {l = 0} ^ {N-1} x_l \ left (\ sum_ {p = - \ infty} ^ {\ infty} y_ {nl-pN} \ derecha) \ \ stackrel {\ mathrm {def}} {} = \ (\ mathbf {x * y_n}) _ n \, \ end {align}$

que es la convolución de la $\ Mathbf {x}$ secuencia con un renovado periódicamente $\ Mathbf {y}$ secuencia definida por:

$(\ Mathbf {y_n}) _ n \ \ stackrel {\ mathrm {def}} {} = \ \ sum_. {P = - \ infty} ^ {\ infty} y _ {(n-PN)} \,$

Del mismo modo, 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 \ estrella y_n}) _ n \,$

cuál es el correlación cruzada de $\ Mathbf {x}$ y $\ Mathbf {y_n}.$

Una evaluación directa de la convolución o correlación suma, más arriba, requiere $O (n ^ 2)$ operaciones. Un método indirecto, usando transformaciones, puede aprovechar la $O (N \ log N)$ eficiencia de la transformada rápida de Fourier (FFT) para lograr un rendimiento mucho mejor. Además, circunvoluciones pueden utilizarse para calcular de manera eficiente a través de DFT Algoritmo FFT de Rader y Algoritmo FFT de Bluestein.

Los métodos también han sido desarrollados para utilizar la convolución circular como parte de un proceso eficiente que logra normal (no circular) convolución con una $\ Mathbf {x}$ o $\ Mathbf {y}$ secuencia potencialmente mucho más largo que el tamaño práctico transformar (N). Dos de tales métodos se denominan solapar-guardar y superponerse a agregar.

Polinomio de interpolación trigonométrica

La polinomio de interpolación trigonométrica

$p (t) = \ frac {x 0} {N} + \ frac {x_1} {N} e ^ {que} + \ cdots + \ frac {X_ {N / 2}} {N} \ cos (Nt / 2 ) + \ frac {X_ {N / 2 + 1}} {N} e ^ {(- N / 2 + 1)} + \ cdots + \ frac {X_ {N-1}} {N} e ^ { -es}$ para $N$ incluso,

$p (t) = \ frac {x 0} {N} + \ frac {x_1} {N} e ^ {que} + \ cdots + \ frac {X _ {\ lfloor N / 2 \ rfloor}} {N} e ^ {\ lfloor N / 2 \ rfloor it} + \ frac {X _ {\ lfloor N / 2 \ rfloor + 1}} {N} e ^ {- \ lfloor N / 2 \ rfloor it} + \ cdots + \ frac { X_ {N-1}} {N} e ^ {- it}$ para $N$ impar,

donde los coeficientes X _k / N son dados por el DFT de x _n anterior, satisface la propiedad de interpolación $p (2 \ pi n / N) = x_n$ para $n = 0, \ ldots, N-1$ .

Porque aun $N$ , Observe que la Componente Nyquist $\ Frac {X_ {N / 2}} {N} \ cos (Nt / 2)$ se maneja de forma especial.

Esta interpolación no es única: aliasing implica que se podría añadir N a cualquiera de las frecuencias complejo de sinusoides (por ejemplo, cambiando $e ^ {-} se$ a $e ^ {i (N-1) t}$ ) Sin cambiar la propiedad de interpolación, pero dando valores diferentes en entre el $x_n$ puntos. La elección anteriormente, sin embargo, es típico porque tiene dos propiedades útiles. En primer lugar, se compone de sinusoides cuyas frecuencias tener las magnitudes más pequeñas posibles, y por lo tanto minimiza la media cuadrática pendiente $\ Int | p '(t) | ^ 2 dt$ de la función de interpolación. En segundo lugar, si el $x_n$ son números reales, entonces $p (t)$ es real también.

En contraste, la más obvia polinomio de interpolación trigonométrica es aquel en el que las frecuencias van de 0 a $N-1$ (En lugar de más o menos $-N / 2$ a $+ N / 2$ como anteriormente), similar a la fórmula DFT inversa. Esta interpolación no minimiza la pendiente, y no es por lo general un valor real de los bienes $x_n$ ; su uso es un error común.

El unitario DFT

Otra manera de mirar el DFT es observar que en la discusión anterior, la DFT se puede expresar como una Matriz Vandermonde:

$\ Mathbf {F} = \ begin {bmatrix} \ omega_N ^ {0 \ cdot 0} & \ omega_N ^ {0 \ cdot 1} & \ ldots y \ omega_N ^ {0 \ cdot (N-1)} \\ \ omega_N ^ {1 \ cdot 0} & \ omega_N ^ {1 \ cdot 1} & \ ldots y \ omega_N ^ {1 \ cdot (N-1)} \\ \ vdots & \ vdots & \ ddots & \ vdots \\ \ omega_N ^ {(N-1) \ cdot 0} & \ omega_N ^ {(N-1) \ cdot 1} y \ ldots y \ omega_N ^ {(N-1) \ cdot (N-1)} \\ \ end {bmatrix}$

donde

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

es una primitiva Raíz enésima de la unidad. La transformada inversa viene 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} = \ vec {F} / \ sqrt {N}$

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

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

donde det () es el determinante función. El determinante es el producto de los valores propios, que son siempre $\ Pm 1$ o $\ Pm i$ como se describe abajo. En un espacio vectorial real, una transformación unitaria puede ser considerado simplemente como una rotación rígida del sistema de coordenadas, y todas las propiedades de una rotación rígida se puede encontrar en el unitaria DFT.

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

$\ 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 la Plancherel teorema 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 como una simple transformación que simplemente especifica las componentes de un vector en un nuevo sistema de coordenadas de coordenadas, entonces lo anterior es sólo la afirmación de que el producto escalar de dos vectores se conserva bajo una transformación DFT unitario. Para el caso especial $\ Mathbf {x} = \ vec {y}$ , Esto implica que la longitud de un vector se conserva como bien esto es sólo El teorema de Parseval:

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

Expresando 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 (adelante) DFT, a través de varios "trucos" muy conocidos. (Por ejemplo, en los cálculos, a menudo es conveniente sólo implementar una transformada rápida de Fourier correspondiente a una transformación dirección y luego para obtener la otra dirección de la transformación de la primera).

En primer lugar, podemos calcular la DFT inversa mediante la inversión de las entradas:

$\ Mathcal {F} ^ {- 1} (\ {x_n \}) = \ mathcal {F} (\ {x_ {N - n} \}) / N$

(Como de costumbre, los subíndices se interpretan módulo $N$ ; Así, por $n = 0$ , Tenemos $x_ {N-0} = x_0$ .)

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

$\ Mathcal {F} ^ {- 1} (\ mathbf {x}) = \ mathcal {F} (\ mathbf {x} ^ *) ^ * / N$

En tercer lugar, una variante de este truco conjugación, que a veces es preferible, ya que no requiere ninguna modificación de los valores de los datos, implica el intercambio de partes reales e imaginarias (que se pueden hacer en un ordenador simplemente modificando punteros). Definir swap ( $x_n$ ) Como $x_n$ con sus partes real e imaginaria intercambiados, es decir, si $x_n = a + b i$ luego cambiar ( $x_n$ ) Es $b + a i$ . De manera equivalente, de intercambio ( $x_n$ ) Es igual $i X_n ^ *$ . Entonces

$\ Mathcal {F} ^ {- 1} (\ mathbf {x}) = \ {textrm intercambio} (\ mathcal {F} (\ textrm {canje} (\ mathbf {x}))) / N$

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

El truco conjugación también se puede utilizar para definir una transformación nueva, estrechamente relacionada con la DFT, es decir involutary, es decir, que es su propio inverso. En particular, $T (\ mathbf {x}) = \ mathcal {F} (\ mathbf {x} ^ *) / \ sqrt {N}$ es claramente su propio inverso: $T (T (\ mathbf {x})) = \ mathbf {x}$ . Una transformación involutary estrechamente relacionados (por un factor de (1 + i) / √2) es $H (\ mathbf {x}) = \ mathcal {F} ((1 + i) \ mathbf {x} ^ *) / \ sqrt {2N}$ , Ya que la $(1 + i)$ factores en $H (H (\ mathbf {x}))$ cancelar el 2. Para las entradas reales $\ Mathbf {x}$ , La parte real de $H (\ mathbf {x})$ no es otro que el discreta Hartley transformada, que también es involutary.

Valores propios y vectores propios

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

Considere la forma unitaria $\ Mathbf {U}$ definido anteriormente para la DFT de longitud $N$ , Donde $\ Mathbf {T} _ {m, n} = \ omega_N ^ {mn} / \ sqrt {N} = \ exp (-2 \ pi i mn / N) / \ sqrt {N}$ . Esta matriz satisface la ecuación:

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

Esto se puede ver a partir de las propiedades inversas anteriores: operativo $\ Mathbf {U}$ dos veces da los datos originales en el orden inverso, de modo operativo $\ Mathbf {U}$ cuatro veces te devuelven los datos originales y es por lo tanto la matriz de identidad. Esto significa que los valores propios $\ Lambda$ satisfacer una ecuación característica:

$\ Lambda ^ 4 = 1.$

Por lo tanto, los valores propios de $\ Mathbf {U}$ son la cuarta raíces de la unidad: $\ Lambda$ es 1, -1, + i, o - i.

Dado que sólo hay cuatro valores propios distintos de este $N \ N veces$ matriz, que tienen algún multiplicidad . La multiplicidad da el número de vectores propios linealmente independientes correspondientes a cada valor propio. (Tenga en cuenta que hay N vectores propios independientes; una matriz unitaria nunca es defectuoso.)

El problema de su multiplicidad fue resuelto por McClellan y Parks (1972), aunque posteriormente se ha demostrado haber sido equivalente a un problema resuelto por Gauss (Dickinson y Steiglitz, 1982). La multiplicidad depende del valor de $N$ modulo 4, y está dada por la siguiente tabla:

Las multiplicidades de los valores propios λ de la matriz unitaria U DFT como una función del tamaño transformar N (en términos de un número entero *m).*
N tamaño	λ = 1	λ = -1	λ = - i	λ = + i
4 m	m + 1	m	m	m - 1
4 m + 1	m + 1	m	m	m
4 m + 2	m + 1	m + 1	m	m
4 m + 3	m + 1	m + 1	m + 1	m

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

La elección de los vectores propios de la matriz DFT se ha convertido en importante en los últimos años con el fin de definir un análogo discreto de la Fourier fraccional transformar-la matriz DFT se puede tomar a potencias fraccionarias exponenciando los valores propios (por ejemplo, Rubio y Santhanam, 2005). Para el continua transformada de Fourier, las funciones propias ortogonales naturales son la Funciones de Hermite, así diversos análogos discretos de éstos se han empleado como los vectores propios de la DFT, tales como la Polinomios Kravchuk (Atakishiyev y Wolf, 1997). El "mejor" opción de vectores propios para definir una discreta de Fourier fraccionaria transformar sigue siendo una pregunta abierta, sin embargo.

La DFT-real de entrada

Si $x 0, \ ldots, x_ {N-1}$ son números reales , ya que a menudo se encuentran en las aplicaciones prácticas, entonces la DFT obedece a la simetría:

$X_k = X_ {N-k} ^ *,$

donde la estrella denota conjugación compleja y los subíndices se interpretan módulo N.

Por lo tanto, la salida de DFT para las entradas reales es un medio redundante, y se obtiene la información completa con sólo mirar aproximadamente la mitad de las salidas $X 0, \ ldots, X_ {N-1}$ . En este caso, el elemento "DC" $X 0$ es puramente real, y para incluso n el elemento "Nyquist" $X_ {N / 2}$ También es real, por lo que hay exactamente N no redundantes números reales en el primer semestre + elemento de Nyquist del complejo de salida X.

Uso La fórmula de Euler, el polinomio de interpolación trigonométrica a continuación puede ser interpretada como una suma de funciones seno y coseno.

Generalizada / desplazado DFT

Es posible desplazar el muestreo transformar en el tiempo y / o dominio de la frecuencia por algunos cambios reales a y b, respectivamente. Esto a veces se conoce como una DFT generalizada (o GDFT), también llamado el desplazado DFT o compensar DFT, y tiene propiedades análogas a la DFT ordinaria:

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

Muy a menudo, los cambios de $1/2$ (La mitad de una muestra) se utilizan. Mientras que la DFT ordinaria corresponde a una señal periódica en el tiempo y dominio de la frecuencia, $a = 1/2$ produce una señal que es anti-periódica en el dominio de la frecuencia ( $X_ {k + N} = - x_k$ ) Y viceversa para $b = 1/2$ . Por lo tanto, el caso específico de $a = b = 1/2$ se conoce como un número impar de la frecuencia de Fourier en tiempo impar transformada discreta (DFT o O ^2). Tal desplazado transformaciones se utilizan con mayor frecuencia para los datos simétricos, para representar diferentes simetrías de frontera, y para los datos-real simétrica que corresponden a las diferentes formas de la discreta coseno y transformadas seno.

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

La transformada discreta de Fourier se puede ver como un caso especial de la transformada z, evaluado en el círculo unidad en el plano complejo; más transformadas z generales corresponden a los cambios complejos a y b anterior.

Multidimensional DFT

La DFT ordinaria calcula la transformada de un conjunto de datos "unidimensional": una secuencia (o array) $x_n$ que es una función de una variable discreta $n$ . Más generalmente, se puede definir la DFT multidimensional de una matriz multidimensional $x_ {n_1, n_2, \ dots, n_d}$ que es una función de $d$ variables discretas $n_ \ ell = 0, 1, \ dots, N_ \ ell-1$ para $\ Ell$ en $1, 2, \ dots, d$ :

$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) \ cdots \ right) \,,$

donde $\ Omega_ {N_ \ ell} = \ exp (-2 \ pi i / N_ \ ell)$ como anteriormente y la $d$ índices del producto van desde $K_ \ ell = 0, 1, \ dots, N_ \ ell-1$ . Esto se expresa de forma más compacta en notación vectorial, donde definimos $\ Mathbf {n} = (n_1, n_2, \ dots, n_d)$ y $\ Mathbf {k} = (k_1, k_2, \ dots, k_d)$ como $d$ vectores dimensionales de los índices de 0 a $\ Mathbf {N} - 1$ , Que definimos como $\ Mathbf {N} - 1 = (N_1 - 1, N_2 - 1, \ dots, N_d - 1)$ :

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

donde la división $\ Mathbf {n} / \ mathbf {N}$ se define como $\ Mathbf {n} / \ mathbf {N} = (n_1 / N_1, \ dots, n_d / N_d)$ a realizar elemento a elemento, y la suma denota el conjunto de sumas anidados anteriores.

La inversa de la DFT multi-dimensional es, de forma análoga al caso unidimensional, dada por:

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

El multidimensional DFT tiene una interpretación sencilla. Así como el DFT unidimensional expresa la entrada $x_n$ como una superposición de sinusoides, la multidimensional DFT expresa la entrada como una superposición de ondas planas o sinusoides oscilantes largo de la dirección $\ Mathbf {k} / \ mathbf {N}$ en el espacio y tiene una amplitud $X_ \ mathbf {k}$ . Tal descomposición es de gran importancia para todo, desde procesamiento digital de la imagen (d = 2) a la solución de ecuaciones diferenciales parciales en tres dimensiones (d = 3) rompiendo la solución arriba en ondas planas.

Computacionalmente, el multidimensional DFT es simplemente la composición de una secuencia de DFT de una dimensión a lo largo de cada dimensión. Por ejemplo, en el caso de dos dimensiones $x_ {n_1, n_2}$ uno primero puede calcular la $N_1$ DFT independientes de las filas (es decir, a lo largo $n_2$ ) Para formar una nueva matriz $y_ {n_1, k_2}$ , Y luego calcular la $N_2$ DFT independientes de $y$ a lo largo de las columnas (junto $n_1$ ) Para formar el resultado final $X_ {k_1, k_2}$ . O bien, se puede transformar las columnas y luego las filas: el orden es irrelevante porque las sumas anidados anterior viaje .

Debido a esto, dado una manera de calcular una DFT de una dimensión (por ejemplo, un algoritmo FFT unidimensional ordinario), uno tiene inmediatamente una forma de calcular de manera eficiente el multidimensional DFT. Esto se conoce como un algoritmo de fila-columna, aunque también son intrínsecamente algoritmos FFT multidimensional.

La entrada de bienes multidimensional DFT

Si las entradas $x_ {n_1, n_2, \ dots, n_d}$ son números reales , ya que a menudo están en las aplicaciones prácticas, a continuación, las salidas DFT tienen una simetría conjugado similar al caso unidimensional arriba:

$X_ {k_1, k_2, \ puntos, k_d} = X_ {N_1 - k_1, N_2 - k_2, \ dots, N_d - k_d} ^ *,$

donde la estrella denota conjugación compleja y la $\ Ell$ subíndice-ésimo se interpreta módulo $N_ \ ell$ (Por $\ Ell = 1,2, \ ldots, d$ ).

Aplicaciones

La DFT ha visto el uso de ancho a través de un gran número de campos; que sólo esbozamos algunos ejemplos a continuación (ver 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 discreta y sus inversas, una transformada rápida de Fourier.

El análisis espectral

Cuando la DFT se utiliza para el análisis espectral, la $\ {X_n \} \,$ secuencia por lo general representa un conjunto finito de uniformemente espaciados de tiempo muestras de algunos de señal $x (t) \,$ , Donde t representa el tiempo. La conversión de tiempo continuo de muestras (de tiempo discreto) cambia el subyacente Transformada de Fourier de x (t) en una Fourier de tiempo discreto de transformación (DTFT), que conlleva generalmente un tipo de distorsión llamada aliasing. La elección de una frecuencia de muestreo adecuado (vea Frecuencia de Nyquist) es la clave para minimizar la distorsión. Del mismo modo, la conversión de un tiempo muy largo (o infinito) secuencia a un tamaño manejable implica un tipo de distorsión llamada fugas, que se manifiesta como una pérdida de detalle (resolución aka) en el DTFT. Elección de una longitud de sub-secuencia apropiada es la clave principal para minimizar ese efecto. Cuando los datos disponibles (y tiempo para procesarlo) es más que la cantidad necesaria para alcanzar la resolución de frecuencia deseada, una técnica estándar es de realizar múltiples DFT, por ejemplo, para crear un espectrograma. Si el resultado deseado es un espectro de potencia y ruido o aleatoriedad está presente en los datos, el promedio de las 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 la Método de Welch y la Método de Bartlett.

Una fuente final de distorsión (o quizás ilusión) es el propio DFT, porque es sólo una muestra discreta de la DTFT, que es una función de un dominio de frecuencia continua. Eso puede ser mitigado por el aumento de la resolución de la DFT. Este procedimiento se ilustra en el de tiempo discreto transformada de Fourier artículo.

El procedimiento se refiere a veces como padding-cero, que es una implementación particular usado en conjunción con el transformada rápida de Fourier (FFT) algoritmo. La ineficiencia de realizar multiplicaciones y sumas con cero valorado "muestras" es más que compensado por la eficiencia inherente de la FFT.
Como ya se ha señalado, las fugas impone un límite a la resolución inherente de la DTFT. Así que hay un límite práctico para el beneficio que se puede obtener a partir de una DFT de grano fino.

Compresión de datos

El campo de procesamiento de señal digital depende en gran medida las operaciones en el dominio de la frecuencia (es decir, la transformada de Fourier). Por ejemplo, varios imágenes con pérdidas y los métodos de compresión de sonido emplean la transformada de Fourier discreta: la señal se corta en segmentos cortos, cada uno se transforma, y luego los coeficientes de Fourier de altas frecuencias, que se supone que son imperceptibles, se descartan. El descompresor calcula la transformada inversa basada en este reducido número de coeficientes de Fourier. (Aplicaciones de compresión a menudo usan una forma especializada de la DFT, la transformada de coseno discreta o, a veces la coseno discreta modificada transformar.)

Ecuaciones diferenciales parciales

Transformadas de Fourier discretas se utilizan a menudo para resolver ecuaciones diferenciales parciales , donde de nuevo la DFT se utiliza como una aproximación para el Serie de Fourier (que se recupera en el límite de infinito N). La ventaja de este enfoque es que se expande la señal en exponenciales complejas e ^inx, que son funciones propias de diferenciación: d / dx = e ^inx en e ^inx. Por lo tanto, en la representación de Fourier, la diferenciación es simple-vamos a multiplicarlo por en. Una ecuación diferencial lineal con coeficientes constantes se transforma en una ecuación algebraica fácilmente solucionable. Una vez, utiliza la DFT inversa para transformar el resultado en la representación espacial ordinaria. Este enfoque se denomina método espectral.

Multiplicación de polinomios

Supongamos que queremos calcular el producto c polinomio (x) = a (x) · b (x). La expresión producto ordinario para los coeficientes de c implica un lineal (acíclico) de convolución, donde los índices no "se envuelven alrededor." Esto puede ser reescrita como una convolución cíclica mediante la adopción de los vectores de coeficientes de a (x) yb (x) con término constante primero, a continuación, añadiendo ceros manera que el coeficiente resultante vectores A y B tienen dimensión d> deg (a (x) ) + deg (b (x)). Luego,

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

Donde c es el vector de coeficientes para c (x), y el operador de convolución $* \,$ se define de manera

$C_n = \ sum_ {m = 0} ^ {d-1} a_m b_ {nm \ \ mathrm {mod} \ d} \ qquad \ qquad \ qquad n = 0,1, ..., d-1$

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

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

Aquí el producto vectorial se toma elementwise. Así, los coeficientes del polinomio producto c (x) son sólo los términos 0, ..., deg (a (x)) + deg (b (x)) del vector de coeficiente

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

Con un Fast transformada de Fourier, el algoritmo resultante toma O (N log N) operaciones aritméticas. Debido a su simplicidad y velocidad, el Cooley-Tukey FFT algoritmo, que se limita a tamaños compuestos, a menudo se elige para la operación de transformación. En este caso, d debe ser elegido como el menor entero mayor que la suma de los grados de polinomio de entrada que es factorizable en pequeños factores primos (por ejemplo, 2, 3, y 5, dependiendo de la implementación FFT).

La multiplicación de enteros grandes

El más rápido conocido algoritmos para la multiplicación de muy grandes números enteros utilizan el método de multiplicación de polinomios descrito anteriormente. Los enteros pueden ser tratadas como el valor de un polinomio evaluado específicamente en la base número, con los coeficientes del polinomio correspondiente a los dígitos en esa base. Después de multiplicación de polinomios, un paso equipaje de propagación relativamente baja complejidad completa la multiplicación.

Algunos transformada de Fourier discreta pares

**Algunos pares DFT**
$x_n = \ frac {1} {N} \ sum_ {k = 0} ^ {N-1} x_k \ cdot e ^ {i 2 \ kn pi / N}$	$X_k = \ sum_ {n = 0} ^ {N-1} x_n \ cdot e ^ {- i 2 \ pi kn / N}$	Nota
$x_n \ cdot e ^ {i 2 \ pi nl / N} \,$	$X_ {k-l} \,$	Teorema del desfase
$x_ {n-l} \,$	$X_k \ cdot e ^ {- i 2 \ pi kl / N}$	Teorema del desfase
$x_n \ in \ mathbb {R}$	$X_k = X_ {N-k} ^ * \,$	Bienes DFT
$a ^ n \,$	$\ Frac {1-a ^ N} {1-a \ cdot e ^ {- i 2 \ pi k / N}}$
${N-1 \ elegir n} \,$	$\ Left (1 + e ^ {- k / N i 2 \ pi} \ right) ^ {N-1} \,$

Derivación como series de Fourier

La DFT se puede derivar como un truncamiento de la Serie de Fourier de una secuencia periódica de impulsos.

DFT sobre campos distintos de los números complejos

Muchas de las propiedades de la DFT depende únicamente del hecho de que $e ^ {- \ frac {2 \ pi i} {N}}$ es un raíz primitiva de la unidad, a veces denotada $\ Omega_N$ o $W_N$ (De modo que $\ Omega_N ^ N = 1$ ). Tales propiedades incluyen la integridad, la ortogonalidad, Plancherel / Parseval, la periodicidad, cambio, de convolución, y las propiedades de unitariedad anteriormente, así como muchos algoritmos FFT. Por esta razón, la Transformada Discreta de Fourier se puede definir mediante el uso de raíces de la unidad en ámbitos distintos de los números complejos; Para obtener más información, consulte transformada de Fourier discreta (general).

Recuperado de " http://en.wikipedia.org/w/index.php?title=Discrete_Fourier_transform&oldid=206659692 "