Transformada de Fourier discreta

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Tipo de Fourier transformado en matemáticas discretas

Relación entre (continua) Transformación Fourier y transformación discreta Fourier. Columna izquierda: Una función continua (top) y su transformación Fourier (bottom). Columna central izquierda: Summación periódica de la función original (top). Fourier transform (bottom) es cero excepto en puntos discretos. La transformación inversa es una suma de sinusoides llamados serie Fourier. Columna central derecha: La función original se discretiza (multiplicada por un peine Dirac) (top). Su transformación Fourier (abajo) es una suma periódica (DTFT) de la transformación original. Columna derecha: El DFT (abajo) calcula muestras discretas del DTFT continuo. El DFT inverso (top) es un resumen periódico de las muestras originales. El algoritmo FFT calcula un ciclo del DFT y su inverso es un ciclo del inverso DFT.

Depiction of a Fourier transform (upper left) and its periodic summation (DTFT) in the lower left corner. Las secuencias espectrales a) superior derecha y b) inferior 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 respectivas fórmulas son: a) la serie Fourier integral y b) el DFT summation. Sus similitudes con la transformación 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 función de frecuencia de valor complejo. El intervalo en el que se muestrea la DTFT es el recíproco de la duración de la secuencia de entrada. Una DFT inversa es una serie de Fourier, que usa las muestras de DTFT como coeficientes de sinusoides complejos 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 de la DTFT.

La DFT es la transformada discreta más importante, utilizada para realizar el análisis de Fourier en muchas aplicaciones prácticas. 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 de sonido, una señal de radio o lecturas diarias de temperatura, muestreadas durante un intervalo de tiempo finito (a menudo definido por una función de ventana). 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 de trama. La DFT también se usa para resolver eficientemente ecuaciones diferenciales parciales y para realizar otras operaciones como convoluciones o multiplicación de números enteros grandes.

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

Definición

El discreta Transformación de Fourier transforma una secuencia de N números complejos ${displaystyle left{mathbf {x} _{n}right}:=x_{0},x_{1},ldotsx_{N-1}}$ en otra secuencia de números complejos, ${displaystyle left{mathbf {X} _{k}right}:=X_{0},X_{1},ldotsX_{N-1},}$ que se define por

{displaystyle {begin{aligned}X_{k}&=sum _{n=0}^{N-1}x_{n}cdot e^{-{frac {i2pi }{N}}kn}\&=sum _{n=0}^{N-1}x_{n}cdot left[cos left({frac {2pi }{N}}knright)-icdot sin left({frac {2pi }{N}}knright)right],end{aligned}}}

()Eq.1)

donde la última expresión se sigue de la primera por la fórmula de Euler.

La transformación 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}$ .

Motivación

Eq.1 también se puede evaluar fuera del dominio ${displaystyle kin [0,N-1]}$ , y esa secuencia extendida es $N$ -peródico. En consecuencia, otras secuencias de $N$ a veces se utilizan índices, como ${textstyle left[-{frac {N}{2}},{frac {N}{2}}-1right]}$ (si $N$ es incluso) y ${textstyle left[-{frac {N-1}{2}},{frac {N-1}{2}}right]}$ (si $N$ es extraño), lo que equivale a cambiar las mitades izquierda y derecha del resultado de la transformación.

Eq.1 se puede interpretar o derivar de varias maneras, por ejemplo:

Describe completamente la discreta transformación Fourier (DTFT) de un $N$ - secuencia periódica, que comprende sólo componentes de frecuencia discreta. (Usando el DTFT con datos periódicos)
También puede proporcionar muestras uniformemente espaciadas del DTFT continuo de una secuencia de longitud finita. (§ muestra el DTFT)
Es la correlación cruzada de la entrada secuencia, $x_{n}$ , y un complejo sinusoide a frecuencia ${textstyle {frac {k}{N}}}$ . Así actúa como un filtro emparejado para esa frecuencia.
Es el análogo discreto de la fórmula para los coeficientes de una serie Fourier:
${displaystyle x_{n}={frac {1}{N}}sum _{k=0}^{N-1}X_{k}cdot e^{i2pi kn/N},quad nin mathbb {Z}}$
()Eq.2)
que es también $N$ -peródico. En el dominio $n [0, N - 1$ , este es el transformación inversa de Eq.1. En esta interpretación, cada uno $X_{k}$ es un número complejo que codifica la amplitud y la fase de un componente sinusoidal complejo ${displaystyle left(e^{i2pi kn/N}right)}$ de la función $x_{n}$ . (ver la serie Discreta Fourier) La frecuencia del sinusoide es k ciclos por ciclo N muestras. Su amplitud y fase son:
${displaystyle {frac {1}{N}}|X_{k}|={frac {1}{N}}{sqrt {operatorname {Re} (X_{k})^{2}+operatorname {Im} (X_{k})^{2}}}}$
${displaystyle arg(X_{k})=operatorname {atan2} {big (}operatorname {Im} (X_{k}),operatorname {Re} (X_{k}){big)}=-icdot ln left({frac {X_{k}}{|X_{k}|}}right),}$
donde atan2 es la forma de dos-argumentos de la función arctan. En forma polar ${displaystyle X_{k}=|X_{k}|e^{iarg(X_{k})}=|X_{k}|operatorname {cis} arg(X_{k})}$ donde cis es la mnemónica para cos + i pecado.

El factor de normalización multiplica el DFT y el IDFT (aquí 1 y ${textstyle {frac {1}{N}}}$ ) y los signos de los exponentes son meramente convenciones, y difieren en algunos tratamientos. Los únicos requisitos de estas convenciones son que el DFT y el IDFT tienen exponentes opuestos y que el producto de sus factores de normalización sea ${textstyle {frac {1}{N}}}$ . Una normalización de ${textstyle {sqrt {frac {1}{N}}}}$ tanto para el DFT como para el IDFT, por ejemplo, hace los transformados unitarios. Un impulso discreto, ${displaystyle x_{n}=1}$ a n= 0 y 0 de otro modo; podría transformarse ${displaystyle X_{k}=1}$ para todos k (factores de normalización del uso 1 para DFT y ${textstyle {frac {1}{N}}}$ para IDFT). Una señal de DC, ${displaystyle X_{k}=1}$ a k= 0 y 0 de otro modo; podría transformarse inversamente ${displaystyle x_{n}=1}$ para todos $n$ (utilización ${textstyle {frac {1}{N}}}$ para DFT y 1 para IDFT) que es consistente con ver a DC como el promedio medio de la señal.

Ejemplo

Este ejemplo demuestra cómo aplicar el DFT a una secuencia de longitud $N=4$ y el vector de entrada

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

Calculando el DFT $mathbf {x}$ utilizando Eq.1

${displaystyle X_{0}=e^{-i2pi 0cdot 0/4}cdot 1+e^{-i2pi 0cdot 1/4}cdot (2-i)+e^{-i2pi 0cdot 2/4}cdot (-i)+e^{-i2pi 0cdot 3/4}cdot (-1+2i)=2}$ ${displaystyle X_{1}=e^{-i2pi 1cdot 0/4}cdot 1+e^{-i2pi 1cdot 1/4}cdot (2-i)+e^{-i2pi 1cdot 2/4}cdot (-i)+e^{-i2pi 1cdot 3/4}cdot (-1+2i)=-2-2i}$ ${displaystyle X_{2}=e^{-i2pi 2cdot 0/4}cdot 1+e^{-i2pi 2cdot 1/4}cdot (2-i)+e^{-i2pi 2cdot 2/4}cdot (-i)+e^{-i2pi 2cdot 3/4}cdot (-1+2i)=-2i}$ ${displaystyle X_{3}=e^{-i2pi 3cdot 0/4}cdot 1+e^{-i2pi 3cdot 1/4}cdot (2-i)+e^{-i2pi 3cdot 2/4}cdot (-i)+e^{-i2pi 3cdot 3/4}cdot (-1+2i)=4+4i}$

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

Transformada inversa

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

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

con $mathbb {C}$ denotando el conjunto de números complejos. Su inverso se conoce como Inverse Discrete Fourier Transform (IDFT). En otras palabras, para cualquier $0}" xmlns="http://www.w3.org/1998/Math/MathML">N■0{displaystyle N confiar0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6b5e672f875388753faa233a18e9f2cf1275aaa4" style="vertical-align: -0.338ex; width:6.325ex; height:2.176ex;"/>$ , un N- vector complejo dimensional tiene un DFT y un IDFT que a su vez son $N$ - vectores complejos dimensionales.

La transformada inversa viene dada por:

{displaystyle x_{n}={frac {1}{N}}sum _{k=0}^{N-1}X_{k}cdot e^{i{frac {2pi }{N}}kn}}

()Eq.3)

Propiedades

Linealidad

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

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

Inversión de tiempo y frecuencia

Revertir el tiempo (es decir, sustituir $n$ por $N-n$ En $x_{n}$ corresponde a la inversión de la frecuencia (es decir, $k$ por $N-k$ ). Matemáticamente, si ${x_{n}}$ representa el vector x entonces

{mathcal {F}}({x_{n}})_{k}=X_{k}

entonces

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

Conjugación en el tiempo

Si ${displaystyle {mathcal {F}}({x_{n}})_{k}=X_{k}}$ entonces ${displaystyle {mathcal {F}}({x_{n}^{*}})_{k}=X_{N-k}^{*}}$ .

Parte real e imaginaria

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

Propiedad	Dominio de tiempo $x_{n}$	Dominio de frecuencia $X_{k}$
Parte real en el tiempo	${displaystyle Re {left(x_{n}right)}}$	${displaystyle {frac {1}{2}}left(X_{k}+X_{N-k}^{*}right)}$
Parte imaginaria en el tiempo	${displaystyle Im {left(x_{n}right)}}$	${displaystyle {frac {1}{2i}}left(X_{k}-X_{N-k}^{*}right)}$
Parte real en frecuencia	${displaystyle {frac {1}{2}}left(x_{n}+x_{N-n}^{*}right)}$	${displaystyle Re {left(X_{k}right)}}$
Parte imaginaria en frecuencia	${displaystyle {frac {1}{2i}}left(x_{n}-x_{N-n}^{*}right)}$	${displaystyle Im {left(X_{k}right)}}$

Ortogonalidad

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

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

Donde ${displaystyle delta _{kk'}}$ es el Kronecker delta. (En el último paso, la suma es trivial si $k=k'$ , donde está 1 + 1 + ⋯ = N, y de otro modo es una serie geométrica que se puede resumir 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 del DFT, y es equivalente a la propiedad unitaria a continuación.

El teorema de Plancherel y el teorema de Parseval

Si $X_{k}$ y $Y_{k}$ son los DFT de $x_{n}$ y $y_{n}$ respectivamente, entonces el teorema de Parseval declara:

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:

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 siguiente condición unitaria.

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 {i2pi }{N}}(k+N)n}=sum _{n=0}^{N-1}x_{n}e^{-{frac {i2pi }{N}}kn}underbrace {e^{-i2pi n}} _{1}=sum _{n=0}^{N-1}x_{n}e^{-{frac {i2pi }{N}}kn}=X_{k}.}

Del mismo modo, se puede demostrar que la fórmula IDFT conduce a una extensión periódica.

Teorema del cambio

Multiplicación $x_{n}$ por a fase lineal ${displaystyle e^{{frac {i2pi (n-1)}{N}}m}}$ para algunos enteros m corresponde a un Cambio circular de la producción $X_{k}$ : $X_{k}$ es reemplazado por $X_{k-m}$ , donde el subscripto es interpretado modulo N (es decir, periódicamente). Análogamente, un cambio circular de la entrada $x_{n}$ corresponde a multiplicar la salida $X_{k}$ por una fase lineal. Matemáticamente, si ${x_{n}}$ representa el vector x entonces

{mathcal {F}}({x_{n}})_{k}=X_{k}

entonces

{displaystyle {mathcal {F}}left(left{x_{n}cdot e^{{frac {i2pi }{N}}nm}right}right)_{k}=X_{k-m}}

{displaystyle {mathcal {F}}left(left{x_{n-m}right}right)_{k}=X_{k}cdot e^{-{frac {i2pi }{N}}km}}

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

El teorema de la convolución para la transformación Fourier discreta (DTFT) indica que una convolución de dos secuencias se puede obtener como la transformación inversa del producto de los transformados individuales. Una simplificación importante ocurre cuando una de las secuencias es N-periodic, denotado aquí por ${displaystyle y_{_{N}},}$ porque ${displaystyle scriptstyle {text{DTFT}}displaystyle {y_{_{N}}}}$ no es cero en sólo frecuencias discretas (ver DTFT § Datos periódicos), y por lo tanto es su producto con la función continua ${displaystyle scriptstyle {text{DTFT}}displaystyle {x}.}$ Esto conduce a una considerable simplificación de la transformación inversa.

{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 ${displaystyle x_{_{N}}}$ es un resumen periódico de la $x$ secuencia: ${displaystyle (x_{_{N}})_{n} triangleq sum _{m=-infty }^{infty }x_{(n-mN)}.}$

Personalmente, las sumas DFT e inversas DFT se toman sobre el dominio ${displaystyle [0,N-1]}$ . Definir esos DFT como $X$ y $Y$ , el resultado es:

{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{Xcdot Yright}_{n}.}

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

{displaystyle (y_{_{N}})_{n}=sum _{p=-infty }^{infty }y_{(n-pN)}=y_{(noperatorname {mod} N)},quad nin mathbb {Z}.}

Entonces la convolución se puede escribir como:

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

que da lugar a la interpretación como circular circular convolution of $x$ y $y.$ A menudo se utiliza para calcular eficientemente su convolución lineal. (ver Convolución Circular, algoritmos de convolución rápida y superposición)

Del mismo modo, la cruz-correlación de $x$ y ${displaystyle y_{_{N}}}$ es dado por:

{displaystyle (xstar y_{_{N}})_{n}triangleq sum _{ell =-infty }^{infty }x_{ell }^{*}cdot (y_{_{N}})_{n+ell }={mathcal {F}}^{-1}left{X^{*}cdot Yright}_{n}.}

Se ha demostrado que cualquier transformada lineal que convierta la convolución en un producto puntual es la DFT (hasta una permutación de coeficientes).

Dualidad del teorema de convolución

También se puede demostrar que:

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

{displaystyle ={frac {1}{N}}(mathbf {X*Y_{N}})_{k},}

que es la convolución circular

mathbf {X}

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^{i2pi t}+cdots +X_{N/2-1}e^{i2pi (N/2-1)t}+X_{N/2}cos(Npi t)+X_{N/2+1}e^{-i2pi (N/2-1)t}+cdots +X_{N-1}e^{-i2pi t}right]&N{text{ even}}\{frac {1}{N}}left[X_{0}+X_{1}e^{i2pi t}+cdots +X_{(N-1)/2}e^{i2pi (N-1)t}+X_{(N+1)/2}e^{-i2pi (N-1)t}+cdots +X_{N-1}e^{-i2pi t}right]&N{text{ odd}}end{cases}}}

donde los coeficientes X_k son dados por el DFT de x_n arriba, satisface la propiedad de la interpolación $p(n/N)=x_{n}$ para ${displaystyle n=0,ldotsN-1}$ .

Para incluso N, note que el componente Nyquist ${textstyle {frac {X_{N/2}}{N}}cos(Npi t)}$ es manejado especialmente.

Esta interpolación es no único: alias implica que uno podría añadir N a cualquiera de las frecuencias sinusoide complejas (por ejemplo, cambiar $e^{-it}$ a $e^{i(N-1)t}$ ) sin cambiar la propiedad de la interpolación, pero dar diferentes valores entre $x_{n}$ puntos. La elección anterior, sin embargo, es típica porque tiene dos propiedades útiles. Primero, consta de sinusoides cuyas frecuencias tienen las magnitudes más pequeñas posibles: la interpolación está limitada. Segundo, si el $x_{n}$ son números reales, entonces $p(t)$ es real también.

En contraste, el polinomio de interpolación trigonométrica más obvio es el que las frecuencias varían de 0 a 0 $N-1$ (en lugar de bruscamente $-N/2$ a $+N/2$ como arriba), similar a la fórmula inversa DFT. Esta interpolación lo hace no minimizar la pendiente, y es no generalmente real-valued para real $x_{n}$ ; su uso es un error común.

La DFT unitaria

(feminine)

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

{displaystyle mathbf {F} ={begin{bmatrix}omega _{N}^{0cdot 0}&omega _{N}^{0cdot 1}&cdots &omega _{N}^{0cdot (N-1)}\omega _{N}^{1cdot 0}&omega _{N}^{1cdot 1}&cdots &omega _{N}^{1cdot (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 ${displaystyle omega _{N}=e^{-i2pi /N}}$ es una raíz primitiva Nth 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 unitaria ${textstyle 1/{sqrt {N}}}$ , el DFT se convierte en una transformación unitaria, definida por una matriz unitaria:

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

Donde ${displaystyle det()}$ es la función determinante. El determinante es el producto de los eigenvalues, que son siempre $pm 1$ o $pm i$ como se describe a continuación. En un espacio vectorial real, una transformación unitaria se puede considerar 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 el DFT unitario.

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 la 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

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

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

{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.

Expresión de 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), a través de varios "trucos" 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 desde la primera).

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

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

(Como de costumbre, los subscriptos se interpretan modulo N; por lo tanto, $n=0$ , tenemos ${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 datos, implica el intercambio de partes reales e imaginarias (que se puede hacer en un ordenador simplemente modificando punteros). Define ${textstyle operatorname {swap} (x_{n})}$ como $x_{n}$ con sus partes reales e imaginarias intercambiadas, es decir, si $x_{n}=a+bi$ entonces ${textstyle operatorname {swap} (x_{n})}$ es $b+ai$ . Equivalentemente, ${textstyle operatorname {swap} (x_{n})}$ iguales $ix_{n}^{*}$ . Entonces...

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

Es decir, la transformada inversa es lo mismo 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 conjugación también se puede utilizar para definir una nueva transformación, estrechamente relacionada con el DFT, que es involutivo, es decir, que es su propio inverso. En particular, ${displaystyle T(mathbf {x})={mathcal {F}}left(mathbf {x} ^{*}right)/{sqrt {N}}}$ es claramente su propio inverso: $T(T(mathbf {x}))=mathbf {x}$ . Una transformación involutiva estrechamente relacionada (por un factor ${textstyle {frac {1+i}{sqrt {2}}}}$ ) es ${displaystyle H(mathbf {x})={mathcal {F}}left((1+i)mathbf {x} ^{*}right)/{sqrt {2N}}}$ , desde el ${displaystyle (1+i)}$ factores en $H(H(mathbf {x}))$ cancelar el 2. Para entradas reales $mathbf {x}$ , la parte real de $H(mathbf {x})$ no es otra que la discreta transformación de Hartley, que también es involutoria.

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 $mathbf {U}$ definida anteriormente para el DFT de longitud N, donde

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

Esta matriz satisface la ecuación polinomial matricial:

mathbf {U} ^{4}=mathbf {I}.

Esto se puede ver desde las propiedades inversas anteriores: $mathbf {U}$ dos veces da los datos originales en orden inverso, por lo que el funcionamiento $mathbf {U}$ cuatro veces devuelve los datos originales y es por lo tanto la matriz de identidad. Esto significa que los eigenvalues $lambda$ satisfacer la ecuación:

lambda ^{4}=1.

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

Puesto que sólo hay cuatro eigenvalues distintos para esto $Ntimes N$ matriz, tienen cierta multiplicidad. La multiplicidad da el número de eigenvectores linealmente independientes correspondientes a cada eigenvalue. (Hay N eigenvectores independientes; una matriz unitaria nunca es defectuosa.)

El problema de su multiplicidad fue resuelto por McClellan y Parks (1972), aunque luego 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:

Multiplicidades de los eigenvalues λ de la matriz DFT unitaria U como función del tamaño de transformación N (en términos de un entero m).
tamaño N	λ = +1	λ = −1	λ = −i	λ = +i
4m	m + 1	m	m	m − 1
4m + 1	m + 1	m	m	m
4m + 2	m + 1	m + 1	m	m
4m + 3	m + 1	m + 1	m + 1	m

De lo contrario, el polinomio característico $mathbf {U}$ es:

det(lambda I-mathbf {U})=(lambda -1)^{leftlfloor {tfrac {N+4}{4}}rightrfloor }(lambda +1)^{leftlfloor {tfrac {N+2}{4}}rightrfloor }(lambda +i)^{leftlfloor {tfrac {N+1}{4}}rightrfloor }(lambda -i)^{leftlfloor {tfrac {N-1}{4}}rightrfloor }.

No se conoce ninguna fórmula analítica simple 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 elecciones de autovectores, seleccionados para satisfacer propiedades útiles como la ortogonalidad y para tener "simple" (p. ej., McClellan y Parks, 1972; Dickinson y Steiglitz, 1982; Grünbaum, 1982; Atakishiyev y Wolf, 1997; Candan et al., 2000; Hanna et al., 2004; Gurevich y Hadani, 2008).

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

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

La expresión de forma cerrada para la serie se puede expresar mediante 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 simples de forma cerrada para el período especial DFT N (Kong, 2008):

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

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

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

${displaystyle F(m)=sin left({frac {2pi }{N}}mright)prod _{s=K+1}^{L-1}left[cos left({frac {2pi }{N}}mright)-cos left({frac {2pi }{N}}sright)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 (por ejemplo, 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 estas como vectores propios de la DFT, como los polinomios de Kravchuk (Atakishiyev y Wolf, 1997). El "mejor" Sin embargo, la 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

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 $P(x)$ y $Q(k)$ , el principio de incertidumbre Heisenberg establece que

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

Donde $D_{0}(X)$ y $D_{0}(x)$ son las diferencias de $|X|^{2}$ y $|x|^{2}$ respectivamente, con la igualdad alcanzada en el caso de una distribución gaussiana adecuadamente normalizada. Aunque las diferencias pueden definirse analógicamente para el DFT, un principio de incertidumbre análoga no es útil, porque la incertidumbre no será invariable. Sin embargo, un principio de incertidumbre significativo ha sido introducido por Massar y Spindel.

Sin embargo, la incertidumbre entrópica de Hirschman tendrá un análogo útil para el caso de la DFT. 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

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

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

y el principio de incertidumbre entrópica se convierte en

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

La igualdad se obtiene para $P_{n}$ igual a traducciones y modulación de un peine de Kronecker adecuado normalizado de período $A$ Donde $A$ es cualquier divisor entero exacto $N$ . La función de masa de probabilidad $Q_{m}$ entonces será proporcional a un peine de Kronecker adecuadamente traducido del período $B=N/A$ .

Principio de incertidumbre determinista

También existe un conocido principio de incertidumbre determinista que utiliza la esparsidad de la señal (o el número de coeficientes no cero). Vamos ${displaystyle left|xright|_{0}}$ y ${displaystyle left|Xright|_{0}}$ ser el número de elementos no cero de las secuencias de tiempo y frecuencia $x_{0},x_{1},ldotsx_{N-1}$ y $X_{0},X_{1},ldotsX_{N-1}$ , respectivamente. Entonces,

{displaystyle Nleq left|xright|_{0}cdot left|Xright|_{0}.}

Como consecuencia inmediata de la desigualdad de medios aritméticos y geométricos, uno también tiene ${displaystyle 2{sqrt {N}}leq left|xright|_{0}+left|Xright|_{0}}$ . Ambos principios de incertidumbre se mostraron ajustados para secuencias "picket-fence" específicamente escogidas (entrenamientos de impulso descreto), y encontrar uso práctico para aplicaciones de recuperación de señales.

DFT de señales reales y puramente imaginarias

Si $x_{0},ldotsx_{N-1}$ son números reales, ya que a menudo están en aplicaciones prácticas, entonces el DFT ${displaystyle X_{0},ldotsX_{N-1}}$ es incluso simétrico:

{displaystyle x_{n}in mathbb {R} quad forall nin {0,ldotsN-1}implies X_{k}=X_{-kmod N}^{*}quad forall kin {0,ldotsN-1}}

, donde

X^{*},

denota conjugación compleja.

De ello se desprende que incluso $N$ $X_{0}$ y ${displaystyle X_{N/2}}$ son de valor real, y el resto del DFT está completamente especificado por sólo ${displaystyle N/2-1}$ números complejos.

Si $x_{0},ldotsx_{N-1}$ son números puramente imaginarios, entonces el DFT ${displaystyle X_{0},ldotsX_{N-1}}$ es simétrico extraño:

{displaystyle x_{n}in imathbb {R} quad forall nin {0,ldotsN-1}implies X_{k}=-X_{-kmod N}^{*}quad forall kin {0,ldotsN-1}}

, donde

X^{*},

denota conjugación compleja.

DFT generalizado (fase desplazada y no lineal)

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

{displaystyle X_{k}=sum _{n=0}^{N-1}x_{n}e^{-{frac {i2pi }{N}}(k+b)(n+a)}quad quad k=0,dotsN-1.}

A menudo, cambios de $1/2$ (la mitad de una muestra) se usan. Mientras que el DFT ordinario corresponde a una señal periódica en los dominios de tiempo y frecuencia, $a=1/2$ produce una señal que es antiperódico en el dominio de frecuencia ( $X_{k+N}=-X_{k}$ ) y viceversa para $b=1/2$ . Así pues, el caso específico de $a=b=1/2$ es conocido como extraña frecuencia Transformación discreta Fourier (o O² DFT). Tales transformaciones cambiadas se utilizan más a menudo para datos simétricos, para representar diferentes simetrías de límites, y para datos simétricos reales que corresponden a diferentes formas de las transformaciones discretas cosina y sine.

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

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 transformadas de bloques ortogonales de amplitud constante que incluyen tipos de fase lineales y no lineales. GDFT es un marco para mejorar las propiedades de dominio de tiempo y frecuencia de la DFT tradicional, p. 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 lineales originales (Akansu y Agirman-Tosun, 2010).

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

DFT multidimensional

El DFT común transforma una secuencia única o un array $x_{n}$ que es una función de exactamente una variable discreta n. El DFT multidimensional de una matriz multidimensional $x_{n_{1},n_{2},dotsn_{d}}$ que es una función d variables discretas $n_{ell }=0,1,dotsN_{ell }-1$ para $ell$ dentro $1,2,dotsd$ se define por:

{displaystyle X_{k_{1},k_{2},dotsk_{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},dotsn_{d}}right)right),}

Donde ${displaystyle omega _{N_{ell }}=exp(-i2pi /N_{ell })}$ como arriba y el d de los índices de producción $k_{ell }=0,1,dotsN_{ell }-1$ . Esto se expresa más compactamente en la notación vectorial, donde definimos $mathbf {n} =(n_{1},n_{2},dotsn_{d})$ y $mathbf {k} =(k_{1},k_{2},dotsk_{d})$ como d- vectores dimensionales de índices de 0 a 0 $mathbf {N} -1$ , que define como $mathbf {N} -1=(N_{1}-1,N_{2}-1,dotsN_{d}-1)$ :

{displaystyle X_{mathbf {k} }=sum _{mathbf {n} =mathbf {0} }^{mathbf {N} -1}e^{-i2pi 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},dotsn_{d}/N_{d})$ para ser realizado en sentido de elemento, y la suma denota el conjunto de summations anidados arriba.

La inversa de la DFT multidimensional es, 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^{i2pi mathbf {n} cdot (mathbf {k} /mathbf {N})}X_{mathbf {k} },.}

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

El DFT multidimensional puede ser calculado por la composición de una secuencia de DFTs unidimensional a lo largo de cada dimensión. En el caso bidimensional $x_{n_{1},n_{2}}$ el $N_{1}$ DFT independientes de las filas (es decir, a lo largo $n_{2}$ ) se computed primero para formar un nuevo array $y_{n_{1},k_{2}}$ . Entonces el $N_{2}$ DFT independientes Sí. a lo largo de las columnas $n_{1}$ ) se computed para formar el resultado final $X_{k_{1},k_{2}}$ . Alternativamente las columnas pueden ser calculadas primero y luego las filas. El orden es inmaterial porque las summaciones anidadas por encima de la conmutación.

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 hay algoritmos FFT intrínsecamente multidimensionales.

La DFT multidimensional de entrada real

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

X_{k_{1},k_{2},dotsk_{d}}=X_{N_{1}-k_{1},N_{2}-k_{2},dotsN_{d}-k_{d}}^{*},

donde la estrella denota de nuevo la conjugación compleja y la $ell$ -th subscript is again interpreted modulo $N_{ell }$ (por $ell =1,2,ldotsd$ ).

Aplicaciones

La DFT ha tenido un amplio uso en una gran cantidad de campos; solo esbozamos algunos ejemplos a continuación (ver también las referencias al final). Todas las aplicaciones de la DFT dependen de manera crucial de la disponibilidad de un algoritmo rápido para calcular transformadas discretas de Fourier y sus inversas, una transformada rápida de Fourier.

Análisis espectral

Discreta transforma incrustada en tiempo & espacio.

Cuando el DFT se utiliza para el análisis espectral de señal, el ${x_{n}}$ secuencia generalmente representa un conjunto finito de muestras de tiempo uniformemente espaciadas de alguna señal $x(t),$ , donde $t$ representa tiempo. La conversión de tiempo continuo a muestras (tiempo de descreto) cambia la transformación subyacente de Fourier $x(t)$ en una transformación Fourier discreta (DTFT), que generalmente implica un tipo de distorsión llamada alias. Elección de una muestra apropiada (ver Tasa de Nyquist) es la clave para minimizar esa distorsión. Del mismo modo, la conversión de una secuencia muy larga (o infinita) a un tamaño manejable implica un tipo de distorsión llamada filtración, que se manifiesta como una pérdida de detalle (a.k.a. resolución) en el DTFT. La elección de una longitud de subsequencia adecuada es la clave principal para minimizar ese efecto. Cuando los datos disponibles (y el tiempo para procesarlo) son más que la cantidad necesaria para alcanzar la resolución de frecuencia deseada, una técnica estándar es realizar múltiples DFTs, por ejemplo para crear un espectrograma. Si el resultado deseado es un espectro de potencia y ruido o aleatoriedad está presente en los datos, promediar los componentes de magnitud de los múltiples DFT es un procedimiento útil para reducir la varianza del espectro (también llamado periodograma en este contexto); dos ejemplos de estas técnicas son el método Welch y el método Bartlett; el tema general de estimación del espectro de potencia de una señal ruidosa se llama estimación espectro.

Una fuente final de distorsión (o quizás ilusión) es la propia DFT, porque es solo una muestra discreta de la DTFT, que es una función de un dominio de frecuencia continuo. Eso se puede mitigar aumentando la resolución de la DFT. Ese procedimiento se ilustra en § Muestreo de la DTFT.

El procedimiento a veces se conoce como cero-padding, que es una aplicación particular utilizada en conjunto con el algoritmo de transformación rápida Fourier (FFT). La ineficiencia de realizar multiplicaciones y adiciones con "samples" de valor cero es más que compensada por la eficiencia inherente de la FFT.
Como ya se ha indicado, la fuga impone un límite a la resolución inherente del DTFT, por lo que existe un límite práctico para el beneficio que puede obtenerse de un DFT fino.

Óptica, difracción y tomografía

La transformada discreta de Fourier se usa ampliamente con frecuencias espaciales para modelar la forma en que la luz, los electrones y otras sondas viajan a través de los sistemas ópticos y se dispersan de los objetos en dos y tres dimensiones. El espacio vectorial dual (directo/recíproco) de objetos tridimensionales pone a disposición además 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, p. en la medicina moderna.

Banco de filtros

Ver § Bancos de filtros FFT y § Muestreo de la DTFT.

Compresión de datos

El campo del procesamiento de señales digitales se basa en gran medida en las operaciones en el dominio de la frecuencia (es decir, en la transformada de Fourier). Por ejemplo, varios métodos de compresión de imagen 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 frecuencias altas, 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 el de la frecuencia que el que se obtiene cortando los datos en segmentos y transformando cada segmento. En el caso de JPEG2000, esto evita las características de imagen espurias que aparecen cuando las imágenes están muy comprimidas con el JPEG original.

Ecuaciones diferenciales parciales

Las transformaciones de Fourier se utilizan a menudo para resolver ecuaciones diferenciales parciales, donde de nuevo el DFT se utiliza como una aproximación para la serie Fourier (que se recupera en el límite de infinito N). La ventaja de este enfoque es que expande la señal en exponenciales complejos ${displaystyle e^{inx}}$ , que son eigenfunctions de diferenciación: ${displaystyle {{text{d}}{big (}e^{inx}{big)}}/{text{d}}x=ine^{inx}}$ . Por lo tanto, en la representación de Fourier, la diferenciación es simple – simplemente multiplicamos por $in$ . (Sin embargo, la elección de $n$ no es único debido al aliado; para que el método sea convergente, se debe utilizar una opció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 fácilmente solvable. Luego se utiliza el DFT inverso para transformar el resultado en la representación espacial ordinaria. Tal enfoque se llama un método espectral.

Multiplicación de polinomios

Supongamos que deseamos calcular el producto polinomial 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 "envuelven." Esto se puede reescribir como una convolución cíclica tomando los vectores de coeficientes para a(x) y b(x) con un término constante primero, luego añadiendo ceros para que los vectores de coeficientes resultantes a y b tengan una dimensión d > grado(a(x)) + grado(b(x)). Después,

mathbf {c} =mathbf {a} *mathbf {b}

Donde c es el vector de los coeficientes para c()x), y el operador conversor $*,$ se define así

c_{n}=sum _{m=0}^{d-1}a_{m}b_{n-m mathrm {mod} d}qquad qquad qquad n=0,1dotsd-1

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

{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 simplemente los términos 0,..., deg(a(x )) + grado(b(x)) del vector coeficiente

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

Con una transformada rápida de Fourier, el algoritmo resultante toma O(N log N) operaciones aritméticas. Debido a su simplicidad y velocidad, el algoritmo FFT de Cooley-Tukey, que se limita a tamaños compuestos, a menudo se elige para la operación de transformación. 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 pequeños factores primos (por ejemplo, 2, 3 y 5, dependiendo de la implementación de FFT).

Multiplicación de enteros grandes

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

Convolución

Cuando los datos se convolucionan con una función con amplia compatibilidad, como para reducir la muestra en una relación de muestreo grande, debido al teorema de convolución y al algoritmo FFT, puede ser más rápido transformarlos, multiplicándolos puntualmente por la transformación del filtro. y luego transformarlo a la inversa. Alternativamente, se obtiene un buen filtro simplemente truncando los datos transformados y volviendo a transformar el conjunto de datos acortado.

Algunos pares discretos de transformadas de Fourier

**Algunos pares DFT**
$x_{n}={frac {1}{N}}sum _{k=0}^{N-1}X_{k}e^{i2pi kn/N}$	$X_{k}=sum _{n=0}^{N-1}x_{n}e^{-i2pi kn/N}$	Nota
$x_{n}e^{i2pi nell /N},$	$X_{k-ell },$	Teorema de cambio de frecuencia
$x_{n-ell },$	$X_{k}e^{-i2pi kell /N},$	Time shift theorem
$x_{n}in mathbb {R}$	$X_{k}=X_{N-k}^{*},$	DFT real
$a^{n},$	$left{{begin{matrix}N&{mbox{if }}a=e^{i2pi k/N}\{frac {1-a^{N}}{1-a,e^{-i2pi k/N}}}&{mbox{otherwise}}end{matrix}}right.$	de la fórmula de progresión geométrica
${N-1 choose n},$	$left(1+e^{-i2pi k/N}right)^{N-1},$	del teorema binomio
$<math alttext="{displaystyle left{{begin{matrix}{frac {1}{W}}&{mbox{if }}2n<W{mbox{ or }}2(N-n){}1Wsi2n.Wo2()N− − n).W0de otra manera{displaystyle left{begin{Matrix}{frac {1}{} {mbox{if} - ¿Qué?<img alt="left{{begin{matrix}{frac {1}{W}}&{mbox{if }}2n<W{mbox{ or }}2(N-n)$	$left{{begin{matrix}1&{mbox{if }}k=0\{frac {sin left({frac {pi Wk}{N}}right)}{Wsin left({frac {pi k}{N}}right)}}&{mbox{otherwise}}end{matrix}}right.$	$x_{n}$ es una función de ventana rectangular W puntos centrados en n=0, donde W es un extraño entero, y $X_{k}$ es una función similar al seno (específicamente, $X_{k}$ es un núcleo Dirichlet)
$sum _{jin mathbb {Z} }exp left(-{frac {pi }{cN}}cdot (n+Ncdot j)^{2}right)$	${sqrt {cN}}cdot sum _{jin mathbb {Z} }exp left(-{frac {pi c}{N}}cdot (k+Ncdot j)^{2}right)$	Discretization and periodic summation of the scaled Gaussian functions for $0}" xmlns="http://www.w3.org/1998/Math/MathML">c■0{displaystyle c]0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ba126f626d61752f62eaacaf11761a54de4dc84" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;"/>$ . Desde $c$ o ${frac {1}{c}}$ es más grande que uno y por lo tanto garantiza la convergencia rápida de una de las dos series, para grande $c$ Usted puede elegir computar el espectro de frecuencias y convertir al dominio del tiempo utilizando la transformación discreta Fourier.

Generalizaciones

Teoría de la representación

El DFT puede interpretarse como una representación compleja del grupo cíclico finito. En otras palabras, una secuencia de $n$ los números complejos se pueden considerar como un elemento $n$ - espacio complejo dimensional $mathbb {C} ^{n}$ o equivalente a una función $f$ del grupo cíclico finito de orden $n$ a los números complejos, ${displaystyle mathbb {Z} _{n}mapsto mathbb {C} }$ . Así que... $f$ es una función de clase en el grupo cíclico finito, y así se puede expresar como una combinación lineal de los caracteres irreducibles de este grupo, que son las raíces de la unidad.

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

Más estrictamente aún, se puede generalizar la DFT cambiando el objetivo (tomando valores en un campo que no sean números complejos) o el dominio (un grupo que no sea un grupo cíclico finito), como se detalla a continuación.

Otros campos

Muchas de las propiedades del DFT sólo dependen del hecho de que ${displaystyle e^{-{frac {i2pi }{N}}}}$ es una raíz primitiva de la unidad, a veces denotada $omega _{N}$ o $W_{N}$ (para que $omega _{N}^{N}=1$ ). Estas propiedades incluyen la integridad, ortogonalidad, Plancherel/Parseval, periodicidad, cambio, convolución y propiedades unitarias arriba, así como muchos algoritmos FFT. Por esta razón, la transformación discreta Fourier se puede definir utilizando raíces de unidad en campos distintos de los números complejos, y tales generalizaciones se llaman comúnmente transformaciones número-teoréticas (NTTs) en el caso de campos finitos. Para más información, consulte la transformación número-teorética y la transformación discreta Fourier (general).

Otros grupos finitos

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

{0,1,ldotsN_{1}-1}times cdots times {0,1,ldotsN_{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 estar en clases laterales de un grupo.

Alternativas

Existen varias alternativas a la 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 de 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 dificultad para representando transitorios. Como las wavelets tienen ubicación además de frecuencia, pueden representar mejor la ubicación, a expensas de una mayor dificultad para representar la frecuencia. Para obtener más información, consulte la comparación de la transformada discreta de ondículas con la transformada discreta de Fourier.

Contenido relacionado

Más resultados...