Algoritmo FFT de factor primo

Algoritmo de transformada rápida de Fourier

El algoritmo de factores primos (PFA) , también llamado algoritmo de Good–Thomas (1958/1963), es un algoritmo de transformada rápida de Fourier (FFT) que reexpresa la transformada discreta de Fourier (DFT) de tamaño N = N ₁ N ₂ como una DFT bidimensional N ₁ × N ₂ , pero solo para el caso en que N ₁ y N ₂ sean primos entre sí . Estas transformadas más pequeñas de tamaño N ₁ y N ₂ pueden evaluarse aplicando PFA de forma recursiva o utilizando algún otro algoritmo de FFT.

PFA no debe confundirse con la generalización de base mixta del popular algoritmo Cooley–Tukey , que también subdivide una DFT de tamaño N = N ₁ N ₂ en transformadas más pequeñas de tamaño N ₁ y N _2. El último algoritmo puede usar cualquier factor (no necesariamente primos relativos), pero tiene la desventaja de que también requiere multiplicaciones adicionales por raíces de la unidad llamadas factores twiddle , además de las transformadas más pequeñas. Por otro lado, PFA tiene las desventajas de que solo funciona para factores primos relativos (por ejemplo, es inútil para tamaños de potencia de dos ) y que requiere una reindexación más complicada de los datos basada en los isomorfismos del grupo aditivo . Sin embargo, tenga en cuenta que PFA se puede combinar con Cooley–Tukey de base mixta, con el primero factorizando N en componentes primos relativos y el segundo manejando factores repetidos.

El PFA también está estrechamente relacionado con el algoritmo FFT anidado de Winograd, donde este último realiza la transformación N ₁ por N ₂ descompuesta mediante técnicas de convolución bidimensional más sofisticadas. Por lo tanto, algunos artículos más antiguos también denominan al algoritmo de Winograd FFT PFA.

(Aunque el PFA es distinto del algoritmo Cooley-Tukey, el trabajo de Good de 1958 sobre el PFA fue citado como inspiración por Cooley y Tukey en su artículo de 1965, y al principio hubo cierta confusión sobre si los dos algoritmos eran diferentes. De hecho, fue el único trabajo FFT anterior citado por ellos, ya que entonces no estaban al tanto de la investigación anterior de Gauss y otros).

Algoritmo

Sea un polinomio y una raíz principal -ésima de la unidad . Definimos la DFT de como la -tupla . En otras palabras, Para simplificar, denotamos la transformación como . ${\displaystyle a(x)}$ ${\displaystyle \omega _{n}}$ ${\displaystyle n}$ ${\displaystyle a(x)}$ ${\displaystyle n}$ ${\displaystyle ({\hat {a}}_{j})=(a(\omega _{n}^{j}))}$ $${\displaystyle {\hat {a}}_{j}=\sum _{i=0}^{n-1}a_{i}\omega _{n}^{ij}\quad {\text{ for all }}j=0,1,\dots ,n-1.}$$ ${\displaystyle {\text{DFT}}_{\omega _{n}}}$

El PFA se basa en una factorización coprima de y se convierte en para algunas opciones de donde es el producto tensorial . ${\textstyle n=\prod _{d=0}^{D-1}n_{d}}$ ${\displaystyle {\text{DFT}}_{\omega _{n}}}$ ${\textstyle \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}}$ ${\displaystyle \omega _{n_{d}}}$ ${\textstyle \bigotimes }$

Mapeo basado en CRT

Para una factorización coprima , tenemos el mapa de resto chino de a con como su inverso donde son los elementos idempotentes ortogonales centrales con . Eligiendo (por lo tanto, ), reescribimos de la siguiente manera: Finalmente, definimos y , tenemos Por lo tanto, tenemos la DFT multidimensional, . ${\textstyle n=\prod _{d=0}^{D-1}n_{d}}$ ${\displaystyle m\mapsto (m{\bmod {n}}_{d})}$ ${\displaystyle \mathbb {Z} _{n}}$ ${\textstyle \prod _{d=0}^{D-1}\mathbb {Z} _{n_{d}}}$ ${\textstyle (m_{d})\mapsto \sum _{d=0}^{D-1}e_{d}m_{d}}$ ${\displaystyle e_{d}}$ ${\textstyle \sum _{d=0}^{D-1}e_{d}=1{\pmod {n}}}$ ${\displaystyle \omega _{n_{d}}=\omega _{n}^{e_{d}}}$ ${\textstyle \prod _{d=0}^{D-1}\omega _{n_{d}}=\omega _{n}^{\sum _{d=0}^{D-1}e_{d}}=\omega _{n}}$ ${\displaystyle {\text{DFT}}_{\omega _{n}}}$ $${\displaystyle {\hat {a}}_{j}=\sum _{i=0}^{n-1}a_{i}\omega _{n}^{ij}=\sum _{i=0}^{n-1}a_{i}\left(\prod _{d=0}^{D-1}\omega _{n_{d}}\right)^{ij}=\sum _{i=0}^{n-1}a_{i}\prod _{d=0}^{D-1}\omega _{n_{d}}^{(i{\bmod {n}}_{d})(j{\bmod {n}}_{d})}=\sum _{i_{0}=0}^{n_{0}-1}\cdots \sum _{i_{D-1}=0}^{n_{D-1}-1}a_{\sum _{d=0}^{D-1}e_{d}i_{d}}\prod _{d=0}^{D-1}\omega _{n_{d}}^{i_{d}(j{\bmod {n}}_{d})}.}$$ ${\displaystyle a_{i_{0},\dots ,i_{D-1}}=a_{\sum _{d=0}^{D-1}i_{d}e_{d}}}$ ${\displaystyle {\hat {a}}_{j_{0},\dots ,j_{D-1}}={\hat {a}}_{\sum _{d=0}^{D-1}j_{d}e_{d}}}$ $${\displaystyle {\hat {a}}_{j_{0},\dots ,j_{D-1}}=\sum _{i_{0}=0}^{n_{0}-1}\cdots \sum _{i_{D-1}=0}^{n_{D-1}-1}a_{i_{0},\dots ,i_{D-1}}\prod _{d=0}^{D-1}\omega _{n_{d}}^{i_{d}j_{d}}.}$$ ${\displaystyle \otimes _{d=0}^{D-1}{\text{DFT}}_{\omega _{n_{d}}}}$

Como isomorfismos del álgebra

El PFA se puede expresar de manera general en términos de isomorfismos algebraicos . En primer lugar, recordamos que para un anillo conmutativo y un isomorfismo de grupo de a , tenemos el siguiente isomorfismo algebraico donde se refiere al producto tensorial de las álgebras . ${\displaystyle R}$ ${\displaystyle G}$ ${\textstyle \prod _{d}G_{d}}$ $${\displaystyle R[G]\cong \bigotimes _{d}R[G_{d}]}$$ ${\displaystyle \bigotimes }$

Para ver cómo funciona PFA, elegimos y son grupos aditivos . También identificamos como y como . Eligiendo como isomorfismo de grupo , tenemos el isomorfismo algebraico , o alternativamente, Ahora observe que es en realidad un isomorfismo algebraico de a y cada uno es un isomorfismo algebraico de a , tenemos un isomorfismo algebraico de a . Lo que PFA nos dice es que donde y están reindexando sin aritmética real en . ${\displaystyle G=(\mathbb {Z} _{n},+,0)}$ ${\displaystyle G_{d}=(\mathbb {Z} _{n_{d}},+,0)}$ ${\displaystyle R[G]}$ ${\textstyle {\frac {R[x]}{\langle x^{n}-1\rangle }}}$ ${\displaystyle R[G_{d}]}$ ${\textstyle {\frac {R[x_{d}]}{\langle x_{d}^{n_{d}}-1\rangle }}}$ ${\displaystyle \eta =a\mapsto (a{\bmod {n}}_{d})}$ ${\textstyle G\cong \prod _{d}G_{d}}$ ${\textstyle \eta ^{*}:R[G]\cong \bigotimes _{d}R[G_{d}]}$ $${\displaystyle \eta ^{*}:{\frac {R[x]}{\langle x^{n}-1\rangle }}\cong \bigotimes _{d}{\frac {R[x_{d}]}{\langle x_{d}^{n_{d}}-1\rangle }}.}$$ ${\displaystyle {\text{DFT}}_{\omega _{n}}}$ ${\textstyle {\frac {R[x]}{\langle x^{n}-1\rangle }}}$ ${\textstyle \prod _{i}{\frac {R[x]}{\langle x-\omega _{n}^{i}\rangle }}}$ ${\displaystyle {\text{DFT}}_{\omega _{n_{d}}}}$ ${\textstyle {\frac {R[x]}{\langle {x_{d}}^{n_{d}}-1\rangle }}}$ ${\textstyle \prod _{i_{d}}{\frac {R[x_{d}]}{\langle x_{d}-\omega _{n_{d}}^{i_{d}}\rangle }}}$ ${\displaystyle \eta '}$ ${\textstyle \bigotimes _{d}\prod _{i_{d}}{\frac {R[x_{d}]}{\langle x_{d}-\omega _{n_{d}}^{i_{d}}\rangle }}}$ ${\textstyle \prod _{i}{\frac {R[x]}{\langle x-\omega _{n}^{i}\rangle }}}$ ${\textstyle {\text{DFT}}_{\omega _{n}}=\eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}$ ${\displaystyle \eta ^{*}}$ ${\displaystyle \eta '}$ ${\displaystyle R}$

Contando el número de transformaciones multidimensionales

Nótese que la condición para transformar en depende de "un" isomorfismo de grupo aditivo de a . Cualquier isomorfismo de grupo aditivo funcionará. Para contar la cantidad de formas de transformar en , solo necesitamos contar la cantidad de isomorfismos de grupo aditivo de a , o alternativamente, la cantidad de automorfismos de grupo aditivo en . Dado que es cíclico , cualquier automorfismo puede escribirse como donde es un generador de . Por la definición de , los ' son exactamente aquellos coprimos con . Por lo tanto, hay exactamente muchos de esos mapas donde es la función totiente de Euler . El ejemplo más pequeño es donde , que demuestra los dos mapas en la literatura: el "mapeo CRT" y el "mapeo ruritano". ^[1] ${\displaystyle {\text{DFT}}_{\omega _{n}}}$ ${\textstyle \eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}$ ${\displaystyle \eta }$ ${\displaystyle (\mathbb {Z} _{n},+,0)}$ ${\textstyle \prod _{d}(\mathbb {Z} _{n_{d}},+,0)}$ ${\displaystyle {\text{DFT}}_{\omega _{n}}}$ ${\textstyle \eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}$ ${\displaystyle (\mathbb {Z} _{n},+,0)}$ ${\textstyle \prod _{d}(\mathbb {Z} _{n_{d}},+,0)}$ ${\displaystyle (\mathbb {Z} _{n},+,0)}$ ${\displaystyle (\mathbb {Z} _{n},+,0)}$ ${\displaystyle 1\mapsto g}$ ${\displaystyle g}$ ${\displaystyle (\mathbb {Z} _{n},+,0)}$ ${\displaystyle (\mathbb {Z} _{n},+,0)}$ ${\displaystyle g}$ ${\displaystyle n}$ ${\displaystyle \varphi (n)}$ ${\displaystyle \varphi }$ ${\displaystyle n=6}$ ${\displaystyle \varphi (n)=2}$

Véase también

• Algoritmo FFT de Bluestein
• Algoritmo FFT de Rader

Notas

1. Buen 1971

Referencias

• Good, IJ (1958). "El algoritmo de interacción y el análisis práctico de Fourier". Revista de la Royal Statistical Society, Serie B . 20 (2): 361–372. JSTOR  2983896.Adenda, ibid. 22 (2), 373-375 (1960) JSTOR  2984108.
• Thomas, LH (1963). "Uso de una computadora para resolver problemas de física". Aplicaciones de las computadoras digitales . Boston: Ginn.
• Duhamel, P.; Vetterli, M. (1990). "Transformadas rápidas de Fourier: una revisión tutorial y un estado del arte". Procesamiento de señales . 19 (4): 259–299. doi :10.1016/0165-1684(90)90158-U.
• Chan, SC; Ho, KL (1991). "Sobre la indexación del algoritmo de transformada rápida de Fourier de factores primos". IEEE Transactions on Circuits and Systems . 38 (8): 951–953. doi :10.1109/31.85638.
• Good, IJ (1971). "La relación entre dos transformadas rápidas de Fourier". IEEE Transactions on Computers . 100 (3): 310–317. doi :10.1109/TC.1971.223236. S2CID  585818.