Datos con relleno cero para la FFT

Question

Si tomo una transformada discreta de Fourier de $\{ c_1, c_2, \ldots, c_n\}$ donde $n$ es primordial, estoy bastante limitado en cuanto a los algoritmos FFT disponibles y su rendimiento. Además, tener algoritmos FFT de radios mixtos et Los algoritmos de FFT de longitud primaria, más el código necesario para determinar cuál utilizar, aumentan el tamaño de mi código, que es un factor limitante.

Supongamos que $n$ es primo y decido, en cambio, tomar la transformada discreta de Fourier de $\{ c_1, c_2, \ldots, c_n, 0\}$ por lo que, ahora, la longitud de los datos ya no es primordial. Sé que la "imagen" que obtengo será más suave en comparación con la verdadera DFT de los datos originales.

¿Hay alguna manera de poner a cero los datos originales, realizar una FFT y luego invertir los efectos de la puesta a cero? Con esto quiero decir que la longitud de la lista de salida debería ser $n$ no $n + 1$ . No espero obtener precisamente el mismo resultado del $n + 1$ FFT rellenada como en el caso del original $O(n^2)$ DFT. Tengo entendido que es prácticamente imposible revertir el efecto de alisado del relleno.

---

Resumen: Puedo poner a cero mis datos para que tengan una longitud no-prima, pero entonces el resultado de mi FFT tiene la longitud incorrecta, y los valores de los índices no coinciden con la verdadera DFT. No puedo simplemente dejar caer el último elemento del resultado de mi FFT, necesito algo más "complicado". ¿Qué post-procesamiento puedo hacer a mis datos rellenados con cero para que se parezcan más a la DFT original, y tengan la misma longitud?

Answer 1

En realidad, al rellenar con ceros no se suaviza ni se pierde información.

La FFT original y la "FFT acolchada" sólo corresponden a muestreo la misma (verdadera) DTFT $X(\omega)$ en diferentes puntos; pero ambos muestreos son suficientes para recuperar (en teoría) la verdadera $X(\omega)$ .

Permítanme cambiar un poco la notación para ser más coherente con el uso común.

Dejemos que $N$ sea la longitud de la señal original $x_n=x_0, x_1 \cdots x_{N-1}$ y que $X(\omega)$ sea su DTFT , $X(\omega)= \sum x_n \exp(-i \omega n)$ Dejemos que $y_n$ sea la misma señal derecha rellenada con ceros, de modo que su longitud sea $N_p>N$ .

Está claro que su DTFT es el mismo.

Sin embargo, la DFT (lo que calcula la FFT) es diferente. Esto se debe a que corresponden al muestreo $X(\omega)$ en diferentes puntos. Si $X_k$ ( $k=0,1, \cdots N-1$ ) es el $k$ componente del DTF de $x_n$ entonces la correspondencia es

$$ X_k \leftrightarrow X(\omega)\biggl|_{\omega=2\pi k /N}$$

Son diferentes, pero de una se puede obtener la otra. Esto es bastante obvio si se piensa que cualquier DFT -acolchada o no- es invertible, por lo que a partir de la FFT acolchada se puede recuperar la señal original, y luego se puede recuperar la FFT sin acolchar.

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi n k /N} = \sum_{n=0}^{N-1} \frac{1}{N_p} \sum_{j=0}^{N_p} Y_j e^{i 2 \pi n j /N_p} e^{-i 2 \pi n k /N}$$

Esto es una especie de interpolación trigonométrica. Pero esto seguramente no es práctico, en su escenario: en lugar de hacer esto, usted realizaría directamente una DFT simple en los datos originales sin acolchado.

Una opción más práctica (pero no exacta) sería hacer una interpolación más sencilla. Supongo que una interpolación cuadrática podría funcionar decentemente. Pero no enchufes a ciegas el $Y_k$ en alguna rutina de interpolación, debe tener en cuenta la naturaleza de una DFT o una señal real (preservar la propiedad hermética), y respetaría la componente cero como su verdadero "origen", por lo que se preserva estrictamente.