La transformada ciclotómica rápida de Fourier es un tipo de algoritmo de transformada rápida de Fourier sobre campos finitos . [1] Este algoritmo primero descompone una DFT en varias convoluciones circulares y luego deriva los resultados de la DFT a partir de los resultados de la convolución circular. Cuando se aplica a una DFT sobre, este algoritmo tiene una complejidad multiplicativa muy baja. En la práctica, dado que generalmente existen algoritmos eficientes para convoluciones circulares con longitudes específicas, este algoritmo es muy eficiente. [2]
La transformada discreta de Fourier sobre campos finitos encuentra una amplia aplicación en la decodificación de códigos de corrección de errores , como los códigos BCH y los códigos Reed-Solomon . Generalizado del campo complejo , una transformada de Fourier discreta de una secuenciasobre un campo finito GF ( p m ) se define como
dónde es la raíz primitiva N - ésima de 1 en GF ( p m ). Si definimos la representación polinomial de como
Es fácil ver eso es simple . Es decir, la transformada discreta de Fourier de una secuencia la convierte en un problema de evaluación polinomial.
Escrito en formato matricial,
La evaluación directa de DFT tiene un complejidad. Las transformadas rápidas de Fourier son solo algoritmos eficientes que evalúan el producto matriz-vector anterior.
Primero, definimos un polinomio linealizado sobre GF (p m ) como
se llama linealizado porque , que proviene del hecho de que para los elementos
Darse cuenta de es modulo invertible porque debe dividir el orden del grupo multiplicativo del campo . Entonces, los elementos se puede dividir en módulos laterales ciclotómicos :
dónde . Por lo tanto, la entrada a la transformada de Fourier se puede reescribir como
De esta manera, la representación polinomial se descompone en una suma de polinomios lineales, y por lo tanto es dado por
- .
En expansión con la base adecuada , tenemos dónde , y por la propiedad del polinomio linealizado , tenemos
Esta ecuación se puede reescribir en forma de matriz como , dónde es un matriz sobre GF ( p ) que contiene los elementos, es una matriz diagonal de bloques, y es una matriz de permutación que reagrupa los elementos en según el índice de coset ciclotómico.
Tenga en cuenta que si la base normal se utiliza para expandir los elementos de campo de , el i-ésimo bloque de es dado por:
que es una matriz circulante . Es bien sabido que un producto matriz-vector circulante puede calcularse eficazmente mediante convoluciones . Por lo tanto, reducimos con éxito la transformada discreta de Fourier en convoluciones cortas.