Objetivos de aprendizaje
- Estudiar el algoritmo de factor primo y el algoritmo de transformada de Fourier de Winograd
El algoritmo de factor primo (PFA) y el algoritmo de transformada de Winograd Fourier (WFTA) son métodos para calcular de manera eficiente la DFT que utilizan, y de hecho, dependen del mapa de índices de tipo 1 del Mapeo de Índice Multidimensional. El uso de este mapa índice precedió al trabajo de Cooley y Tukey, pero su potencial no se concretó hasta que se combinó con los cortos algoritmos DFT de Winograd.
La base teórica numérica para la indexación en estos algoritmos puede, al principio, parecer más complicada que en la FFT Cooley-Tukey; sin embargo, si se aborda desde el punto de vista general del mapeo de índices del Mapeo de Índice Multidimensional, es sencillo, y parte de un enfoque común para romper grandes problemas en los más pequeños. El desarrollo en esta sección será paralelo al de El algoritmo de transformada rápida de Fourier Cooley-Tukey.
Los mapas de índices generales de Mapeo de Índice Multidimensional deben satisfacer las condiciones de Tipo 1 que son
\[K_1=aN_2\; \text{and}\; K_2=bN_1\; \text{with}\; (K_1N_1)=(K_2N_2)=1 \nonumber \]
\[K_3=cN_2\; \text{and}\; K_4=dN_1\; \text{with}\; (K_3N_1)=(K_4N_2)=1 \nonumber \]
Los cálculos de filas y columnas en The Index Map están desacoplados por lo que para este caso se encuentran
\[((K_1K_4))_N=((K_2K_3))_N=0 \nonumber \]
Además, para hacer de cada suma corta un DFT,KiKi“role="presentation” style="position:relative;” tabindex="0"> también \(K_i\)debe satisfacer
\[((K_1K_3))_N=N_2\; \text{and}\; ((K_2K_4))_N=N_1 \nonumber \]
Con el fin de tener los valores más pequeños paraKiKi“role="presentation” style="position:relative;” tabindex="0"> \(K_i\), las constantes en la ecuación se eligen para ser
KiKi“role="presentación” style="position:relative;” tabindex="0"> \[a=b=1,\; c=((N_{2}^{-1}))_N,\; d=((N_{1}^{-1}))_N \nonumber \]
que da para los mapas de índice en la ecuación
\[n=((N_2n_1+N_1n_2))_N \nonumber \]
\[k=((K_3k_1+K_4k_2))_N \nonumber \]
El mapa del índice de frecuencia es una forma del teorema del resto chino. Usando estos mapas de índice, el DFT en Mapeo de Índice Multidimensional se convierte en
\[X=\sum_{n_2=0}^{N_2-1}\sum_{n_1=0}^{N_1-1}xW_{N_1}^{n_1k_1}W_{N_2}^{n_2k_2} \nonumber \]
que es una DFT bidimensional pura sin factores de twiddle y las sumaciones se pueden hacer en cualquier orden. Podrían utilizarse otras opciones distintas de la ecuación. Por ejemplo,\(a=b=c=d=1\) provocará que el mapa de índices de entrada y salida sea el mismo y, por lo tanto, no habrá ninguna aleatulación del orden de salida. Las breves sumas en (96), sin embargo, ya no serán DFT cortas.
Una característica importante de los cortos DFT de Winograd descritos en los algoritmos de DFT cortos de Winograd que es útil tanto para el PFA como para el WFTA es el hecho de que las constantes multiplicadoras en los algoritmos de DFT cortos de Winograd son reales o imaginarias, nunca un número complejo general. Por esa razón, la multiplicación por datos complejos requiere sólo dos multiplicaciones reales, no cuatro. Esa es una característica muy significativa. También es cierto que eljj“role="presentation” style="position:relative;” tabindex="0">\(j\) multiplicador se puede conmutar desde elDD“role="presentación” style="position:relative;” tabindex="0">jj“role="presentation” style="position:relative;” tabindex="0">\(D\) operador a la última parte delATAT“role="presentation” style="position:relative;” tabindex="0">\(A^T\) operador. Esto significa queDD“role="presentación” style="position:relative;” tabindex="0">jj“role="presentation” style="position:relative;” tabindex="0"> el \(D\)operador solo tiene multiplicadores reales y los cálculos sobre datos reales permanecen reales hasta la última etapa.
DD“role="presentación” style="position:relative;” tabindex="0"> Colaborador
