11.2: Diversos enfoques para el desarrollo de métodos especiales
- Última actualización
-
-
Guardar como PDF
Hay dos métodos que utilizan una FFT compleja de una manera especial para aumentar la eficiencia. El primer método utiliza una FFT compleja Length-N para calcular dos FFT reales de longitud-N poniendo las dos secuencias de datos reales en las partes real y las imaginarias de la entrada a una FFT compleja. Debido a que las transformaciones de datos reales tienen partes reales pares y partes imaginarias impares, es posible separar las transformaciones de las dos entradas con adiciones adicionales 2N-4. Este método requiere, sin embargo, que dos entradas estén disponibles al mismo tiempo.
El segundo método utiliza el hecho de que la última etapa de una FFT de diezmation-in-time radix-2 combina dos transformadas independientes de longitud N/2 para calcular una transformada de longitud-N. Si los datos son reales, las dos transformaciones de media longitud se calculan mediante el método descrito anteriormente y se realiza la última etapa para calcular la longitud total-N FFT de los datos reales. Cabe señalar que la FFT de media longitud no tiene que ser calculada por una FFT de radio 2. De hecho, debe calcularse mediante el algoritmo de datos complejos más eficiente posible, como el SRFFT o el PFA. La separación de las dos transformaciones de media longitud y el cálculo de la última etapa requiere multiplicaciones\(N-6\) reales y(5/2)N-6(5/2)N-6“role="presentation” style="position:relative;” tabindex="0"> adiciones \((5/2)N-6\)reales.
Es posible derivar algoritmos de datos reales más eficientes directamente en lugar de usar una FFT compleja. La idea básica es de Berland y Sande que, en cada etapa, utiliza las simetrías de una base constante Cooley-Tukey FFT para minimizar la aritmética y el almacenamiento. En la derivación habitual de la FFT radix-2, la transformada Length-N se escribe como la combinación de la Length-N/2 DFT de los datos indexados pares y la Length-N/2 DFT de los datos indexados impares. Si la entrada a cada DFT de media longitud es real, la salida tendrá simetría hermitiana. De ahí que la salida de cada etapa se pueda organizar de manera que los resultados de esa etapa almacenen la DFT compleja con la parte real ubicada donde habría ido la mitad de la DFT, y la parte imaginaria ubicada donde habría ido el conjugado. Esto elimina la mayoría de los cálculos redundantes y el almacenamiento pero complica ligeramente el direccionamiento. La estructura de mariposa resultante para este algoritmo se asemeja a la de la transformada rápida de Hartley. El algoritmo completo tiene la mitad del número de multiplicaciones y N-2 menos de la mitad de las adiciones del complejo básico FFT. La aplicación de este enfoque a la FFT de base dividida da un algoritmo particularmente interesante.
También se pueden desarrollar versiones especiales tanto del PFA como del WFTA para datos reales. Debido a que las operaciones en las etapas del PFA pueden ser conmutadas, es posible mover la combinación de la transformación de la parte real de la entrada y la parte imaginaria a la última etapa. Debido a que la parte imaginaria de la entrada es cero, la mitad del algoritmo simplemente se omite. Esto da como resultado que el número de multiplicaciones requeridas para la transformación real sea exactamente la mitad del requerido para datos complejos y el número de adiciones sea aproximadamente N menos de la mitad que el requerido para el caso complejo porque agregar un número real puro a un número imaginario puro no requiere un número real real adición. Desafortunadamente, la indexación y transferencia de datos se vuelve algo más complicada. Un enfoque similar se puede tomar con el WFTA.
