En esta sección se examinarán las reducciones en aritmética en la DFT que resulten únicamente del mapeo de índices. En algoritmos prácticos siempre se combinan varios métodos, pero es útil para comprender los efectos de un método particular estudiarlo solo.
La forma más general de una DFT bidimensional desacoplada viene dada por
\[X(k_{1},k_{2})=\sum_{n_{2}=0}^{N_{2}-1}\left \{ \sum_{n_{1}=0}^{N_{1}-1} x(n_{1},n_{2})f_{1}(n_{1},n_{2},k_{1})\right \}f_{2}(n_{2},k_{1},k_{2}) \nonumber \]
donde la suma interna calcula la\(N_2\) longitud-\(N_1\) DFT y, si es para un mapa de tipo dos, los efectos de los TFs. Si el número de operaciones aritméticas para una longitud-\(N\) DFT se denota por\(F(N)\), el número de operaciones para esta suma interna es
F=N2F(N1)F=N2F(N1)“role="presentación” style="position:relative;” tabindex="0"> \[F=N_{2}F(N_{1}) \nonumber \]
La suma externa que da\(N_1\) longitud-\(N_2\) DFT requiere\(N_1F(N_2)\) operaciones. El número total de operaciones aritméticas es entonces
\[F=N_{2}F(N_{1})+N_{1}F(N_{2}) \nonumber \]
La primera pregunta a considerar es para una longitud fija\(N\), cuál es la relación óptima de\(N_1\) y\(N_2\) en el sentido de minimizar la cantidad requerida de aritmética. Para responder a esta pregunta,\(N_1\) y\(N_2\) se supone temporalmente que son variables reales en lugar de enteros. Si se supone que las\(N_i\) DFT de longitud corta en la ecuación y cualquier multiplicación de TF requieren\(N_i^2\) operaciones, es decir
\[F(N_{i})=N_{i}^{2} \nonumber \]
Por lo tanto, las eficiencias resultantes del mapeo de índices con la DFT se convierten
\[F=N_{2}N_{1}^{2}+N_{1}N_{2}^{2}=N(N_{1}+N_{2})=N(N_{1}+NN_{1}^{-1}) \nonumber \]
Para encontrar el mínimo de\(F\) over\(N_1\), la derivada de\(F\) con respecto a\(N_1\) se establece en cero (asumiendo temporalmente que las variables sean continuas) y el resultado requiere\(N_{1}=N_{2}\)
\[\frac{\mathrm{d} F}{\mathrm{d} N_{1}}=0\; \; \; \; \Rightarrow N_{1}=N_{2} \nonumber \]
Este resultado también se ve fácilmente desde la simetría de\(N_1\), y en\(N_2\), en\(N=N_1N_2\). Si se utiliza un modelo más general de la complejidad aritmética de los DFT cortos, se obtiene el mismo resultado, pero se debe hacer un examen más detallado para asegurar que\(N_{1}=N_{2}\) es un mínimo global.
N1=N2N1=N2“role="presentation” style="position:relative;” tabindex="0"> Si solo se van a considerar los efectos del mapeo de índices, entonces se usa el\(F(N)=N^2\) modelo y la ecuación establece que los dos factores deben ser iguales. Si hay\(M\) factores, un razonamiento similar muestra que todos los\(M\) factores deben ser iguales. Para la secuencia de longitud
F(N)=N2F(N)=N2“role="presentación” style="position:relative;” tabindex="0"> \[N=R^{M} \nonumber \]
ahora hay\(M\) longitud-\(R\) DFT y, dado que los factores son todos iguales, el mapa índice debe ser de tipo dos. Esto significa que debe haber factores de twiddle.
Para simplificar el análisis, sólo se considerará el número de multiplicaciones. Si el número de multiplicaciones para una longitud-\(R\) DFT es\(F(R)\), entonces la fórmula para los recuentos de operación en la ecuación generaliza a
\[F=N\sum_{i=1}^{M}\frac{F(N_{i})}{N_{i}}=NM\frac{F(R)}{R} \nonumber \]
para\(N_i=R\)
\[F=N\ln R(N)\frac{F(R)}{R}=(N\ln N)\frac{F(R)}{R\ln R} \nonumber \]
Esta es una fórmula muy importante la cual fue derivada por Cooley y Tukey en su famoso artículo sobre la FFT. Afirma que para un dado\(R\) que se denomina base, el número de multiplicaciones (y adiciones) es proporcional a\(N\ln N\). También muestra la relación con el valor de la base,\(R\).
Para tener una idea de la “mejor” base, se supone que el número de multiplicaciones para calcular una longitud-\(R\) DFT es
\[F(R)=R^{x} \nonumber \]
Si esto se usa con la ecuación, se\(R\) puede encontrar el óptimo.
\[\frac{\mathrm{d} F}{\mathrm{d} R}=0\; \; \; \; \Rightarrow R=e^{\frac{1}{(x-1)}} \nonumber \]
Para\(x=2\) esto da\(R=e\), siendo el entero más cercano tres.
El resultado de este análisis establece que si no se utilizan otros métodos de ahorro aritmético que no sean el mapeo de índices, y si las\(R\) DFT de longitud más TF requierenF=R2F=R2“role="presentation” style="position:relative;” tabindex="0"> \(F=R^{2}\)multiplicaciones, el algoritmo óptimo requiere\(F=3N\log_{3}N\) multiplicaciones para una longitud\(N=3^{M}\) DFT. Compare esto con\(N^2\) para un cálculo directo y la mejora es obvia.
Si bien este es un resultado interesante del análisis de los efectos del mapeo de índices por sí solo, en la práctica, el mapeo de índices casi siempre se usa junto con algoritmos especiales para las\(N_i\) DFT de longitud corta en la ecuación. Por ejemplo, si\(R=2\; \text{or}\; 4\), no se requieren multiplicaciones para los DFT cortos. Solo los TFs requieren multiplicaciones. Winograd (ver Algoritmos DFT cortos de Winograd) ha derivado algunos algoritmos para DFT cortos que requieren O (N) multiplicaciones. Esto significa queF(Ni)=KNiF(Ni)=KNi“role="presentación” style="position:relative;” tabindex="0">
\[F(N_{i})=KN_{i} \nonumber \]
y el recuento de operaciones\(F\) en “Eficiencias resultantes del mapeo de índices con el DFT” es independiente de\(N_i\). Por lo tanto, la derivada de\(F\) es cero para todos\(N_i\). Obviamente, estos casos particulares deben ser examinados.
