Estoy tratando de comprender cómo calcular la transformada rápida de Fourier sobre un campo finito. Esta pregunta se planteó en el análisis de algunos de los códigos BCH.
Considere el campo finito $F$ con $2^n$ elementos. Es posible definir un (discreta) de la transformada de Fourier en vectores de longitud $2^n-1$ como sigue. Elegir un $2^n-1$ raíz de la unidad $\omega\in F$. Entonces, dado un vector $V=(V_0,...,V_{2^n-2})\in F^{2^n-1}$, podemos definir su transformada de Fourier $W=(W_0,...,W_{2^n-2}) \in F^{2^n-1}$ como: $$W_i=\sum_{j=0}^{2^n-2} \omega^{ij} V_j$$ Encontrar un $\omega$ podemos utilizar elementos primitivos de $F$.
Supongamos que tenemos $V$ y nos gustaría para calcular eficientemente $W$. Si tuviéramos la operación a través de los números complejos, se podría elegir a cualquiera de un número de algoritmos de la transformada rápida de Fourier. La mezcla de base de Cooley-Tukey algoritmo se traduce modificado en este contexto, por lo que si $2^n-1$ es el producto de pequeños factores (es decir, es suave), entonces todos estamos conjunto.
Sin embargo, $2^n-1$ podría ser la mejor (después de todo, estos números incluyen los números primos de Mersenne) o contienen grandes factores primos. La tradicional Cooley-Tukey algoritmo ya no es eficiente. Sobre los números complejos, que esto no supone un problema, existen rápido algoritmos (como Bluestein del algoritmo y Rader del algoritmo) para el manejo de este caso. Estos algoritmos suelen involucrar a reformular una $N$-punto de la transformada de Fourier como una convolución y la evaluación de la convolución mediante la realización de una $2^m$ de puntos de la FFT, donde $2^m\geq 2N-1$.
Por desgracia para nosotros, no es $2^m$ raíz de la unidad en cualquier campo finito de característica 2. Contigua a dicha raíz de nuestro campo muestra un anillo más grande, y la mayor complejidad en el manejo de estos elementos aparece para cancelar la velocidad a la que habría recibido de la FFT. En (1), Pollard sugiere el uso de Bluestein del algoritmo, pero su argumento no parece aplicarse a los campos de la característica 2 (a menos que yo estoy entendiendo él).
Mi pregunta es: en el caso descrito anteriormente, ¿cómo puedo calcular una transformada rápida de Fourier? Para mi propósito original, tenía la esperanza de encontrar un radix-dos del algoritmo, pero en este momento yo estaría interesado en cualquier algoritmo rápido.
(1) J. M. Pollard. "La transformada Rápida de Fourier en un Campo Finito". Las matemáticas de la Computación, Vol. 25, Nº 114 (Abr., 1971), pp 365-374.
