13.2: Conclusión

Última actualización
Guardar como PDF

Page ID: 87038

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Este libro ha desarrollado una clase de algoritmos eficientes basados en el mapeo de índices y álgebra polinómica. Esto proporciona un marco a partir del cual se pueden derivar la FFT de Cooley-Tukey, la FFT de base dividida, el PFA y el WFTA. Incluso los programas que implementan estos algoritmos pueden tener una estructura similar. Los teoremas de Winograd se presentaron y demostraron ser muy poderosos tanto en algoritmos derivados como en evaluarlos. La FFT de radio 2 simple proporciona un medio compacto y elegante para calcular de manera eficiente la DFT. Si se permite alguna elaboración, se puede tener una mejora significativa de la FFT de base dividida, la FFT de radix-4 o la PFA. Si las multiplicaciones son caras, el WFTA requiere lo menos de todo.

Se describieron varios métodos para transformar datos reales que son más eficientes que el uso directo de una FFT compleja. Una FFT compleja se puede utilizar para datos reales creando artificialmente una entrada compleja a partir de dos secciones de entrada real. Un método alternativo y ligeramente más eficiente es construir una FFT especial que utilice las simetrías en cada etapa.

A medida que las computadoras pasan a multiprocesadores y multinúcleo, escribir y mantener programas eficientes se vuelve cada vez más difícil. La forma altamente estructurada de FFT permite la generación automática de programas muy eficientes que se adaptan específicamente a un DSP o arquitectura de computadora en particular.

Para la convolución de alta velocidad, el uso tradicional de FFT o PFA con bloqueo es probablemente el método más rápido, aunque las transformaciones rectangulares, la aritmética distribuida o las transformaciones teóricas numéricas pueden tener futuro con hardware VLSI especial.

Las ideas presentadas en estas notas también pueden aplicarse al cálculo de la transformada discreta de Hartley, la transformada discreta del coseno y a las transformaciones teóricas numéricas.

Hay muchas áreas para futuras investigaciones. La relación del hardware con los algoritmos, el uso adecuado de múltiples procesadores, el diseño y uso adecuados de los procesadores de matriz y procesadores vectoriales son todos abiertos. Todavía quedan muchas preguntas sin respuesta en algoritmos multidimensionales donde una simple extensión de métodos unidimensionales no será suficiente.

Colaborador

ContribeeBurrus