¿Por qué FFT produce números complejos en lugar de números reales?

Todas las implementaciones de FFT con las que nos hemos encontrado dan como resultado valores complejos (con partes reales e imaginarias), incluso si la entrada al algoritmo fue un conjunto discreto de números reales (enteros).

¿No es posible representar el dominio de la frecuencia en términos de números reales únicamente?

La FFT es fundamentalmente un cambio de base. La base en la que la FFT cambia su señal original es un conjunto de ondas sinusoidales. Para que esa base describa todas las posibles entradas, debe poder representar tanto la fase como la amplitud; la fase se representa mediante números complejos.

Por ejemplo, suponga que FFT una señal que contiene solo una onda sinusoidal. Dependiendo de la fase, es posible que obtenga un resultado de FFT completamente real. Pero si cambia la fase de su entrada unos pocos grados, ¿de qué otra manera puede la salida FFT representar esa entrada?

editar: Esta es una explicación algo vaga, pero solo estoy tratando de motivar la intuición.

La FFT le proporciona amplitud y fase. La amplitud se codifica como la magnitud del número complejo (sqrt (x ^ 2 + y ^ 2)) mientras que la fase se codifica como el ángulo (atan2 (y, x)). Para tener un resultado estrictamente real de la FFT, la señal entrante debe tener simetría par (es decir, x [n] = conj (x [Nn])).

Si lo único que le importa es la intensidad, la magnitud del número complejo es suficiente para el análisis.

Sí, es posible representar los resultados del dominio de frecuencia de FFT de una entrada estrictamente real utilizando solo números reales.

Esos números complejos en el resultado de FFT son simplemente 2 números reales, que son necesarios para darle las coordenadas 2D de un vector de resultado que tiene una longitud y un ángulo de dirección (o magnitud y fase). Y cada componente de frecuencia en el resultado de FFT puede tener una amplitud y una fase únicas (en relación con algún punto de la apertura de FFT).

Un número real por sí solo no puede representar tanto la magnitud como la fase. Si tira la información de fase, eso fácilmente podría distorsionar masivamente la señal si intenta recrearla usando un iFFT (y la señal no es simétrica). Entonces, un resultado FFT completo requiere 2 números reales por contenedor FFT. Estos 2 números reales están agrupados en algunas FFT en un tipo de datos complejo por convención común, pero el resultado de FFT podría fácilmente (y algunas FFT lo hacen) simplemente producir 2 vectores reales (uno para coordenadas coseno y otro para coordenadas seno).

También hay rutinas de FFT que producen magnitud y fase directamente, pero se ejecutan más lentamente que las FFT que producen un resultado vectorial complejo (o dos reales). También existen rutinas de FFT que calculan solo la magnitud y simplemente descartan la información de fase, pero generalmente no se ejecutan más rápido que permitiéndote hacerlo tú mismo después de una FFT más general. Tal vez le ahorren a un codificador algunas líneas de código a costa de no ser invertibles. Pero muchas bibliotecas no se molestan en incluir estas formas más lentas y menos generales de FFT, y simplemente dejan que el codificador convierta o ignore lo que necesitan o no necesitan.

Además, muchos consideran que las matemáticas involucradas son mucho más elegantes usando aritmética compleja (donde, para una entrada estrictamente real, la correlación del coseno o el componente par de un resultado de FFT se coloca en el componente real, y la correlación sinusoidal o componente impar del El resultado de FFT se coloca en el componente imaginario de un número complejo).

(Agregado :) Y, como otra opción más, puede considerar los dos componentes de cada contenedor de resultados FFT, en lugar de componentes reales e imaginarios, como componentes pares e impares, ambos reales.

Si su coeficiente FFT para una frecuencia dada fes x + i y, puede verlo xcomo el coeficiente de un coseno a esa frecuencia, mientras que el yes el coeficiente del seno. Si agrega estas dos ondas para una frecuencia particular, obtendrá una onda desfasada en esa frecuencia; la magnitud de esta onda es sqrt(x*x + y*y)igual a la magnitud del coeficiente complejo.

La transformada de coseno discreta (DCT) es un pariente de la transformada de Fourier que produce todos los coeficientes reales. Muchos algoritmos de compresión de imagen / vídeo utilizan una DCT bidimensional.

1. La transformada discreta de Fourier es fundamentalmente una transformación de un vector de números complejos en el "dominio del tiempo" a un vector de números complejos en el "dominio de la frecuencia" (yo uso comillas porque si aplica los factores de escala correctos, la DFT es propia inverso). Si las entradas son reales, entonces se puede realizar dos DFT a la vez: Tome los vectores de entrada X y Y y calcular F ( x  +  i  y ). Olvidé cómo se separa la DFT después, pero sospecho que se trata de simetría y conjugados complejos.

2. El tipo de transformada de coseno discreta le permite representar el "dominio de frecuencia" con los reales, y es común en los algoritmos de compresión con pérdida (JPEG, MP3). Lo sorprendente (para mí) es que funciona a pesar de que parece descartar información de fase, pero esto también parece hacerla menos útil para la mayoría de los propósitos de procesamiento de señales (no conozco una manera fácil de hacer convolución / correlación con un DCT).

Probablemente me equivoqué en algunos detalles;)