Transformada rápida de Fourier

Un ejemplo de estructura de algoritmo FFT, usando una descomposición en FFTs de tamaño medio

Un análisis discreto de Fourier de una suma de ondas cosinas a 10, 20, 30, 40 y 50 Hz

A rápido Fourier transformado ()FFT) es un algoritmo que computa la transformación discreta Fourier (DFT) de una secuencia, o su inverso (IDFT). El análisis Fourier convierte una señal de su dominio original (a menudo tiempo o espacio) a una representación en el dominio de frecuencia y viceversa. El DFT se obtiene descomponiendo una secuencia de valores en componentes de diferentes frecuencias. Esta operación es útil en muchos campos, pero computarla directamente de la definición es a menudo demasiado lenta para ser práctica. Un FFT calcula rápidamente tales transformaciones al factorizar la matriz DFT en un producto de factores escasos (casi cero). Como resultado, logra reducir la complejidad de la computación del DFT O()N2){textstyle Oleft(N^{2}right)}, que surge si uno simplemente aplica la definición de DFT, a O()Nlog⁡ ⁡ N){textstyle O(Nlog N)}, donde N{displaystyle N} es el tamaño de los datos. La diferencia de velocidad puede ser enorme, especialmente para conjuntos de datos largos donde N puede estar en miles o millones. En presencia de errores de redondeo, muchos algoritmos FFT son mucho más precisos que evaluar la definición DFT directa o indirectamente. Hay muchos algoritmos FFT diferentes basados en una amplia gama de teorías publicadas, desde simple complejo-número aritmética a la teoría de grupos y la teoría de números.

Representación basada en el tiempo (arriba) y representación basada en la frecuencia (abajo) de la misma señal, donde la representación inferior puede obtenerse desde la parte superior por la transformación Fourier

Las transformadas rápidas de Fourier se utilizan ampliamente para aplicaciones en ingeniería, música, ciencias y matemáticas. Las ideas básicas se popularizaron en 1965, pero algunos algoritmos se derivaron ya en 1805. En 1994, Gilbert Strang describió la FFT como "el algoritmo numérico más importante de nuestra vida", y se incluyó en Top 10 Algorithms of 20th Century de la revista IEEE Computing in Science & Ingeniería.

Los algoritmos FFT más conocidos dependen de la factorización de N, pero hay FFTs con O(N log N) complejidad para todos N, incluso para el mejorN. Muchos algoritmos FFT dependen sólo del hecho de que e− − 2π π i/N{textstyle e^{-2pi i/N} es un N-la raíz primitiva de la unidad, y así se puede aplicar a transformaciones analógicas sobre cualquier campo finito, tales como transformaciones número-teoréticas. Puesto que el DFT inverso es el mismo que el DFT, pero con el signo opuesto en el exponente y un 1/N factor, cualquier algoritmo FFT puede adaptarse fácilmente para él.

Historia

El desarrollo de algoritmos rápidos para DFT se remonta al trabajo inédito de Carl Friedrich Gauss en 1805 cuando lo necesitaba para interpolar la órbita de los asteroides Palas y Juno a partir de observaciones de muestra. Su método era muy similar al publicado en 1965 por James Cooley y John Tukey, a quienes generalmente se les atribuye la invención del algoritmo FFT genérico moderno. Si bien el trabajo de Gauss es anterior incluso a los resultados de Joseph Fourier en 1822, no analizó el tiempo de cálculo y finalmente utilizó otros métodos para lograr su objetivo.

Entre 1805 y 1965, algunas versiones de FFT fueron publicadas por otros autores. Frank Yates en 1932 publicó su versión llamada interacción algoritmo, que proporcionó una eficiente computación de transformados Hadamard y Walsh. El algoritmo de Yates todavía se utiliza en el campo del diseño estadístico y el análisis de experimentos. En 1942, G. C. Danielson y Cornelius Lanczos publicaron su versión para computar DFT para la cristalografía de rayos X, un campo donde el cálculo de las transformaciones de Fourier presentó un formidable cuello de botella. Mientras que muchos métodos en el pasado se habían centrado en reducir el factor constante O()N2){textstyle Oleft(N^{2}right)} computación aprovechando "symmetries", Danielson y Lanczos se dieron cuenta de que uno podría utilizar la "periodicidad" y aplicar un "dificulto doble" a "doble [N] con sólo un poco más que doble el trabajo", aunque como Gauss no analizaron que esto llevó a O()Nlog⁡ ⁡ N){textstyle O(Nlog N)} escalando.

James Cooley y John Tukey redescubrieron independientemente estos algoritmos anteriores y publicaron un FFT más general en 1965 que es aplicable cuando N es composite y no necesariamente un poder de 2, así como analizar el O()Nlog⁡ ⁡ N){textstyle O(Nlog N)} escalando. Tukey surgió de la idea durante una reunión del Comité Asesor Científico del Presidente Kennedy, donde un tema de discusión implicaba la detección de pruebas nucleares por la Unión Soviética estableciendo sensores para rodear el país desde fuera. Para analizar la salida de estos sensores, se necesitaría un algoritmo FFT. En discusión con Tukey, Richard Garwin reconoció la aplicabilidad general del algoritmo no sólo a los problemas de seguridad nacional, sino también a una amplia gama de problemas incluyendo uno de interés inmediato para él, determinando las periodicidades de las orientaciones de la columna en un cristal 3-D de Helium-3. Garwin dio la idea de Tukey a Cooley (ambos trabajaban en los laboratorios de Watson de IBM) para su implementación. Cooley y Tukey publicaron el periódico en un tiempo relativamente corto de seis meses. Como Tukey no funcionó en IBM, la patentabilidad de la idea fue dudada y el algoritmo entró en el dominio público, que, a través de la revolución informática de la próxima década, hizo FFT uno de los algoritmos indispensables en el procesamiento de señales digitales.

Definición

Vamos x0{displaystyle x_{0},..., xN− − 1{displaystyle x_{N-1} ser números complejos. El DFT se define por la fórmula

Xk=.. n=0N− − 1xne− − i2π π kn/Nk=0,...... ,N− − 1,{displaystyle X_{k}=sum ¿Por qué? Kn/N}qquad k=0,ldotsN-1,}

Donde ei2π π /N{displaystyle e^{i2pi} es un primitivo Na raíz de 1.

Evaluar esta definición requiere directamente O()N2){textstyle Oleft(N^{2}right)} operaciones: hay N productos X_k, y cada salida requiere una suma de N términos. Un FFT es cualquier método para calcular los mismos resultados en O()Nlog⁡ ⁡ N){textstyle O(Nlog N)} operaciones. Todos los algoritmos FFT conocidos requieren .. ()Nlog⁡ ⁡ N){textstyle Theta (Nlog N)} operaciones, aunque no hay evidencia conocida de que la menor complejidad es imposible.

Para ilustrar los ahorros de un FFT, considere el recuento de multiplicaciones complejas y adiciones para N=4096{textstyle N=4096} puntos de datos. Evaluar las sumas del DFT implica directamente N2{textstyle N^{2} multiplicaciones complejas y N()N− − 1){textstyle N(N-1)} adiciones complejas, de las cuales O()N){textstyle O(N)} operaciones se pueden salvar eliminando operaciones triviales como multiplicaciones por 1, dejando alrededor de 30 millones de operaciones. En contraste, el algoritmo de radio-2 Cooley–Tukey, para N un poder de 2, puede calcular el mismo resultado con sólo ()N/2)log2⁡ ⁡ ()N){textstyle (N/2)log _{2}(N)} multiplicaciones complejas (de nuevo, ignorando simplificaciones de multiplicaciones por 1 y similar) y Nlog2⁡ ⁡ ()N){textstyle Nlog _{2}(N)} adiciones complejas, en total alrededor de 30.000 operaciones, mil veces menos que con evaluación directa. En la práctica, el rendimiento real en las computadoras modernas suele estar dominado por factores distintos de la velocidad de las operaciones aritméticas y el análisis es un tema complicado (por ejemplo, ver Frigo & Johnson, 2005), pero la mejora general de la O()N2){textstyle Oleft(N^{2}right)} a O()Nlog⁡ ⁡ N){textstyle O(Nlog N)} restos.

Algoritmos

Algoritmo Cooley-Tukey

Por lejos el FFT más utilizado es el algoritmo Cooley-Tukey. Este es un algoritmo de división y conquista que descompone recursivamente un DFT de cualquier tamaño compuesto N=N1N2{textstyle N=N_{1}N_{2} en muchos tamaños DFT más pequeños N1{textstyle N_{1} y N2{textstyle N_{2}, junto con O()N){displaystyle O(N)} multiplicaciones por complejas raíces de la unidad llamadas tradicionalmente factores twiddle (después de Gentleman y Sande, 1966).

Este método (y la idea general de una FFT) fue popularizado por una publicación de Cooley y Tukey en 1965, pero luego se descubrió que esos dos autores habían reinventado de forma independiente un algoritmo conocido por Carl Friedrich Gauss alrededor de 1805 (y posteriormente redescubierta varias veces en formas limitadas).

El uso más conocido del algoritmo Cooley-Tukey es dividir la transformada en dos partes de tamaño N/2 en cada paso y, por lo tanto, está limitado a tamaños de potencia de dos, pero cualquier factorización puede usarse en general (como lo sabían tanto Gauss como Cooley/Tukey). Estos se denominan casos radix-2 y mixed-radix, respectivamente (y otras variantes, como la FFT de raíz dividida, también tienen sus propios nombres). Aunque la idea básica es recursiva, la mayoría de las implementaciones tradicionales reorganizan el algoritmo para evitar la recursividad explícita. Además, debido a que el algoritmo de Cooley-Tukey divide la DFT en DFT más pequeñas, se puede combinar arbitrariamente con cualquier otro algoritmo para la DFT, como los que se describen a continuación.

Otros algoritmos FFT

Existen algoritmos FFT además de Cooley-Tukey.

Para N = N₁N₂ con coprimos N₁ y N₂, se puede usar el algoritmo de factor primo (Good–Thomas) (PFA), basado en el teorema del resto chino, para factorizar la DFT de manera similar a Cooley-Tukey pero sin los factores de giro. El algoritmo de Rader-Brenner (1976) es una factorización similar a Cooley-Tukey pero con factores de giro puramente imaginarios, que reducen las multiplicaciones a costa de aumentar las adiciones y reducir la estabilidad numérica; más tarde fue reemplazada por la variante de raíz dividida de Cooley-Tukey (que logra el mismo conteo de multiplicación pero con menos adiciones y sin sacrificar la precisión). Los algoritmos que recursivamente factorizan la DFT en operaciones más pequeñas distintas de las DFT incluyen los algoritmos Bruun y QFT. (Los algoritmos de Rader-Brenner y QFT se propusieron para tamaños de potencia de dos, pero es posible que se puedan adaptar a N compuestos generales. El algoritmo de Bruun se aplica a compuestos arbitrarios pares tamaños.) El algoritmo de Bruun, en particular, se basa en interpretar la FFT como una factorización recursiva del polinomio z^N − 1, aquí en polinomios de coeficiente real de la forma z^M − 1 y z^2M + az^M + 1.

Otro punto de vista polinomial es explotado por el algoritmo Winograd FFT, que factoriza z^N − 1 en polinomios ciclotómicos, que a menudo tienen coeficientes de 1, 0 o −1 y, por lo tanto, requieren pocas multiplicaciones (si las hay), por lo que Winograd se puede usar para obtener FFT de multiplicación mínima y, a menudo, se usa para encontrar algoritmos eficientes para factores pequeños. De hecho, Winograd demostró que la DFT se puede calcular solo con O(N) multiplicaciones irracionales, lo que lleva a un límite inferior alcanzable comprobado en el número de multiplicaciones para tamaños de potencia de dos; desafortunadamente, esto tiene el costo de muchas más adiciones, una compensación que ya no es favorable en los procesadores modernos con multiplicadores de hardware. En particular, Winograd también utiliza el PFA, así como un algoritmo de Rader para FFT de tamaños principales.

El algoritmo de Rader, que explota la existencia de un generador para el grupo multiplicativo módulo primo N, expresa una DFT de tamaño primo N como una convolución cíclica de (compuesto) tamaño N − 1, que luego se puede calcular mediante un par de FFT ordinarias a través del teorema de convolución (aunque Winograd usa otros métodos de convolución). Otra FFT de tamaño primo se debe a L. I. Bluestein y, a veces, se la denomina algoritmo chirp-z; también vuelve a expresar una DFT como una convolución, pero esta vez del mismo tamaño (que puede ser rellenado con ceros a una potencia de dos y evaluado por radix-2 Cooley-Tukey FFT, por ejemplo), a través de la identidad

nk=− − ()k− − n)22+n22+k22.{displaystyle nk=-{ { k-n}{2}{2}}+{frac {n^{2}{2}}{2}}}+{frac}}{frac}}}{f}}{f}}}{f}} {f}}} {k^{2}{2}}}}

La transformada rápida de Fourier hexagonal (HFFT) tiene como objetivo calcular una FFT eficiente para los datos muestreados hexagonalmente mediante el uso de un nuevo esquema de direccionamiento para cuadrículas hexagonales, llamado Array Set Addressing (ASA).

Algoritmos FFT especializados para datos reales o simétricos

En muchas aplicaciones, los datos de entrada para la DFT son puramente reales, en cuyo caso las salidas satisfacen la simetría

XN− − k=XkAlternativa Alternativa {displaystyle ¿Qué?

Se han diseñado algoritmos FFT eficientes para esta situación (ver, por ejemplo, Sorensen, 1987). Un enfoque consiste en tomar un algoritmo ordinario (por ejemplo, Cooley-Tukey) y eliminar las partes redundantes del cálculo, ahorrando aproximadamente un factor de dos en tiempo y memoria. Alternativamente, es posible expresar una DFT de entrada real de longitud par como una DFT compleja de la mitad de la longitud (cuyas partes reales e imaginarias son los elementos pares/impares de los datos reales originales), seguidos por O(N) operaciones de posprocesamiento.

Alguna vez se creyó que las DFT de entrada real se podían calcular de manera más eficiente por medio de la transformada discreta de Hartley (DHT), pero posteriormente se argumentó que normalmente se puede encontrar un algoritmo DFT de entrada real (FFT) especializado que requiere menos operaciones que el correspondiente algoritmo DHT (FHT) para el mismo número de entradas. El algoritmo de Bruun (arriba) es otro método que se propuso inicialmente para aprovechar las entradas reales, pero no ha demostrado ser popular.

Hay más especializaciones de FFT para los casos de datos reales que tienen simetría par/impar, en cuyo caso se puede obtener otro factor de aproximadamente dos en el tiempo y la memoria y la DFT se convierte en la(s) transformada(s) discreta(s) de coseno/seno (DCT/DST). En lugar de modificar directamente un algoritmo FFT para estos casos, las DCT/DST también se pueden calcular a través de FFT de datos reales combinados con preprocesamiento y posprocesamiento O(N).

Problemas informáticos

Límites de complejidad y número de operaciones

Una cuestión fundamental de interés teórico de larga data es demostrar límites más bajos en la complejidad y el funcionamiento exacto cuenta de transformaciones rápidas Fourier, y muchos problemas abiertos permanecen. No se prueba rigurosamente si los TFT realmente requieren Ω Ω ()Nlog⁡ ⁡ N){textstyle Omega (Nlog N)} (es decir, orden Nlog⁡ ⁡ N{displaystyle Nlog N} o mayor) operaciones, incluso para el simple caso de potencia de dos tamaños, aunque no se conocen algoritmos con menor complejidad. En particular, el recuento de operaciones aritméticas suele ser el foco de tales preguntas, aunque el rendimiento real en computadoras modernas es determinado por muchos otros factores como la optimización de caché o de tuberías CPU.

Después de la obra de Shmuel Winograd (1978), un apretadoN) límite inferior es conocido por el número de multiplicaciones reales requerido por un FFT. Se puede demostrar que sólo 4N− − 2log22⁡ ⁡ ()N)− − 2log2⁡ ⁡ ()N)− − 4{textstyle 4N-2log ¿Por qué? se requieren multiplicaciones reales irracionales para calcular un DFT de potencia de dos longitudes N=2m{displaystyle N=2^{m}. Además, se conocen algoritmos explícitos que logran este conteo (Heideman & Burrus, 1986; Duhamel, 1990). Sin embargo, estos algoritmos requieren demasiadas adiciones para ser prácticas, al menos en computadoras modernas con multiplicadores de hardware (Duhamel, 1990; Frigo & Johnson, 2005).

No se conoce un límite inferior estricto en el número de adiciones requeridas, aunque se han demostrado límites inferiores bajo algunas suposiciones restrictivas sobre los algoritmos. En 1973, Morgenstern demostró ser Ω Ω ()Nlog⁡ ⁡ N){displaystyle Omega (Nlog N)} inferior ligado a la adición cuenta para algoritmos donde las constantes multiplicativas han ligado magnitudes (que es verdad para la mayoría pero no todos los algoritmos FFT). Pan (1986) demostró ser Ω Ω ()Nlog⁡ ⁡ N){displaystyle Omega (Nlog N)} menor límite asumiendo un límite en una medida de la "asincrónica" del algoritmo FFT, pero la generalidad de esta suposición no está clara. Para el caso del poder de dos N, Papadimitriou (1979) argumentó que el número Nlog2⁡ ⁡ N{textstyle Nlog _{2}N} de adiciones complejas-número alcanzadas por algoritmos Cooley-Tukey es óptima bajo ciertas suposiciones en el gráfico del algoritmo (sus suposiciones implican, entre otras cosas, que no se explotan las identidades aditivas en las raíces de la unidad). (Este argumento implicaría que al menos 2Nlog2⁡ ⁡ N{textstyle 2Nlog _{2}N} se requieren adiciones reales, aunque esto no es un límite ajustado porque se requieren adiciones adicionales como parte de multiplicaciones complejas-número.) Hasta ahora, ningún algoritmo publicado FFT ha logrado menos que Nlog2⁡ ⁡ N{textstyle Nlog _{2}N} complejo-número adiciones (o su equivalente) para potencia-de-dosN.

Un tercer problema es minimizar el total número de multiplicaciones y adiciones reales, a veces llamadas la "complejidad alérgica" (aunque en este contexto es el conteo exacto y no la complejidad asintotica que se está considerando). De nuevo, no se ha probado ningún límite inferior ajustado. Desde 1968, sin embargo, el recuento publicado más bajo para poder de dos N fue logrado por el algoritmo FFT de split-radix, que requiere 4Nlog2⁡ ⁡ ()N)− − 6N+8{textstyle 4Nlog _{2}(N)-6N+8} multiplicaciones y adiciones reales para N ■ 1. Esto se redujo recientemente ♪ ♪ 349Nlog2⁡ ⁡ N{textstyle sim {frac {34}{9}Nlog _{2}N} (Johnson y Frigo, 2007; Lundy y Van Buskirk, 2007). Un recuento ligeramente mayor (pero aún mejor que el radio de división para N ≥ 256) se demostró ser provablemente óptima N ≤ 512 bajo restricciones adicionales a los posibles algoritmos (flugrafos tipo split-radix con factores multiplicadores de módulos), por reducción a un modulo de satisfiabilidad teorías problema solvable por fuerza bruta (Haynal ' Haynal, 2011).

La mayoría de los intentos de reducir o probar la complejidad de los algoritmos FFT se han centrado en el caso ordinario de datos complejos, porque es el más simple. Sin embargo, las FFT de datos complejos están tan estrechamente relacionadas con los algoritmos para problemas relacionados, como las FFT de datos reales, las transformadas de coseno discretas, las transformadas de Hartley discretas, etc., que cualquier mejora en una de estas conduciría inmediatamente a mejoras en las otras (Duhamel y Vetterli, 1990).

Aproximaciones

Todos los algoritmos FFT discutidos anteriormente calculan la DFT exactamente (es decir, despreciando los errores de punto flotante). Algunas "FFT" sin embargo, se han propuesto algoritmos que calculan la DFT aproximadamente, con un error que puede hacerse arbitrariamente pequeño a expensas de mayores cálculos. Dichos algoritmos intercambian el error de aproximación por una mayor velocidad u otras propiedades. Por ejemplo, un algoritmo FFT aproximado de Edelman et al. (1999) logra requisitos de comunicación más bajos para computación paralela con la ayuda de un método multipolar rápido. Una FFT aproximada basada en ondículas de Guo y Burrus (1996) tiene en cuenta entradas/salidas escasas (localización de tiempo/frecuencia) de manera más eficiente de lo que es posible con una FFT exacta. Otro algoritmo para el cálculo aproximado de un subconjunto de las salidas DFT se debe a Shentov et al. (1995). El algoritmo de Edelman funciona igualmente bien para datos dispersos y no dispersos, ya que se basa en la compresibilidad (deficiencia de rango) de la propia matriz de Fourier en lugar de la compresibilidad (esparcimiento) de los datos. Por el contrario, si los datos son escasos, es decir, si solo K de N los coeficientes de Fourier son distintos de cero, entonces la complejidad se puede reducir a O(Klog(N)log(N/K)), y se ha demostrado que esto conduce a aceleraciones prácticas en comparación con un ordinario FFT para N/K > 32 en un ejemplo de N grande (N = 2²²) usando un algoritmo aproximado probabilístico (que estima el mayor K coeficientes con varios decimales).

Precisión

Los algoritmos FFT tienen errores cuando se utiliza aritmética de punto flotante de precisión finita, pero estos errores son generalmente bastante pequeños; la mayoría de algoritmos FFT, por ejemplo. Cooley-Tukey, tiene excelentes propiedades numéricas como consecuencia de la estructura de summación de par en par de los algoritmos. El límite superior en el error relativo para el algoritmo Cooley-Tukey es O()ε ε log⁡ ⁡ N){textstyle O(epsilon log N)}, en comparación con O()ε ε N3/2){textstyle O(epsilon N^{3/2})} para la ingenua fórmula DFT, donde ε es la máquina de punto flotante de precisión relativa. De hecho, los errores de la raíz media cuadrado (rms) son mucho mejores que estos límites superiores, siendo sólo O()ε ε log⁡ ⁡ N){textstyle O(epsilon {sqrt {log N}}} para Cooley-Tukey y O()ε ε N){textstyle O(epsilon {fn}}} para el ingenuo DFT (Schatzman, 1996). Estos resultados, sin embargo, son muy sensibles a la exactitud de los factores twiddle utilizados en el FFT (es decir, los valores de función trigonométrica), y no es inusual que las implementaciones FFT incautantes tengan mucha peor precisión, por ejemplo si usan fórmulas de recurrencia trigonométrica inexactas. Algunos FFT que no son Cooley–Tukey, como el algoritmo Rader–Brenner, son intrínsecamente menos estables.

En aritmética de punto fijo, los errores de precisión finita acumulados por algoritmos FFT son peores, con errores rms creciendo como O()N){textstyle O({sqrt {N})} para el algoritmo Cooley-Tukey (Welch, 1969). Alcanzar esta precisión requiere una atención cuidadosa al escalar para minimizar la pérdida de precisión, y los algoritmos FFT de punto fijo implican el rescaling en cada etapa intermedia de las descomposiciones como Cooley–Tukey.

Para verificar la corrección de una implementación FFT, se pueden obtener garantías rigurosas O()Nlog⁡ ⁡ N){textstyle O(Nlog N)} tiempo por un procedimiento simple que comprueba la linearidad, respuesta a impulsos y propiedades de tiempo de cambio en los insumos aleatorios (Ergün, 1995).

FFT multidimensionales

Como se define en el artículo DFT multidimensional, el DFT multidimensional

Xk=.. n=0N− − 1e− − 2π π ik⋅ ⋅ ()n/N)xn{displaystyle X_{mathbf {k}=sum _{mathbf {n} ♪♪♪ {N} -1}e^{-2pi} imathbf {k} cdot (mathbf {n} /mathbf {N}x_{mathbf {n}

transforma un array x_n con una d- vector dimensional de índices n=()n1,...... ,nd){textstyle mathbf {n} =left(n_{1},ldotsn_{d}right)} por un conjunto de d sumas anidadas (sobre nj=0...... Nj− − 1{textstyle n_{j}=0ldots N_{j}-1} para cada uno j), donde la división n/N, definido como n/N=()n1/N1,...... ,nd/Nd){textstyle mathbf {n} /mathbf {N} =left(n_{1}/N_{1},ldotsn_{d}/N_{d}right)}, se realiza elemento-sabio. Equivalentemente, es la composición de una secuencia de d conjuntos de DFTs unidimensionales, realizados a lo largo de una dimensión a la vez (en cualquier orden).

Este punto de vista compositivo proporciona inmediatamente el algoritmo DFT multidimensional más simple y común, conocido como el fila-column algoritmo (después del caso bidimensional, abajo). Es decir, uno simplemente realiza una secuencia de d FFT de una dimensión (por cualquiera de los algoritmos anteriores): primero se transforma a lo largo de los n₁ dimensión, entonces a lo largo de la n₂ dimensión, y así sucesivamente (o en realidad, cualquier orden funciona). Este método se muestra fácilmente con el habitual O()Nlog⁡ ⁡ N){textstyle O(Nlog N)} complejidad, donde N=N1⋅ ⋅ N2⋅ ⋅ ⋯ ⋯ ⋅ ⋅ Nd{textstyle N=N_{1}cdot N_{2}cdot cdots cdot N_{d} es el número total de puntos de datos transformados. En particular, hay N/N₁ transformaciones de tamaño N₁, etcétera, por lo que la complejidad de la secuencia de FFTs es:

NN1O()N1log⁡ ⁡ N1)+⋯ ⋯ +NNdO()Ndlog⁡ ⁡ Nd)=O()N[log⁡ ⁡ N1+⋯ ⋯ +log⁡ ⁡ Nd])=O()Nlog⁡ ⁡ N).{displaystyle {begin{aligned} {N}{N_{1}}O(N_{1}log N_{1})+cdots +{frac {N}{N_{d}}O(N_{d}log N_{d}[6pt]={}Ohleft(Nleft[log N_{1}+cdots +log N_{d}right)=O(Nlog N).end{aligned}}}}}} {N}{N}{n}{d}}}}}}{n}}}}}{n}}{n}}}}{n}}}}} {n}}}}}}}}}}} {n}} {n}} {n}}}}}}}}}}}}}}}}}}}}}}}}}}} {nn}}}}}}}}}}}}}}nnnnnnnnnnn}}}}}n}nnnnnnnnnnnnnn

En dos dimensiones, la x_k puede ser visto como n1× × n2{displaystyle n_{1}times No. matriz, y este algoritmo corresponde a la primera realización de la FFT de todas las filas (resp. columnas), agrupando las filas transformadas resultantes (resp. columnas) juntos como otra n1× × n2{displaystyle n_{1}times No. matriz, y luego realizar el FFT en cada una de las columnas (resp. filas) de esta segunda matriz, y agrupar los resultados en la matriz de resultado final.

En más de dos dimensiones, a menudo es ventajoso para la localidad de cache agrupar las dimensiones recursivamente. Por ejemplo, un FFT tridimensional podría realizar primero FFT bidimensional de cada "slice" plano para cada uno fijo n₁, y luego realizar los FFT de una dimensión a lo largo de los n₁ dirección. Más generalmente, un algoritmo caché-oblivioso asintomáticamente óptimo consiste en dividir las dimensiones recursivamente en dos grupos ()n1,...... ,nd/2){textstyle (n_{1},ldotsn_{d/2}} y ()nd/2+1,...... ,nd){textstyle (n_{d/2+1},ldotsn_{d}} que se transforman recursivamente (redondeando si d (ver Frigo y Johnson, 2005). Sin embargo, esto sigue siendo una variación directa del algoritmo de columna fila que en última instancia requiere sólo un algoritmo FFT de una dimensión como el caso base, y todavía tiene O(NlogN) complejidad. Otra variación es realizar transposiciones de matriz entre la transformación de las dimensiones posteriores, de modo que las transformaciones funcionen con datos contiguos; esto es especialmente importante para situaciones de memoria fuera de núcleo y distribuidas donde el acceso a datos no contiguos es extremadamente lento.

Hay otros algoritmos FFT multidimensionales que son distintos del algoritmo de columna de fila, aunque todos tienen O()Nlog⁡ ⁡ N){textstyle O(Nlog N)} complejidad. Tal vez el más simple FFT no-hace es el algoritmo FFT vector-radix, que es una generalización del algoritmo ordinario Cooley-Tukey donde se divide las dimensiones transformadoras por un vector r=()r1,r2,...... ,rd){textstyle mathbf {r} =left(r_{1},r_{2},ldotsr_{d}right)} de radios a cada paso. (Esto también puede tener beneficios de caché.) El caso más simple de vector-radix es donde todos los radios son iguales (por ejemplo, vector-radix-2 divides Todos de las dimensiones por dos), pero esto no es necesario. Vector radix con solo un único radio no-unidad a la vez, es decir. r=()1,...... ,1,r,1,...... ,1){textstyle mathbf {r} =left(1,ldots1,r,1,ldots1right)}, es esencialmente un algoritmo de columna de fila. Otros métodos, más complicados, incluyen algoritmos de transformación polinomio debido a Nussbaumer (1977), que ven la transformación en términos de convoluciones y productos polinomios. Véase Duhamel y Vetterli (1990) para más información y referencias.

Otras generalizaciones

An O()N5/2log⁡ ⁡ N){textstyle O(N^{5/2}log N)} generalización a armónicos esféricos en la esfera S² con N² nodos fue descrito por Mohlenkamp, junto con un algoritmo conjeturado (pero no probado) para tener O()N2log2⁡ ⁡ ()N)){textstyle O(N^{2}log ^{2}(N)} complejidad; Mohlenkamp también proporciona una implementación en la biblioteca libftsh. Un algoritmo esférico-armónico con O()N2log⁡ ⁡ N){textstyle O(N^{2}log N)}La complejidad es descrita por Rokhlin y Tygert.

El algoritmo de plegado rápido es análogo a la FFT, excepto que opera en una serie de formas de onda agrupadas en lugar de una serie de valores escalares reales o complejos. La rotación (que en la FFT es la multiplicación por un fasor complejo) es un desplazamiento circular de la forma de onda del componente.

Varios grupos también han publicado "FFT" algoritmos para datos no equiespaciados, como se revisa en Potts et al. (2001). Dichos algoritmos no calculan estrictamente la DFT (que solo se define para datos equiespaciados), sino alguna aproximación de la misma (una transformada de Fourier discreta no uniforme, o NDFT, que a menudo se calcula solo de forma aproximada). De manera más general, existen varios otros métodos de estimación espectral.

Aplicaciones

La FFT se utiliza en software de grabación digital, muestreo, síntesis aditiva y corrección de tono.

La importancia de la FFT se deriva del hecho de que ha hecho que trabajar en el dominio de la frecuencia sea igual de factible computacionalmente que trabajar en el dominio temporal o espacial. Algunas de las aplicaciones importantes de la FFT incluyen:

• algoritmos de multiplicación de gran entero rápido y multiplicación polinomio,
• multiplicación eficiente de matriz-vector para Toeplitz, circulante y otras matrices estructuradas,
• Filtrar algoritmos (ver métodos superlap–add y overlap–save),
• algoritmos rápidos para transformaciones discretas de cosina o sine (por ejemplo, DCT rápido utilizado para codificación y decodificación JPEG y MPEG/MP3),
• aproximación rápida Chebyshev,
• resolver ecuaciones de diferencia,
• computación de distribuciones isotópicas.
• modulación y desmodulación de símbolos de datos complejos utilizando la división de frecuencias ortogonales multiplexing (OFDM) para 5G, LTE, Wi-Fi, DSL y otros sistemas de comunicación modernos.

Áreas de investigación

Grandes FFT

Con la explosión de grandes datos en campos como la astronomía, la necesidad de 512K FFTs ha surgido para ciertos cálculos interferometría. Los datos recogidos por proyectos como WMAP y LIGO requieren FFTs de decenas de miles de millones de puntos. Como este tamaño no encaja en la memoria principal, por lo que los FFTs fuera de núcleo son un área activa de investigación.

FFTs aproximados

Para aplicaciones como la RMN, es necesario calcular los DFTs para puntos de rejilla no uniformemente espaciados y/o frecuencias. Los enfoques basados en multipolo pueden calcular cantidades aproximadas con factor de aumento del tiempo de ejecución.

Grupo FFT

El FFT también puede ser explicado e interpretado usando la teoría de la representación grupal permitiendo una mayor generalización. Una función en cualquier grupo compacto, incluido el no cíclico, tiene una expansión en términos de una base de elementos de matriz irreducibles. Sigue siendo un área activa de investigación para encontrar un algoritmo eficiente para realizar este cambio de base. Aplicaciones incluyendo una eficiente expansión armónica esférica, analizando ciertos procesos de Markov, robótica etc.

FFT cuántica

El algoritmo rápido de Shor para la factorización de entero en un equipo cuántico tiene una subrutina para calcular DFT de un vector binario. Esto se implementa como secuencia de puertas cuánticas de 1 o 2 bits ahora conocidas como FFT cuántica, que es efectivamente el FFT Cooley-Tukey realizado como una factorización particular de la matriz Fourier. Actualmente se está explorando la extensión de estas ideas.

Referencia de idioma