Algoritmo FFT de factor primo

Algoritmo de transformada rápida de Fourier

El algoritmo de factor primo (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 un tamaño N = N ₁ N ₂ como una DFT bidimensional N ₁ × N ₂ , pero solo para el caso en el que N ₁ y N ₂ son primos relativos . Estas transformadas más pequeñas de tamaño N ₁ y N ₂ se pueden evaluar aplicando PFA de forma recursiva o utilizando algún otro algoritmo FFT.

PFA no debe confundirse con la generalización de base mixta del popular algoritmo de Cooley-Tukey , que también subdivide una DFT de tamaño N = N ₁ N ₂ en transformaciones más pequeñas de tamaño N ₁ y N ₂ . El último algoritmo puede utilizar cualquier factor (no necesariamente primos relativos), pero tiene la desventaja de que también requiere multiplicaciones adicionales por raíces unitarias llamadas factores de giro , además de las transformaciones más pequeñas. Por otro lado, PFA tiene las desventajas de que sólo funciona para factores relativamente primos (por ejemplo, es inútil para potencias de dos tamaños) y que requiere una reindexación más complicada de los datos basada en los isomorfismos de grupos aditivos . Sin embargo, tenga en cuenta que PFA se puede combinar con Cooley-Tukey de base mixta, donde el primero factoriza N en componentes relativamente primos y el segundo maneja factores repetidos.

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 llaman al algoritmo de Winograd PFA FFT.

(Aunque el PFA es distinto del algoritmo de 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, e inicialmente hubo cierta confusión sobre si los dos algoritmos eran diferentes. De hecho , fue el único trabajo anterior de FFT citado por ellos, ya que en ese momento no estaban al tanto de la investigación anterior de Gauss y otros).

Algoritmo

Sea un polinomio y una raíz principal de la unidad . Definimos la DFT de como -tupla . En otras palabras, por simplicidad, 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 para algunas opciones de donde está 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 residuos chino de a con como su inverso, donde están 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 de álgebra

PFA se puede expresar de manera de alto nivel en términos de isomorfismos de álgebra . Primero recordamos que para un anillo conmutativo y un isomorfismo de grupo de a , tenemos el siguiente isomorfismo de álgebra donde se refiere al producto tensorial de á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 somos grupos aditivos . También identificamos como y como . Al elegir como isomorfismo de grupo , tenemos el isomorfismo de álgebra , o alternativamente, ahora observe que en realidad es un isomorfismo de álgebra de a y cada uno es un isomorfismo de álgebra de a , tenemos un isomorfismo de álgebra de a . Lo que nos dice PFA es que dónde y se 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

Observe que la condición para transformarse en se basa en "un" isomorfismo de grupo aditivo de a . Cualquier isomorfismo de grupo aditivo funcionará. Para contar el número de formas de transformarse en , solo necesitamos contar el número de isomorfismos de grupos aditivos de a , o alternativamente, el número de automorfismos de grupos aditivos en . Dado que es cíclico , cualquier automorfismo se puede escribir como donde es un generador de . Según la definición de , los , son exactamente aquellos coprimos con . Por lo tanto, existen exactamente muchos mapas de este tipo donde está la función totiente de Euler . El ejemplo más pequeño es el de , que muestra los dos mapas de la literatura: el "mapeo CRT" y el "mapeo de Ruritania". ^[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}$

Ver también

• Algoritmo FFT de Bluestein
• Algoritmo FFT de Rader

Notas

1. Bueno 1971

Referencias

• Bien, IJ (1958). "El algoritmo de interacción y análisis práctico de Fourier". Revista de la Royal Statistical Society, Serie B. 20 (2): 361–372. JSTOR  2983896.Anexo, ibídem. 22 (2), 373-375 (1960) JSTOR  2984108.
• Thomas, LH (1963). "Usar 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 del tutorial y un estado del arte". Procesamiento de señales . 19 (4): 259–299. doi :10.1016/0165-1684(90)90158-U.
• Chan, Carolina del Sur; Ho, KL (1991). "Sobre la indexación del algoritmo de transformada rápida de Fourier de factor primo". Transacciones IEEE sobre circuitos y sistemas . 38 (8): 951–953. doi : 10.1109/31.85638.
• Bien, IJ (1971). "La relación entre dos transformadas rápidas de Fourier". Transacciones IEEE en computadoras . 100 (3): 310–317. doi :10.1109/TC.1971.223236. S2CID  585818.